Advent of Code Day 7 (in Prolog!)

I’ve been addicted to Advent of Code recently. I didn’t start when the event started, but after enough discussion on the MuseDev Slack, I took a look and got sucked into this fun and well-designed event. The first 6 days are quick little puzzles that provide a nice but still “mentally active” break from other tasks. Day 7 got really interesting and let me revisit one of my favorite seldom-used technologies: Logic Programming (and Prolog!).

In this post I’ll walk through how to solve the Day 7 challenge with Prolog. You can follow along in this live notebook. I also have this GitHub repo which provides a full solution for the large inputs the challenge problem asks you to run on.

Day 7 Part 1

The description for Day 7 is here. It gives some rules for what bags must be contained in other bags and then asks how many different bags might eventually contain a shiny gold bag. It immediately brought back memories of grad school and the various languages researchers have created where backtracking proof search is central to the execution model. Graph problems, planning problems, inference — all of these can be represented as proof search problems, and a variety of “logic programming” languages have been created to make these problems easy to solve. We’re going to solve this one in Prolog. We’ll start by defining a binary relation “bag_in”:

bag_in(outer_bag, inner_bag) means that inner_bag is in outer_bag

If you’ve never used a system like Prolog, the syntax “bag_in(outer_bag, inner_bag)” probably looks like a function call that takes two arguments. But in Prolog there aren’t really functions as we normally think of them. Instead there are predicates, which are “statements of fact”. So “bag_in(outer_bag, inner_bag)” means that it is the case that inner_bag is inside outer_bag. It doesn’t express a computation like a function call would. Instead it expresses that a given relation is true. The Prolog interpreter’s job is to figure out what facts are true given some background facts that establish the “rules of the game”. Which is exactly what this Advent of Code problem is asking us to do. It defines a set of rules and then asks questions about what is implied by those rules.

So to see how to solve this problem with Prolog, let’s take a look at the first two example rules from the Advent of Code problem page:

light red bags contain 1 bright white bag, 2 muted yellow bags.

dark orange bags contain 3 bright white bags, 4 muted yellow bags.

These could be represented as:

bag_in(light_red, bright_white)

bag_in(light_red, muted_yellow)

bag_in(dark_orange, bright_white)

bag_in(dark_orange, muted_yellow)

Note that I’m ignoring the number of bags of each color as that is not relevant for this part of the problem.

Suppose we could answer the question “how many different bag colors X satisfy bag_in(X, shiny_gold)?” This would tell us how many bags directly contain a shiny gold bag. This is almost what the problem wants, except that it asks the transitive version of this question. How many bags eventually contain a shiny gold bag? Let’s write that predicate:

transitive_in(X, Y) holds if bag_in(X, Y) holds (this is the base case)

transitive_in(X, Y) holds if bag_in(X,Z) and transitive_in(Z,Y) for some Z (this is the “transitive” or “inductive” case)

So a bag is transitively in a bag if it is directly in the bag or if some other bag Z is directly in the bag and the bag we’re searching for is transitively in bag Z.

How do you compute a transitive closure? With the magic of Prolog, we don’t have to know. We’ll ask the system to produce solutions for us and it will do the leg work of expanding all these definitions and managing the search process.

findall(X,transitive_in(X,shiny_gold),Solutions).

This “query” will find all solutions to the question “for what values of X does “transitive_in(X,shiny_gold) hold?” and will set the variable “Solutions” to the list of solutions (i.e. possible values of X).

The query as written will return some duplicates, but we can eliminate those by asking the system to use “tabling”, which is essentially caching / memoization. This avoids recomputing already-discovered facts and gives us only unique solutions. See this live notebook for a full working example including the one-line query to return the solution to the Part 1 puzzle example, which asks for a count of the number of solutions.

Day 7 Part 2

Part 2 (which I can’t seem to link to directly) poses the following question:

How many individual bags are required inside your single shiny gold bag?

That is, if you open the shiny gold bag, take out all the bags inside, and then open those bags, and continue this process until you’re out of bags to open, how many bags do you have at the end (not counting the initial shiny gold bag). This question differs from the question in part 1 in two respects. First, it asks about what bags are inside the shiny gold bag instead of what bags the shiny gold bag might be contained in. Second, and more importantly, because of the way the rules are written, this “forward” problem of opening up bags doesn’t really involve proof search. The “backward” problem of wrapping a shiny gold bag in other bags had multiple solutions since there are multiple ways to wrap up a given bag. But there is only one valid list for the contents of a given bag. The solution for this part is still elegantly expressible as a Prolog program that reuses the infrastructure we built for Part 1 and that solution is described in the same notebook.

Note: If the rules for bags contained choices, for example “a shiny gold bag may either contain 2 bright plum bags or 3 muted orange bags” then there would be multiple solutions for the “forward” search problem and Part 2 would look more similar to Part 1 (we would want to compute something about the set of all solutions rather than just look at a particular solution).

Solving Day 7 For Real

The actual inputs that Advent of Code provides are much longer than the short rule lists in the examples. The real inputs contain hundreds of rules. That’s too many to translate by hand, so I wrote some Python code to generate the Prolog file for the real inputs. That’s available in this GitHub repo along with instructions on how to use it.