Jesper Dramsch , , read in 7 minutes

Ah yes, a story of failure and caching

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

Looks like we're traversing a graph again...

Valve AA has flow rate=0; tunnels lead to valves DD, II, BB
Valve BB has flow rate=13; tunnels lead to valves CC, AA
Valve CC has flow rate=2; tunnels lead to valves DD, BB
Valve DD has flow rate=20; tunnels lead to valves CC, AA, EE
Valve EE has flow rate=3; tunnels lead to valves FF, DD
Valve FF has flow rate=0; tunnels lead to valves EE, GG
Valve GG has flow rate=0; tunnels lead to valves FF, HH
Valve HH has flow rate=22; tunnel leads to valve GG
Valve II has flow rate=0; tunnels lead to valves AA, JJ
Valve JJ has flow rate=21; tunnel leads to valve II

The implementation

Sorting the tuple, despite adding a wholly new sorting operation, vastly speeds up the solution from 30 seconds to 5 seconds.

This is due to the cache-function caching inputs and output of the functions, and when the tuple is sorted every time, the same items will be cached properly.

max_steam = max(
    max_steam,
    current_steam
    + tunneling(
        valves, tuple(sorted(opened + (valve,))), valve=tunnel, minutes=minutes - steps
    ),
)

Such a small change...

Another really important change is to remove all flow rates that are 0 and find the shortest path between each valve with a non-zero flow rate.

def compress_valves(valves):
    # Find all valves with flow
    flow_valves = [valve.name for valve in valves.values() if valve.flow != 0]

    # find the shortest path between all valves with flow
    for v in flow_valves + ["AA"]:
        valves[v].neighbours = FrozenDict()
        for v2 in flow_valves:
            if v != v2:
                valves[v].neighbours[v2] = find_shortest_path(valves, v, v2)

    for v in flow_valves:
        if valves[v].flow == 0 and not v == "AA":
            valves.pop(v)

    return valves

This was difficult enough. Already and looking at the solutions thread, I was very confused how other Pythonistas managed to get timings in the five-second range.

Until I realised I can compress the graph, which reduced the recurrent calls and therefore different values to cache and the sorting of visited nodes to consolidate that cache.

This one was very much a cache-optimisation lesson...

@cache
def tunneling(valves, opened=(), valve="AA", minutes=30):
    if minutes <= 0:
        return 0

    if len(opened) == len(valves) - 1:
        return 0

    max_steam = 0
    minutes -= 1
    current_steam = 0

    if valve not in opened:
        current_steam = minutes * valves[valve].flow
        opened = tuple(sorted(opened + (valve,)))

    for tunnel, steps in valves[valve].neighbours.items():
        max_steam = max(
            max_steam,
            current_steam
            + tunneling(
                valves,
                opened,
                valve=tunnel,
                minutes=minutes - steps + (current_steam == 0),
            ),
        )

    return max_steam

Which walks through each other valve with non-zero flow and finds the maximum.

Part Dos

This one broke me. It is December 24th today and I finally managed to solve it.

I wrote a version that works with the example input but wouldn't run on the other output.

An important realisation here was that "you" and the elephant do not have to run in parallel.

