DEV Community

Cover image for Hill Climbing Algorithm
Robert Mion
Robert Mion

Posted on

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:

A through Z highlighted

How about going from end to start?

Z through A highlighted

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

Getting from A to E

Drawing the spiral to z

From E 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
Enter fullscreen mode Exit fullscreen mode

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:
Counting the steps

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:
The shortest path starting at any a

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.

Oldest comments (0)