Code
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"
];
function buildGraph(edges) {
// map으로 쓰기 위해
let graph = Object.create(null);
// 함수 내에서 반복되는 기능을 함수화
function addEdge(from, to) {
if (graph[from] == null) {
graph[from] = [to];
} else {
graph[from].push(to);
}
}
// forEach vs. map
for (let [from, to] of edges.map(e => e.split("-"))) {
addEdge(from, to);
addEdge(to, from);
}
return graph;
}
const roadGraph = buildGraph(roads);
class VillageState {
constructor(place, parcels) {
this.place = place;
this.parcels = parcels;
}
move(destination) {
if (!roadGraph[this.place].includes(destination)) {
return this;
} else {
// p를 수정하지 않도록 주의
let parcels = this.parcels.map(p => {
if (p.place != this.place) return p;
return {place: destination, address: p.address};
}).filter(p => p.place != p.address);
return new VillageState(destination, parcels);
}
}
}
/*
let first = new VillageState(
"Post Office",
[{place: "Post Office", address: "Alice's House"}]
);
let next = first.next("Alice's House");
console.log(next.place);
// Alice's House
console.log(next.parcels);
// []
console.log(first.place);
// Post Office
*/
function runRobot(state, robot, memory)
{
for (let turn = 0;; turn++) {
if (state.parcels.length == 0) {
console.log(`Done in ${turn} turns`);
break;
}
let action = robot(state, memory);
state = state.move(action.direction);
memory = action.memory;
console.log(`Moved to ${action.direction}`);
}
}
function randomPick(array)
{
let choice = Math.floor(Math.random() * array.length);
return array[choice];
}
function randomRobot(state)
{
return {direction: randomPick(roadGraph[state.place])};
}
// static method
VillageState.random = function(parcelCount = 5) {
let parcels = [];
for (let i = 0; i < parcelCount; i++) {
let address = randomPick(Object.keys(roadGraph));
let place;
do {
place = randomPick(Object.keys(roadGraph));
} while (place == address);
parcels.push({place, address});
}
return new VillageState("Post Office", parcels);
}
// run!
// runRobot(VillageState.random(), randomRobot);
const mailRoute = [
"Alice's House", "Cabin", "Alice's House", "Bob's House",
"Town Hall", "Daria's House", "Ernie's House",
"Grete's House", "Shop", "Grete's House", "Farm",
"Marketplace", "Post Office"
];
function routeRobot(state, memory)
{
if (memory.length == 0) {
memory = mailRoute;
}
return {direction: memory[0], memory: memory.slice(1)};
}
// run!
// runRobot(VillageState.random(), routeRobot, []);
function findRoute(graph, from, to)
{
let work = [{at: from, route: []}];
for (let i = 0; i < work.length; i++) {
let {at, route} = work[i];
for (let place of graph[at]) {
if (place == to) return route.concat(place);
if (!work.some(w => w.at == place)) {
work.push({at: place, route: route.concat(place)});
}
}
}
}
function goalOrientedRobot({place, parcels}, route)
{
if (route.length == 0) {
let parcel = parcels[0];
if (parcel.place != place) {
route = findRoute(roadGraph, place, parcel.place);
} else {
route = findRoute(roadGraph, place, parcel.address);
}
}
return {direction: route[0], memory: route.slice(1)};
}
// run!
// runRobot(VillageState.random(), goalOrientedRobot, []);
// Ex. Measuring a robot
function runRobotSilently(state, robot, memory) {
for (let turn = 0;; turn++) {
if (state.parcels.length == 0) return turn;
let action = robot(state, memory);
// state, memory에 "대입"해도 함수 호출 밖의 state나 memory가 바뀌는 게 아님
state = state.move(action.direction);
memory = action.memory;
}
}
function compareRobots(robot1, memory1, robot2, memory2) {
let tasks = 100;
let steps1 = 0, steps2 = 0;
for (let i = 0; i < tasks; ++i) {
let state = VillageState.random();
steps1 += runRobotSilently(state, robot1, memory1);
steps2 += runRobotSilently(state, robot2, memory2);
}
console.log(`robot1: ${steps1/tasks}`);
console.log(`robot2: ${steps2/tasks}`);
}
// compareRobots(routeRobot, [], goalOrientedRobot, []);
// Ex. Robot efficiency (**)
// 출제 의도에 맞지 않고 생각보다 빠르지 않음
function myRobot({place, parcels}, route) {
if (route.length == 0) {
let target = null;
for (let p of parcels) {
if (p.place != place) {
target = p;
break;
}
}
if (target !== null) {
route = findRoute(roadGraph, place, target.place);
} else {
route = findRoute(roadGraph, place, parcels[0].address);
}
}
return {direction: route[0], memory: route.slice(1)};
}
// Solution
function yourRobot({place, parcels}, route) {
if (route.length == 0) {
let routes = parcels.map(p => {
if (p.place != place) {
return {route: findRoute(roadGraph, place, p.place), pickUp: true};
}
else {
return {route: findRoute(roadGraph, place, p.address), pickUp: false};
}
});
function score({route, pickUp}) {
return -route.length + (pickUp ? 0.5 : 0);
}
route = routes.reduce((a, b) => {
return score(a) > score(b) ? a : b;
}).route;
}
return {direction: route[0], memory: route.slice(1)};
}
// Ex. Persistent group (***)
class PGroup {
constructor(elements) {
this.elements = elements;
}
add(e) {
//if (this.has(e)) return new PGroup(this.elements);
if (this.has(e)) return this;
else return new PGroup(this.elements.concat([e]));
}
delete(e) {
if (!this.has(e)) {
// return new PGroup(this.elements);
return this;
} else {
return new PGroup(this.elements.filter(elem => elem !== e));
}
}
has(e) {
return this.elements.includes(e);
}
}
PGroup.empty = new PGroup([]);
The task
- If you’re thinking in terms of object-oriented programming, your first impulse might be to start defining objects for the various elements in the world: a class for the robot, one for a parcel, maybe one for places. These could then hold properties that describe their current state, such as the pile of parcels at a location, which we could change when updating the world.
- This is wrong.
- At least, it usually is. The fact that something sounds like an object does not automatically mean that it should be an object in your program. Reflexively writing classes for every concept in your application tends to leave you with a collection of interconnected objects that each have their own internal, changing state. Such programs are often hard to understand and thus easy to break.
- Instead, let’s condense the village’s state down to the minimal set of values that define it. There’s the robot’s current location and the collection of undelivered parcels, each of which has a current location and a destination address. That’s it.
Persistent data
Simulation
- A delivery robot looks at the world and decides in which direction it wants to move. As such, we could say that a robot is a function that takes a
VillageState object and returns the name of a nearby place.
- Because we want robots to be able to remember things, so that they can make and execute plans, we also pass them their memory and allow them to return a new memory.
- Thus, the thing a robot returns is an object containing both the direction it wants to move in and a memory value that will be given back to it the next time it is called.
- What is the dumbest strategy that could possibly work? The robot could just walk in a random direction every turn.
- We’ll first need a way to create a new state with some parcels. A static method (written here by directly adding a property to the constructor) is a good place to put that functionality.
Exercises
Persistent group
- Most data structures provided in a standard JavaScript environment aren’t very well suited for persistent use. Arrays have
slice and concat methods, which allow us to easily create new arrays without damaging the old one. But Set, for example, has no methods for creating a new set with an item added or removed.
- The class’s constructor can take such an array as argument and store it as the instance’s (only) property. This array is never updated.
- ...
- You need only one
empty instance because all empty groups are the same and instances of the class don’t change. You can create many different groups from that single empty group without affecting it.