<div class="notebook"> <div class="nb-cell markdown" name="md6"> # Advent of Code Day 7 </div> <div class="nb-cell markdown" name="md7"> ### Part 1 </div> <div class="nb-cell markdown" name="md1"> We take a slightly more space efficient approach than what we described in the blog post. We first translate the rules from the challenge problem directly, using a list of bags to record the nesting under each bag. Bags that appear multiple times according to the rules also appear multiple times in the list. </div> <div class="nb-cell program" data-background="true" name="p1"> in(light_red, [bright_white, muted_yellow, muted_yellow]). in(dark_orange, [bright_white, bright_white, bright_white, muted_yellow, muted_yellow, muted_yellow, muted_yellow]). in(bright_white, [shiny_gold]). in(muted_yellow, [shiny_gold,shiny_gold, faded_blue,faded_blue,faded_blue, faded_blue,faded_blue,faded_blue, faded_blue,faded_blue,faded_blue]). in(shiny_gold, [dark_olive, vibrant_plum, vibrant_plum]). in(dark_olive, [faded_blue, faded_blue, faded_blue, dotted_black, dotted_black, dotted_black, dotted_black]). in(vibrant_plum, [faded_blue, faded_blue, faded_blue, faded_blue, faded_blue, dotted_black, dotted_black, dotted_black, dotted_black, dotted_black, dotted_black]). in(faded_blue, []). in(dotted_black, []). </div> <div class="nb-cell markdown" name="md2"> Then we define color_in using this "in" predicate. </div> <div class="nb-cell program" data-background="true" name="p2"> bag_in(X,Y) :- in(X,Z), member(Y,Z). </div> <div class="nb-cell markdown" name="md3"> Finally we can define the transitive version of color_in and ask the system to use "tabling", which is essentially memoization / caching. </div> <div class="nb-cell program" data-background="true" name="p3"> :- table transitive_in/2. transitive_in(X,Y) :- bag_in(X,Y). transitive_in(X,Y) :- bag_in(X,Z), transitive_in(Z,Y). </div> <div class="nb-cell markdown" name="md4"> Finally, let's ask which bags (eventually) contain a shiny gold bag. </div> <div class="nb-cell query" name="q1"> findall(X,transitive_in(X,shiny_gold),Solutions). </div> <div class="nb-cell markdown" name="md5"> And we can also easily return the count. </div> <div class="nb-cell query" name="q2"> findall(X,transitive_in(X,shiny_gold),Solutions), length(Solutions, Len). </div> <div class="nb-cell markdown" name="md8"> ### Part 2 Day 2 asks us to return a count of all the bag that are nested inside a shiny gold bag. Our solution will proceed one "level" at a time, creating an inventory of what bags we have seen. We will add each bag to the inventory as we pull it out of the bag it is contained in. </div> <div class="nb-cell markdown" name="md9"> We start with a predicate `expand(BagList,BagListContents)` that holds when the bag list `BagList` contains the bags in `BagListContents` (another list of bags). </div> <div class="nb-cell program" data-background="true" name="p4"> expand([],[]). expand(BagList,BagListContents) :- BagList = [Bag|RestOfBagList], expand(RestOfBagList,RestOfBagListContents), in(Bag,BagContents), append(BagContents,RestOfBagListContents,BagListContents). </div> <div class="nb-cell markdown" name="md10"> Let's walk through this. If we have an empty list of bags, then it has an empty list of contents. The syntax `[Bag|RestOfBagList]` matches a list whose first element is `Bag` and where `RestOfBagList` contains everything except that first element (the "tail" of the list). So this is a recursive definition where we compute the contents of a bag list by computing the contents of the first bag in the list (line 5), computing the contents of the rest of the list (line 4), and combining them (line 6). </div> <div class="nb-cell markdown" name="md16"> Let's test it on a shiny gold bag. </div> <div class="nb-cell query" name="q6"> expand([shiny_gold],Contents). </div> <div class="nb-cell markdown" name="md11"> Now that we can expand one level, we just have to do this until we reach the end. However, we also want to keep a list of the bags we see as we do this expansion. We'll define a `tracing_transitive_expand` predicate that does this. The predicate `tracing_transitive_expand(X,Y,TRACE)` holds if, starting from bag list `X`, after some number of "unwrapping" steps we obtain bag list `Y`, and `TRACE` is a list of the bags we have "pulled out" of bags we opened. </div> <div class="nb-cell program" data-background="true" name="p5"> tracing_transitive_expand(X,[],[]) :- expand(X,[]). tracing_transitive_expand(X,Y,TRACE) :- expand(X,Z), tracing_transitive_expand(Z,Y,TRACE1), append(Z,TRACE1,TRACE). </div> <div class="nb-cell markdown" name="md12"> The first line is the base case, where we discover that none of the bags in `X` contain any other bags and so `Y` is empty and the trace is empty. The second definition looks at the first expansion step (line 3) to see what list of bags we obtain when we open the bags in `X` (we call this list `Z`). Then we check to see what trace we get when we expand `Z` (line 4). Finally, we ensure that the full trace (`TRACE`) contains the trace we get starting from `Z` (`TRACE1`) as well as the list of bags `Z` which were "pulled out of `X`" in this current round of expansion. Note that we do not add `X` to the trace. This means that when we ask how many bags are contained in a shiny gold bag (as the original problem asks us to do), we do not count that initial shiny gold bag -- only those bags nested inside it. As an additional exercise, you might try writing the version of `tracing_transitive_expand` that also counts the outermost bag(s). </div> <div class="nb-cell markdown" name="md15"> Let's test it! </div> <div class="nb-cell query" name="q4"> tracing_transitive_expand([shiny_gold],[],TRACE). </div> <div class="nb-cell markdown" name="md13"> #### Counting To countt the number of bags, we just need to compute the length of the list `TRACE`. This is different from the counting problem in Part 1, which required us to count the *number of solutions*. Here, there is only one solution and the question is about the size of that solution. </div> <div class="nb-cell program" data-background="true" name="p6"> size(X,Z) :- tracing_transitive_expand(X,[],TRACE), length(TRACE,Z). </div> <div class="nb-cell markdown" name="md14"> We compute the size by first finding the `TRACE` that corresponds to a full expansion of the list of bags `X` and then ensuring the `Z` is the length of that trace (line 3). </div> <div class="nb-cell query" name="q3"> size([shiny_gold],Z). </div> <div class="nb-cell markdown" name="md17"> And we get the right answer! </div> <div class="nb-cell markdown" name="md18"> ### Finishing Up We've hand-coded the first example rules set from the Day 7 problem description. There's a second second in Part 2 that we could also translate by hand to test our code. To solve the full problem for a real input, which has hundreds of rules, we need to programmatically translate the input into Prolog. I have code for that up on this [GitHub repo](https://github.com/smagill/aoc2020). </div> </div>