# Mail Robot

[data structure](/web/appendix/data.md) ⟩ [Graph](/web/appendix/data/graph.md) ⟩ [example](/web/appendix/data/graph/ex.md) ⟩ Mail Robot 

{% hint style="success" %}

* 送<mark style="color:yellow;">**五個**</mark>**包裹**，目前跑分結果：
  * 「<mark style="color:yellow;">**先收件再送件**</mark>」與「<mark style="color:yellow;">**挑最近的跑**</mark>」，在伯仲之間，約需移動 <mark style="color:yellow;">**12**</mark> 次。
  * 「<mark style="color:yellow;">**固定路線**</mark>」約需 <mark style="color:orange;">**18**</mark> 次。
  * 「<mark style="color:yellow;">**無頭蒼蠅式**</mark>」平均需要 <mark style="color:red;">**69**</mark> 次。
    {% endhint %}

{% tabs %}
{% tab title="💾 Robot" %}

* replit ⟩ [graph: a robot](https://replit.com/@pegasusroe/graph-a-robot#Robot/Robot.js) , require ⟩ [Graph](/web/appendix/data/graph.md)&#x20;

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

{% endtab %}

{% tab title="💾 Parcel" %}

* replit ⟩ [Parcel](https://replit.com/@pegasusroe/graph-a-robot#Robot/Parcel.js)

```javascript
// 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 };
```

{% endtab %}

{% tab title="💈範例" %}

* replit ⟩ [index.js](https://replit.com/@pegasusroe/graph-a-robot#index.js)

```javascript
'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));
```

{% endtab %}

{% tab title="👥 相關" %}

* [Queue](/web/appendix/data/queue.md) - used in <mark style="color:purple;">**breadth-first search**</mark>.
* replit ⟩ [Robot (old code)](https://replit.com/@pegasusroe/Robot-v30#js/Graph.js)
  {% endtab %}

{% tab title="📗 參考" %}

* [x] Eloqent JavaScript ⟩ [Ch. 7 Project: A Robot](https://eloquentjavascript.net/07_robot.html) ⭐️&#x20;
* [ ] MakeUseOf ⟩ [A Guide to the Graph Data Structure](https://www.makeuseof.com/graph-data-structure/)
* [ ] simplilearn ⟩ [Your One-Stop Solution For Graphs In Data Structures](https://www.simplilearn.com/tutorials/data-structure-tutorial/graphs-in-data-structure)
* [ ] VisuAlgo ⟩ [GRAPH TRAVERSAL (DFS/BFS)](https://visualgo.net/en/dfsbfs?slide=1)
  {% endtab %}
  {% endtabs %}


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://lochiwei.gitbook.io/web/appendix/data/graph/ex/robot.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.