Kalanand's December 2016 Log

December 2nd

Walking in a 2d plane

We are given a set of walking instructions. Each instruction asks to make either left or right turn then walk a number of blocks. Our task is to figure out the final destination.

Let's say we start at (0, 0) and are given the following instructions: L1, R1, L2, R1, R2. We will first go left 1 to (-1, 0), then right one to (-1, 1), then left two to (-3, 1), then right 1 to (-3, 2) and finally right two to (-1, 2).

We can keep track of orientation using complex numbers. If we multiply a complex number by 'i' we get a rotation of 90 degrees in the counter-clockwise direction (i.e., turn left). Similarly, multiplying by '-i' we get a rotation of 90 degrees in the clockwise direction (i.e., turn right).

A quick implementation follows.

#!/usr/bin/env python

def complex_walk(path):
    splitStr = [x.strip() for x in path.split(",")]

    #Convert the steps into form [R, 1]...
    i = complex(0, 1)
    dirs = [[(i if x[0] is "L" else -i), int(x[1:])] for x in splitStr] 

    #Destination: start from the origin
    dest = complex(0, 0)

    #Multiply direction ('i' or '-i') to previous_position + translation 
    for dir in reversed(dirs):
        dest = dir[0]*(dir[1]*i + dest)

    #print the final position
    print path, "from (0, 0) = ", (int(dest.real), int(dest.imag))


complex_walk("L1, L2, R2")  ## should be (-3, -2)
complex_walk("L1, R1, L2, R1, R2") ## should be (-1, 2)

Go to November's log