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, []);

7.2 Robot efficiency

Can you write a robot that finishes the delivery task faster than goalOrientedRobot? If you observe that robot’s behaviour, what obviously stupid things does it do? How could those be improved?

If you solved the previous exercise, you might want to use your compareRobots function to verify whether you improved the robot.

Hints

The main limitation of goalOrientedRobot is that it only considers one parcel at a time. It will often walk back and forth across the village because the parcel it happens to be looking at happens to be on the other side of the map, even if there are others much closer.

One possible solution would be to compute routes for all packages and then take the shortest one. Even better results can be obtained by, if there are multiple shortest routes, preferring the ones that go to pick up a package instead of delivering a package.

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.