Created
November 29, 2023 06:43
Revisions
-
dishbreak created this gist
Nov 29, 2023 .There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1,163 @@ # The Space Hash 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 ## Why Two-Dimensional Arrays Fall Apart 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) ```go 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: ```go b := to2dSlice(input) n := b[j][i] ``` This is how the same thing might look in Python: ```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 result ``` This 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. ## Introducing the Space Hash 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. ```go 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. ```golang 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](https://go.dev/tour/basics/12). 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. ```python 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 result ``` And 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. ```python 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 result ``` This 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. ## Why Are Space Hashes Useful? 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](https://www.geeksforgeeks.org/load-factor-and-rehashing/). 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: ```golang 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]) } } } ``` ## Conclusion 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! This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1,46 @@ package main import ( "fmt" "image" ) 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 } 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 } func main() { input := []string{ "## # ##", " ### ", " ## # #", } space := toSpaceHash(input) fmt.Println(countNeighbors(space)) } This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1,62 @@ def to2dList(input: list[str]) -> list[list[str]]: result = [] for line in input: l = [] for c in line: l += c result.append(l) return result 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 result def countNeighbors(space: dict[tuple[int, int], str]) -> dict[tuple[int, int], str]: 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], str] = {} 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 result def main(): input = [ "## # ##", " ### ", " ## # #", ] r = to2dList(input) print(r) h = toSpaceHash(input) print(h) print(countNeighbors(h)) if __name__ == "__main__": main()