Glude
BAN USER- 1of 1 vote
AnswersYou 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).
- Glude in United States
Find an algorithm to get the monkey in the fewest shots possible.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Trees and Graphs
@ Anonymous
"solution for 5 trees is the below sequence
2 3 3 4 4 3 3 2 2"
shoot 2 => monkey 1 -> 2
shoot 3 => monkey 2 -> 1
shoot 3 => monkey 1 -> 2
shoot 4 => monkey 2 -> 3
shoot 4 => monkey 3 -> 4
shoot 3 => monkey 4 -> 5
shoot 3 => monkey 5 -> 4
shoot 2 => monkey 4 -> 5
shoot 2 => monkey 5 -> 4, Monkey wins
"for 7 trees it will be
2 3 3 4 4 5 5 6 6 5 5 4 4 3 3 2 2"
=> This sequence has the exact same flaw
@ cobra : the tree configuration is not specified in the problem description. that means the configuration can be anything. Your goal is to define the type of configurations that do not accept a solution, and for the configurations which do, find an algorithm to produce a shot sequence that is a solution.
- Glude August 03, 2012@ Anonymous : for 4 trees in a line, your counter example 1 -> 2 -> 1 -> 2 -> 1 doesn't work against sequence 2 3 3 2.
Here is why :
shoot 2 => monkey 1 -> 2
shoot 3 => monkey 2 -> 1
shoot 3 => monkey 1 -> 2
shoot 2 => monkey dead, you can't do the last move from 2 -> 1
I still think 2 3 3 2 works against every possible move of the monkey and I can prove it.
if there is a cycle of length more than 2 nodes in the graph, there is no solution to the problem
- Glude August 03, 2012