Part 1

We are searching for paths through a cave system, which can be described as a simple graph. Our paths must connect the start and end nodes, and they can contain some cycles; namely, “large caves” (nodes labeled with upper-case names). Specifically, we want to know the number of valid paths through the given cave.

This kind of puzzle is perfect for relational programming, but the specific information we’re required to find is an immediate obstacle to this approach. We can quickly sketch out a predicate path(A, B, Path) (to use a generalized logic programming notation) which succeeds if Path is a valid path from A to B, but we want to know how many times this relation succeeds for a given graph (cave system). This is “extra-logical”; presumably there’s some weird Prolog technique for dealing with this, but we’ll try a different approach.

(The embedded logic programming language miniKanren is nicely suited to this task, since it’s rather easy to pull a list of successes out of miniKanren into the host functional language. Here is a solver using this idea. Unfortunately, it is extremely slow.)

AOC 2021 Index