Complex numbers for planar geometry

2020-12-12, Comments

Once again, I’m enjoying solving Eric Wastl’s excellent Advent of Code puzzles.

Today, day 12 involved a ship navigating in a 2D plane. The ship follows a series of instructions taking the form of actions and values such as F10 N3 F7 R90 F11 ..., where, for the first part:

  • actions N, S, E, W step by the value in the compass directions N, S, E, W
  • actions L, R turn the ship left and right by the number of degrees specified by the value
  • action F advances the ship in the direction it faces by the given value

Perhaps the most obvious way to model this is by implementing a Point class, with x and y values, and suitable methods to advance and rotate.

Another way is to use complex numbers, which are natively supported by Python — and many other languages. The complex plane is a 2D plane. The point (x, y) is represented by a single complex number p = x + y * j. Stepping in any direction corresponds to addition, and rotation to multiplication.

So, the instructions N, S, E, W map to adding complex numbers j, -j, 1, -1.

Quarter turns left and right map to multiplication by j and -j.

def ship_position(instructions):
    '''Return the final position of the ship after following the instructions

    Instructions are a series of (action, value) pairs.
    ship, direction = 0, 1 # Start at the origin facing E
    step = {'N':1j, 'W':-1, 'S':-1j, 'E': 1}
    turn = {'R':-1j, 'L':1j}
    for action, value in instructions:
        if action in 'NSEW':
            ship += value * step[action]
        elif action in 'LR':
            assert value % 90 == 0 # check rectilinear motion
            direction *= turn[action] ** (value//90)
            assert action == 'F'
            ship += value * direction
    return ship

It’s also possible to implement the conditionals above arithmetically. We can think of each instruction advancing the ship (possibly by zero) and turning it (possibly by zero degrees).

def ship_position(instructions):
    ship, direction = 0, 1
    step = {'N':1j, 'W':-1, 'S':-1j, 'E': 1}
    turn = {'R':-1j, 'L':1j}
    for action, value in instructions:
        ship += value * (step.get(action, 0) + (action=='F') * direction)
        direction *= turn.get(action, 1) ** (value//90)
    return ship

More solutions here, and thanks again to Eric Wastl.