✨Mail Robot

data structure ⟩ Graph ⟩ example ⟩ Mail Robot

  • 送五個包裹，目前跑分結果：

    • 「先收件再送件」與「挑最近的跑」，在伯仲之間，約需移動 12 次。

    • 「固定路線」約需 18 次。

    • 「無頭蒼蠅式」平均需要 69 次。

const { log } = console;

// ⭐ import
const _Array = require('../ext/Array_ext.js');          // Array extension
const { Graph } = require('../DataStructure/Graph.js'); // Graph

// 2022.12.29 - 21:23 - (•) first version
//
// ----------------------------------------------------------------------------
// ⭐ Robot                     (❗means "mutating" methods)
//    ex: `new Robot(graph, parcels, location)`
// ----------------------------------------------------------------------------
// private members:
//    .#location                - robot's current location
//    .#graph                   - robot's internal "map"
//    .#parcels                 - parcels to be delivered
//    .#moveCount               - robot's move count
// 🔹 .#moveToNeighbor()        - ❗move to neighbor
// ----------------------------------------------------------------------------
// 🟦 Robot.strategy            - strategy on deciding next move
// ----------------------------------------------------------------------------
// 🔸 .undeliveredParcels       - parcels haven't been delivered
// 🔸 .carriedParcels           - parcels on robot
// 🔸 .parcelsToCollect         - (undelivered) parcels not on robot
// 🔸 .isDone                   - check if robot is done
// 🔸 .moveCount                - count robot's moves
// 🔹 .move()                   - ❗move to another node (not necessarily neighbor)
// 🔹 .run()                    - ❗run robot on chosen strategy
// ----------------------------------------------------------------------------
// 🔸 .debugMode
class Robot {

    // private fields
    #location;        // robot's current location
    #graph;           // robot's internal "map"
    #parcels;         // parcels to be delivered
    #moveCount = 0;

    // public fields
    debugMode = false;

    // --------------------------------
    // strategies for next move
    // --------------------------------

    // 🟦 Robot.strategy
    static strategy = {

        // 🟦 Robot.strategy.randomMove():
        randomMove() {
            return function() {
                return this.#graph.neighborsOf(this.#location).randomElement;
            }
        },

        // 🟦 Robot.strategy.mailRoute():
        // - If we find a route that passes all places in the village, 
        //   the robot could run that route twice, at which point it 
        //   is guaranteed to be done.
        mailRoute() {

            // mail truck's route
            const route = [
                "A", "C", "A", "B", "T", "D", "E",
                "G", "S", "G", "F", "M", "P"
            ];

            let i = route.indexOf(this.#location);
            if (i === -1) { throw new Error(`no such vertex: ${start}!`) };

            return function() {
                i += 1;
                if (i === route.length) i = 0;
                return route[i];
            };
        },

        // 🟦 Robot.strategy.nearest:
        // - go to the nearest node to collect/send parcels
        nearest() {
            return function() {

                // targets: carriedParcels (to) & parcelsToCollect (from)
                // (duplicates removed)
                const toGet = this.parcelsToCollect.map(p => p.from).removeDuplicates();
                const toSend = this.carriedParcels.map(p => p.to).removeDuplicates();
                const targets = toGet.union(toSend);

                if (targets.length === 0) return null;

                // find nearest target
                const nearestNode = targets.reduce((nearest, node) => {
                    const d1 = this.#graph.distance(nearest, this.#location);
                    const d2 = this.#graph.distance(node, this.#location);
                    if (d2 < d1) nearest = node;
                    return nearest;
                });

                if (this.debugMode) {
                    log(
                        `-`.repeat(30) + '\n' +
                        `•   robot: ${this.#location}, nearest: ${nearestNode}\n` +
                        `      get: [${toGet}], send: [${toSend}]\n` +
                        `  targets: [${targets}]`,
                    );
                }

                return nearestNode;
            }
        },

        // 🟦 Robot.strategy.collectFirst:
        // - always collect first, then send.
        collectFirst() {
            return function() {

                // targets: carriedParcels (to) & parcelsToCollect (from)
                // (duplicates removed)
                const toGet = this.parcelsToCollect.map(p => p.from).removeDuplicates();
                const toSend = this.carriedParcels.map(p => p.to).removeDuplicates();
                
                const targets = (toGet.isEmpty) ? toSend : toGet;

                if (targets.isEmpty) return null;

                // find nearest target
                const nearestNode = targets.reduce((nearest, node) => {
                    const d1 = this.#graph.distance(nearest, this.#location);
                    const d2 = this.#graph.distance(node, this.#location);
                    if (d2 < d1) nearest = node;
                    return nearest;
                });

                if (this.debugMode) {
                    log(
                        `-`.repeat(40) + '\n' +
                        `•   robot: ${this.#location}, ${toGet.isEmpty ? 'send' : 'collect'}: ${nearestNode}\n` +
                        `      get: [${toGet}], send: [${toSend}]\n` +
                        `  targets: [${targets}]`,
                    );
                }

                return nearestNode;
            }
        },

    };

    // ⭐ constructor
    constructor(graph, parcels, location = 'P') {
        this.#graph = graph;
        this.#parcels = parcels;
        this.#location = location;
    }

    // 🔸 .undeliveredParcels
    // undelivered parcels (including parcels not currently carried by robot)
    get undeliveredParcels() {
        return this.#parcels.filter(p => !p.isDelivered);
    }

    // 🔸 .carriedParcels
    // parcels on robot
    get carriedParcels() {
        return this.undeliveredParcels.filter(p => p.location === this.#location);
    }

    // 🔸 .parcelsToCollect
    // parcels not on robot
    get parcelsToCollect() {
        return this.undeliveredParcels.filter(p => p.location !== this.#location);
    }

    // 🔸 .isDone
    // is job done?
    get isDone() {
        return this.undeliveredParcels.length === 0;
    }

    // 🔹 .#moveToNeighbor()
    // - private method
    #moveToNeighbor = function(neighbor) {

        // check if "neighbor" is really a neighbor.
        if (!this.#graph.areNeighbors(this.#location, neighbor)) {
            throw new Error(`Robot: ⛔ invalid move: ${this.#location} -> ${neighbor}!`);
        }

        // update carried parcels
        this.carriedParcels.forEach(p => p.move(neighbor));

        // update self
        const from = this.#location;
        this.#location = neighbor;
        this.#moveCount += 1;
        
        if (this.debugMode) log(`[${this.#moveCount}] robot: ${from} -> ${neighbor}`);
    };

    // 🔹 .move()
    move(to) {
        const path = this.#graph.findShortestPath(this.#location, to);
        if (!path) throw new Error(`Robot: ⛔ ${to} is not reachable!`);
        if (this.debugMode) log(`•    path: [${path}]`);
        path.slice(1).forEach(node => this.#moveToNeighbor(node));
    }

    // 🔸 .moveCount
    get moveCount() { return this.#moveCount; }

    // 🔹 .run()
    // run the robot
    // example: robot.run(Robot.strategy.mailRoute);
    run(strategy) {

        // return a proper function depending on `strategy`
        const nextStop = strategy.call(this).bind(this);

        // while not done, keep running
        while (!this.isDone) {
            const to = nextStop();
            if (!to) throw new Error(`⛔ robot can't go anywhere from ${this.#location}!`);
            this.move(to);
        }

        // now it's done
        if (this.debugMode) log(
            `-`.repeat(40) + '\n' +
            `🏁 delivery complete in ${this.#moveCount} moves!\n`
        );
    }
}

// export 
module.exports = { Robot };
PreviousGraph examplesNextalgorithm

Last updated