Grid Robot Algorithms: MOVE_FORWARD, ROTATE and CAN_MOVE

Beginner35 min3 exercises45 XP

Prerequisites

Python Functions: Define, Call, and Return Values Python While Loops: When For Loops Aren't Enough Python Lists: Create, Access, Modify, and Loop Through Lists Python Dictionaries: The Complete Guide with Real Examples

0/3 exercises

Many exam questions show a robot on a grid and ask which code segment gets it to a goal square, using four commands from the reference sheet: MOVE_FORWARD(), ROTATE_LEFT(), ROTATE_RIGHT() and CAN_MOVE(direction). The small Python robot on this page runs any path you write, so you can check a trace instead of guessing.

What can the robot do?

The robot always sits in one square and faces one of four ways. It understands four commands:

MOVE_FORWARD() moves the robot one square forward, in the direction it is facing.

ROTATE_LEFT() turns the robot 90 degrees counterclockwise, in place. It stays in the same square.

ROTATE_RIGHT() turns the robot 90 degrees clockwise, in place.

CAN_MOVE(direction) is true if the square one step away in that direction is open, and false otherwise. The direction is left, right, forward or backward, measured from the way the robot is facing. It only looks: the robot does not move.

One rule decides many questions: if the robot tries to move into a square that is not open, or off the edge of the grid, it stays where it is and the program terminates. Nothing after that line runs.

On the exam the grid is a picture: the robot is a triangle pointing the way it faces, blocked squares are shaded, and the goal square is marked. This page draws grids as text:

. is an open square and # is a blocked square.

G is the goal. Other letters, like A and B, are open squares with names.

^, >, v and < are the robot, pointing up, right, down or left on the page.

Which way is left for the robot?

Left and right belong to the robot, not to you. When the robot faces down the page, its left hand points to the right side of the page. A trick that helps: turn your paper so that you face the same way as the robot.

This table shows where each command points, for each way the robot can face:

Robot faces	After ROTATE_LEFT()	After ROTATE_RIGHT()	CAN_MOVE(left) checks	CAN_MOVE(backward) checks
up	left	right	the square to the left	the square below
right	up	down	the square above	the square to the left
down	right	left	the square to the right	the square above
left	down	up	the square below	the square to the right

Two facts save time: three left turns leave the robot facing the same way as one right turn, and two turns in the same direction make it face backward.

How does the Python robot work?

The robot is a dictionary that remembers the grid, its row, its column and the way it faces. The grid is a list of strings, one string per row. Row 0 is the top row and column 0 is the left edge. Each facing has a step: moving up subtracts 1 from the row, moving right adds 1 to the column, and so on.

Turning uses MOD. The four directions sit in a list in clockwise order, so a right turn moves one place along the list, and % 4 wraps from the last direction back to the first. A left turn is three right turns. Run the boxes on this page in order: each one uses the functions defined in the boxes above it.

The robot, part 1: where it is and how it turns

DIRECTIONS = ["up", "right", "down", "left"] # clockwise order

STEPS = {"up": (-1, 0), "right": (0, 1), "down": (1, 0), "left": (0, -1)}

robot = {"grid": [], "row": 0, "col": 0, "facing": "up"}

def place(grid, row, col, facing):

robot.update(grid=grid, row=row, col=col, facing=facing)

def turned(quarter_turns):

"""Where the robot would face after this many clockwise quarter turns."""

position = DIRECTIONS.index(robot["facing"])

return DIRECTIONS[(position + quarter_turns) % 4]

def rotate_right():

robot["facing"] = turned(1)

def rotate_left():

robot["facing"] = turned(3) # three right turns make one left turn

place(["..."], 0, 0, "up")

for turn in [rotate_left, rotate_left, rotate_right]:

turn()

print(f"After {turn.__name__}():", robot["facing"])

Output

After rotate_left(): left
After rotate_left(): down
After rotate_right(): left

Next, is_open checks that a square is inside the grid and not blocked, and can_move turns a direction relative to the robot (forward, right, backward, left) into a direction on the page, then checks the square there. show prints the grid with the robot drawn as an arrow.

The robot, part 2: looking around with CAN_MOVE