@cache
def floptunneling(valves, opened=(), all_valves=("AA", "AA"), all_minutes=(26, 26)):
    eleflop = all_minutes[0] > all_minutes[1]

    minutes = all_minutes[eleflop]
    valve = all_valves[eleflop]

    if max(all_minutes) <= 0:
        return 0

    if len(opened) == len(valves) - 1:
        return 0

    if minutes <= 0:
        eleflop = not eleflop
        minutes = all_minutes[eleflop]
        valve = all_valves[eleflop]

    # print(all_valves, end="")
    max_steam = 0
    current_steam = 0
    minutes -= 1

    if valve not in opened:
        current_steam = minutes * valves[valve].flow
        opened = tuple(sorted(opened + (valve,)))

    for tunnel, steps in valves[valve].neighbours.items():
        new_minutes = minutes - steps + (current_steam == 0)
        if new_minutes < all_minutes[not eleflop]:
            all_minutes = (new_minutes, all_minutes[not eleflop])
            all_valves = (tunnel, all_valves[not eleflop])
        else:
            all_minutes = (all_minutes[not eleflop], new_minutes)
            all_valves = (all_valves[not eleflop], tunnel)
        # all_minutes = all_minutes[:eleflop] + (new_minutes,) + all_minutes[eleflop+1:]
        # all_valves = all_valves[:eleflop] + (tunnel,) + all_valves[eleflop+1:]
        max_steam = max(
            max_steam,
            current_steam
            + floptunneling(
                valves, opened, all_valves=all_valves, all_minutes=all_minutes
            ),
        )
    return max_steam

Again, this ran into caching problems. Having a tuple for the valves and minutes just exploded the number of items to cache.

There must be a way to solve this with the linear run.

And there is.

As always user /u/4HbQ has an absolutely bonkers solution and I worked through understanding that solution.

def search(t, u='AA', vs=frozenset(F), e=False):
    return max([F[v] * (t-D[u,v]-1) + search(t-D[u,v]-1, v, vs-{v}, e)
           for v in vs if D[u,v]<t] + [search(26, vs=vs) if e else 0])

print(search(30), search(26, e=True))

I had everything I needed and my original solution. I just overcomplicated it.

The mind trick here is to realise that you can have the elephant do its rounds at every stage of "you" walking around.

So this means I can change my code to accommodate the elephant running its rounds as follows:

@cache
def tunneling(valves, opened=(), valve="AA", minutes=30, ele=False):
    if minutes <= 0:
        return 0

    if len(opened) == len(valves) - 1:
        return 0

    # First let the elephant run thanks to the cache function
    max_steam = 0 if not ele else tunneling(valves, opened, valve="AA", minutes=26)
    minutes -= 1
    current_steam = 0

    if valve not in opened:
        current_steam = minutes * valves[valve].flow
        opened = tuple(sorted(opened + (valve,)))

    # Now test all the neighbouring valves
    for tunnel, steps in valves[valve].neighbours.items():
        max_steam = max(
            max_steam,
            current_steam
            + tunneling(
                valves,
                opened,
                valve=tunnel,
                minutes=minutes - steps + (current_steam == 0),
                ele=ele,
            ),
        )

    return max_steam

The line max_steam = 0 if not ele else tunneling(valves, opened, valve="AA", minutes=26) can be run efficiently because of the cache-function that saves all of the runs. Therefore once it walked through all combinations, it runs in O(1) due to the simple lookup.

Then we simply call tunneling with tunneling(day.data, minutes=26, ele=True) and get the elephant-aided output.

Error Log

It's December 24th when I finally solved this with heavy help from the solutions thread. I lost my mind on this and out of frustration I stopped adding errors here, especially when I got unconcentrated over the weekend. Sorry.

  • for tunnel in tunnels[valve]: TypeError: string indices must be integers, not 'str' replaced the wrong variable. That was silly.
  • self.name: str NameError: name 'self' is not defined tried to write dataclasses from memory
  • v.neighbours[v2.name] = find_shortest_path(valves, v.name, v2.name) TypeError: 'NoneType' object does not support item assignment Gotta initialize those values.
  • if min(minutes) <= 0: UnboundLocalError: cannot access local variable 'minutes' where it is not associated with a value forgot to rename the variable
  • all_minutes = (new_minutes,) + all_minutes[not eleflop] TypeError: can only concatenate tuple (not "int") to tuple forgot I changed to index instead of slice
  • ...

But here's the thing.

I found a solution that would work on a bigger machine and I was able to adapt my existing code to a solution that I understood.

This, to me is progress, because I genuinely understood what I'm doing rather than blindly copying a piece of code.

A victory after all. I hope I never have to do this again.