✨Mail Robot

data structure ⟩ Graph ⟩ example ⟩ Mail Robot

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

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

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

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

💾 Robot

• replit ⟩ graph: a robot , require ⟩ Graph

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 };

💾 Parcel

• replit ⟩ Parcel

// 2022.12.29 - 21:23 - (•) first version
//
// ⭐ Parcel
//
//   ex: `new Parcel(from, to)`
// -----------------------------------------------
//   private fields:
//
//     #from
//     #to
//     #location
// -----------------------------------------------
// 🟧 Parcel.constantSamples
// 🟦 Parcel.randomSamples()
// 🟦 Parcel.copyParcels()    - copy parcels ⭐
// -----------------------------------------------
// 🔸 .isDelivered        - check if parcel is delivered
// 🔸 .location           - current location
// 🔸 .from               - `from` address
// 🔸 .to                 - `to` address
// 🔹 .move()             -❗(mutating) move to next stop
// -----------------------------------------------
// 🔹 .toString()
// 🔹 .copy()             - new copy of this parcel
// 
class Parcel {
    
    // private properties
    #from;
    #to;
    #location;    // current locaation

    // 🟦 Parcel.samples()
    // - create some random parcels
    static randomSamples(nodes, count = 5) {
        const result = [];
        for (let i = 0; i < count; i++) {
            // choose a random "from" address
            const from = nodes.randomElement;
            // choose a random 'to' address until "to" != "from"
            let to;
            do { to = nodes.randomElement } while ( to === from);
            // now, to !== from
            result.push(new Parcel(from, to));
        }
        return result;
    }

    // 🟧 Parcel.constantSamples
    static get constantSamples() {
        return [
            new Parcel('M', 'A'), new Parcel('M', 'E'), new Parcel('C', 'G'), 
            new Parcel('G', 'A'), new Parcel('G', 'E'), 
        ];
    }

    // 🟦 Parcel.copyParcels()
    static copyParcels(parcels) {
        return parcels.map(parcel => parcel.copy());
    }
    
    // ⭐ constructor
    constructor(from, to) {
        this.#from = from;        // fixed
        this.#to = to;            // fixed
        this.#location = from;
    }
    
