(Hello, friends. This is yet another puzzle from BWOC. I don't know the solution to this one yet, so I was thinking we could work on this together.)
You are tasked with designing a robot to explore a large but finite maze. The maze is drawn on a square grid, and walls exist on some of the edges of the square grid. Some of the squares contain a flag.
Your robot may interact with the world in the following ways:
1) Check which of the 4 adjacent edges contain walls.
2) Move to one of the 4 adjacent squares (provided there is no wall in the way).
3) Check if there is a flag on your square.
4) Pick up a flag (provided there is a flag on your square and the robot is not already holding a flag).
5) Put down a flag (provided the robot is holding a flag and there is not already a flag on your square).
6) Generate a random bit.
7) Output a number.
Your robot will be placed in a maze. The maze will contain some number of flags (from 100 to 1000). All flags will be reachable from the robot’s starting position. Your robot is tasked with determining the number of flags. The robot may take as long as it needs, but may only output one number and must output the correct answer eventually, with probability 1.
The catch is that your robot is not Turing complete. It only has a finite amount of memory. You can give your robot as much memory as you need, but it must succeed on arbitrarily large mazes
(Hello, friends. This is yet another puzzle from BWOC. I don't know the solution to this one yet, so I was thinking we could work on this together.)
You are tasked with designing a robot to explore a large but finite maze. The maze is drawn on a square grid, and walls exist on some of the edges of the square grid. Some of the squares contain a flag.
Your robot may interact with the world in the following ways:
1) Check which of the 4 adjacent edges contain walls.
2) Move to one of the 4 adjacent squares (provided there is no wall in the way).
3) Check if there is a flag on your square.
4) Pick up a flag (provided there is a flag on your square and the robot is not already holding a flag).
5) Put down a flag (provided the robot is holding a flag and there is not already a flag on your square).
6) Generate a random bit.
7) Output a number.
Your robot will be placed in a maze. The maze will contain some number of flags (from 100 to 1000). All flags will be reachable from the robot’s starting position. Your robot is tasked with determining the number of flags. The robot may take as long as it needs, but may only output one number and must output the correct answer eventually, with probability 1.
The catch is that your robot is not Turing complete. It only has a finite amount of memory. You can give your robot as much memory as you need, but it must succeed on arbitrarily large mazes
Share this post
Link to post
Share on other sites