-4
$\begingroup$

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.

$\endgroup$
11
  • $\begingroup$ Do you know the optimal solution to this puzzle? $\endgroup$ Commented Aug 29, 2023 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$
    – Bass
    Commented Aug 29, 2023 at 18:28
  • $\begingroup$ Have you beaten 87.42445 guesses? $\endgroup$ Commented Aug 29, 2023 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$ Commented Aug 29, 2023 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$ Commented Aug 29, 2023 at 19:51

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
1
  • $\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$
    – Bob Bixler
    Commented Aug 29, 2023 at 21:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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