Module aoc::year2019::day18

source ·
Expand description

§Many-Worlds Interpretation

Our high level approach is to simplify the problem into graph path finding. We only ever need to move directly from key to key, so the maze becomes a graph where the nodes are keys and the edge weight is the distance between keys. Doors modify which edges are connected depending on the keys currently possessed.

We first find the distance betweeen every pair of keys then run Dijkstra’s algorithm to find the shortest path that visits every node in the graph. The maze is also constructed in such a way to make our life easier:

  • There is only ever one possible path to each key. We do not need to consider paths of different lengths that need different keys.
  • As a corollary, if key b lies between a and c then |ac| = |ab| + |bc|. This enables a huge optimization that we only need to consider immediate neighbours. If we do not possess key b then it never makes sense to skip from a to c since b is along the way. We can model this by treating keys the same as doors. This optimization sped up my solution by a factor of 30.

On top of this approach we apply some high level tricks to go faster:

  • We store previously seen pairs of (location, keys collected) to total distance in a map. If we are in the same location with the same keys but at a higher cost, then this situation can never be optimal so the solution can be discarded.
  • When finding the distance between every pair of keys, it’s faster to first only find the immediate neighbors of each key using a Breadth first search then run the Floyd-Warshall algorithm to contruct the rest of the graph. Even though the Floyd-Warshall asymptotic bound of O(n³) is higher than the asymptotic bounds of repeated BFS, this was twice as fast in practise for my input.

We also apply some low level tricks to go even faster:

  • The set of remaining keys needed is stored as bits in an u32. We can have at most 26 keys so this will always fit. For example needing a, b and e is represented as 10011.

  • Robot location is also stored the same way. Robots can only ever be in their initial location or at a key, so this gives a max of 26 + 4 = 30 locations. As a nice bonus this allows part one and part two to share the same code.

  • For fast lookup of distance between keys, the maze is stored as adjacency matrix. a is index 0, b is index 1 and robots’s initial positions are from 26 to 29 inclusive. For example (simplifying by moving robot from index 26 to 2):

        #########    [0 6 2]
    #b.A.@.a# => [6 0 4]
    #########    [2 4 0]

Structs§

  • Door 🔒
    distance in the edge weight between nodes. needed stores any doors in between as a bitfield.
  • Maze 🔒
    initial is the complete set of keys that we need to collect. Will always be binary 11111111111111111111111111 for the real input but fewer for sample data.
  • State 🔒
    position and remaining are both bitfields. For example a robot at key d that needs b and c would be stored as position = 1000 and remaining = 110.

Functions§