A simple "turtle"

A simple "turtle'' virtual robot lives on an infinite two-dimensional plane on which its location is always an integer pair of $(x,y)$ co-ordinates. It can face only in directions parallel to the $x$ and $y$ axes (i.e. 'North', 'East', 'South' or 'West') and it understands four commands:

  • F: move forward one unit;
  • L: turn left (anti-clockwise) by $90^\circ$;
  • R: turn right (clockwise) by $90^\circ$;
  • S: stop and exit.

The following Python program takes a list of such commands as a string and tracks the turtle's location. The turtle starts at $(0,0)$, facing in the direction $(1,0)$ ('East'). The program ignores (but warns about) invalid commands, and reports when the turtle crosses its own path.

commands = 'FFFFFLFFFLFFFFRRRFXFFFFFFS'

# Current location, current facing direction
x, y = 0, 0
dx, dy = 1, 0
# Keep track of the turtle's location in the list of tuples, locs
locs = [(0, 0)]

for cmd in commands:
    if cmd == 'S':
        # Stop command
        break
    if cmd == 'F':
        # Move forward in the current direction
        x += dx
        y += dy
        if (x, y) in locs:
            print('Path crosses itself at: ({}, {})'.format(x,y))
        locs.append((x,y))
        continue
    if cmd in 'LR':
        # Turn to the left (anti-clockwise) or right (clockwise)
        # L => (dx, dy): (1,0) -> (0, 1) -> (-1,0) -> (0,-1) -> (1,0)
        # R => (dx, dy): (1,0) -> (0,-1) -> (-1,0) -> (0, 1) -> (1,0)
        sgn = 1
        if dy != 0:
            sgn = -1
        if cmd == 'R':
            sgn = -sgn
        dx, dy = sgn * dy, sgn * dx
        continue
    # if we're here it's because we don't recognise the command: warn
    print('Unknown command:', cmd)
else:
    # We exhausted the commands without encountering an S for STOP
    print('Instructions ended without a STOP')

# Plot a path of asterisks
# First find the total range of x and y values encountered
x, y = zip(*locs)
xmin, xmax = min(x), max(x)
ymin, ymax = min(y), max(y)
# The grid size needed for the plot is (nx, ny)
nx = xmax - xmin + 1
ny = ymax - ymin + 1
# Reverse the y-axis so that it decreases *down* the screen
for iy in reversed(range(ny)):
    for ix in range(nx):
        if (ix+xmin, iy+ymin) in locs:
            print('*', end='')
        else:
            print(' ', end='')
    print()

Some notes:

  • We can iterate over the string commands to take its characters one at a time.

  • The else: clause to the for loop is only executed if we do not break out of it on encountering a STOP command.

  • We unzip the list of tuples, locs, into separate sequences of the $x$ and $y$ coordinates with zip(*locs).

The output produced from the commands given is:

Unknown command: X
Path crosses itself at: (1, 0)
 *****
 *   *
 *   *
******
 *    
 *    
 *    
 *