I’ve really enjoyed thinking about the puzzles at http://gurmeet.net/puzzles/, especially looking for ways to solve them or get hints as to how to solve them using visualization without knowing the answers. Last Time I explored puzzle 11, Treasure Island, and this time I’ll look at puzzle 5, Fox in a Hole.
The Puzzle
Here is the wording from http://gurmeet.net/puzzles/:
Consider five holes in a line. One of them is occupied by a fox. Each night,
the fox moves to a neighboring hole, either to the left or to the right. Each
morning, you get to inspect a hole of your choice. What strategy would ensure
that the fox is eventually caught?
The Challenge
The question I asked was, can we, without knowledge of a working strategy, create a fox that plays optimally against us so we can be sure we’ve come up with a strategy that will work? We could simulate a fox that chooses to move left or right randomly, but we would never be sure that our strategy is fool proof. Can we make sure our fox plays hard to get if we don’t even know how to catch it? Turns out we can. Try out the demo of my solution and see if you can both figure out how to catch the fox and understand why a strategy works. Implementation details are below the demo. Code is at https://gist.github.com/azundo/5941503.
Instructions
Click on a hole to select it for inspection. You win if the fox has nowhere
left to hide. If you give up, click the button and one possible path the fox
could have taken to avoid your inspections will be shown.
A Quantum Fox
Instead of modeling our fox as being in one concrete location, we’ll keep track of all possible holes the fox could be in at any given time without getting caught, depending on which holes we have inspected in the past. We’ll use a finite-state machine to keep track of which holes the fox could be in. If we ever get to the state where the fox couldn’t be in any holes without being caught, we know our strategy is a good one. We don’t require any knowledge of the best path for the fox to choose, or a winning strategy.
Our State Space
Each state in our state space will consist of all of the possible holes the fox
could be in at any one time. There are 5 holes and each hole has two states: it
is either possible for the fox to be in that hole, or not possible. This gives
us a state space of size 2^5 = 32
. We could model this as a bit vector with 5
bits, but for clarity I will use a simple array. If it is possible for the fox
to be in hole i
, then our state array will contain i
. We’ll number our
holes 0
, 1
, 2
, 3
, 4
.
For example, before we check any holes, our state would be [0, 1, 2, 3, 4]
.
The fox could be in any hole. If we check hole 2
, then our state would move
to [0, 1, 3, 4]
. In the case where there is no possible hole for our fox to
be in without catching him at some point, our state is an empty array []
.
State Transitions
The key implementation detail when using a state machine is our state transitions. How do we decide which state we move to next? In our case our next state is dependent on two things, our previous state (the set of possible holes the fox could have been in yesterday) and our selection of which hole to check.
To start let’s forget about the action of checking a hole. How can we determine
what holes the fox can be in based on what holes it could have been in
yesterday? If it was possible for the fox to be in hole i
yesterday, then it
is possible for the fox to be in any hole beside i
today. If we iterate over
all of the holes that the fox could have been in yesterday then we’ll get the
set of holes it could be in today.
We’ll use a very simple adjacency list to make our lives easy. If we access
element i
of the adjacency list we will get back an array containing all of
the holes next to i
.
1 2 3 4 5 6 7 8 9 10 |
|
This adjacency list defines a very simple graph where each hole is a node connected by edges to each of its adjacent holes. The first and last holes only have one adjacent hole (and thus one edge) while the others have two.
Accessing element 0
of our ADJACENCY_LIST
tells us which holes are next
to hole 0
. If we want to know the set of possible future holes, we take the
set of possible past holes and add all of the adjacent holes. Simple enough.
Lastly we don’t include the hole that we chose to inspect since the fox would get caught if he ended up there. Hence, our transition function looks like this:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
|
If we ever end up with an empty state, the fox has nowhere to go. We must have caught it at some point, no matter where it started and how it decided to move.
Every time we select a hole to inspect, we’ll update our state and push a copy of it onto an array to keep track of what states we’ve been through in the past. We’ll use that later.
1 2 3 4 5 6 7 8 9 10 11 |
|
Reconstructing the Fox’s Moves
If we save each state we reach, we can reconstruct a possible path the fox could have taken to get to the current state. Let’s choose any arbitrary hole from the current state, and work backwards by looking for adjacent holes in the previous state. We are guaranteed to find a backwards path since every hole in our current state must be possible. Here is the code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
|
Demo and Further Steps
Throwing this together with some d3.js drawing and we get the demo from above. The full code is in a gist at https://gist.github.com/azundo/5941503 and viewable on bl.ocks.org at http://bl.ocks.org/azundo/5941503.
You could also make solving the puzzle a bit easier if you showed all possible holes the fox could be in as you go along, instead of only showing one possible path at the end. Feel free to fork and implement this as a good exercise in d3 basics.
Now can you catch the fox?
Attributions
- Fox designed by Sebastian Blei from The Noun Project