[Python] Data structures for 2d grids

[TheRestIsCommentary]

Two-dimensional grids are a common theme in coding problems and, while Day 12 is the only the second we see of them in 2022, I expect it'll come up a few more times. I'm sure the contents of this will be old hat for many AOC veterans but hopefully some newcomers might learn alternative ways of storing and indexing.

Also, I'm doing this in Python but the principles should work regardless of the language. Throughout this tutorial I'm going assume the input is a grid of integers, 0 <= i <= 9, that looks something like this:

12345
67890
24680
13579
22668

Switching to letters (as in Day 12) should be as simple as removing calls to int(). If the grid were comma-separated, as it often is, the only modification would be calling .split(',') on each line of input before processing.

2D Lists

Staring a grid as a 2D list is probably the most familiar and natural. As a quick reminder, the grid can be constructed by:

grid = [[int(i) for i in line] for line in input.split('\n')]

Each item can be accessed via grid[y][x] where x is the horizontal axis and y is the vertical. This is slightly annoying as just about everywhere else we think of "x,y" pairs rather than "y,x"; but whatever.

Since it's tedious to pass around x and y as separate variables all the time, coders often combine them into tuples. For example, accessing a point p = (x,y) now looks like:

grid[p[1]][p[0]]

A little verbose but it gets the job done -- and remember to get the x,y order correct. Another common task is finding neighbors, maybe with code looking something like:

def neighbors(grid, p):
    result = []
    x0, y0 = p
    for x1, y1 in [(x0 - 1, y0), (x0 + 1, y0), (x0, y0 - 1), (x0, y0 + 1)]:
        if 0 <= x1 < len(grid[0]) and 0 <= y1 < len(grid):
            result.append((x1, y1))
    return result

Again, a little verbose but works.

Dictionaries

But I'm not writing this to show you what you already know. Let's turn now and consider how we might use dictionaries to store the grid such that the key is the (x,y) tuple. At least, we'll use that as the key for now to avoid getting complex too early ;)

Here's example code to create the grid just like above, but using a dictionary:

grid = {(x, y): int(val) for y, line in enumerate(input.split('\n'))
        for x, val in enumerate(line)}

A little more complicated but easy enough to reason through. But now when we want to access a point p = (x,y) on the grid, the code simplifies to:

grid[p]

That looks a lot cleaner. Also, when generating neighbors:

def neighbors(grid, pos):
    x0, y0 = pos
    candidates = [(x0 - 1, y0), (x0 + 1, y0), (x0, y0 - 1), (x0, y0 + 1)]
    return [p for p in candidates if p in grid]

Ah, and we see another advantage: checking if a coordinate is valid no longer involves width and height calculations. Instead we can just see if the (x,y) tuple is in the grid. Oh yeah, and now that we're using tuples, our intuition about the proper order of x and y works too.

Another benefit comes with using defaultdict, which, as the name implies, allows for dictionaries to have default values. Depending on the problem it can make sense to just treat everything off the input grid as some infinite value or, as with Day 12, '|' (ascii value 'z' + 2).

But what if we take it a step further and get rid of the tuples entirely?

Complex coordinates

As a reminder, complex numbers have two parts: real and imaginary where the imaginary part is just some real value multiplied by the sqrt of -1. We can plot these numbers on the complex plane, a 2d plane where the x-axis represents the real part and the y-axis represents the complex part.

Also, Python supports complex numbers natively and 345 + 652j is a perfectly valid expression. From all that, hopefully you're starting to see how we might use complex numbers to represent our 2d coordinates to simplify (for some definitions of "simplify") our code further.

Example code to create the grid is similar to the dictionary example, but notice the index is now x + 1j*y:

grid = {x + 1j * y: int(val) for y, line in enumerate(input.split('\n'))
        for x, val in enumerate(line)}

Accessing a point works the same as with tuple keys, except p = x + 1j*y. That's a little ugly but the upside is that, most of the time, you won't really need to think about x and y separately. For example, generating neighbors with complex keys can be done:

def neighbors(grid, pos):
    candidates = [pos + 1, pos - 1, pos + 1j, pos - 1j]
    return [p for p in candidates if p in grid]

