Hill Climbing Algorithm
Tags: adventofcode, algorithms, javascript, programming
Published: 2022-12-13 00:59:37

## [Advent of Code 2022 Day 12](https://adventofcode.com/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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/3sxnddpr4g587jwlir5e.gif)

How about going from end to start?

![Z through A highlighted](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/md8m6x051mwynl46qif5.gif)

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 `c`s!
- There is one column of `b`s
- There are tons of `a`s, 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 `e`s start at the bottom of the `d`s

![Getting from A to E](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/20n7zycydjy5ff004pdr.gif)

### Drawing the spiral to `z`
![From E to Z](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/bg25cr8oxwqnv0r48qvg.jpg)

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:
![Counting the steps](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/sy08j61lef5p60tzcyuq.jpg)

Thankfully, that was the correct answer!

## Part 2

### Not too many options, thankfully
- Sure, there are a ton of `a`s
- But because I need to move to a `b`, I can only pick from the `a`s along the left edge
- And choosing any `a`s higher than the starting one in Part 1 would be foolish
- So my options are just the `a`s 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 `c`s 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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/crlvvee0xyoulozbo24j.jpg)

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.