Eloquent JavaScript 07 robot

robot

To the book page
代码解释由AI生成。

总代码

数据结构和图的构建

首先定义了村庄中各个地点之间的道路：

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"
];

接着，定义 buildGraph 函数来构建图：

function buildGraph(edges) {
    let graph = Object.create(null); // 创建一个空对象作为图
    function addEdge(from, to) { // 定义一个添加边的函数
      if (from in graph) {
        graph[from].push(to); // 如果节点已经存在，直接添加边
      } else {
        graph[from] = [to]; // 如果节点不存在，创建新数组并添加边
      }
    }
    for (let [from, to] of edges.map(r => r.split("-"))) {
      addEdge(from, to); // 添加双向边
      addEdge(to, from);
    }
    return graph; // 返回构建好的图
}
  
const roadGraph = buildGraph(roads);

村庄状态类

VillageState 类表示村庄的状态，包括机器人的位置和包裹的位置：

class VillageState {
    constructor(place, parcels) {
      this.place = place; // 机器人当前所在的位置
      this.parcels = parcels; // 包裹列表，每个包裹有一个位置和目标地址
    }
  
    move(destination) {
      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); // 返回新的村庄状态
      }
    }
}

运行机器人

runRobot 函数模拟机器人运行：

function runRobot(state, robot, memory) {
    for (var turn = 0;; turn++) {
      if (state.parcels.length == 0) {
        break; // 如果所有包裹都已送达，结束循环
      }
      let action = robot(state, memory); // 调用机器人函数，获取下一步动作
      state = state.move(action.direction); // 移动到下一步位置
      memory = action.memory; // 更新机器人的记忆
    }
    return turn; // 返回所用的回合数
}

随机机器人

randomRobot 随机选择一个方向移动：

function randomPick(array) {
    let choice = Math.floor(Math.random() * array.length);
    return array[choice]; // 从数组中随机选择一个元素
}
  
function randomRobot(state) {
    return {direction: randomPick(roadGraph[state.place])}; // 随机选择一个邻居方向
}

预定义路径机器人

routeRobot 按照预定义的路径移动：

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)}; // 按照路径顺序移动
}

目标导向机器人

goalOrientedRobot 根据包裹的位置和目标地址找到最佳路径：

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)}; // 返回下一步方向和剩余路径
}

效率机器人

efficientRobot 根据所有包裹找到最短路径，以提高效率：

function efficientRobot({place, parcels}, route) {
    if (route.length == 0) {
        let routes = [];
        for (let parcel of parcels) {
        if (parcel.place != place) {
            routes.push(findRoute(roadGraph, place, parcel.place)); // 找到包裹位置的路径
        } else {
            routes.push(findRoute(roadGraph, place, parcel.address)); // 找到包裹目标地址的路径
        }
        }
        route = routes.reduce((shortest, current) => 
        shortest.length < current.length ? shortest : current // 选择最短路径
        );
    }
    return {direction: route[0], memory: route.slice(1)}; // 返回下一步方向和剩余路径
}

机器人比较

compareRobots 用于比较两个机器人的性能：

function compareRobots(robot1, memory1, robot2, memory2) {
    let totalTurns1 = 0;
    let totalTurns2 = 0;
    for (let i = 0; i < 100; i++) {
      let state = VillageState.random(); // 随机生成初始状态
      totalTurns1 += runRobot(state, robot1, memory1); // 运行第一个机器人
      totalTurns2 += runRobot(state, robot2, memory2); // 运行第二个机器人
    }
    console.log(`Robot 1 average turns: ${totalTurns1 / 100}`);
    console.log(`Robot 2 average turns: ${totalTurns2 / 100}`);
}

最后，比较目标导向机器人和效率机器人的表现：

compareRobots(goalOrientedRobot, [], efficientRobot, []);

这段代码会运行两个机器人各100次，比较它们完成任务所需的平均回合数。

Exercises

Measuring a robot

