Back

Science and Engineering

Which Barn Is Last?

Sometimes, computer scientists face problems with few, if any, solutions. Other times, problems seem to have too many solutions. For a computer scientist, it can be surpassingly tricky to design algorithms for problems that have a huge number of possible solutions!

When an algorithm has to navigate the real world, it's common to encounter explosions in the number of possible solutions. Self-driving cars obviously have this problem, and so does your "friendly" autonomous surveillence-and-same-day-delivery drone, the Eye of Amazoo.

The Eye of Amazoo The Eye of Amazoo

Take a look at the situation described below. (You can run the program by pressing the Run Code button.)

There's only one sequence of three instructions that can get the drone to the red barn #1.\#1. The drone must go East/Right twice, and then go South/Down once.

In a more open map, there are suddenly three different paths to the orange barn #2.\#2. (You can modify this program by dragging tiles from the top row onto the program in the second row.)

Every solution uses the same three steps: two moves to the East/Right and one to the South/Down. But the drone's move to the south can happen first, second, or third.

Another kind of open-endedness comes from the drone needing to take extra steps. If we update the rules to say

  1. the drone must reach the barn and
  2. the drone can only reach a barn at the very last step,

then there are suddenly two different programs that solve this puzzle in exactly five steps:

The map is the same as the map from the first step, so the overall movement is the same: the drone must go East/Right twice, and then South/Down once.

The rules mean that the "South/Down" instruction can only be the very last instruction: it's against the rules to visit the yellow barn #3\#3 more than once. The extra two instructions must be an extra movement to the left, followed by an extra movement to the right. This movement can begin in exactly one of the following two locations highlighted in green:

Today's Challenge

The Eye of Amazoo has to make deliveries at three different barns.

Its procedure for working out which order to visit the houses is as follows:

  • Count the number of possible routes to a barn that take 44 moves or fewer.
  • Go to the barn with the least number of possible routes.
  • Recompute for the remaining barns from the drone‚Äôs new position.

The drone does not move onto a square with a barn unless it is making a delivery. Which barn will the drone visit last?

×

Problem Loading...

Note Loading...

Set Loading...