Another day, another Advent of Code 2020 problem.
That one seems fun! For some nerdy values of fun.
Our input is a set of rules:
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.
And the question we have to answer is: "How many bag colors can eventually
contain at least one shiny gold bag?"
From looking at the example input above, for example, "bright white bags" can
directly contain a shiny gold bag, whereas light red bags can contain a
bright white bag which can contain a shiny gold bag.
The question for part 1 doesn't use "how many bags of colors Y can be
contained in bags of color X", so I suspect it's going to show up in part 2
(which, as a reminder, I can't see until I've solved the first part) - I'd
like to try and parse and represent that input as types that make it easy to
answer that first question.
Bags are clearly defined by two things: an adjective (light, dark, bright,
muted, shiny, vibrant, faded, dotted) and a color (red, orange, white,
yellow, gold, olive, plum, etc).
We don't know yet how many different adjectives or colors there'll be, so I'm
tempted to just represent those as borrowed strings:
Rust code
/// (adjective, color), i.e. ("dark", "orange")
type BagSpec<'a> = (&'a str, &'a str);
"Spec" is used here as a shorthand for "specification".
From there, all our rules are simply a mapping from BagSpec
to a quantity
and another BagSpec
:
Rust code
use std::collections::HashMap;
/// K can contain V.0 of V.1
type Rules<'a> = HashMap<BagSpec<'a>, (usize, BagSpec<'a>)>;
But here's the thing - some bags can contain several types of other bags.
From the example above:
light red bags contain 1 bright white bag, 2 muted yellow bags.
We can't represent this rule with our current set of types:
Rust code
fn main() {
let mut rules: Rules = Default::default();
rules.insert(("light", "red"), (1, ("bright", "white")));
rules.insert(("light", "red"), (2, ("muted", "yellow")));
dbg!(&rules);
}
Shell session
$ cargo run --quiet
[src/main.rs:13] &rules = {
(
"light",
"red",
): (
2,
(
"muted",
"yellow",
),
The second rule has overwritten the first one!
The good news is: there's a crate (and a type) for that!
Shell session
$ cargo add multimap
Adding multimap v0.8.2 to dependencies
Rust code
use multimap::MultiMap;
/// K can contain V.0 of V.1
type Rules<'a> = MultiMap<BagSpec<'a>, (usize, BagSpec<'a>)>;
Shell session
$ cargo run --quiet
[src/main.rs:13] &rules = {
(
"light",
"red",
): [
(
1,
(
"bright",
"white",
),
),
(
2,
(
"muted",
"yellow",
),
),
],
}
Ooh, just like HeaderMap
in hyper?
Let's now try parsing our sample rules into this data structure.
Shell session
$ cargo add peg
Adding peg v0.6.3 to dependencies
Rust code
fn parse_rules(input: &str) -> Rules<'_> {
let mut rules: Rules = Default::default();
peg::parser! {
pub(crate) grammar parser() for str {
pub(crate) rule root(r: &mut Rules<'input>)
= (line(r) "." whitespace()*)* ![_]
rule line(r: &mut Rules<'input>)
= spec:bag_spec() " contain " rules:rules() {
if let Some(rules) = rules {
for rule in rules {
r.insert(spec, rule)
}
}
}
rule bag_spec() -> BagSpec<'input>
= adjective:name() " " color:name() " bag" "s"? { (adjective, color) }
rule rules() -> Option<Vec<(usize, BagSpec<'input>)>>
= rules:rule1()+ { Some(rules) }
/ "no other bags" { None }
/// Rule followed by an optional comma and space
rule rule1() -> (usize, BagSpec<'input>)
= r:rule0() ", "? { r }
/// A single rule
rule rule0() -> (usize, BagSpec<'input>)
= quantity:number() " " spec:bag_spec() { (quantity, spec) }
rule number() -> usize
= e:$(['0'..='9']+) { e.parse().unwrap() }
/// A sequence of non-whitespace characters
rule name() -> &'input str
= $((!whitespace()[_])*)
/// Spaces, tabs, CR and LF
rule whitespace()
= [' ' | '\t' | '\r' | '\n']
}
}
parser::root(input, &mut rules).unwrap();
rules
}
Now, dbg!()
makes for pretty verbose output - maybe we can replicate the
formatting of the input, for inspection?
Rust code
use std::fmt;
struct FormattedRules<'a>(Rules<'a>);
impl fmt::Display for FormattedRules<'_> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
for (k, vv) in &self.0 {
write!(f, "{} {} bags can contain ", k.0, k.1)?;
if vv.is_empty() {
write!(f, "no other bags")?;
} else {
for (i, v) in vv.iter().enumerate() {
if i > 0 {
write!(f, ", ")?;
}
write!(
f,
"{} {} {} {}",
v.0,
v.1 .0,
v.1 .1,
if v.0 == 1 { "bag" } else { "bags" }
)?;
}
}
writeln!(f, ".")?;
}
Ok(())
}
}
Rust code
fn main() {
let rules = parse_rules(include_str!("input.txt"));
print!("{}", FormattedRules(rules));
}
Now, to compare the output of our program to the sample input,
we have to sort it - good old sort
command will work out just fine:
Shell session
$ cargo run --quiet | sort -n
bright white bags can contain 1 shiny gold bag.
dark olive bags can contain 3 faded blue bags, 4 dotted black bags.
dark orange bags can contain 3 bright white bags, 4 muted yellow bags.
light red bags can contain 1 bright white bag, 2 muted yellow bags.
muted yellow bags can contain 2 shiny gold bags, 9 faded blue bags.
shiny gold bags can contain 1 dark olive bag, 2 vibrant plum bags.
vibrant plum bags can contain 5 faded blue bags, 6 dotted black bags.
Shell session
$ cat src/input.txt | sort -n
bright white bags contain 1 shiny gold bag.
dark olive bags contain 3 faded blue bags, 4 dotted black bags.
dark orange bags contain 3 bright white bags, 4 muted yellow bags.
dotted black bags contain no other bags.
faded blue bags contain no other bags.
light red bags contain 1 bright white bag, 2 muted yellow bags.
muted yellow bags contain 2 shiny gold bags, 9 faded blue bags.
shiny gold bags contain 1 dark olive bag, 2 vibrant plum bags.
vibrant plum bags contain 5 faded blue bags, 6 dotted black bags.
Seems good! The only difference is we don't remember bags that can contain no other bags. I'm going to say that doesn't matter right now - but we can always change our mind later.
Back to the question. Even though this data structure is flat, we have
a graph on our hands: