索引
Notes
-
Excercise
注释即笔记：
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) {
// graph的存储格式类似于
// graph.place_a: [place_b, place_c]
// 表示由a能够直接到达b或者c
let graph = Object.create(null); function addEdge(from, to) {
// 首先判断该起点有没有被添加
if(graph[from] == null) {
graph[from] = [to];
} else {
graph[from].push(to);
}
} // 'Alice's House-Bob's House'.split("-")
// → ['Alice's House', 'Bob's House']
for(let [from, to] of edges.map(r => r.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) {
// move表示机器人的一次移动。
// 首先检查是否存在一条从当前位置this.place到目的地destination的路
// 如果不存在就说明不是合法的移动，返回旧的VillageState。
// 如果存在，就更新机器人的当前位置，也就是更新VillageState.place
// 为destination，当然同时需要更新包裹的状态：1-还没被机器人拿到
// 的包裹不去管它，2-拿到的包裹则更新当前位置place（目的地address不改变）
// 3-最后过滤掉已经送到的包裹（目的地就在本地）
// PS. 整个move方法实际上是重造了一个VillageState，并没改变旧的
// VillageState对象
if(!roadGraph[this.place].includes(destination)) {
return this;
} else {
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);
}
}
} /**
* 可以用Object.freeze冻结对象
* 所有对该对象属性的写入操作会被忽略
* 这需要计算机做一些额外工作
* let object = Object.freeze({value: 5});
object.value = 10;
console.log(object.value);
// → 5
*/ /**
* But the most important limit
* on what kind of systems we can build
* is how much we can understand.
* Anything that makes your code easier
* to understand makes it possible
* to build a more ambitious system.
* 写程序最重要的限制是我们能够理解多少
*/ // robot实际上是一个函数接口，
// 该函数输入state和memory
// 输出决策action用于实际移动
// 这样写就能够动态更改策略了。
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];
} // 最愚蠢但有效的策略--随机决定下一个方向。
// 虽然这里只有一个参数，但是js允许传
// 入更多（或者更少）的参数。在这里，传入的
// memeory被忽略了
function randomRobot(state) {
return {
direction: randomPick(roadGraph[state.place])
};
} // 初始化
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);
}; // runRobot(VillageState.random(), randomRobot);
// 版本一，步数不稳定 // runRobotAnimation(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"
]; // [a,b,c].slice(1)
// → [b,c]
// [a,b,c].slice(1, 2)
// → [b] // 包括start不包括end
function routeRobot(state, memory) {
if(memory.length == 0) {
memory = mailRoute;
}
// memory类似于队列
// 等价: return {direction: memory.shift(), memory: memory}
return {
direction: memory[0],
memory: memory.slice(1)
};
} // runRobot(VillageState.random(), routeRobot, []);
// 版本二，最多26步 /**
* The problem of finding a route
* through a graph is a typical search problem.
* We can tell whether a given solution (a route)
* is a valid solution, but we can’t directly compute
* the solution the way we could for 2 + 2.
* Instead, we have to keep creating potential solutions
* until we find one that works.
*/ // 返回一点到另一点的最短路线，参考：C++ 电路布线/最短路径问题
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]) {
// 搜索四周围，如果找到了目的地就直接+1返回。
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) {
// 首先判断当前制定的路线走完没有，
// 走完就重新制定下一条路线
// 逐个包裹处理（当然也有可能顺
// 路完成其它包裹的fetch和投递）
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)};
} runRobot(VillageState.random(), goalOrientedRobot, []);
// 版本三，平均十来步的样子
Exercises
① Measuring a robot
function testRobot(state, robot, memory) {
for(let turn = 0;; turn++) {
if(state.parcels.length == 0) {
return turn;
break;
}
let action = robot(state, memory);
state = state.move(action.direction);
memory = action.memory;
}
}
function compareRobots(robot1, memory1, robot2, memory2) {
let tasks = [];
for (let i = 0; i != 100; ++i) {
tasks.push(VillageState.random());
}
let total1 = 0, total2 = 0;
for (let task of tasks) {
total1 += testRobot(task, robot1, memory1);
total2 += testRobot(task, robot2, memory2);
}
console.log(`average turns: robot1 ${total1 / 100}, robot2 ${total2 / 100}`);
}
compareRobots(routeRobot, [], goalOrientedRobot, []);
// → average turns: robot1 18.07, robot2 15.03
- - -- - - - - -- -- -- - - - - -- - -- - -
② Robot efficiency
没做任何优化的穷举，而且还用递归。。。6个以上包裹浏览器应该会直接崩溃掉。。
/**
max表示一个包裹要被处理的次数
arr为长度为包裹数量的全0数组
arr[i]表示第i个包裹被处理的次数
当arr为[max, max, max, ...]时
表示所有包裹已经被处理完
返回的sequences包含处理包裹的
所有顺序集合
*/
function makeSequences(max, arr) { const sequences = []; const fillArrWith = (max, arr, start, sequence) => {
// 填充起始点
arr[start] += 1;
sequence.push(start);
// 判断是否已经填充满
let sum = 0;
for (let x of arr) {
sum += x;
};
if (sum == max * arr.length) {
sequences.push(sequence);
return;
}
// 寻找下一个填充点
for (let i = 0; i != arr.length; ++i) {
if (arr[i] < max) fillArrWith(max, arr.slice(), i, sequence.slice());
}
}; for (let i = 0; i != arr.length; ++i) {
fillArrWith(max, arr.slice(), i, []);
} return sequences;
} /**
把生成的序列转化为具体业务相关的表达。
得到route并不是实际的route 而是可能不相邻的地点
routes包含所有能够完成任务的路线
*/
function sequencesToRoutes(sequences, {place, parcels}) {
const routes = []; const flag = parcels.map(() => 0); // 用于之后拷贝用
// 逐个序列处理
for (let sequence of sequences) {
let route = [place]; // 添加起点
let localFlag = flag.slice(); // 标记包裹的状态
for (let num of sequence) {
if (localFlag[num] == 0) { // 第一次处理包裹num：到place取包裹
localFlag[num]++; // 包裹num已取,这样可以保证某包裹的place一定优先于该包裹的address入队
if (route[route.length - 1] != parcels[num].place) { // 避免出现两个连续重复place
route.push(parcels[num].place);
}
} else { // 第二次处理包裹num： 送包裹，去该包裹的目的地
if (route[route.length-1] != parcels[num].address) {
route.push(parcels[num].address);
}
}
}
routes.push(route);
} return routes;
} /**
* 计算单个路线需要的最短步数
* turnsMap用于保存已经计算的两点值，避免重复计算
*/
function turnsOfRoute(route, turnsMap=new Map()) {
let totalTurns = 0;
for (let i = 0; i != route.length - 1; ++i) {
// 两点、两点处理。
let routeKey = route[i].concat(route[i + 1]);
let turns = turnsMap.get(routeKey);
if (turns != undefined) {
totalTurns += turns;
} else {
turns = findRoute(roadGraph, route[i], route[i + 1]).length;
// 计算 a到b 的最小步数 ↑
// 保存计算结果 ↓
turnsMap.set(routeKey, turns);
routeKey = route[i + 1].concat(route[i]); // a到b和b到a的最短路是一样的。
turnsMap.set(routeKey, turns); totalTurns += turns;
}
}
return totalTurns;
} /**
* 寻找最短路线
*/
function shortestRoute(routes) {
let min = Infinity;
let tempRoute;
let turnsMap = new Map(); // 用于保存已经计算的两点值，避免重复计算
for (let route of routes) {
let turns = turnsOfRoute(route, turnsMap);
if (turns < min) {
min = turns;
tempRoute = route; // 保存最短路线
}
} // 将最短路线转化为相邻的可以实际移动的地点序列
let result = [];
for (let i = 0; i != tempRoute.length - 1; ++i) {
// 仍然是两点、两点处理
let midRoute = findRoute(roadGraph, tempRoute[i], tempRoute[i + 1]);
if (result[result.length - 1] != midRoute[0]) { // 避免出现两个连续重复place
result = result.concat(midRoute);
} else {
result = result.concat(midRoute.shift());
}
}
return result;
} function simpleRobot({place, parcels}, route) {
if(route.length == 0) {
let sequences = makeSequences(2, parcels.map(() => 0)); // 转化成一种比较抽象的东西。。。
let routes = sequencesToRoutes(sequences, {place, parcels});
route = shortestRoute(routes);
}
return {direction: route[0], memory: route.slice(1)};
} //runRobot(VillageState.random(), simpleRobot, []);
// 版本四，穷举。。 平均 10.64
//runRobotAnimation(VillageState.random(), simpleRobot, []);
- - -- - - - - -- -- -- - - - - -- - -- - -
③ Persistent group
结果没错，实现上有点跑偏。。（英语阅读能力不足造成的）
class PGroup {
add(x) {
let result = Object.create(PGroup.prototype);
if (this.container == undefined) {
this.container = [];
}
if (!this.container.includes(x)) {
result.container = this.container.concat(x);
} else {
result.container = this.container;
}
return result;
}
delete(x) {
let result = Object.create(PGroup.prototype);
if (this.container != undefined) {
result.container = this.container.filter(a => !(a === x));
}
return result;
}
has(x) {
if (this.container != undefined) {
return this.container.includes(x);
}
return false;
}
}
PGroup.empty = Object.create(PGroup.prototype);
let a = PGroup.empty.add("a");
let ab = a.add("b");
let b = ab.delete("a");
console.log(b.has("b"));
// → true
console.log(a.has("b"));
// → false
console.log(b.has("a"));
// → false