# 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:

```
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.

Thank you for reading!

Gergely.