ARROWS = {"up": "^", "right": ">", "down": "v", "left": "<"}

def is_open(row, col):

grid = robot["grid"]

inside = 0 <= row < len(grid) and 0 <= col < len(grid[0])

return inside and grid[row][col] != "#"

def can_move(direction):

quarter_turns = {"forward": 0, "right": 1, "backward": 2, "left": 3}[direction]

d_row, d_col = STEPS[turned(quarter_turns)]

return is_open(robot["row"] + d_row, robot["col"] + d_col)

def show():

for r, line in enumerate(robot["grid"]):

cells = list(line)

if r == robot["row"]:

cells[robot["col"]] = ARROWS[robot["facing"]]

print(" ".join(cells))

place([".#.", "..#", "..."], 1, 1, "up")

show()

for direction in ["forward", "right", "backward", "left"]:

print(f"CAN_MOVE({direction}):", can_move(direction))

Output

. # .
. ^ #
. . .
CAN_MOVE(forward): False
CAN_MOVE(right): False
CAN_MOVE(backward): True
CAN_MOVE(left): True

The robot faces up, so its forward square is the blocked one above it, its right is the blocked square to its right on the page, and its left and backward squares are open.

How do you trace a path?

Here is a short program for the robot below. It starts in the bottom-left corner, facing right, and the goal is in the top-right corner:

. . . . G
. # # . .
> . . . .

Pseudocode: a path to the goal

Run it

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

To trace it, write down the square (row, column) and the facing after each command:

Step	Command	Square (row, column)	Facing
start	none	(2, 0)	right
1 to 3	MOVE_FORWARD() three times	(2, 3)	right
4	ROTATE_LEFT()	(2, 3)	up
5 and 6	MOVE_FORWARD() twice	(0, 3)	up
7	ROTATE_RIGHT()	(0, 3)	right
8	MOVE_FORWARD()	(0, 4), the goal	right

Now let the Python robot run the same path. move_forward raises an error if the square ahead is blocked, which stops the program like the reference sheet's robot. REPEAT n TIMES becomes a for loop with range(n):

The robot, part 3: moving and running a path

def move_forward():

if not can_move("forward"):

raise RuntimeError("Blocked: the robot stays put and the program terminates.")

d_row, d_col = STEPS[robot["facing"]]

robot["row"] += d_row

robot["col"] += d_col

course = [

"....G",

".##..",

".....",

]

place(course, 2, 0, "right")

show()

for _ in range(3):

move_forward()

rotate_left()

for _ in range(2):

move_forward()

rotate_right()

move_forward()

print()

show()

print("On the goal:", course[robot["row"]][robot["col"]] == "G")

Output

. . . . G
. # # . .
> . . . .

. . . . >
. # # . .
. . . . .
On the goal: True

How do loops shorten robot code?

Long straight runs are written with REPEAT n TIMES. When you do not know how far the robot must go, combine a loop with CAN_MOVE. This loop drives the robot forward until the square ahead is blocked or off the grid:

Pseudocode: drive until something is in the way

Run it

REPEAT UNTIL(NOT CAN_MOVE(forward))
{
  MOVE_FORWARD()
}

REPEAT UNTIL checks its condition before each pass. If the square ahead is already blocked, the body runs zero times, so this loop can never crash the robot into a wall. In Python, "repeat until the robot cannot move" is "while the robot can move":

Drive to the wall, turn, drive again

corridor = [

"......",

"#####.",

"#####G",

]

place(corridor, 0, 0, "right")

moves = 0

while can_move("forward"): # REPEAT UNTIL(NOT CAN_MOVE(forward))

move_forward()

moves += 1

rotate_right()

while can_move("forward"):

move_forward()

moves += 1

show()

print("Moves:", moves)

Output

. . . . . .
# # # # # .
# # # # # .
# # # # # v
Moves: 8

The same two loops would work on a corridor of any length. That is the power of building a path from CAN_MOVE instead of counting squares.

What happens when the robot is blocked?

A move into a blocked square, or off the grid, does not happen. The robot stays in its square and the program ends, so any commands after that line never run. Exam questions use this rule as a trap: a code segment that looks almost right can stop one square short.

