Advent Of Code - Day 15

Today, again, we open up Red Blob Games. It is a great source of information and descriptions. Especially, since this scenario is right up Red Blob’s ally. We need some weighted path finding. And Red Blob has a lovely post on that using the ever famous Dijkstra algorithm with a Priority Queue.

Day 15 - Part 1

Let’s get to it. After refreshing my memory about priority queues, I remembered that there is a package and some sample code in Go which implements priority queues using the container/heap package here.

Pretty straight forward. There are some bits that we don’t need. For example, the update function is not needed. And there is a single small thing which we really need to be aware of in this code base. This part:

func (pq PriorityQueue) Less(i, j int) bool {
	// We want Pop to give us the highest, not lowest, priority so we use greater than here.
	return pq[i].priority > pq[j].priority
}

This infuriating detail got me at least 20 minutes of trying to figure out why my path wasn’t correct. We need to change this to <.

Also, important detail is that you don’t use the priority queue directly. You use it with heap.Push(&pq). Otherwise the priorities and indexes will not be up to date.

Okay, first… We parse our grid using our trusty character cheat code:

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

Then we write our path finding. It’s a bit more verbose in Go than in Python of course. We have to initialize the PQ, then add in some code to get the neighbors, than set up the cameFrom part and traverse that backwards to get our full path. I’m sure there are better solutions out there than this, but this is what I feel comfortable with. And I saw many solutions using PQ.

The whole thing looks like this:

	start := point{x: 0, y: 0}
	goal := point{x: len(grid[0]) - 1, y: len(grid) - 1}
	pq := make(PriorityQueue, 0)
	heap.Init(&pq)
	heap.Push(&pq, &Item{
		point:    start,
		priority: grid[0][0],
	})
	cost := map[point]int{
		start: grid[0][0],
	}
	cameFrom := map[point]point{
		start: start,
	}
	for pq.Len() > 0 {
		current := heap.Pop(&pq).(*Item)

		if current.point == goal {
			break
		}
		for _, next := range neighbors(current.point, grid) {
			newCost := cost[current.point] + grid[next.y][next.x]
			if v, ok := cost[next]; !ok || newCost < v {
				cameFrom[next] = current.point
				cost[next] = newCost
				heap.Push(&pq, &Item{
					point:    next,
					priority: newCost,
				})
			}
		}
	}

Not that bad. And now, following the path back and calculating the sum.

	var sum int
	current := goal
	for current != start {
		sum += grid[current.y][current.x]
		current = cameFrom[current]
	}
	fmt.Println("sum: ", sum)

And that’s it. This is our correct number. Now, checking part 2…

Day 15 - Part 2

Part 2 is the same, but with a twist. We have to expand the grid by… what? Uh. So, our tile is just a piece of a greater tile. And as we duplicate our tile, we need to increase the numbers by one compared to their original part.

Okay, this takes a little bit to wrap my head around. So let’s remove some rules and make it easier. First, let’s deal with a simpler objective. Just copy our initial tile into a 5x5 grid. To do that, we create the initial grid with the size original y * 5 and original x * 5.

	expandedGrid := make([][]int, len(grid)*5)
	for i := 0; i < len(expandedGrid); i++ {
		expandedGrid[i] = make([]int, len(grid[0])*5)
	}

Done. Now, copy over the initial rows.

	// Prime the first tile
	for y := 0; y < len(grid); y++ {
		for x := 0; x < len(grid[y]); x++ {
			expandedGrid[y][x] = grid[y][x]
		}
	}

With this, actually we did create our 5x5 matrix, so let’s think a little bit about the problem. We take each number of the original grid, and +1-it compared to the previous number in the original grid. Let’s make this easy as the example has it. If the grid would be a single number, 8, we would get this grid:

If look at the pattern, all we have to do is create the first row correctly, and then we just +1 downwards on each column and we are golden(star (pun intended))! Nice. So, let’s create that first row.

	// fill out first line for all of the original grid sizes.
	for y := 0; y < len(grid); y++ {
		for x := len(grid[y]); x < len(expandedGrid[y]); x++ {
			// x - the length of the initial grid
			newValue := (expandedGrid[y][x-len(grid[y])] + 1) % 10
			if newValue == 0 {
				newValue = 1
			}
			expandedGrid[y][x] = newValue
		}
	}

Basically, the newValue := (expandedGrid[y][x-len(grid[y])] + 1) % 10 new value, is the original location, which is the current location minus the size of the original grid[y] and then +1. And it wraps around of course.

That’s fantastic. With that, we have our first row like this:

Now, we just have to go downwards with the same logic. Compared to the original location, minus the size, and +1.

	// fill out downwards
	for y := len(grid); y < len(expandedGrid); y++ {
		for x := 0; x < len(expandedGrid[y]); x++ {
			// x - the length of the initial grid
			newValue := (expandedGrid[y-len(grid)][x] + 1) % 10
			if newValue == 0 {
				newValue = 1
			}
			expandedGrid[y][x] = newValue
		}
	}

And done! We have our correct grid! We run the path finding, which didn’t change, and we have our correct result! Another star in the bag!

Conclusion

Today, we again learned that Red Blob Games is an invaluable resource of path finding information. And it’s nice to read through the material once in a while to refresh our knowledge about these things that exist. And we had some fun manipulating a matrix again and understanding that patterns will save our asses in these exercises.

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

Thank you for reading!

Gergely.

Advent Of Code - Day 15#

Day 15 - Part 1#

Day 15 - Part 2#

Conclusion#

Advent Of Code - Day 15

Day 15 - Part 1

Day 15 - Part 2

Conclusion