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.

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