7.2 Robot Efficiency (Eloquent JavaScript Solutions)

7-2 Eloquent Javascript Solutions.js

function runRobot(state, robot, memory) {
  for (let turn = 0; ; turn++) {
    if (state.parcels.length == 0) {
      return turn;
    }
    let action = robot(state, memory);
    state = state.move(action.direction);
    memory = action.memory;
  }
}

function compareRobots(robots, iterations = 100) {
  for (let i = 0; i < iterations; i++) {
    let state = VillageState.random();
    for (let robot of robots) {
      if ('results' in robot === false) {
        robot.results = [];
      }
      robot.results.push(runRobot(state, robot.robot, []));
    }
  }
  for (let robot of robots) {
    //    let turns = Math.floor(
    //      robot.results.reduce((a, c) => a + c, 0) / robot.results.length + 0.5
    //    );
    let turns = robot.results.reduce((a, c) => a + c, 0) / robot.results.length;
    console.log(`${robot.name} completed in an average of ${turns} turns.`);
  }
}

function routeRobot(state, memory) {
  if (memory.length == 0) {
    memory = mailRoute;
  }
  return { direction: memory[0], memory: memory.slice(1) };
}

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) };
}

function lazyRobot({ place, parcels }, route) {
  if (route.length == 0) {
    // Describe a route for every parcel
    let routes = parcels.map(parcel => {
      if (parcel.place != place) {
        return {
          route: findRoute(roadGraph, place, parcel.place),
          pickUp: true
        };
      } else {
        return {
          route: findRoute(roadGraph, place, parcel.address),
          pickUp: false
        };
      }
    });

    // This determines the precedence a route gets when choosing.
    // Route length counts negatively, routes that pick up a package
    // get a small bonus.
    function score({ route, pickUp }) {
      return (pickUp ? 0.5 : 0) - route.length;
    }
    route = routes.reduce((a, b) => (score(a) > score(b) ? a : b)).route;
  }

  return { direction: route[0], memory: route.slice(1) };
}

function superRobot({ place, parcels }, route) {
  if (route.length == 0) {
    // Describe a route for every parcel
    let routes = parcels.map(parcel => {
      if (parcel.place != place) {
        return {
          route: findRoute(roadGraph, place, parcel.place),
          pickUp: true
        };
      } else {
        return {
          route: findRoute(roadGraph, place, parcel.address),
          pickUp: false
        };
      }
    });
    // favour routes that include a drop-off
    for (let route of routes) {
      route.includesDropOff = false;
      for (let parcel of parcels) {
        if (route.route.includes(parcel.address)) {
          // route includes a drop-off
          route.includesDropOff = true;
        }
      }
    }
    // This determines the precedence a route gets when choosing.
    // Route length counts negatively, routes that pick up a package
    // or include a drop-off get a small bonus.
    function score({ route, pickUp, includesDropOff }) {
      return (pickUp ? 0.75 : 0) - (includesDropOff ? 0.75 : 0) - route.length;
    }
    route = routes.reduce((a, b) => (score(a) > score(b) ? a : b)).route;
  }

  return { direction: route[0], memory: route.slice(1) };
}

compareRobots(
  [
    {
      name: 'Route Robot',
      robot: routeRobot
    },
    {
      name: 'Goal Oriented Robot',
      robot: goalOrientedRobot
    },
    {
      name: 'Lazy Robot',
      robot: lazyRobot
    },
    {
      name: 'Super Robot',
      robot: superRobot
    }
  ],
  1000
);

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

Analysis

The superRobot is, on average, 0.2 turns quicker than the official solution's lazyRobot. It favours routes that include a drop-off on the way to a pick-up.