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.

Find my solutions here: github.com/JesperDramsch/advent-of-code

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: G.add_edge((x, y), (x + 1, y)) if y < len(row) - 1 and data[x][y + 1] <= val + 1: G.add_edge((x, y), (x, y + 1)) # Backward if 0 < x and data[x - 1][y] <= val + 1: G.add_edge((x, y), (x - 1, y)) if 0 < y and data[x][y - 1] <= val + 1: G.add_edge((x, y), (x, y - 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`