Advent Of Code - Day 9

This one was an interesting one, and a step up from previous days. I used a BFS here and I have a fantastic link for the description, usage and appliance of BFS and others like A*. Pop over to Red Blog Games for all the good stuff. There are fantastic articles about all sorts of path finding and walking algorithms.

Day 9 - Part 1

We start off again with something easy. Basically, just walk through a map, and find lowest values in it compared to neighbors of a cell. Here, we get to know a thing called direction calculation. In Go I have a list of points for that which will come in handy in other situations. But first, let’s parse our input. This time, I actually have a neat little trick on Go to create a slice of numbers from a slice of string numbers:

	input := strings.Split(string(content), "\n")

	grid := make([][]int, 0)
	for _, i := range input {
		row := make([]int, 0)
		for _, v := range i {
			c := v - '0'
			row = append(row, int(c))
		}
		grid = append(grid, row)
	}

In Go, characters are runes and they can be used like numbers with the ascii representations. So if you subtract the ascii number 0 from the ascii value 1 you’ll get 1 as a value. Converting that to int gives you the number that you want. Neat.

With that out of the way, let’s find our lowest points.

	sum := 0
	// display(grid)
	for y := 0; y < len(grid); y++ {
		for x := 0; x < len(grid[y]); x++ {
			lowest := true
			for _, d := range directions {
				np := point{x: x + d.x, y: y + d.y}
				if np.x >= 0 && np.x < len(grid[y]) && np.y >= 0 && np.y < len(grid) {
					if grid[np.y][np.x] <= grid[y][x] {
						lowest = false
						break
					}
				}
			}
			if lowest {
				fmt.Println("lowest: ", grid[y][x])
				sum += grid[y][x] + 1
			}
		}
	}
	fmt.Println("sum: ", sum)

What is directions?

	directions = []point{
		{x: -1, y: 0},
		{x: 0, y: -1},
		{x: 1, y: 0},
		{x: 0, y: 1},
	}

What’s happening here is, instead of doing something like if x-1 < ... x-1... we save the up, down, left, right as directions which we add to the current coordinates. This could easily now be expanded with say x: -1, y: -1 which would be to upper left corner. This way we don’t have to add any new ifs. We loop through them and check the boundaries.

Then we just a min on all the points and sum them up. Done. Nice. Now, comes the bigger part.

Day 9 - Part 2

For this, we first have to understand what the heck is going on. Reading the text, we see some keywords like, lowest point and that they should converge to that point. And also the 9 is the limit and it’s not part of the whole thing. We also read on that it flows downward which makes us tempted to do this search from the other way around. But, we already have the point of origin. So let’s start from there and go outside.

What are we trying to do here exactly? We are trying to find paths which lead back to our lowest point. Our natural stopper will be the number 9 and the ends of the map. Also, we will search for higher numbers than ours. Just to recap. Start from lowest, and find paths with numbers that are higher than the previous number.

This is a BFS algorithm. And the linked blog will explain it better than I could. I really encourage you to take a look. It has great resources for these things.

I’m just going to show the Go equivalent.

	for _, p := range basins {
		sizes = append(sizes, calculateBasinSize(p, grid))
	}
	sort.Ints(sizes)
	l := len(sizes)
	fmt.Println("sum: ", sizes[l-1]*sizes[l-2]*sizes[l-3])

Calculate Basin is then the BFS:

func neighbors(p point, grid [][]int) []point {
	var result []point

	for _, d := range directions {
		np := point{x: p.x + d.x, y: p.y + d.y}
		if np.x >= 0 && np.x < len(grid[p.y]) && np.y >= 0 && np.y < len(grid) {
			if grid[np.y][np.x] > grid[p.y][p.x] && grid[np.y][np.x] != 9 {
				result = append(result, np)
			}
		}
	}

	return result
}

func calculateBasinSize(p point, grid [][]int) int {
	start := p
	seen := map[point]struct{}{
		start: {},
	}
	queue := []point{start}
	var current point
	for len(queue) > 0 {
		current, queue = queue[0], queue[1:]
		for _, next := range neighbors(current, grid) {
			if _, ok := seen[next]; !ok {
				queue = append(queue, next)
				seen[next] = struct{}{}
			}
		}
	}
	return len(seen)
}

The gist of this is the queue thing, finding neighbors based on the rules we have. Greater than us, and not 9. And then we return the number of seen points. Those will be the size of the basin.

And we are done. We do the calculation and hopefully we’ll have the right result.

Conclusion

Today we learned about BFS and later on about A* and various path finding algorithms which will come in handy later on.

The repository for all my solutions for AOC 2021 can be found here.

Thank you for reading!

Gergely.