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 importednetworkx as nx