Chiton
Tags: adventofcode, programming, algorithms, computerscience
Published: 2022-01-25 17:46:30

## [Advent of Code Day 2021 Day 15](https://adventofcode.com/2021/day/15)

## Solve for X where...
`X = the lowest possible sum of all but the first item's 'risk level' in a path from the top-left to the bottom-right corners of a square area`

## The puzzle input is...
- A multi-line string

## It represents
- A 2D area of equal length and width: a square
- Each number is a `risk level` a.k.a. weight

## Keywords that hint at the type of algorithm
- Start
- Destination
- Find a path
- Lowest total

## I had no idea. But with keywords, I could Google.
- Shortest path between two points
- Graph theory
- Weighted graph
- Minimum Cost Path
- Minimum Path Sum
- Dijkstra and his super-famous algorithm
- The A* (A-star) variant algorithms

## Deceived by the example diagram...again!
The example grid features a deceptively convenient lowest-risk path: all moves are right or down.
```
1163751742     S
1381373672     |
2136511328     ------.
3694931569           \.
7463417111            |
1319128137            \.
1359912421             |
3125421639             |
1293138521             \.
2311944581              #
```

Had the example been something like the diagram below - [Offered by an astute and helpful reddit user](https://www.reddit.com/r/adventofcode/comments/rgqzt5/2021_day_15_solutions/hoyzfex/?utm_source=share&utm_medium=web2x&context=3) - I would have better understood immediately how difficult this puzzle is:
```
19111   S /-\
19191   | | |
11191   \_/ |
99991       |
99991       #
```

With my narrow view of the problem, I proceeded to study and attempt to reproduce a Minimum Cost Path algorithm.
- I discovered [this informative Youtube lecture](% youtube t1shZ8_s6jc %)
- I found several coded solutions
- One was in JavaScript, the language I best understand
- The solution was simple enough to digest and memorize
- I attempted to re-write it from scratch

### The algorithm works like this
```
For each row in the grid
  For each column in the row
    If it's the top-left cell, continue
    If it's the top row:
      Update the current cell's value to the sum of: the value in the cell to the left, and that of the current cell
    Else, if it's the first cell in the row:
      Update the current cell's value to the sum of: the value in the same column of the prior row, and that of current cell
    Else:
      Update the current cell's value to the sum of: the lesser of two values - that of the same column in the prior row, and that of the cell to the left in the same row, and that of the current cell

Return the updated value in the bottom-right cell
```

### Here's a fun visualization of how this algorithm works:
![Visualization of minimum cost path algorithm](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/28664pglsbq9z4qo6n98.gif)

## How the next few moments went
- Ran the algorithm on my puzzle input
- Saw the returned number
- Typed it in as the answer
- Did not get a gold star
- Started questioning everything

### It wasn't until much later that I discovered the hidden truth described earlier:
- The lowest-risk path may require going up and left along the path

### I browsed several solutions and noticed common traits about the code:
- Very long and complex
- Confusing and intimidating
- Not inviting of focused study

### I was encouraged to study pathfinding theory instead:
- [Pathfinding or pathing](https://en.wikipedia.org/wiki/Pathfinding)
- [Lengthy](https://www.algorithms-and-technologies.com/a_star/javascript) [write-ups](https://www.freecodecamp.org/news/dijkstras-shortest-path-algorithm-visual-introduction/) and [eloquent](https://eloquentjavascript.net/1st_edition/appendix2.html) [instructional texts](https://eloquentjavascript.net/07_robot.html)
- [A few](https://en.wikipedia.org/wiki/File:Astar_progress_animation.gif) [really cool](https://en.wikipedia.org/wiki/File:Astarpathfinding.gif) animations attempting to visualize A* algorithms
- [An interactive demo of the A* algorithm](https://bgrins.github.io/javascript-astar/demo/)
![Visualization of one A-star algorithm](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/38bgqfnyb9g2n36v6wsm.gif)

## Celebrating my accomplishments
- A basic understanding of Dijkstra's algorithm
- A full understanding and recreation of at least one implementation of a Minimum Cost Path algorithm
- Designing a visualization of that algorithm
- Discovering why my answer was wrong
- Recognizing that I was not prepared to spend the time required now to generate my puzzle input's correct answer - just for Part 1

## Saving for later
I'm not skilled enough to understand the computer science techniques needed to solve this puzzle
- Dijkstra's algorithm
- The A-star variant
- Binary heaps

Perhaps one day I will feel ready. Until then, onto the next puzzle!