# Hill Climbing Algorithm

`2022-12-13`

Original Prompt ## Part 1

One of the best things that AoC does is provide practical awareness about classic CS algorithms. Today’s beneficiary is Dijkstra’s algorithm, one of the foremost shortest path algorithms. I’ve written about it at length in previous years, such as on 2021 day 15, so I’m going to be brief here. I recommend giving day 15 a skim, since it goes into great detail.

But, I don’t want to leave you empty handed, so here are the sparknotes.

Dijkstra is all about finding the shortest path across a graph. To implement, you need to track the following:

- points you’ve visited (the
`seen`

set) - the shortest distance you’ve found so far to a given point (a
`dict`

of`distances`

) - an always-sorted list of points you’ve seen (but not visited directly) along with
*a*distance you can reach them via (the`queue`

); initialized to`[(0, start)]`

Those in hand, you perform the following steps until the queue is empty or you’ve found your destination:

- pop the first point +
`distance`

pair from the queue - if that point is your destination, return
`distance`

- if you’ve visited that point before, skip
- add that point to
`visited`

- for each neighbor you can visit:
- if that neighbor is in
`visited`

, skip - calculate the distance it would take to reach the neighbor
- if the calculated distance is the shorter than the shortest path to the point so far, update the shortest distance and add the neighbor to the queue

- if that neighbor is in

If you’re a visual learner, here’s a great gif from Wikimedia:

That out of the way, let’s apply that to today’s problem. First, as always, input parsing!

```
GridPoint = tuple[int, int] # so useful, I actually have it in my base class
class Solution(StrSplitSolution): grid: List[List[str]] = []
def parse_grid(self) -> GridPoint: self.grid = [list(l) for l in self.input] for row, line in enumerate(self.input): if (col := line.find("S")) >= 0: return row, col raise ValueError("Unable to find start point")
```

Nothing too fancy, but we do have a chance to use the ”walrus operator”, which combines assignment with a conditional. Basically, it prevents us having to write:

`for row, line in enumerate(self.input): if line.find("S") >= 0: col = line.find("S") return row, col# or ... col = line.find("S") if col >= 0: return row, col`

Anyway, we parse our input into nested lists and return the location of our starting point. Next, we set up our variables as mentioned above:

```
from collections import defaultdict
...
class Solution(StrSplitSolution): ...
def part_1(self) -> int: start = self.parse_grid()
visited: set[GridPoint] = set() # thing to track #1 distances = defaultdict(lambda: 10_000) # thing to track #2 queue: list[tuple[int, GridPoint]] = [(0, start)] # thing to track #3
```

We’re using Python’s `defaultdict`

, a superbly useful data structure. Instead of ever throwing a `KeyError`

, it’ll instead call a function you provide. It’s most commonly used with a basic data type (as `defaultdict(int)`

, since `int()`

returns `0`

), but can be anything. We’re worried about finding minimum distances, so the default, unvisited distance should be bigger than we’re ever going to see. Given the size of our input grid (42x84), 10k seemed like plenty.

You’ll also notice that our priority queue is just a regular `list`

. Python’s built-in priority queue is a function that takes (and modifies) a list, so we don’t need to do anything fancy to initialize it.

Then, the algorithm itself, annotated with the numbered step from above:

```
from heapq import heappop, heappush...
class Solution(StrSplitSolution): ...
def part_1(self) -> int: ...
while queue: # 1 distance, current = heappop(queue) src = self.grid[current[0]][current[1]]
# 2 if src == "E": return distance
# 3 if current in visited: continue
# 4 visited.add(current)
# 5.2 new_distance = distance + 1
for n in neighbors( current, 4, ignore_negatives=True, max_x_size=num_rows, max_y_size=num_cols, ): # 5.1 if n in visited: continue
if not can_step(src, self.grid[n[0]][n[1]]): continue
# 5.3 if new_distance < distances[n]: distances[n] = new_distance heappush(queue, (new_distance, n))
return -1 # no path found
```