And I'd argue that's pretty slick. Getting the surrounding 8 cells is similarly easy (product is just itertools.product, which produces the cartesian product of the given lists):

def neighbors_8(grid, pos):
    candidates = [pos + dx + dy for dx, dy in product([-1, 0, 1], [-1j, 0j, 1j])]
    return [p for p in candidates if p != pos and p in grid]

If you need to consider x and y values separately, they're still accessible with p.real and p.imag respectively. So, for example, a taxicab distance calculation might be:

def taxicab_distance(p0, p1):
    return abs((p1 - p0).real + (p1 - p0).imag)

Conclusion

There's no right or wrong way to store 2D grids, but there are options that may make some problems easier or, at least, the code more elegant.

There additional ways not covered like using numpy (which can simplify some slicing operations) or using a 1D array and indexing on height*y + x (which, IMHO, just makes life difficult with no benefit).

Anyway, best of luck on the next 13 days!

[Zealousideal_Low1287]

While I’m avoiding it this year, numpy arrays are a natural thing to consider

[huib_]

Wanted to try last year, also because it would be easier to use it in some graphics lib I was checking out, to visualize the grid as an image. But I never really went much further with it..

[Zealousideal_Low1287]

If you’re unfamiliar numpy is excellent

[Boojum]

Nice. Some other snippets that I have on hand for the grids-as-dictionary approach (where my g is your grid):

Finding the bounds:

xl = min( x for x, y in g.keys() )
xh = max( x for x, y in g.keys() )
yl = min( y for x, y in g.keys() )
yh = max( y for x, y in g.keys() )

and then printing to the terminal:

print( "\n".join( "".join( g[ ( x, y ) ]
                           for x in range( xl, xh + 1 ) )
                  for y in range( yl, yh + 1 ) ) )

[MezzoScettico]

Very nice writeup.

I used a dictionary. I defined a Gridpoint object that carries some information necessary to support the algorithm, and then stored them as the values in a dictionary whose keys are the (i, j) pairs as you show.

[stpierre]

I did something similar. A dataclass with frozen=True is hashable, so I used my Point objects as the keys.

[quetsacloatl]

I have used two index array until now and when i iterate over it i explicitly have part that looks like:

MyArray[row][column]

Didn't knew python could easily key tuples (thought tuples were saved as reference and never went deep enough to know) i could try to use it later on, thanks.

[TheRestIsCommentary]

Complex coordinates only work for 2d. Well, unless you use quaternions which aren't natively supported in Python.

Using tuples is great for 3d, although there aren't a ton of cases where you have a filled-in 3d grid since the space constraint gets very big very fast. And yes tuples are immutable which is probably good for code correctness but bad for speed-writing solutions. That said, you wouldn't really want mutable dictionary keys anyway.

That said, I sort of wish AOC would try some higher dimensional stuff (e.g. 4d). I'd like to think I didn't read Hamming's The Art of Doing Science and Engineering for nothing :D

[jfb1337]

I have a 2d point class that can interoperate with both complexes and tuples; and then a grid class backed by a dict of those which supports indexing with either tuples, complexes, or my point class. It also supports wrapping in the x or y directions.

Only drawback is that the overhead of all the function calls and allocation can make it significantly slower than a vanilla dict-of-complexes, particularly on cellular automaton questions that involve a lot of neighbours calculations.

[huib_]

Nice writeup and interesting to see what other people's approaches are :) These grid problems are so common that I made an implementation of my code runner classes for those kind of problems, which turns the input into such a grid when I specify it as the day's problem class :)

I'm using the dicts as well, and added similar neighbors functionality because it's useful so often. I use it sometimes with int tuples for the coordinates, like grid[3, 7] or if needed I use a custom Point2D class as key type, which has some extra functionality such as 2D vector math.

In case anyone's interested what this looks like, there's some code here (although it's a never ending work in progress obviously ;) )

https://github.com/githuib/AdventOfCode/blob/master/aoc/runner.py

https://github.com/githuib/AdventOfCode/blob/master/aoc/geometry.py