Advent of Code: Day 7
Well, today was our streak breaker. For the life of me, I could not get Raku to run in a timely manner. I ended up reverting to Python and using a more imperative approach. Nevertheless, I am sharing it here for anyone who cares!
The Problem
Part 1
For the past few days, we have been traveling. First we had troubles at the airport, then we had trouble finding our seat, and then we had issues filling out the customs form. But, we have landed safely and are ready to enjoy our vacation!
However, our luggage is taking a long time getting to the carousel due to recent luggage rules that have been put into effect. We are given a list of the rules that looks like the following:
light red bags contain 1 bright white bag, 2 muted yellow bags.
dark orange bags contain 3 bright white bags, 4 muted yellow bags.
bright white bags contain 1 shiny gold bag.
muted yellow bags contain 2 shiny gold bags, 9 faded blue bags.
shiny gold bags contain 1 dark olive bag, 2 vibrant plum bags.
dark olive bags contain 3 faded blue bags, 4 dotted black bags.
vibrant plum bags contain 5 faded blue bags, 6 dotted black bags.
faded blue bags contain no other bags.
dotted black bags contain no other bags.
We have a shiny gold bag, and we want to know how many color combinations there are for the outermost bag. With the above example, we have:
- A bright white bag, which can hold our shiny gold bag directly
- A muted yellow bag, which can hold our shiny gold bag directly, plus some other bags
- A dark orange bag, which can hold bright white and muted yellow bags, either of which could then hold our shiny gold bag
- A light red bag, which can hold bright white and muted yellow bags, either of which could then hold our shiny gold bag
So the question is, given a much larger input file, how many outermost bags can eventually hold our shiny gold bag?
Solution
See below for explanation and any implementation-specific comments.
from dataclasses import dataclass
from typing import List, Tuple
import sys
@dataclass(unsafe_hash=True) # [1][2]
class Bag:
adjective: str
color: str
def contains_target(self, target, rules):
rule = rules[self]
held_bags = [item[0] for item in rule.contents]
return any(bag == target or bag.contains_target(target, rules) for bag in held_bags)
@dataclass
class Rule:
bag: Bag
contents: List[Tuple[Bag, int]]
def parse_line(line):
bag_desc, contents = line.split(' contain ')
# Create Bag
adjective, color, _ = bag_desc.split(' ')
bag = Bag(adjective, color)
# Fill in contents
_contents = []
if contents != 'no other bags.':
inner_bags = contents.split(', ')
for _bag in inner_bags:
quantity, adjective, color, _ = _bag.split(' ')
inner_bag = (Bag(adjective, color), int(quantity))
_contents.append(inner_bag)
# Turn the contents into a rule and return
rule = Rule(bag, _contents)
return (bag, rule)
if __name__ == '__main__':
input_file = sys.argv[1]
rules = {}
with open(input_file) as file:
for line in file:
stripped = line.strip()
bag, rule = parse_line(stripped)
rules[bag] = rule
target = Bag('shiny', 'gold')
can_hold_target = 0
for bag in rules.keys():
if bag.contains_target(target, rules):
can_hold_target += 1
print(can_hold_target)
This runs as such:
$ python main.py input.txt
151
Explanation
The logic of this one is fairly straightforward:
- For each line in the file, we turn it into a key-value pair of
Bag
andRule
, where theBag
contains the color of the outer bag and theRule
contains a list of inner bags, as well as how many of them we hold. - For each outer bag we call
.contains_target
which will recursively check if this bag will ever hold our shiny gold bag. - We tally up the outer bags that returned
True
above.
I tried to apply this logic in Raku, but I just kept finding myself fighting the type system.
First, rather than the inelegant parsing I did here, I tried to use one of Raku’s grammars, which ended up being clunky, and it took me several hours just to get the data to parse.
Once it was parsed to my liking, I ran into an issue that Hash
es only use strings as keys. There is a way to circumvent it, but there is a known bug in the compiler that casts them to strings anyway.
Finally, after rewriting my parser and using parameterized hashes as the above documentation suggested, I began fighting their type system. Here is what a Hash
’s declaration looks like:
class Hash is Map { }
class Map does Associative does Iterable { }
role Associative[::TValue = Mu, ::TKey = Str(Any)] { }
role Iterable { }
So some functions expect a Hash
, others expect an Iterable
others an Associative
. With non-parameterized types, they all work great and it just converts it to what it needs at runtime. However, with the parameterized types needed to circumvent the Hash
issue, I would get errors like this:
Error: Expected Associative[Bag] but found Hash[Bag]
Rather than waste my whole day on the issue, I decided to fall back to ol’ reliable: Python.
Specific Comments
- Dataclasses are a fairly recent addition to Python, and are similar to Scala case classes. The idea is they generate the
__init__
and other helper functions for you, and are meant to be used to store data with keys (similar to anamedtuple
). - To use an object as a key in a dictionary, it has to implement
__hash__
and__eq__
. By default, thedataclass
does not generate a__hash__
function for us, but it will withunsafe_hash=True
. Normally you would want to implement your own__hash__
function, but it is safe in this case.
Part 2
Now the question flips: if our outermost bag is our shiny gold bag, how many bags are we required to store inside of it?
Solution
See below for explanation and any implementation-specific comments.
from dataclasses import dataclass
from typing import List, Tuple
import sys
@dataclass(unsafe_hash=True)
class Bag:
adjective: str
color: str
def contains_target(self, target, rules):
rule = rules[self]
held_bags = [item[0] for item in rule.contents]
return any(bag == target or bag.contains_target(target, rules) for bag in held_bags)
def get_contents(self, rules):
contents = rules[self].contents
total_bags = 0
for bag, quantity in contents:
total_bags += quantity + (quantity * bag.get_contents(rules))
return total_bags
@dataclass
class Rule:
bag: Bag
contents: List[Tuple[Bag, int]]
def parse_line(line):
bag_desc, contents = line.split(' contain ')
# Create Bag
adjective, color, _ = bag_desc.split(' ')
bag = Bag(adjective, color)
# Fill in contents
_contents = []
if contents != 'no other bags.':
inner_bags = contents.split(', ')
for _bag in inner_bags:
quantity, adjective, color, _ = _bag.split(' ')
inner_bag = (Bag(adjective, color), int(quantity))
_contents.append(inner_bag)
# Turn the contents into a rule and return
rule = Rule(bag, _contents)
return (bag, rule)
if __name__ == '__main__':
input_file = sys.argv[1]
rules = {}
with open(input_file) as file:
for line in file:
stripped = line.strip()
bag, rule = parse_line(stripped)
rules[bag] = rule
target = Bag('shiny', 'gold')
# Part 1
can_hold_target = 0
for bag in rules.keys():
if bag.contains_target(target, rules):
can_hold_target += 1
# Part 2
total_contents = target.get_contents(rules)
print(f'Part 1: {can_hold_target}')
print(f'Part 2: {total_contents}')
This runs as such:
$ python main.py input.txt
Part 1: 151
Part 2: 41559
Explanation
As you can see, all we had to add was our get_contents
function to the Bag
class. For each bag in the shiny gold bag, it counts not only the bag itself, but all the bags within it as well.
I don’t have any implementation-specific comments on this one, as it is pretty straightforward, especially with such a small change from part 1. The only thing I will say is I did not add the CLI that I have added to my Raku solutions because it is much more cumbersome in Python. Every language has its strong suits!
Final Thoughts
While I am bummed that I failed in my goal to write functional Raku for all 25 days of this thing, I think it is important to note that it is best to use the right tool for the job. I think I could have struggled through it in Raku, but I don’t have the time, patience, or know-how to do that; especially when we’ve got another challenge coming tomorrow! I will continue to try to do the rest of the problems in functional Raku, but if I can’t do it, at least we’ve already bridged that gap!