In a lot of Advent of Code problems, you're asked to deal with 2-dimensional or 3-dimensional data sets. Some examples of this include:
- Cellular Automata problems: problems where each element changes based on its neighbors
- Image processing problems: problems where we need to compose an image from pixels
- Pathfinding problems: problems where we need to find a path across a 2-dimensional map
For any of these problems, you'd be forgiven for thinking that you'd need to set up a 2-dimensional datastructure -- a slice of slices in Go or a list of lists in Python. Here's what that would look like in Go. The function to2dSlice() takes in a slice of strings (like, say, your puzzle input)
func to2dSlice(input []string) [][]byte {
b := make([][]byte, len(input))
for i, s := range input {
b[i] = []byte(s)
}
return b
}This would return a slice of slices, and you'd be able to access the element in row j and column i like so:
b := to2dSlice(input)
n := b[j][i]This is how the same thing might look in Python:
def to2dList(input: list[str]) -> list[list[str]]:
result = []
for line in input:
l = []
for c in line:
l += c
result.append(l)
return resultThis is nice and all, but gets really annoying if you need to handle any of the following cases:
- A space that grows in two dimensions. Most cellular automata problems grow in both x and y dimensions every time step. In order to accomodate the growth, you'll have to copy data to a new datastructure, taking care to remap coordinates along the way.
- A problem that adds a degree of freedom. In at least a few Advent of Code problems, you'll go from 2D to 3D to even N dimensions. When this shift happens, your datastructure itself needs to change.
- A problem with neighbor analysis. These get particularly annoying, and they're a common feature in cellular automata problems. Writing the code to check for neighbors at the boundary of the space becomes tedious e.g. you don't want to check the left neighbor of cells on the left edge of the space. Sure you could just check for index errors, but do you have to?
Here's the thing -- just because you are thinking of the problem as a 2-D space doesn't mean the computer has to. Consider a paper map -- why is it called a map? Because it maps points in the real world onto points on a piece of paper. You might find that if you model your space like a map, things will get much easier.
Let's remind ourselves about maps, aka associative arrays. These handy-dandy datastructures store key-value pairs, where each key and value are pieces of data. What would happen if we used a map to represent our data. What would that look like?
Here's an example in Go. I'm taking advantage of the built-in image.Point type. Note the use of the image.Pt() convenience function to create a Point struct.
func toSpaceHash(input []string) map[image.Point]byte {
b := make(map[image.Point]byte)
for j, s := range input {
for i, c := range s {
b[image.Pt(i, j)] = byte(c)
}
}
return b
}Let's say we want to count how many neighbors each point on our space has. (Spoiler: this is something you often have to do in Advent of Code.) To simplify things, let's assume that a point containing a # is non-empty. We can take advantage of a little bit of vector math and quickly search thru our neighbors.
func countNeighbors(space map[image.Point]byte) map[image.Point]int {
result := make(map[image.Point]int, len(space))
neighbors := []image.Point{
image.Pt(1, 0), image.Pt(-1, 0), image.Pt(0, 1), image.Pt(0, -1),
}
for p := range space {
acc := 0
for _, n := range neighbors {
o := p.Add(n)
if space[o] == '#' {
acc++
}
}
result[p] = acc
}
return result
}Python developers might be surprised that we're not checking for existence of the key in the map prior to accessing it. That's because in Go, we take advantage of zero-value behavior. When a key isn't present in the map, we'll get the zero value for the value type.
In Python things work a little differently. We need to use hashable (aka immutable) data types as keys, so we'll use tuples.
def toSpaceHash(input: list[str]) -> dict[tuple[int, int], str]:
result: dict[tuple(int, int), str] = {}
i = 0
j = 0
for line in input:
i = 0
for c in line:
result[(i, j)] = c
i += 1
j += 1
return resultAnd the count neighbor functionality looks quite similar to the Go example, with the difference being that in Python we must check for presence of the key first.
def countNeighbors(space: dict[tuple[int, int], str]) -> dict[tuple[int, int], int]:
neighbors = [
(1, 0), (-1, 0), (0, -1), (0, 1),
]
def add(pt1, pt2):
return (pt1[0] + pt2[0], pt1[1] + pt2[1])
result: dict[tuple[int, int], int] = {}
for p in space:
acc = 0
for n in neighbors:
o = add(p, n)
if o not in space:
continue
if space[o] == "#":
acc += 1
result[p] = acc
return resultThis datastructure strategy doesn't have a formal name, but I've taken to calling it a "space hash" in my own source code, because it's a hashmap that represents a space.
Space hashes don't have to deal with a lot of the annoying problems that come from 2D arrays.
A space that grows in two dimensions. With a 2D array, by definition there can be no negative x or y coordinates. With a space hash (0, 0), (-100, -1900), and (90, 809) are all valid coordinates. There's no need to remap the space each time it grows.
A problem that adds a degree of freedom. If you go from a 2D coordinate system to a 3D coordinate system, your algorithm might not need to change much at all! Whether it's 2 dimensions, 3 dimensions, or more, the space hash will happily store your points.
A problem with neighbor analysis. As we showed above, it's pretty easy to store vectors pointing to neighbors from a given point and use vector addition to access them (if they exist). This results in code that's way easier to write than the chain of if statements you'd need otherwise.
One thing to note, however -- maps don't necessarily preserve insertion order. This is because maps can grow internally and get shuffled around in the rehashing process. If you're looking to traverse your space hash in a defined order, you'll want to keep track of minimum and maximum coordinate values and explicitly traverse the space. Here's what it might look like in Go:
func traverse(space map[image.Point]byte, callback func(image.Point, byte), min, max image.Point) {
for j := min.Y; j++; j <= max.Y {
for i := min.X; i++; i <= max.X {
p := image.Pt(i, j)
callback(p, space[p])
}
}
}The space hash has been a tremendously useful tool to me as I navigate Advent of Code. It provides a ton of flexibility in the coordinate system, can easily expand as the problem escalates in difficulty (and it often does), and it makes things like looking up neighbors a snap. Give it a try!