This problem is borrowed from the blog By Way of Contradiction. Check out their other logic problems!
You are tasked with designing a robot to explore a finite maze and count the number of flags in the maze. Your robot should consider the maze as a 2 dimensional grid of spaces, where any edge of the grid may contain a wall that prevents your robot from passing. The maze contains between 100 and 1000 flags, each in its own space. Every flag will be reachable from your robots starting position. You’re given the latest and greatest of hardware – your robot can have any finite amount of memory. Your robot will be able to do the following things while in the maze:
1) Check if there is a wall on any edge of the current square
2) Move to an adjacent square (assuming no wall blocks the path)
3) Pick up a flag (if the current square contains one, and the robot is not already holding a flag)
4) Put down a flag (if the current square does not contain one, and the robot is already holding a flag)
5) Generate a random bit
6) Announce the number of flags
Your robot should announce the number of flags only once, and it should be correct when it does so. The robot can take as long as it needs, but, over an infinite time span, it must eventually announce the correct count. Your algorithm should work for arbitrarily large mazes without changing the amount of available memory (the maze can be MUCH larger than whatever amount of memory you choose to have).
What is your algorithm for counting the flags?
Do you love challenges? Then you will love LiveRamp. Apply now to join our team.