We can take a slight shortcut with step `5.2`

- because each step adds exactly 1 to the distance, we can pre-calculate that; usually Dijkstra’s is used on a graph with weighted edges (where the cost to visit each neighbor is variable).

I also used two functions that I hadn’t already defined because they didn’t make sense out of the context. One determines if we can move from a letter to another letter, based on the height rules:

```
def can_step(src: str, dst: str) -> bool: if dst == "E": dst = "z"
if src == "S": src = "a"
return ord(src) + 1 >= ord(dst)
```

The other gives a bunch of neighboring tuples based on a center point. It comes up enough in AoC that I’ve made a generic version of it:

```
from itertools import productfrom operator import itemgetter
DIRECTIONS = sorted(product((-1, 0, 1), repeat=2), key=itemgetter(1))
def neighbors( center: GridPoint, num_directions=8, *, ignore_negatives: bool = False, max_x_size: int = 0, max_y_size: int = 0,) -> Iterator[Tuple[int, int]]: """ given a point (2-tuple) it yields each neighboring point. Iterates from top left to bottom right, skipping any points as described below:
* `num_directions`: Can get cardinal directions (4), include diagonals (8), or include self (9) * `ignore_negatives`: skips points where either value is less than 0 * `max_DIM_size`: if specified, skips points where the dimension value is greater than the max grid size in that dimension. If doing a 2D-List based (aka `(row,col)` grid) rather than a pure `(x,y)` grid, the max values should be `len(DIM) - 1`.
For a 2D list-based grid, neighbors will come out in (row, col) format. """ assert num_directions in {4, 8, 9}
for dx, dy in DIRECTIONS: if num_directions == 4 and dx and dy: # diagonal; skip continue
if num_directions != 9 and not (dx or dy): # skip self continue
rx = center[0] + dx ry = center[1] + dy
if ignore_negatives and (rx < 0 or ry < 0): continue
if max_x_size and (rx > max_x_size): continue
if max_y_size and (ry > max_y_size): continue
yield (rx, ry)
```

Honestly, the fanciest part is `DIRECTIONS`

, which uses a couple of neat tricks to produce the following list:

`[(-1, -1), (0, -1), (1, -1), (-1, 0), (0, 0), (1, 0), (-1, 1), (0, 1), (1, 1)]`

Namely, it:

- uses
`itertools.product`

with the`repeat`

kwarg to get every pair of 2 numbers from`(-1, 0, 1)`

. - Then it sorts them using the 2nd item of each tuple (and not swapping if it doesn’t need to).
- This gives us offsets from top-left to bottom right, read left-to-right and top-to-bottom

Finally, you can see the `heappush`

and `heappop`

functions in action: they ensure the list is still sorted after each operation, an important feature for a priority queue.

That’ll do it! Great job implementing a classic today.

## Part 2

Like the other days, we need to put the bulk of our work into a function and call it with slightly smaller inputs. Our `part_1`

becomes `def _solve(self, start: GridPoint) -> int:`

and the call to `parse_grid`

is removed.

Next, we refactor `parse_grid`

to the following:

```
class Solution(StrSplitSolution): ...
def find_letters(self, letter: str): for row, line in enumerate(self.grid): for col, c in enumerate(line): if c == letter: yield row, col
```

This yields all the occurrences of a given letter (instead of manually finding `S`

). This lets us right a unified solve:

```
class Solution(StrSplitSolution): ...
def solve(self) -> tuple[int, int]: self.grid = [list(l) for l in self.input]
shortest_path_from_start = self._solve(next(self.find_letters("S")))
shortest_path = min( filter( lambda x: x >= 0, (self._solve(loc) for loc in self.find_letters("a")) ) )
return shortest_path_from_start, shortest_path
```

We’ve inlined our grid parsing, since there wasn’t much to it. We manually call `next`

once to get our starting position (which will error if one isn’t found) and then iterate like normal through all the `a`

‘s. We could have done a nested list comprehension instead of a call to `filter`

, but I find them less readable, so I went this way today instead.