โจMail Robot
data structure โฉ Graph โฉ example โฉ Mail Robot
้ไบๅๅ ่ฃน๏ผ็ฎๅ่ทๅ็ตๆ๏ผ
ใๅ ๆถไปถๅ้ไปถใ่ใๆๆ่ฟ็่ทใ๏ผๅจไผฏไปฒไน้๏ผ็ด้็งปๅ 12 ๆฌกใ
ใๅบๅฎ่ทฏ็ทใ็ด้ 18 ๆฌกใ
ใ็ก้ ญ่ผ่ ๅผใๅนณๅ้่ฆ 69 ๆฌกใ
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 };Last updated
Was this helpful?