Chiton

Advent of Code Day 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 - 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
• 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:

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
• Lengthy write-ups and eloquent instructional texts
• A few really cool animations attempting to visualize A* algorithms
• An interactive demo of the A* algorithm

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!