Monkey Hunter algorithm - Interview question [closed]

Question

Question asked in an Interview:

You are a hunter in the forest. A monkey is in the trees, but you don't know where and you can't see it. You can shoot at the trees, you have unlimited ammunition. Immediately after you shoot at a tree, if the monkey was in the tree, he falls and you win. If the monkey was not in the tree, he jumps (randomly) to an adjacent tree (he has to).

Find an algorithm to get the monkey in the fewest shots possible.

SOLUTION:

The correct answer according to me was in the comments, credit to @rtperson:

You could eliminate this possibility by shooting each tree twice as you sweep left, giving you a worst case of O(2n). EDIT: ...that is, a worst case of O(2n-1). You don't need to shoot the last tree twice.

Answer 1

I will make an assumption.

1. The trees are arranged in 1D left to right.

It would seem you could guarantee a hit shooting at the left most tree and going to the right. The Monkey won't be able to jump two trees, because he has to jump to an adjacent tree, so you will eventually hit the monkey.

Best case is O(1)

Worse case is O(2n-1)

rtperson is correct. The monkey could choose to go left to the place you just shot which means you will miss him.

1 2 3 4 5 6 7
x m   

1 2 3 4 5 6 7 (missed him)
m x 

So each space requires two shots:

1 2 3 4 5 6 7
x m   

m
1 2 3 4 5 6 7  (dead monkey)
x  

or

1 2 3 4 5 6 7
  x m  

1 2 3 4 5 6 7
  x   m

etc

Answer 2

There is not enough information here.

Because the Monkey jumps to an adjacent tree you need to know the configuration of the trees to answer this question (How many there are and their location in relation to one another).

Answer 3

I'm not sure if it's the fastest way to find the monkey, but I would just pick one tree and shoot at it until monkey falls down. Because if it's not there, monkey can randomly jumps at it.

Answer 4

You need to know:

1. Spatial characteristics of trees
2. Ammo type - an arrow will kil a monkey in 1 tree, agent orange will clear the forest
3. Movement pattern, does the monkey jump in one direction or both, or if 3D forward and back
4. And most importantly can you see the monkey when it's jumping, you can't see it hiding in the tree, but is it exposed otherwise

Beyond that the most efficient is "the child lost in the mall theory" also known as "I didn't study for the test" theory. Just fire in one place until you hit the monkey

Answer 5

So this is really just about probabilities, which aren't my strong point. Not that it will stop me from trying an answer.

Let's assume N trees.

If you shoot at the same tree over and over, AND if the monkey is jumping randomly from tree to tree, then we may see a hit within N rounds. Of course, random doesn't mean it will visit every value within a given number of cycles, so there's a great chance that we'll need more than N shots.

Other approaches such as shooting at random trees, shooting a pattern of trees, etc... all introduce another degree of probability to the question. And the total probability of a hit becomes product of the two probabilities. P(1:N) * P(shooting).

Shooting the same tree is the only way to minimize the increase in probability from which tree to shoot.

We can add more noise to the matter by discussing whether the trees are linear or some other layout. But that information ultimately becomes irrelevant to the end answer.

Or you can do as James suggests and break the rules of the game.

Answer 6

I'd try some probabilistic approach: Lets define the forest as a n by k array of trees.

At the beginning, each tree has the same probability 1/(n * k) of accomodating the monkey.

After each shot, you can recalculate the probability for each tree by looking at all of its neighbour trees and calculating the product of the previous probability and the probability of the monkey jumping from that tree to the current one. Summing up all these products gives the new probability for the current tree.

Note, that after the first shot, the probabilities aren't equal anymore: The "corner trees" will be less probable, because the probability of the monkey jumping away from them is one, but the probability of him jumping back is only 2/3 (because each of the two neighbours of the corner has three neighbours).

Also, you'll have to set the probability for each tree you shot at to zero (if the shot was unsucessful), because clearly the monkey wasn't there. Again, this "zero" will "propagate" somehow, I guess.

Now my strategy would be to shoot at the tree with the highest probability. But it might also be a good tactic to try to first maximize the probability at some point and then shoot there. I would have to implement this for being sure :).

Note that no algorithm can guarantee that you get the monkey (if the forest is big enough). Assume the monkey was intelligent and knowing your algorithm, he can always escape (since he would be able to predict the next tree you're shooting at, he can always decide to not jump on this tree, assuming each tree has at least two neighbour trees). And the "random" monkey always can just randomly act like an intelligent one and so randomly escape (or btw. accidentially write all of Shakespeare's work on a typewriter ;) ...)