    // 🔸 .isDelivered
    get isDelivered() { return this.#location === this.#to; }  
    // 🔸 .location
    get location() { return this.#location; }            
    // 🔸 .from
    get from() { return this.#from; }                    
    // 🔸 .to
    get to() { return this.#to; }                        

    // 🔹 move()
    move(to) {

        // check if parcel has been delivered already
        if (this.isDelivered) {
            console.log(`⚠️ can't move parcel: parcel is delivered!`);
            return;
        }
        
        this.#location = to;
    }

    // 🔹 .toString()
    toString() {
        return `Parcel ${this.#from} -> ${this.#to} (current: ${this.#location})`;
    }

    // 🔹 .copy()
    copy() {
        return new Parcel(this.#from, this.#to);
    }
}

// export
module.exports = { Parcel };

💈範例

• replit ⟩ index.js

'use strict';                // ⭐ toggle sloppy/strict mode
const { log } = console;

// ⭐ import
const { Graph } = require('./DataStructure/Graph.js');
const { Robot } = require('./Robot/Robot.js');
const { Parcel } = require('./Robot/Parcel.js');
// ---------------------------------------------------------------------------

// ⭐ roads (edges)
const roads = [
    "Alice's House-Bob's House", "Alice's House-Cabin",
    "Alice's House-Post Office", "Bob's House-Town Hall",
    "Daria's House-Ernie's House", "Daria's House-Town Hall",
    "Ernie's House-Grete's House", "Grete's House-Farm",
    "Grete's House-Shop", "Marketplace-Farm",
    "Marketplace-Post Office", "Marketplace-Shop",
    "Marketplace-Town Hall", "Shop-Town Hall"
];

const edges = roads.map(s => s.split('-').map(s => s[0]));
// [
//   [ 'A', 'B' ], [ 'A', 'C' ],
//   [ 'A', 'P' ], [ 'B', 'T' ],
//   [ 'D', 'E' ], [ 'D', 'T' ],
//   [ 'E', 'G' ], [ 'G', 'F' ],
//   [ 'G', 'S' ], [ 'M', 'F' ],
//   [ 'M', 'P' ], [ 'M', 'S' ],
//   [ 'M', 'T' ], [ 'S', 'T' ]
// ]

// ⭐ node names
const node = Object.create(null);
roads
    .flatMap(s => s.split('-').map(s => [s[0], s]))
    .forEach(([char, name]) => node[char] = name);
// {
//   A: "Alice's House",
//   B: "Bob's House",
//   C: 'Cabin',
//   P: 'Post Office',
//   T: 'Town Hall',
//   D: "Daria's House",
//   E: "Ernie's House",
//   G: "Grete's House",
//   F: 'Farm',
//   S: 'Shop',
//   M: 'Marketplace'
// }

// adjacency list
const list = Graph.edgesToAdjacencyList(edges);
// A: [B,C,P]
// B: [A,T]
// C: [A]
// P: [A,M]
// T: [B,D,M,S]
// D: [E,T]
// E: [D,G]
// G: [E,F,S]
// F: [G,M]
// S: [G,M,T]
// M: [F,P,S,T]

// ⭐ Graph
const graph = new Graph(list);

// ⭐ Parcel
// const parcels = Parcel.randomSamples([...graph.nodes]);

const parcels = Parcel.constantSamples;
// log(parcels.map(p => String(p)));
// [
//   'Parcel M -> A (current: M)',
//   'Parcel M -> E (current: M)',
//   'Parcel C -> G (current: C)',
//   'Parcel G -> A (current: G)',
//   'Parcel G -> E (current: G)'
// ]

// ⭐ 4 strategies
const mode = [
    Robot.strategy.collectFirst,
    Robot.strategy.nearest,
    Robot.strategy.mailRoute,
    Robot.strategy.randomMove,
];

// ⭐ Robot
// const robot = new Robot(graph, Parcel.copyParcels(parcels));
// robot.debugMode = true;
// robot.run(mode[1]);

// ⭐ count robots moves on 4 differenct strateges.
// - sending 5 parcels each time.
function moveCounts() {

    // parcel samples
    const parcels = Parcel.randomSamples([...graph.nodes]);

    // robots
    const robots = [
        new Robot(graph, Parcel.copyParcels(parcels)),
        new Robot(graph, Parcel.copyParcels(parcels)),
        new Robot(graph, Parcel.copyParcels(parcels)),
        new Robot(graph, Parcel.copyParcels(parcels)),
    ];

    // run/compare robots
    const counts = robots.map((robot, i) => {
        robot.run(mode[i]);
        return robot.moveCount;
    });

    return counts;
}

// run moveCounts() a few times.
function benchmark(times = 100) {

    const records = [];

    for (let i = 0; i < times; i++) {
        records.push(moveCounts());
    }

    return records
        .reduce(([a, b, c, d], [p, q, r, s]) => [a + p, b + q, c + r, d + s])
        .map(x => x / times);
}

// ✅ log expressions that never throw
// ---------------------------------------------------------------------------
;[
    benchmark(100),    
    // [ 11.51, 11.49, 17.70, 64.10 ]    (100 times)
    // [ 12.41, 12.64, 18.03, 69.27 ]
    // [ 12.23, 12.40, 18.11, 69.54 ]
    // [ 12.10, 12.28, 18.38, 69.61 ]
    // [ 12.08, 11.90, 18.60, 69.63 ]
    // [ 12.04, 12.11, 18.16, 68.52 ]    (1000 times)

].forEach(x => log(x));

👥 相關

• Queue - used in breadth-first search.

• replit ⟩ Robot (old code)

📗 參考

• Eloqent JavaScript ⟩ Ch. 7 Project: A Robot ⭐️
• MakeUseOf ⟩ A Guide to the Graph Data Structure
• simplilearn ⟩ Your One-Stop Solution For Graphs In Data Structures
• VisuAlgo ⟩ GRAPH TRAVERSAL (DFS/BFS)