The Python robot raises an error in that case. Below, try and except catch the error so the program can show where the robot stopped:

A blocked move ends the program

place(["..#.", "...."], 0, 0, "right")

move_forward()

try:

move_forward() # the square ahead is blocked

print("This line never runs")

except RuntimeError as problem:

print("Error:", problem)

show()

Output

Error: Blocked: the robot stays put and the program terminates.
. > # .
. . . .

Can an algorithm find its own way through a maze?

Finding a robot's path through a maze is one of the classic algorithms worth knowing, because new algorithms are often built on it. One well-known method is the right-hand rule: keep your right hand on the wall and walk. As robot commands: if the robot can move right, turn right and step; otherwise, if it can move forward, step; otherwise turn left.

Pseudocode: the right-hand rule

Run it

REPEAT UNTIL(GoalReached())
{
  IF(CAN_MOVE(right))
  {
    ROTATE_RIGHT()
    MOVE_FORWARD()
  }
  ELSE
  {
    IF(CAN_MOVE(forward))
    {
      MOVE_FORWARD()
    }
    ELSE
    {
      ROTATE_LEFT()
    }
  }
}

GoalReached() is not on the reference sheet. When a question needs a procedure like that, the question describes it. In Python it is a small function that checks for a G under the robot:

The right-hand rule in Python

def at_goal():

return robot["grid"][robot["row"]][robot["col"]] == "G"

maze = [

".#...",

".#.#.",

"...#G",

]

place(maze, 0, 0, "down")

steps = 0

while not at_goal() and steps < 50: # REPEAT UNTIL(GoalReached())

if can_move("right"):

rotate_right()

move_forward()

elif can_move("forward"):

move_forward()

else:

rotate_left()

steps += 1

show()

print("Reached the goal:", at_goal(), "after", steps, "passes of the loop")

Output

. # . . .
. # . # .
. . . # v
Reached the goal: True after 12 passes of the loop

The right-hand rule reaches the goal in many mazes, but not all. If a block of wall stands on its own in an open area, the robot can circle that block forever, which is why the Python loop also stops after 50 passes. Change the maze and run it again to test your own layouts.

Check your understanding

The robot is facing toward the bottom of the grid. It then runs ROTATE_LEFT() three times. Which way does it face now?

AToward the left side of the gridBToward the right side of the gridCToward the top of the gridDToward the bottom of the grid

The robot starts in the bottom-left square, facing right. Squares A to D are open. In which square is the robot after the code segment runs?

```

A . . . B

. # # . .

. . C # .

> . . . D

```

REPEAT 4 TIMES
{
  MOVE_FORWARD()
}
ROTATE_LEFT()
REPEAT 3 TIMES
{
  MOVE_FORWARD()
}

ASquare ABSquare BCSquare CDSquare D

Run this pseudocode

The robot starts facing toward the bottom of the grid. In which square is the robot when the code segment ends?

```

. . . . .

v # . A .

. . . . .

B . C D #

```

REPEAT UNTIL(NOT CAN_MOVE(forward))
{
  MOVE_FORWARD()
}
ROTATE_LEFT()
REPEAT UNTIL(NOT CAN_MOVE(forward))
{
  MOVE_FORWARD()
}

ASquare ABSquare BCSquare CDSquare D

Run this pseudocode

The robot starts in the bottom-left square, facing right. Which of the code segments move the robot to the goal square G? Select two answers.

```

. . . G

. # . .

> . . #

```

Select 2 answers.

Segment I
REPEAT 2 TIMES
{
  MOVE_FORWARD()
}
ROTATE_LEFT()
REPEAT 2 TIMES
{
  MOVE_FORWARD()
}
ROTATE_RIGHT()
MOVE_FORWARD()
 
Segment II
ROTATE_LEFT()
REPEAT 2 TIMES
{
  MOVE_FORWARD()
}
ROTATE_RIGHT()
REPEAT 3 TIMES
{
  MOVE_FORWARD()
}
 
Segment III
MOVE_FORWARD()
ROTATE_LEFT()
REPEAT 2 TIMES
{
  MOVE_FORWARD()
}
ROTATE_RIGHT()
REPEAT 2 TIMES
{
  MOVE_FORWARD()
}
 
