Back to Challenge Set 11

Pseudocode Challenge: Robot on a Grid

Difficulty  

divider

Objective

Three problems on the robot block. This is a recurring exam question type — it arrives with a picture of a grid and a robot in one square — and nothing else in this course teaches it. There is no C# equivalent to translate from, so this page is the only place you meet it before May.

Do this on paper. There is nothing to run and nothing to type. On exam day you get this notation on a printed sheet and no computer, so practicing it any other way practices the wrong thing. Draw the grid and move a pencil around it.

What You Are Allowed to Use

Everything the robot block gives you, plus the control flow you already have. Nothing else appears in these problems.

Movement
MOVE_FORWARD()
ROTATE_LEFT()
ROTATE_RIGHT()
Sensing
CAN_MOVE(direction)


direction is one of
  left  right  forward  backward
Counted loop
REPEAT n TIMES
{
  ...
}
Conditional loop
REPEAT UNTIL(condition)
{
  ...
}
Selection
IF(condition)
{
  ...
}
ELSE
{
  ...
}

What each one does:

CommandEffect
MOVE_FORWARD()One square in the direction the robot is facing
ROTATE_LEFT()Turn 90 degrees counterclockwise, in place
ROTATE_RIGHT()Turn 90 degrees clockwise, in place
CAN_MOVE(direction)true if the next square that way is open

Three rules that catch people:

  • Directions are relative to the robot, not to the grid. CAN_MOVE(left) means the robot's left, which changes every time it rotates. This is the single most common mistake on this question type.
  • Walking into a wall or off the grid ends the program. The robot does not stop politely and carry on to the next line — it stays put and everything after that never runs.
  • ROTATE does not move the robot. It turns in place and costs no squares. Students lose squares to this on almost every trace.

REPEAT UNTIL runs while its condition is false — it is the opposite way round from while, which Activity 1.17 covered. Problem 3 turns on exactly that.

The Problems

Problem 1 — trace

The robot starts in the bottom-left square of a 4 by 4 grid with every square open, facing up. Where does it end up, and which way is it facing?

Problem 1
MOVE_FORWARD()
MOVE_FORWARD()
ROTATE_RIGHT()
MOVE_FORWARD()

Problem 2 — trace

Same 4 by 4 grid, every square open. The robot starts in the bottom-left square facing right.

Problem 2
REPEAT 3 TIMES
{
  MOVE_FORWARD()
}
ROTATE_LEFT()
MOVE_FORWARD()
MOVE_FORWARD()

Then answer this: what would happen if the loop said REPEAT 4 TIMES instead? Be specific about what the robot does and what happens to the rest of the program.

Problem 3 — explain

The robot is somewhere on a grid, facing an unknown direction, with walls in unknown places. Explain in two or three sentences what this program does.

Problem 3
REPEAT UNTIL(CAN_MOVE(forward))
{
  ROTATE_RIGHT()
}
MOVE_FORWARD()

Then answer this: describe a situation in which this program never finishes.

Submit

Your three answers. For Problems 1 and 2, give the robot's final square and the direction it faces.

Show your working for the traces. A wrong answer with visible reasoning is worth more to both of us than a right one with none — and on the exam, a drawn grid is the difference between these questions being easy and being a coin flip.

Commence Challenge