# 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) - 1, y: len(grid) - 1}
pq := make(PriorityQueue, 0)
heap.Init(&pq)
heap.Push(&pq, &Item{
point:    start,
priority: grid,
})
cost := map[point]int{
start: grid,
}
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)*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:

``````8 9 1 2 3
9 1 2 3 4
1 2 3 4 5
2 3 4 5 6
3 4 5 6 7
``````

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:

``````89123
00000
00000
00000
00000
``````

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.