Segment IV
REPEAT 2 TIMES
{
  MOVE_FORWARD()
}
ROTATE_LEFT()
REPEAT 2 TIMES
{
  MOVE_FORWARD()
}
ROTATE_LEFT()
MOVE_FORWARD()

ASegment IBSegment IICSegment IIIDSegment IV

Run this pseudocode

The robot starts facing right. What happens when the code segment runs?

```

. A # B

> D C .

. # . .

```

MOVE_FORWARD()
ROTATE_LEFT()
MOVE_FORWARD()
ROTATE_RIGHT()
MOVE_FORWARD()
ROTATE_RIGHT()
MOVE_FORWARD()

AThe robot stays in square A, and the program terminates.BThe robot ends in square D, because the blocked move is skipped and the program continues.CThe robot ends in square B.DThe robot moves into the blocked square, and the program terminates.

Run this pseudocode

The robot is in the middle square, facing left. Which of the following expressions evaluate to true? Select two answers.

```

. # .

. < #

. . .

```

Select 2 answers.

ACAN_MOVE(forward)BCAN_MOVE(right)CCAN_MOVE(left)DCAN_MOVE(backward)

The robot starts in the bottom-left corner of an open 3 by 3 grid, facing up. Where is the robot after the code segment runs, and which way does it face?

```

. . .

^ . .

```

REPEAT 4 TIMES
{
  MOVE_FORWARD()
  ROTATE_RIGHT()
}

AIn its starting square, facing upBIn its starting square, facing rightCOne square above its starting square, facing upDDiagonally up and to the right of its start, facing left

Run this pseudocode

Practice exercises

Which Way Now?

Write Code

Write final_facing(start, turns). start is "up", "right", "down" or "left", and turns is a string of turns: "L" for ROTATE_LEFT() and "R" for ROTATE_RIGHT(). Return the way the robot faces after all the turns.

final_facing("up", "R")     ->  "right"
final_facing("up", "LL")    ->  "down"

DIRECTIONS = ["up", "right", "down", "left"] # clockwise order

def final_facing(start, turns):

# Walk along DIRECTIONS: +1 for a right turn, -1 for a left turn

pass

Is That Square Open?

Write Code

Write is_open(grid, row, col). grid is a list of strings, where "#" is a blocked square and anything else is open. Return True only if the square is inside the grid and not blocked. Squares off the edge count as not open.

is_open(["..#", "..."], 0, 2)   ->  False   (blocked)
is_open(["..#", "..."], 1, 2)   ->  True

Careful: in Python, grid[-1] does not raise an error. It quietly gives the last row.

def is_open(grid, row, col):

# Check that row and col are inside the grid before looking at the square

pass

Run a Robot Program

Write Code

Write run_program(grid, row, col, facing, commands). commands is a list of "F" (MOVE_FORWARD), "L" (ROTATE_LEFT) and "R" (ROTATE_RIGHT). Run them in order and return a tuple (row, col, facing) with where the robot ends.

Follow the reference sheet's rule: if an "F" would move into a "#" square or off the grid, the robot stays where it is and the program terminates. Return its position at that moment and ignore the remaining commands.

grid = ["....", ".#..", "...."]
run_program(grid, 2, 0, "right", ["F", "F", "L", "F", "F"])  ->  (0, 2, 'up')
run_program(grid, 2, 0, "up", ["F", "R", "F"])               ->  (1, 0, 'right')

DIRECTIONS = ["up", "right", "down", "left"] # clockwise order

STEPS = {"up": (-1, 0), "right": (0, 1), "down": (1, 0), "left": (0, -1)}

def run_program(grid, row, col, facing, commands):

# Return (row, col, facing) after the commands

pass

Exam topics: 3.9 Developing Algorithms (AAP-2.M). Robot questions also use 3.6 Conditionals (AAP-2.H) and 3.8 Iteration (AAP-2.K).

What can the robot do?

Which way is left for the robot?

How does the Python robot work?

How do you trace a path?

How do loops shorten robot code?

What happens when the robot is blocked?

Can an algorithm find its own way through a maze?

Check your understanding

Practice exercises

Related Tutorials