Escape the Labyrinth

Computers are only as intelligent as their programming allows them to be. In order for a robot to produce amazing feats, programmers must have a strong grasp of algorithms, and understand how it would interact with its surroundings. For this teaser into Computer Science, you are asked to follow an algorithm and determine what the result will be. Pretend that you are a robot, and can only obey the instructions that are given to you. If your algorithm was written by a good programmer, the code will make a sense and you'll see how it achieves the goal. At other times, the instructions will baffle you and you'll wonder who would ever write such a thing.

Here are some tips for you to get started:

1. Track what happens at each step.
2. Be aware of where you are in the code, and be clear of what happens next.
3. Keep a record of your intermediate steps, in case you need to backtrack.
4. Not all algorithms end. Sometimes they loop endlessly, especially if they go back to the start.
5. Practice with more algorithms!

Theseus is practicing his maze escape skills on the simple labyrinth above. He starts at the square labeled "in", facing right (the direction of the arrow), and begins by walking forward one square. The exit is in the bottom right square. After his initial step, can he use the following algorithm to help him escape from this labyrinth?

• If he sees a wall directly to his front, left, and right, spin around 180 degrees.
• Otherwise, if he has a choice of two directions to move in (other than the direction he just came from), spin around 180 degrees and walk forward one square.
• Otherwise, if there is one direction to move in (other than the direction he just came from), walk forward one square in that direction.
• If he is at the exit, stop.
• Otherwise, go to the first step.

• At the start, he has one direction to move in, and so he takes one step to the right.
• He has one direction to move in, and so he takes one step to the right.
• He has one direction to move in, and so he takes one step to the right.
• He sees a wall to his front, left and right. So he spins around 180 degrees.
• He has one direction to move in, and so he takes one step to the left.
• He has one direction to move in, and so he takes one step to the left.
• He has one direction to move in, and so he takes one step to the left. He is now back to the starting point, but facing left.
• He has one direction to move in, and so he takes one step down.
• He has two directions to move in, so he spins around 180 degrees and walks forward one square. He is now back to the starting point.
• From here, he has one direction to move in, and so he takes one step to the right.

We see that this process repeats indefinitely, and so he will be stuck in a loop and be unable to escape from the labyrinth.

This diagram shows what happens as he follows the algorithm.

Back to Quiz: Labyrinth Liberation

Computer Science problems can be classified in the following areas:

• Knowledge: Be introduced to Strings, Graphs, Arrays, Linked Lists, Objects, and understand why they are important to the Computer Scientist.
• Writing code: Understand the basics of writing code using Subroutines, While Loops, For Loops, and Conditionals. This helps you understand the complexity of your code, and how to improve it.
• Speeding up the programming: Using algorithms for Sorting, dynamic programming, Monte-Carlo, and Memoization we can solve much more challenging problems in a reasonable amount of time.