3
$\begingroup$

There is this question:

As a result of the US Election, a wall is built along the entire Canadian border. You have been told there is a mouse hole in the wall, but it can only be seen when you are standing in front of it. Your task is to find the mouse hole by walking along the wall; however, you are standing in Minnesota and do not know whether the hole is East or West of your current location.

Give an algorithm that will allow you to find the mouse hole in O(n) steps, where n is the (unknown to you) distance in steps from your initial location to the mouse hole.

I was thinking that to find the mouse hole in O(n) steps, I would have to go both East and West at the same time.

But seeing that I can't do this (or maybe I can?), I thought that regardless of direction I first take since I'm traveling around the US border and then around the Canadian border, I would have traveled a linear time. I'm also thinking that this problem might resemble a graph?

How can I go about writing an algorithm to describe this?

$\endgroup$

2 Answers 2

1
$\begingroup$

Here is one strategy. Choose a direction (left or right) arbitrarily. Then go for some number of steps. If found the hole, you are done. Else turn around, and move backwards for a double number of steps. If found the hole you are done. Else return to start. Repeat. In each repetition of this loop, you need to increase the distance you walked. To specify the algorithm, now you need to say for how long you walk until turning back, and how much you increase the distance walked in each consecutive loop. In order for this to be efficient, you want exponential increase, i.e., in iteration $i$ you walk left for $2^i$ steps, then turn walk right for $2 * 2^i$ and return back to start for a total of $4*2^i = 2^{i+2}$ steps in iteration $i$. Now, if a hole is located at position $n$ = $2^j$ for some $j$ then you will discover it in iteration $j$. By that time you would have walked $\sum_{i=0}^j 2^{i+2} = 4(2^{j+1}-1) \le 8n = O(n)$ steps.

$\endgroup$
2
  • $\begingroup$ (worst case would be at $n = 2^j + 1$) $\endgroup$
    – greybeard
    Commented Feb 6, 2016 at 21:40
  • $\begingroup$ Good comment! Indeed, I only gave the analysis for the easiest case when $n$ is a power of two. The general case differs by a multiplicative constant. $\endgroup$ Commented Feb 7, 2016 at 0:24
3
$\begingroup$

This problem goes by various names, including the linear search problem and the cow path problem. The solution indicated in Denis's answer is optimal for deterministic algorithms (though the competitive ratio is 9 rather than 8), but randomized algorithms can do almost twice as better; see Kao, Rife and Tate.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.