// 运行机器人并计算所需回合数
function runRobotCount(state, robot, memory) {
  for (let turn = 0;; turn++) { // 从0开始记录回合数
    if (state.parcels.length == 0) { // 如果所有包裹都已送达
      return turn; // 返回总回合数
    }
    let action = robot(state, memory); // 获取机器人下一步的动作
    state = state.move(action.direction); // 根据机器人的指示移动
    memory = action.memory; // 更新机器人的记忆
  }
}

// 比较两个机器人的表现
function compareRobots(robot1, memory1, robot2, memory2) {
  let totalTurns1 = 0, totalTurns2 = 0; // 初始化两个机器人所用的总回合数
  let tasks = 100; // 设置任务数量为100

  for (let i = 0; i < tasks; i++) { // 循环运行100次
    let state = VillageState.random(); // 随机生成初始状态
    totalTurns1 += runRobotCount(state, robot1, memory1); // 运行第一个机器人并累计回合数
    totalTurns2 += runRobotCount(state, robot2, memory2); // 运行第二个机器人并累计回合数
  }

  // 输出每个机器人完成任务所需的平均回合数
  console.log(`Robot 1 averaged ${totalTurns1 / tasks} turns per task`);
  console.log(`Robot 2 averaged ${totalTurns2 / tasks} turns per task`);
}

// 比较预定义路径机器人和目标导向机器人的表现
compareRobots(routeRobot, [], goalOrientedRobot, []);

Robot efficiency

// 找到从起点到多个目标中最短的路线
function findShortestRoute(graph, from, goals) {
  // 对每个目标调用 findRoute 函数，返回所有路径
  let routes = goals.map(goal => findRoute(graph, from, goal));
  // 通过 reduce 方法找到最短的路径
  return routes.reduce((shortest, current) => 
    shortest.length < current.length ? shortest : current
  );
}

// 高效机器人，选择最优路径来传递包裹
function efficientRobot({place, parcels}, route) {
  if (route.length == 0) { // 如果当前没有预定的路径
    let routes = []; // 存储所有可能的路径
    for (let parcel of parcels) { // 遍历每个包裹
      if (parcel.place != place) {
        // 如果包裹还没被捡起，找到去包裹位置的路径
        routes.push(findRoute(roadGraph, place, parcel.place));
      } else {
        // 如果包裹已捡起，找到去目标地址的路径
        routes.push(findRoute(roadGraph, place, parcel.address));
      }
    }
    // 选择所有路径中最短的一条
    route = routes.reduce((shortest, current) => 
      shortest.length < current.length ? shortest : current
    );
  }
  // 返回机器人下一步的方向和更新后的记忆
  return {direction: route[0], memory: route.slice(1)};
}

runRobotAnimation(VillageState.random(), efficientRobot, []);

Persistent group

class PGroup {
  constructor(members) {
    this.members = members; // 初始化成员列表
  }

  // 添加新成员
  add(value) {
    if (this.has(value)) return this; // 如果成员已经存在，返回当前对象
    return new PGroup(this.members.concat(value)); // 否则，创建新对象并添加新成员
  }

  // 删除成员
  delete(value) {
    if (!this.has(value)) return this; // 如果成员不存在，返回当前对象
    return new PGroup(this.members.filter(m => m !== value)); // 否则，创建新对象并删除指定成员
  }

  // 检查成员是否存在
  has(value) {
    return this.members.includes(value); // 返回成员是否在列表中
  }

  // 定义一个静态属性，表示一个空的 PGroup 实例
  static empty = new PGroup([]);
}

// 测试实现
let a = PGroup.empty.add("a"); // 向空组添加 'a'
let ab = a.add("b"); // 向包含 'a' 的组添加 'b'
let b = ab.delete("a"); // 从包含 'a' 和 'b' 的组删除 'a'

console.log(b.has("b")); // → true  检查 'b' 是否存在
console.log(a.has("b")); // → false 检查 'b' 是否存在
console.log(b.has("a")); // → false 检查 'a' 是否存在