Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question

closed as off topic by Bryan Oakley, Steven A. Lowe, Steve Evers, Karl Bielefeldt, Caleb Aug 6 '12 at 17:54

Questions on Programmers Stack Exchange are expected to relate to software development within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

19  
Burn the forest using the gunpowder from your unlimited ammo supply –  James Aug 6 '12 at 16:44
7  
Is this a simplified 2D (trees have two neighbors each) forest, or a simplified 3D (trees have K neighbors each) forest, or a complicated 3D forest (trees have 0-K neighbors, and the number depends on how far neighbors may be away from each other)? –  delnan Aug 6 '12 at 16:49
5  
Does "fewest shots possible" refer to best-case, worst-case, or average-case number of shots? Or perhaps amortized for hunting multiple monkeys simultaneously? (I swear to god, coming up with these questions is a hundred times more fun than actually giving the answer they're looking for.) –  delnan Aug 6 '12 at 16:58
18  
My answer, firing a weapon without seeing your target violates firearm and hunting safety rules. –  jfrankcarr Aug 6 '12 at 17:14
6  
If this question was asked only giving the information you provided I get the feeling it was more about getting you to ask questions that would help reach a solution rather than the solution... –  Rig Aug 6 '12 at 17:50

6 Answers 6

up vote 4 down vote accepted

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

share|improve this answer
4  
Not really. If you shoot at tree k, and the monkey is sitting in k+1, then the monkey could jump into three k when you fire at k+1. There's no guarantee of hitting the monkey this way. –  rtperson Aug 6 '12 at 18:12
1  
You could eliminate this possibility by shooting each tree twice as you sweep left, giving you a worst case of O(2n). EDIT: <ahem> ...that is, a worst case of O(2n-1). You don't need to shoot the last tree twice. –  rtperson Aug 6 '12 at 18:15
    
If you are in the middle of a forest, the trees would form a circle around you. Assuming 'adjacent' means only the trees to the left or right in this arrangement, he would still be able to keep moving around the circle to avoid you. –  Joshua Shane Liberman Aug 6 '12 at 18:24
6  
Shooting twice isn't helping much: The monkey could have been on the tree after the next on the first shot and on the tree just to the right on the second one. After the second, he just jumps to the one you shot twice and you miss him ... –  MartinStettner Aug 6 '12 at 18:41
1  
@Rig I can make as many assumptions as I want. That is one thing I would be looking for in an engineer. Can that person fill in some gaps in a problem. If the problem is left unconstrained and is unsolvable the first thing to do is constrain it and solve from there. –  Andrew Finnell Aug 7 '12 at 13:12

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.

share|improve this answer
1  
If the monkey's choice is indeed truly random, this actually stands a chance of never hitting the monkey. It might as well jump between the same two trees forever. –  delnan Aug 6 '12 at 16:48
    
@delnan That doesn't mean you can't optimize for expected number of shots. –  Brian Aug 6 '12 at 16:51
    
@Brian Sure, the expected number of shots is (or should be, I'm never 100% confident with these things) finite, but at least in the case of a simplified 2D forest there's probably a better way, and intuitively it seems the expected number is pretty bad. –  delnan Aug 6 '12 at 16:53
    
I suggest to get back to statistics basics. It's not about being confident or not. It's just statistics and probability. –  Adronius Aug 25 '12 at 7:05

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).

share|improve this answer
1  
We could be looking at the Texas Sharpshooter Fallacy. When we hit the monkey we say that's what we were aiming at all along. –  jfrankcarr Aug 6 '12 at 20:20

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.

share|improve this answer
    
Wouldn't it be true that shooting at the leftmost and right most trees have a lesser chance of being hits, because there are less paths for the monkey to travel to get into them (from only one side, vs both sides)? –  Chris Aug 6 '12 at 18:28
    
@Chris - I think that presumes a linear array of trees, which we weren't told. "Adjacent tree" is not defined in this case, so I went with a uniform, random distribution pattern. –  GlenH7 Aug 6 '12 at 19:30

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

share|improve this answer
    
#2 and #3 is in fact stated (ammo kills single monkey in single tree; movement is random), #4 is implied to be false. –  delnan Aug 6 '12 at 17:48
2  
Repeatedly firing at the same spot in a mall when there is a lost child wandering around is a very bad idea. :P –  Mason Wheeler Aug 6 '12 at 17:48
2  
LOL "lost child theory" meant to be what people are taught when they are kids, if you get lost, stay in one place and you will eventually be found –  user60812 Aug 6 '12 at 17:51

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 ;) ...)

share|improve this answer

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