# Find the Rat in the Hole

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.

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