Hill Climbing Algorithm

Advent of Code 2022 Day 12

Part 1

1. Plan: solve visually
2. Playing Where's Waldo with each letter
3. Shortest path to d then e
4. Drawing the spiral to z
5. Walking the spiral

Plan: solve visually

• I'm not skilled in writing traditional shortest-path algorithms, especially ones that use Dijkstra's algorithm - like A*
• I have been successful in recursively traversing a 2D grid as a half-baked alternative approach
• Perhaps that technique would work here
• But I first want to see if I could arrive at the correct answer using my eyes and careful analysis of my puzzle input

Playing Where's Waldo with each letter

Using Find in my browser on the input, I highlighted each letter:

How about going from end to start?

Hmm...I'm starting to notice some interesting things in the placement of letters:

• There will be no way to avoid moving in a spiral from d to z
• There are two sets of i, j, and k - one seems to create a wall around d, and the other is the one I'll need to use
• All letters from d to z - with the exceptions of ijk - appear in a single cluster
• There are so many cs!
• There is one column of bs
• There are tons of as, but I'll likely need to avoid all but the one I start on

Shortest path to d then e

• It seems there are two paths: one from above and one from below
• Drawing curvy lines makes the one from below feel shorter, especially since es start at the bottom of the ds

Drawing the spiral to z

I see now that I must traverse both sets of ijk.

Thus, the path will be these letters in order:

a b c d e f g h i j k i j k l m n o p q r s t u v w x y z

I'm fairly confident in the shape of my path and the letters that get me through it.

Now comes the hard part:

• Which specific instances of each letter in each set will get me from a to z in the fewest steps

Walking the spiral

• I took it nice and slow
• I counted everything twice

This is how it went:

Thankfully, that was the correct answer!

Part 2

Not too many options, thankfully

• Sure, there are a ton of as
• But because I need to move to a b, I can only pick from the as along the left edge
• And choosing any as higher than the starting one in Part 1 would be foolish
• So my options are just the as south of the starting one in Part 1
• Of those, it would be foolish to start from one that is any further south than a straight horizontal line from one of the cs before the path trends downward

Visually, the yellow-highlighted segment starts from the a that I believe heeds the shortest path:

I was right!

I did it!!

• I solved both parts!
• Using my eyes instead of a program!
• Which made this puzzle a lot more fun, actually!

I'm glad the grid of the puzzle was small enough to make it approachable for me.

And I enjoyed leveraging my browser's Find tool to inspect each letter.