When helping elves, you should use complex numbers to navigate in 2D

I'm hugely grateful to 4HbQ for sharing their solutions and python tricks in r/adventofcode! They're the inspiration for this post.

The first time I saw someone use complex numbers of navigate in two dimensions, I was horrified. Why would someone want to use x + y * 1j rather than x and y to represent a point in space? It seemed like a technique that was only useful if you were trying to solve a problem in the fewest number of characters, even at the cost of readability. After using complex numbers to solve problems in two dimensions and admiring 4HbQ's Advent of Code solutions, I've completely changed my mind: navigating 2d space with complex numbers leads to code that is both simpler and more readable.

The normal way that people represent 2d space is with a list of lists, with the outer list representing the y axis and the inner list representing the x axis.

# maze adapted from an example from https://adventofcode.com/2024/day/20
maze = [[r for r in row] for row in """
.......#....E
.#.###.#.###.
.....#.#...#.
.###.#####.#.
.#.#.......#.
.#.#####.###.
...........#.
##.#.#####.#.
...#.....#.#.
.#.#.###.#.#.
.....#...#.#.
.###.#.#.#.#.
S..#.....#...
""".strip().splitlines()]

You immediately run into two annoyances with this representation. First, you need to worry about bounds checking. You can't blindly reference maze[y][x] because that might not be in bounds. Instead, you need to check if y >= 0 and y < len(maze) and x >= 0 and x < len(maze[0]) before checking the value at maze[y][x].^[1] Second, referencing a point requires accessing points with y and then x, which is exactly opposite the standard x,y notation^[2] that people get used to in school.^[3]

If you use complex numbers, you can't use a list, so you immediately avoid the problem of bounds checking. If you're using a dictionary, you can simply check if a point is in the dictionary (if point in maze:). Or if you're using a defaultdict, you can set a reasonable default value for anything that is out of bounds. Similarly, there's no confusion about the order of x and y because there's only a point.

maze = defaultdict(lambda: '#')
for r, row in enumerate(maze_string.splitlines()):
    for c, char in enumerate(row):
        maze[r * 1j + c] = char

You can, of course, use (x, y) tuples in a dictionary rather than a list to represent 2-dimensional space, and that will have similar benefits: you won't need to worry about bounds-checking and you can order your tuples in the (x, y) order.

But once you start trying to navigate around two dimensional space with a list of lists, you run into another small annoyance: you need to repeat the exact same code for both x and y. Checking bounds? You'll need to check for both x and y. Moving? You'll need to add dx to x and dy to y. You can simply add two complex numbers to together to get a new point. Compare the following pieces of code:

# maze is a list of lists
x, y = points.pop()
for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
    xx = x + dx
    yy = y + dy
    if yy < 0 or yy >= len(maze) or xx < 0 or xx >= len(maze[0]):
        continue
    if maze[yy][xx] == "#":
        continue
    ...

# maze is a defaultdict(lambda: "#") of complex numbers
p = points.pop()
for d in (1, -1, 1j, -1j):
    if maze[p + d] == "#":
        continue
    ...

While it's not a huge difference, I've mistyped y + dy as y + dx or x < len(maze) many times. Extra lines of code are extra opportunities to make mistakes, and having both x and y doubles the number of lines of code you need to get right.

Aside from making it easy to add together points, one other nice property of complex numbers is that you can rotate them clockwise by multiplying them by 1j and counter-clockwise by multiplying them by -1j. I find dir *= 1j a whole lot easier to write than needing to write out all of the transformations:

clockwise_rotations = {
    (0, -1): (1, 0), # up to right
    (1, 0): (0, 1), # right to down
    (0, 1): (-1, 0), # down to left
    (-1, 0): (0, -1), # left to up
}
dir = clockwise_rotations[dir]

Rotating with multiplication is so much easier that even in situations where I'm using tuples to represent dx, dy, I'd still be tempted to rotate them by converting them to complex numbers first:

dx, dy = dir
clockwise_rotated = complex(*dir) * 1j
dir = clockwise_rotated.real, clockwise_rotated.imag

At this point, you might be screaming at me about python libraries that represent points as vectors that let you do everything that I've just described in more than just two dimensions. If you're comfortable with those libraries, using them is probably simpler than using complex numbers! But one small benefit to complex numbers is that they're part of the standard library, so they'll always be available, even in a leetcode-esque coding challenge.^[4]

But all of this is skipping the most important reason to use complex numbers: they're fun! I like writing code that's terse and overly clever. I find using complex numbers for 2d navigation to be more enjoyable than using tuples, and that's important! Clever code is terrible to maintain in a production system, but I'm writing code to solve silly Advent of Code problems, and complex numbers lend themselves to terse, fun-to-write code.

