grid dictionary

Storing coordinate based grids, planes, maps or levels inside a Python dictionary has a few benefits (and a few negative tradeoffs) compared to lists of lists.

Benefit 1: neighbour check

For example, if we have a grid of

1 4 9
2 3 7
8 5 6

we could store it as

[
 [1,4,9],
 [2,3,7],
 [8,5,6]
]

but if we ever need to check any neighbouring cells, we need to manually make sure we don’t cross any index boundaries. For example, in (0, 0), we need to remember to check that a neighbour at (-1, 0) cannot be accessed.

If we instead store this as a dictionary with (x, y) keys:

{
 (0, 0): 1,
 (1, 0): 4,
 (2, 0): 9,
 (0, 1): 2,
 (1, 1): 3,
 (2, 1): 7,
 (0, 2): 8,
 (1, 2): 5,
 (2, 2): 6
}

we can always access any index, regardless of it doesn’t exist:

grid.get((-1, 0)) # None

and if there’s a default value that’s not None, we can define that as well:

grid.get((-1, 0), '#')

Benefit 2: sparse grids

Sometimes in Advent of Code puzzles, we don’t need to store the state of every coordinate. For example in the following:

X . . X
. . . X
X . . .
. . X .

where . is considered “empty”, we could only store the coordinates where there is an X and treat every missing coordinate as . when accessing them with .get() as above.

Downside: iterating over

One downside of a dictionary approach is if we need to do a lot of iterating over the individual cells, especially if we have a sparse grid.

We need to keep track of the smallest and largest x and y and do nested for loops:

for y in range(min_y, max_y+1):
	for x in range(min_x, max_x+1):
	  do_something_with(grid[y][x])

It’s also very easy to make one-off errors with this. Ask me how I know.

If we have a full grid with coordinates filled in right order we can usually loop over the keys:

for (x, y), value in grid.items():
  do_something_else_with(x, y, value)