A rat is in one of 100 holes that are in a line. Each night he moves to the left or right 0,1, or 2 holes randomly selected. You pick one hole each day to look in until you find him. What procedure do you use in order to minimize the expected number of days before you find him? This question is of my own devising.
$\begingroup$
$\endgroup$
11
-
$\begingroup$ Do you know the optimal solution to this puzzle? $\endgroup$– user1502040Aug 29 at 18:13
-
1$\begingroup$ I think I do, but it's very bayesian and extremely computation heavy. By the way, what exactly happens if the rat tries to go left further than the leftmost hole? $\endgroup$– BassAug 29 at 18:28
-
$\begingroup$ Have you beaten 87.42445 guesses? $\endgroup$– user1502040Aug 29 at 18:30
-
$\begingroup$ Nice problem. I totally agree with @Bass. My fear is that you have to maintain a huge Bayesian structure mapping all possibilities from the past (if you want the optimal solution), and exploit it maybe with greedy policy or epsilon or whatever. I think one can achieve good approximations with simpler data structures or making some approximations, but then this became more an ML challenge than a puzzle. However some simple heuristics seem to perform better than 87 days. $\endgroup$– 10010100102ohnoAug 29 at 18:46
-
2$\begingroup$ If you do not know the optimal solution, then this is not a puzzle, it is an engineering problem. Puzzles need a clever, hidden insight that leads to a beautiful, unambiguous solution. $\endgroup$– Mike EarnestAug 29 at 19:51
|
Show 6 more comments
1 Answer
$\begingroup$
$\endgroup$
1
Following this zero-indexed sequence of guesses:
[94, 97, 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50, 53, 56, 59, 62, 65, 68, 71, 74, 77, 80, 83, 86, 89, 92, 95, 5, 2, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46, 49, 52, 55, 58, 61, 64, 67, 70, 73, 76, 79, 82, 85, 91, 94, 97, 89, 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50, 53, 56, 59, 62, 65, 68, 71, 74, 77, 80, 83, 86, 89, 92, 95, 5, 2, 10, 13, 16, 19, 22, 97, 94, 91, 29, 32, 35, 38, 41, 44, 47, 50, 53, 56, 59, 62, 65, 68, 71, 74, 77, 80, 83, 86, 89, 92, 95, 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50, 53, 56, 59, 62, 65, 68, 71, 74, 77, 80, 83, 86, 89, 92, 95, 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50, 53, 56, 59, 62, 65, 68, 71, 74, 91, 94, 97, 86, 83, 80, 77, 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 91, 94, 97, 44, 47, 50, 53, 56, 59, 62, 65, 68, 71, 74, 77, 80, 83, 86, 89, 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50, 97, 94, 91, 54, 57, 60, 63, 66, 69, 72, 75, 78, 81, 84, 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50, 53, 56, 59, 91, 94, 97, 86, 83, 80, 77, 74, 71, 68, 65, 62, 2, 5, 8, 11, 14, 17, 20, 23, 91, 94, 97, 54, 51, 48, 45, 42, 39, 36, 33, 30, 88, 85, 82, 79, 76, 73, 70, 67, 64, 61, 58, 55, 5, 2, 91, 94, 97, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48, 51, 54, 86, 83, 80, 77, 74, 71, 68, 65, 62, 8, 5, 2, 91, 94, 97, 13, 16, 19, 22, 25, 28, 54, 51, 48, 45, 42, 39, 36, 33, 87, 84, 81, 78, 75, 72, 69, 66, 8, 5, 2, 91, 94, 97, 14, 17, 20, 23, 26, 29, 61, 58, 55, 52, 49, 46, 43, 40, 37, 34, 8, 5, 2, 87, 84, 81, 78, 75, 72, 69, 66, 63, 60, 91, 94, 97, 15, 18, 21, 24, 27, 30, 11, 8, 5, 2, 53, 50, 47, 44, 41, 38, 87, 84, 81, 78, 75, 72, 69, 66, 63, 60, 57, 91, 94, 97, 13, 16, 19, 22, 25, 28, 31, 34, 5, 2, 37, 40, 43, 46, 49, 52, 55, 58, 85, 82, 79, 76, 73, 70, 67, 64, 61, 94, 97, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 2, 5, 8, 47, 50, 53, 56, 91, 88, 85, 82, 79, 97]
followed by uniform random guessing, achieves an average guess number of about 83.363. This was found by depth-3 lookahead search with entropy as the cost function. It seems like scanning up and down in steps of 3 is a major part of the strategy, but there are also many seemingly-random jumps.
-
$\begingroup$ Good answer. I also got 83 days just starting at 1 and moving 3 to the right each day and then starting over at 1 once you reached or exceeded 100. $\endgroup$ Aug 29 at 21:18