Code Comparison

Let's compare solutions to a simple 2D navigation problem: finding the length of the shortest path through a maze. We can start with a "standard" way of solving this solution: creating a two dimensional array and using Djikstra's algorithm:

import heapq

maze_string = """.......#....E
.#.###.#.###.
.....#.#...#.
.###.#####.#.
.#.#.......#.
.#.#####.###.
...........#.
##.#.#####.#.
...#.....#.#.
.#.#.###.#.#.
.....#...#.#.
.###.#.#.#.#.
S..#.....#..."""

def dist_to_end_of_maze(maze_string):
    maze = [[r for r in  row] for row in maze_string.splitlines()]
    dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
    # iterating through every value in the maze is slightly more painful
    end = next((y, x) for x, row in enumerate(maze) for y, char in enumerate(row) if char == "E")
    start = next((y, x) for x, row in enumerate(maze) for y, char in enumerate(row) if char == "S") 
    todo = [(0, start)]
    seen = set()
    while todo:
        steps, curr = heapq.heappop(todo)
        if curr == end:
            return steps
        y, x = curr
        for dx, dy in dirs:
            yy = y + dy
            xx = x + dx
            if yy < 0 or yy >= len(maze) or xx < 0 or xx >= len(maze[yy]): 
                continue
            if maze[yy][xx] == "#":
                continue
            if (yy, xx) in seen:
                continue
            seen.add((yy, xx))
            heapq.heappush(todo, (steps + 1, (yy, xx)))

print(dist_to_end_of_maze(maze_string))

This isn't a terrible solution! On the whole, it feels pretty readable and straightforward.^[5] But let's compare this against a solution that uses a defaultdict and complex numbers:

import heapq
from collections import defaultdict

def dist_to_end_of_maze (maze_string):
    maze = defaultdict(lambda: '#')
    for r, row in enumerate(maze_string.splitlines()):
        for c, char in enumerate(row):
            maze[r * 1j + c] = char
    dirs = (1, -1, 1j, -1j)
    goal = next(pos for pos, char in maze.items() if char == "E")
    start = next(pos for pos, char in maze.items() if char == "S")
    todo = [(0, 0, start)]
    seen = set()
    tiebreaker = 0 # having to use a tiebreaker is annoying, but heapq doesn't know how to compare complex numbers
    while todo:
        steps, _, curr = heapq.heappop(todo)
        if curr == goal:
            return steps
        for pos in (curr + d for d in dirs):
            if maze[pos] == "#" or pos in seen:
                continue
            seen.add(pos)
            tiebreaker += 1
            heapq.heappush(todo, (steps + 1, tiebreaker, pos))

Not needing to repeat logic for x and y, skipping bounds-checking, and not having y and x be backwards from their conventional order leads to a solution that I find a bit more understandable. If you haven't written code with complex numbers, it might look terrible to you! But give it a try, and you might find that you like it.

A few more code snippets

Rather than setting up your defaultdict with two for loops, you can construct the data structure by starting with a defaultdict and then using | with a list comprehension: maze = defaultdict(lambda: '#') | { r * 1j + c: char for r, row in enumerate(maze_string.splitlines()) for c, char in enumerate(row) }
Want to move diagonally too? dirs = (dr * 1j + dc for dr in (-1, 0, 1) for dc in (-1, 0, 1) if dr or dc)
I mentioned this in the code example above, but heapq will choke if it ever tries to compare complex numbers. You can work around that by either providing a random number as the second parameter or incrementing a tiebreaker property: heapq.heappush(points, (steps + 1, random.random(), pos + d))

If you need to check bounds, I prefer using range rather than < and >=: if y in range(len(maze)) and x in range(len(maze[y])) reads more clearly to me than if y >= 0 and y < len(maze) and x >= 0 and x < len(maze[y]). ↩︎
When I use a list of lists to represent two dimensions, I use r and c to refer to the indexes of rows and columns so that I don't confuse myself with the order of y and x. ↩︎
If you want to use [x][y] access, you can transpose the array: maze = [*zip(*maze)]. It does mean you need to iterate carefully if you want to print the maze in its original orientation. ↩︎
For most engineering jobs, there's no reason to ever write code that navigates in two dimensions, but that doesn't stop anyone from asking code challenge questions about it! (And if you do need to navigate in two dimensions for your job, you should completely ignore everything I've written here!) ↩︎
When I wrote this solution, I had one slightly hard-to-track down bug because I used y in one spot where I should have used yy. Take a look at that code again: if I had misordered x and y somewhere, how easy would it be to notice? ↩︎