2.06 Algorithm Basics

Algorithms: Solving a Maze POGIL Worksheet

Algorithms: Solving a Maze

The problem below is similar to a type of AP CSP exam question. Consider a robot that can follow the simple sequence commands below:

Let's put our robot in the maze below. The robot is represented as a black triangle and is initially facing up. It can only move forward to a white square. It cannot move onto the black squares or move beyond the edge of the grid.

Answer the following questions with your POGIL team:

1. For the robot in the maze above, is CAN_MOVE(forward) true? Is CAN_MOVE(right) true?

CAN_MOVE(forward) will return true while CAN_MOVE(right) will return false.

1. (Portfolio) Write an algorithm using the 4 commands above to navigate the robot through the maze to reach the gray square. You can pretend that one of you is the robot and walk through your algorithm with your fingers on the maze. Are there commands that are repeated in your algorithm? Circle them.

MOVE_FORWARD

MOVE_FORWARD

ROTATE_RIGHT

MOVE_FORWARD

MOVE_FORWARD

MOVE_FORWARD

MOVE_FORWARD

ROTATE_LEFT

MOVE_FORWARD

MOVE_FORWARD

1. (Portfolio) Let's replace the repeated commands with a repetition control structure. The following command can be used to repeat a block of commands:

Rewrite your algorithm above using Repeat n times control structures (substituting in a

number for n) instead of repeating the MOVE_FORWARD command many times.

REPEAT 2 times

MOVE_FORWARD

ROTATE_RIGHT

REPEAT 4 times

MOVE_FORWARD

ROTATE_LEFT

REPEAT 2 times

MOVE_FORWARD

Here’s a more general way to navigate a maze with the following algorithm which uses GoalReached to test if the robot has reached the gray square.

REPEAT UNTIL GoalReached

{

IF (CAN_MOVE forward)

MOVE_FORWARD

IF (CAN_MOVE left)

ROTATE_LEFT

MOVE_FORWARD

IF (CAN_MOVE right)

ROTATE_RIGHT

MOVE_FORWARD

}

1. Which part(s) of the algorithm above are selection control structures? Circle them.
2. Which part of the algorithm above is a repetition control structure? Circle it. Remember a control structure can consist of multiple statements.

5.) (Portfolio) Write an algorithm for washing a stack of 10 items that are cups and saucers mixed together, where the rule is that the cups are washed in hot water and the saucers in cold water. Use simple commands like hot_wash and cold_wash. You may also use the control structures IF and REPEAT n times. Identify the parts of your algorithm that are examples of Sequence, Selection, and Repetition.

REPEAT UNTIL Goal Reached

{

IF (CUP)

HOT_WASH

IF (SAUCER)

COLD_WASH

}