The Maze

Welcome to the final project! The dog has ended up in a hedge maze. The editor holds the program from the Conditions lesson, which reliably took the dog along every winding path. Run it and watch the first map.

The dog walks back and forth and never gets to the goal. Why? On a winding path, there was only one way to go on from every place. A maze, however, has junctions. At a junction, the program from the Conditions lesson always goes straight on, so it never turns into a side passage. It walks to the end of a corridor, turns around, walks to the other end, and so on, over and over. A program that works on one set of data can behave quite differently on another. That's why programs are tested on inputs that are as varied as possible.

There's a simple and famous algorithm for mazes: the right-hand rule. Put your right hand on a wall of the maze and never take it off. If you keep walking along the wall, you'll get to the goal in every maze whose walls are all connected. The mazes in this course are like that.

For the dog, it means this. On every pass through the loop:

1. If there's a path to the right, it turns right and takes a step.
2. Otherwise, if there's a path ahead, it takes a step.
3. Otherwise, it turns left.

Notice that in the first point, the dog takes a step right after turning right. If it didn't, on the next pass it would see a path to the right again (the one it just came from) and keep spinning. In the third point, on the other hand, just turning is enough: on the next pass, the dog decides again, with a new view. In a dead end, it turns left twice and walks back.

You know these decisions from the Conditions lesson; they just need a different order and content. Change the program, or build it again.