Problem 1 - Robot Vacuum

Summary

A robot is given a sequence of instructions, each of which moves a robot 1 space North, South, East or West on a 2D grid. What is the smallest number of instructions needed for the robot to get back to the start?

Solution

Suppose the robot only goes east and west. Then, the smallest number of instructions to go back must be the difference between the number of east and west instructions, since the number of east instructions should equal the number of west instructions if the robot wants to return to the start.

For example, the sequence EEWEWEWEEEW has 7 East instructions and 4 West instructions. Following these instructions, the robot end up 3 spaces east of where it started. This means that adding 3 West instructions should return it to the start.

We can do the same calculation for North and South instructions, since they follow the same rule. Adding these two answers together (since north/south and east/west don't affect each other) gives the answer.

Code

infile = open("robotin.txt", "r")
outfile = open("robotout.txt", "w")

# We don't actually need K here, only the second line instrs
K = infile.readline()
instrs = infile.readline()

# v: Number of spaces north of start (negative value for south)
v = 0
# h: Number of spaces east of start (negative value for west)
h = 0

for instr in instrs:
    if instr == 'N':
        v += 1
    if instr == 'S':
        v -= 1
    if instr == 'E':
        h += 1
    if instr == 'W':
        h -= 1

ans = abs(v)+abs(h)

outfile.write(str(ans) + "\n")

Click here to go back.