Rabbit in the hole: solving the algorithm

I recently came across this video: Coding interview with Dan Abramov where the creator of Redux engages in a mock interview with YouTuber Ben Awad. During this interview, an algorithmic question is posed to him. As I enjoy challenges of this kind, I'd like to present you with the question and my solution.

Note: This statement appears to be a 100-holes version of the problem known as "Fox in the hole" attributed to K. Rustan M. Leino from Microsoft Research. I would have liked to confidently cite the author here, but like any classic, its attribution gets lost in history! The original problem is presented with 5 holes and a fox.

Imagine 100 aligned holes and a rabbit hiding randomly in one of them. You can only look into one hole at a time - any hole - but each time you do, the rabbit jumps to an adjacent hole.

Some technical details:

• The rabbit's actions are considered random. We won't be overly-clever on the pseudo-random aspect of random. Random is here perfect!
• The rabbit is at position l, unknown at time t. We check the hole at index x.
• The sequence of actions is as follows:
  • We check a hole at index x.
  • If the rabbit is there, we win.
  • If the rabbit (at position k ≠ x) is not there, it randomly jumps to either k-1 or k+1.

In this paragraph, I will use some letters and mathematical symbols to represent and describe my point. Don't be alarmed: paradoxically, it's less complicated and shorter than narrating it with words! If mathematics isn't your cup of tea, feel free to skip directly to the solution! Also know that english is not my native language, so I hope my explanations won't be too convoluted.

Prerequisites

The first thing we need to agree upon is the definition of parity. By that, I mean determining whether a number is even or odd, i.e., if it is divisible by 2. A even number can necessarily be written in the form 2k with k ∈ ℕ, meaning a positive integer. Conversely, an odd number is written in the form 2k+1.

The second thing is that, by definition, the parity of two consecutive numbers is reversed. This means that an odd number always follows an even number, and vice versa.

From this, we can demonstrate that regardless of the number n, n+2 has the same parity as n.

Let n be an even number, n = 2k, then n+2 = 2k+2 = 2(k+1) can be written in the form 2x, where x=k+1, so n+2 is even.
Let n be an odd number, n = 2k+1, then n+2 = 2k+1 +2 = 2(k+1) +1 can be written in the form 2x+1, where x=k+1, so n+2 is odd.

By extending this reasoning, two numbers whose difference is even have the same parity. So, if n is even, n+2x is even. And if n is odd, n+2x is odd.

Let an even number be n = 2k, then n+2x = 2k+2x = 2(k+x) is even.
Let an odd number be n = 2k+1, then n+2x = 2k +1+2x = 2(k+x)+1 is odd.

Demonstration

Let's denote N as the number of holes.
Let's denote p as the position of the rabbit.
Let's denote i as the index of the hole being checked at the moment.

Consider the following procedure : the holes are tested successively in order, from the first to the last. Thus, if we test hole i, the next one tested will be i+1, until N the number of holes.

At the beginning of each step of the procedure, when we are about to check the i-th hole, three scenarios are possible:

1. If p=i : the rabbit is in the hole.
2. If p0 and i0 were of the same parity: then p and i are still of the same parity (cf prerequisites).
3. If p0 and i0 were of different parity: then p and i are still of different parity (cf prerequisites).

Case 1: p=i

The rabbit is in the hole... nothing to say, the game is over!

Case 2: p=i+2x

The rabbit and us have started the game on holes of the same parity, so we are still on holes of the same parity (cf prerequisites) so we have p=i+2x with an unknown x. If the rabbit is behind us (x<0), we will never find the rabbit, it's obvious.
If the rabbit is in front of us (x>0) then we have two options:

• If the rabbit moves to hole p+1 :
  Then we won't find it in the next turn because it is escaping. However, since there is a finite number N of holes, the rabbit cannot always escape. It will necessarily turn around at some point.
• If the rabbit moves to hole p-1 :
  Then in the next turn, we will find the rabbit only if we are in the same hole, i.e., if p-1 = i+1.
  Since p=i+2x, we will find the rabbit only if i+2x-1 = i+1. And this condition is true only for x=1
  In other words, if the rabbit is two holes ahead of us at the beginning of this turn and jumps in our direction, we will necessarily find it in the next turn. And this scenario will definitely happen in this case 2 because the rabbit cannot flee forever.

What we have just shown is that our procedure will necessarily flush out the rabbit if at the beginning of the game it is at an even number of holes from us.

Case 3: p=i+2x+1

In this case, we did not start the game on holes of the same parity. So at any moment, p=i+2x+1 (cf prerequisites). Just like before:
If the rabbit is behind us (x<0), we will never find the rabbit, it is obvious.
If the rabbit is in front of us (x>0) then we have two options:

• If the rabbit moves to hole p+1 : the reasoning is the same as in case 2.
• If the rabbit moves to hole p-1 :
  Then in the next turn, we find the rabbit only if we are in the same hole, i.e., if p-1 = i+1.
  Since p=i+2x+1, we will find the rabbit only if i+2x+1-1 = i+1. And this condition is true only for 2x=1. This is not possible with integer x. This shows that we will never find the rabbit because we can never physically be in the same hole when we look into it!

What we have just shown is that our procedure will always miss the rabbit if at the beginning of the game it is at an odd number of holes from us.

Building on all the observations and demonstrations from the previous chapter, we can now construct a robust algorithm.

Let's iterate through the holes from index 0 to 100. We know from case 2 that if the rabbit is on an even hole {0, 2, 4..., 98}, we will definitely find it. Since we start at the first possible hole, it cannot be behind us at the beginning of the game, and we have shown that by advancing in this way, we will inevitably flush it out.

If - after checking the last hole - we haven't found our rabbit, we now know that it is on a hole with a different parity from ours, so on an odd hole, i.e., {1, 3, 5... 99}. Restarting the procedure a second time, but from hole 1 this time, we know that we are now on an odd hole together, and therefore once again, by our previous demonstration, that we will find it.

In conclusion, here is the resolution algorithm I suggest:

For start ranging from 0 to 1:
|  For i ranging from start to N:
|  |  Check hole i:
|  |  |  - if the rabbit is there:
|  |  |    |  => end of the game "The rabbit is in hole i"
|  |  |  - otherwise, continue

This algorithm - in the worst case - will go through all N holes twice. For each hole, a finite and constant set of operations is performed (checking the hole and the rabbit jumping to its next position).

The complexity of such an algorithm is therefore noted as O(2N)
(pronounced big-O of two N)

Limitations

Our algorithm relies on a number of limitations that should be understood:

• The world is finite: there is a finite number of holes, so the rabbit cannot flee forever.
• The rabbit's jumps are not random: we know its pattern of movement.
• Movements are adjacent in a one-dimensional world: hole positions. Therefore, it follows a known parity rule on which our algorithm relies.
• The world has a single, unfolded dimension: there is no possible loop. The world is neither a maze (graph) of underground tunnels nor a circle.

Do you have a better solution or any comments?
Leave a comment!