[Solved]: Algorithm for finding a mouse hole in a wall in O(n) time

Problem Detail: 

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?

Asked By : Brian

Answered By : Denis Pankratov

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/52772

3.2K people like this

 Download Related Notes/Documents