Jesper Dramsch , , read in 4 minutes

Don't mistake paths for hills!

## What is Advent of Code?

In this little series, I want to write about the thought processes I have behind solving the puzzles presented in Advent of Code.

During the Advent of Code small coding puzzles are presented with varying levels of difficulty. They're always Christmas-themed text puzzles where you help elves out of some mess to save the holidays. The puzzles are deliberately ambiguous to not bias puzzlers into a certain solution, they always have an example input in the text to explain some details and an input file for each day that comes in the form of a text file you can download. The solution is a simple number or a string you enter, which is checked by the website automatically. After you finish part 1, part 2 unlocks, which is a variation on part 2. This can be a little twist on part 1 or a large twist that changes the problem formulation into a problem that would take brute force solutions to compute longer than the heat death of the universe would take.

These descriptions won't be a perfect narrative, but rather how I think about these problems and where I see different solutions. I apologise for the possibility of rambling!

## The example input

We have a big square with letters and an S and an E. I wonder if this is our maze!

```Sabqponm
abcryxxl
accszExk
acctuvwj
abdefghi
```

IT IS!

## The implementation

This is one of those old tricks, one that a lot of scientists who work with Dynamic Time Warping get wrong actually!

This is not an optimization problem. We don't have to use gradient descent here.

This is a path-finding problem, we want to use something like A* here!

I won't implement that myself. Yesterday took too much out of me, so instead I import the lovely `networkx` and build a graph!

First I figured I'd just need a normal graph.

Up is down, right?

Well... not exactly. We're happy sliding down any steepness of hill but will only go up a steepness of 1.

So `nx.DiGraph()` it is!

Wait how do I build this graph from letters?

I don't. I just applied `ord()` to each item and replace "S" and "E" with their height.

Then I can build the graph by traversing the map and checking for the steepness constraints!

```def build_graph(data):
G = nx.DiGraph()

for x, row in enumerate(data):
for y, val in enumerate(row):
# Forward
if x < len(data)-1 and data[x+1][y] <= val + 1:
if y < len(row)-1 and data[x][y+1] <= val + 1:
# Backward
if 0 < x and data[x-1][y] <= val + 1:
if 0 < y and data[x][y-1] <= val + 1:
return G
```

Pretty alright, I'd say!

## Part Deux

Oh fun!

So we can reuse the entirety of part 1 and simply check for all "a" on the map.

I made the easy mistake of checking them all, but of course there are basins that are completely disconnected.

Some `try` `except` later and I can simply return the minimum.

## Refactor

Well...

Every time I'm proud of a solution the solutions thread humbles me:

```def build_graph(data):
"""Build graph from 2D structure

Parameters
----------
data : List(List(int)
Data of map

Returns
-------
G : networkx.DiGraph
Directed graph of map
"""
# Build graph from 2 dimensional array
G = nx.grid_2d_graph(len(data), len(data[0]), create_using=nx.DiGraph)
# Remove edges that are not valid
G.remove_edges_from([(a, b) for a, b in G.edges if data[b[0]][b[1]] > data[a[0]][a[1]] + 1])
# Faster than building the graph from scratch
return G
```

Removing edges is faster it seems. Good to know for the future.

## Error Log

A few silly mistakes. Especially going for a non-directional graph first. But overall a good run!

• `wrong answer: 23` well... the hill climbing seemed easy. Now to find what I did wrong.
• `if 0 < x < len(data) and row - 1 <= data[x-1][y] <= row + 1: TypeError: unsupported operand type(s) for -: 'list' and 'int'` didn't think about where the actual value is...
• `day.data[E[1]][E[0]] = ord("z") IndexError: list index out of range` switched rows and columns and forgot this one.
• `import scipy as sp ModuleNotFoundError: No module named 'scipy'` for once it's not my error! The big data seems to need scipy for networkx.
• `raise nx.NetworkXNoPath(f"No path between {source} and {target}.") networkx.exception.NetworkXNoPath: No path between S and E.` Oh no... Ah. I need a directed graph.
• `raise nx.NetworkXNoPath(f"No path between {source} and {target}.") networkx.exception.NetworkXNoPath: No path between (0, 10) and (20, 120).` haha, yeah of course there are basins without connection to the peak.
• `except networkx.exception.NetworkXNoPath: NameError: name 'networkx' is not defined` ah just copied the exception but imported `networkx as nx`