Advent of Rust 7: What Type is a sum()?

Welcome back to the stream-of-consciousness log of me solving the puzzles at Advent of Code 2020 in order to teach myself the Rust programming language.

This is the end of the first week of learning. The posts are getting shorter, and while I found in the first days that writing about each compiler error helped me think about what might be causing it, now I have usually figured out what’s going on before I finish writing.

So I think today’s might be the last installment in which I go into so much detail about compiler errors; starting this week I’ll post shorter entries, maybe bunched into a few days at a time, that write about the approach I took and what errors were still surprising to me, instead of writing about every time I have to add or delete a & operator. (But if hearing about those details would still be useful to you, now is a good time to let me know!)

Day 7, Part 1

Today’s puzzle is complicated, I have to read the description several times. The input file contains a number of rules about which color bags can hold which other color bags, written in prose. The answer to the puzzle is how many colors of bags can contain a “shiny gold” bag, either directly or by containing other bags which contain the shiny gold bag.

I start with cargo new puzzle7 and copying over the boilerplate from yesterday. Also, I’m not sure I understand exactly what the rules look like, so I download the input file and check what it contains. A lot of lines like this:

light green bags contain 2 pale cyan bags.
dim tan bags contain 3 shiny teal bags, 5 bright white bags, 4 striped bronze bags.
dotted magenta bags contain 2 faded cyan bags, 4 bright yellow bags.
dull silver bags contain 3 striped green bags.

For this puzzle I can ignore how many of each color of bag can be contained (I suspect it will come back in Part 2, though) and focus on which colors can be contained by which other colors.

I will need to figure out how to obtain the rules out of the prose-like sentences in the input file, and I think I will use scan_fmt! for this, so I add it to Cargo.toml.

I don’t immediately get an idea for a data structure to hold this information, so maybe I will work on the string scanning first, and see if I get any ideas about a data structure while I do that. The one thing that I do notice (after thinking about it for a little bit) is that the input file provides information about which colors can contain which other colors, but to answer the puzzle, I need to look up for a given color which colors it can be contained by. So in any case, I will need to reverse the relationships given by the rules.

But first to the string scanning!

for line in read_lines("input")?.map(|s| s.unwrap()) {
    let (container, contents) =
        scan_fmt!(&line, "{[a-z ]} bags contain {[a-z ]}.", String, String)
            .expect(&format!("{} didn't match pattern", line));
    let contained_bags = if contents == "no other bags" {
        vec![]
    } else {
        contents
            .split(", ")
            .map(|bag| {
                scan_fmt!(bag, "{[a-z ]} bag", String)
                    .expect(&format!("{} didn't match pattern", bag))
            })
            .collect::<Vec<String>>()
    };
    println!("{} -> {:?}", container, contained_bags);
}

I googled “rust format string” (as I haven’t actually done that yet, I’ve only formatted strings with println!()) and discover in Rust by Example that there is a format!() macro which works just like println!(). I use this to provide better error messages, since I do expect that I probably haven’t got the scanning patterns correct the first time.

Running cargo clippy suggests using .unwrap_or_else(|_| panic!("{} didn't match pattern", line)) instead of .expect(&format!("{} didn't match pattern", line)) and it even prints a link that I can read which explains why that’s better!

I made a few other typos and left out some & operators, but that stuff is probably boring by now. The one interesting error that I did make is that I originally tried collect::<Vec<&str>>(). I think this was probably due to not thinking hard enough about the type of the vector, rather than misunderstanding something. The compiler error was clear enough: “a value of type Vec<&str> cannot be built from an iterator over elements of type String“.

When I run this code, it panics on the first line of the input file! The line light green bags contain 2 pale cyan bags. doesn’t match the pattern that I gave to scan_fmt!(). Here’s where I would really like to be able to try a few things in a Rust REPL until I get it right. But I have an idea of what might be going wrong. Maybe the matchers in scan_fmt!() are eager, so the first {[a-z ]} matches everything until the end of the string? I try it like this:

let (adjective, color, contents) = scan_fmt!(
    &line,
    "{} {} bags contain {[a-z ]}.",
    String,
    String,
    String
)
.unwrap_or_else(|_| panic!("{} didn't match pattern", line));
let container = format!("{} {}", adjective, color);

(and the same change to the second scan_fmt!() call as well)

Having changed that I get another panic when trying to scan the contained bags. This time it tells me that the empty string didn’t match the pattern. I wonder how I got an empty string? I look at the scan_fmt!() documentation again figure out that {[a-z ]} is probably only matching one character; what I really want is {/[a-z ]+/}. I make this change, but the error still occurs.

I add a println!("{} {} {}", adjective, color, contents); after the first scan_fmt!() call to see what I’m getting. It seems that contents is blank. But, I see that I have forgotten the comma in the regular expression, and what’s more, even though I figured I could ignore the digits for Part 1 of the puzzle, I cannot ignore them when scanning the string, because of course they are still there! 😳

So, I use "{} {} bags contain {/[0-9a-z, ]+/}." for the first pattern, and "{*d} {} {} bag" for the second pattern, and the program runs. I get output such as:

light green -> ["pale cyan"]
dim tan -> ["shiny teal", "bright white", "striped bronze"]
dull aqua -> []

Now, I still have to figure out what data structure to store this in! I’m thinking that if I use a tree, where each node points to the other nodes that can contain that color of bag, then I can start at the node for shiny gold bags and just count the total number of nodes below it. I google “rust tree” and land on the trees package, but that seems more advanced than what I want, and I don’t understand the documentation very well. I also read this article which says it is more aimed at beginners, and from reading it, it seems like trees are fairly difficult to implement in Rust the way that you would in C, but there is a more convenient way to do it using Vec.1

It also occurs to me that I would like to be able to look up bag rules by the color of the bag. If I had a tree, I’d have to search the whole tree to find my shiny gold bag starting point. So maybe a HashMap<String, Vec<String>> is the appropriate data structure, with the key being the color of the bag, and the value being a vector of other bag colors that can contain this bag.

I decide to use the Entry API that I used yesterday to build the tree. I add use std::collections::HashMap; and let mut rules = HashMap::new(); in the appropriate places, and then write this code:

if contents != "no other bags" {
    contents
        .split(", ")
        .map(|bag| {
            let (adjective, color) = scan_fmt!(bag, "{*d} {} {} bag", String, String)
                .unwrap_or_else(|_| {
                    panic!("'{}' ({}) didn't match pattern", bag, contents)
                });
            format!("{} {}", adjective, color)
        })
        .for_each(|color| {
            let mut entry = rules.entry(color).or_insert(vec![]);
            entry.push(container);
        });
};
println!("{:?}", rules["shiny gold"]);

(Yes, unlike a few days ago I now know that iterators have a for_each() method because I found out that there is documentation for the Iterator trait where I can look…) This gives me a few errors:

warning: variable does not need to be mutable
  --> src/main.rs:31:25
   |
31 |                     let mut entry = rules.entry(color).or_insert(vec![]);
   |                         ----^^^^^
   |                         |
   |                         help: remove this `mut`
   |
   = note: `#[warn(unused_mut)]` on by default

error[E0507]: cannot move out of `container`, a captured variable in an `FnMut` closure
  --> src/main.rs:32:32
   |
21 |         let container = format!("{} {}", adjective, color);
   |             --------- captured outer variable
...
32 |                     entry.push(container);
   |                                ^^^^^^^^^ move occurs because `container` has type `String`, which does not implement the `Copy` trait

I remove the mut from entry (I wrote it because it seemed like an entry should be mutable, but then I realize I didn’t have mut yesterday either). The second error actually makes sense. I need to have a different copy of the string for the containing bag in each vector. I can’t remember off the top of my head whether this would be achieved by String::from() so I quickly google “rust copy string” and land right away on the Clone trait, so I add container.clone() to my code.

Now the code runs, but I get a panic in my debug-print of rules["shiny gold"]. This key doesn’t exist in the map! I change the line to print out the entirety of rules to check that the general shape of the data is what I expected; it is. I wonder why there’s no shiny gold?

I try to print rules["clear gray"] which is the last entry in my debug output, so I know it must exist in the map. I still get the panic, so therefore I must be indexing the map wrong. I think I am actually supposed to use get() and not the [] operator (though then why does the code compile?) I change it to rules.get(&"clear gray").expect("Key not present") and get another interesting error:

error[E0277]: the trait bound `String: Borrow<&str>` is not satisfied
  --> src/main.rs:37:32
   |
37 |         println!("{:?}", rules.get(&"clear gray").expect("Key not present"));
   |                                ^^^ the trait `Borrow<&str>` is not implemented for `String`
   |
   = help: the following implementations were found:
             <String as Borrow<str>>

If I’m reading this error message correctly, then I think it says that I can use "clear gray" here and it will be automatically converted to a temporary String to pass to get(), but the same does not happen for &"clear gray". So I remove the &, but then I get back to the panic that I got earlier: “Key not present”.

Maybe it’s get(&String::from("clear gray"))? Same result, that doesn’t work either.

Then I realize it! I accidentally have my debug-print inside the loop, so it’s printing out the rule after every line in the input file, instead of once at the end! So the first time I try to access rules["clear gray"], it hasn’t been inserted yet. I change the print statement back to rules["shiny gold"], move it down one line and indeed, I get a list of bag colors that can contain a shiny gold bag. One step closer to the solution!

Now I need to count the number of bag colors that can contain a shiny gold bag, plus the number of bag colors that can contain those colors of bags, and so on. The downside is that I don’t know whether there are bag colors that can contain each other (or in math-speak, whether the graph is cyclic.) If I knew for sure the graph was acyclic (bag colors can only contain other bag colors that they are not contained by) then I could implement this by just counting the number of elements in each Vec in the node for "shiny gold" and below. There’s an easy way to find out, though; if I try that and the graph is cyclic, then my program will go into an infinite loop, and I’ll notice soon enough! So I decide to try this. I write this function:

fn total_containers_for(rules: &HashMap<String, Vec<String>>, bag_color: &str) -> usize {
    let containers = &rules[bag_color];
    containers.len()
        + containers
            .iter()
            .map(|color| total_containers_for(rules, color))
            .sum()
}

and I try to print out total_containers_for(&rules, "shiny gold") at the end of the program. I get an error that I don’t understand:

error[E0284]: type annotations needed: cannot satisfy `<usize as std::ops::Add<_>>::Output == usize`
  --> src/main.rs:46:9
   |
46 |         + containers
   |         ^ cannot satisfy `<usize as std::ops::Add<_>>::Output == usize`

I stare at this for a while, but I really just don’t get any closer to understanding it. I refactor it into this, to see if the error is in the first or second half of the expression:

let n_direct_containers = containers.len();
let n_indirect_containers = containers
    .iter()
    .map(|color| total_containers_for(rules, color))
    .sum();
n_direct_containers + n_indirect_containers

That changes the error message into something more understandable:

error[E0282]: type annotations needed
  --> src/main.rs:46:9
   |
46 |     let n_indirect_containers = containers
   |         ^^^^^^^^^^^^^^^^^^^^^ consider giving `n_indirect_containers` a type

OK, that I can do! I add : usize to the variable and it compiles. (I’d like to refactor it back into one expression, but I’m not sure how to add a type annotation to only part of an expression, so I leave it like this.)

Now the program runs, but it panics again, in total_containers_for(), at the &rules[bag_color] expression. I add the following debug-prints:2

let mut debug: Vec<&String> = rules.keys().collect();
debug.sort();
println!("{:?}", debug);
let containers = &rules
    .get(bag_color)
    .unwrap_or_else(|| panic!("{} not found in rules", bag_color));

I find that light fuchsia is the key that’s not found, and indeed it’s not there in the sorted list of keys. So now at least I know I am indexing the map correctly, but there’s a bug in my code that puts all the rules into the map. I open the input file and do a search for light fuchsia. It’s only present in one line:

light fuchsia bags contain 1 shiny gold bag, 5 faded beige bags, 2 dark chartreuse bags, 3 light brown bags.

Apparently, nothing is allowed to contain light fuchsia bags! Since it never appears in the second half of a rule, it’s never added to the map. So what I need to do is add all of the colors in the first half of the rule as well. I add this line to the appropriate place:3

rules.entry(container).or_insert(vec![]);

But this is a mistake: it changes the inferred key type of the HashMap from String to &String, making the subsequent inserts invalid! Luckily I learned above that I can clone() the string, so I change it again to:

rules.entry(container.clone()).or_insert(vec![]);

With this, the program runs, and gives me an answer. It’s not over yet, though: the Advent of Code website tells me my answer is too high.

What to do next? I don’t have any immediate ideas about what could be going wrong. I decide to try running the program on the example input given in the puzzle description, to see if I get the right answer on that. I mv input real_input to back up the input, and then change the input file to have the following contents:

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.

I then run the program again, and get the answer 6, whereas the correct answer is 4. So I add println!("{:?}", rules); to examine the rules map that I’ve generated. It all seems correct with what is in the file, but I think I’ve found the bug: I’m not removing duplicates from the list of bags that can contain shiny gold bags, so I’m counting light red and dark orange twice.

This will take a bit of refactoring! I change total_containers_for() to a new function all_containers_for() which returns a HashSet of bag colors that can contain the requested bag:

fn all_containers_for(rules: &HashMap<String, Vec<String>>, bag_color: &str) -> HashSet<String> {
    let containers = &rules[bag_color];
    let mut colors: HashSet<String> = containers.iter().map(|s| s.clone()).collect();
    for color in containers.iter() {
        let mut indirect_colors = all_containers_for(rules, color);
        colors.extend(indirect_colors.drain());
    }
    colors
}

Then to get my answer I do println!("{}", all_containers_for(&rules, "shiny gold").len());

I also get a suggestion from cargo clippy:

warning: you are using an explicit closure for cloning elements
  --> src/main.rs:46:39
   |
46 |     let mut colors: HashSet<String> = containers.iter().map(|s| s.clone()).collect();
   |                                       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ help: consider calling the dedicated `cloned` method: `containers.iter().cloned()`

Well that’s useful!

This runs (except that I forgot the mut on both of the HashSet variables at first…) and I get the answer 4, as it should be. Hopefully if I run this again on the real input, I’ll get the real answer! I bring back the real input file with mv real_input input, run the program again, and get an answer. This time it’s correct. Phew!

Day 7, Part 2

Let’s hope Part 2 goes a bit faster than Part 1, this has been more difficult than the other days and I’m a bit tired of it!

Part 2 of the puzzle is to consider the rules the other way around. We have to once again start from a shiny gold bag, but this time say how many bags it must contain.

I think it’s best to assemble a different set of rules, since we are looking up the bags in the other direction. I’ll rename the existing rules to container_rules, and introduce a new contains_rules of type HashMap<String, Vec<(String, usize)>>. Then once I have a database of contains_rules, I can write a function total_contained_by() that will give me the total number of bags that must be contained by the given bag; recursively, similar to all_containers_for().

After a few typos and forgotten .clone()s, my main() function looks like this:

fn main() -> Result<(), io::Error> {
    let mut container_rules = HashMap::new();
    let mut contents_rules = HashMap::new();
    for line in read_lines("input")?.map(|s| s.unwrap()) {
        let (adjective, color, contents) = scan_fmt!(
            &line,
            "{} {} bags contain {/[0-9a-z, ]+/}.",
            String,
            String,
            String
        )
        .unwrap_or_else(|_| panic!("{} didn't match pattern", line));
        let container = format!("{} {}", adjective, color);
        container_rules.entry(container.clone()).or_insert(vec![]);
        if contents != "no other bags" {
            contents
                .split(", ")
                .map(|bag| {
                    let (num, adjective, color) =
                        scan_fmt!(bag, "{d} {} {} bag", usize, String, String).unwrap_or_else(
                            |_| panic!("'{}' ({}) didn't match pattern", bag, contents),
                        );
                    (num, format!("{} {}", adjective, color))
                })
                .for_each(|(num, color)| {
                    let container_entry = container_rules.entry(color.clone()).or_insert(vec![]);
                    container_entry.push(container.clone());
                    let contents_entry = contents_rules.entry(container.clone()).or_insert(vec![]);
                    contents_entry.push((num, color));
                });
        };
    }

    if is_part2() {
        println!("{:?}", contents_rules);
    } else {
        println!(
            "{}",
            all_containers_for(&container_rules, "shiny gold").len()
        );
    }

    Ok(())
}

I print out the new contents_rules map with cargo run 2 and it looks like what I might expect. Now I try to write total_contained_by():

fn total_contained_by(rules: &HashMap<String, Vec<(usize, String)>>, bag_color: &str) -> usize {
    rules[bag_color]
        .iter()
        .map(|(num, color)| num * total_contained_by(rules, color))
        .sum()
}

This compiles, but again crashes with a missing key when I run it. I do get a pretty quick idea of what the problem is, though: I’m forgetting to add the entry to contents_rules if the second part of the rule is contains no other bags. I move the let contents_entry = contents_rules.entry(container.clone()).or_insert(vec![]); line up above the if statement and try again. This time, I get an answer of zero! Clearly the wrong answer, because there is this line in the input file:

shiny gold bags contain 5 mirrored lavender bags, 4 shiny maroon bags, 4 striped yellow bags.

So even if those bags contain nothing else, the answer has to be at least 13.

I do a bit of debug-printing and find out that total_contained_by() is always returning zero, no matter what, so that’s why the total answer is zero. It should return zero for bags that don’t contain other bags. But if a bag contains no other bags, then I still have to count that bag itself! So I change the map() line in total_contained_by() to this:

.map(|(num, color)| num * total_contained_by(rules, color) + 1)

Now I get a more realistic answer from the program. I put it into the puzzle website, but it’s still too low. Then I realize that if my bag contains five other bags that each contain no other bags, I still have to count five bags, not one! In other words, I’ve forgotten the parentheses:

.map(|(num, color)| num * (total_contained_by(rules, color) + 1))

(I also check the puzzle description again to make sure I don’t need to count the original shiny gold bag, but I don’t!) Running the program again gives me a much higher answer which is, finally, correct according to the website.

Here’s the full code, but without the boilerplate:

use std::collections::{HashMap, HashSet};

#[macro_use]
extern crate scan_fmt;

fn main() -> Result<(), io::Error> {
    let mut container_rules = HashMap::new();
    let mut contents_rules = HashMap::new();
    for line in read_lines("input")?.map(|s| s.unwrap()) {
        let (adjective, color, contents) = scan_fmt!(
            &line,
            "{} {} bags contain {/[0-9a-z, ]+/}.",
            String,
            String,
            String
        )
        .unwrap_or_else(|_| panic!("{} didn't match pattern", line));
        let container = format!("{} {}", adjective, color);
        container_rules.entry(container.clone()).or_insert(vec![]);
        let contents_entry = contents_rules.entry(container.clone()).or_insert(vec![]);
        if contents != "no other bags" {
            contents
                .split(", ")
                .map(|bag| {
                    let (num, adjective, color) =
                        scan_fmt!(bag, "{d} {} {} bag", usize, String, String).unwrap_or_else(
                            |_| panic!("'{}' ({}) didn't match pattern", bag, contents),
                        );
                    (num, format!("{} {}", adjective, color))
                })
                .for_each(|(num, color)| {
                    let container_entry = container_rules.entry(color.clone()).or_insert(vec![]);
                    container_entry.push(container.clone());
                    contents_entry.push((num, color));
                });
        };
    }

    if is_part2() {
        println!("{}", total_contained_by(&contents_rules, "shiny gold"));
    } else {
        println!(
            "{}",
            all_containers_for(&container_rules, "shiny gold").len()
        );
    }

    Ok(())
}

fn total_contained_by(rules: &HashMap<String, Vec<(usize, String)>>, bag_color: &str) -> usize {
    rules[bag_color]
        .iter()
        .map(|(num, color)| num * (total_contained_by(rules, color) + 1))
        .sum()
}

fn all_containers_for(rules: &HashMap<String, Vec<String>>, bag_color: &str) -> HashSet<String> {
    let containers = &rules[bag_color];
    let mut colors: HashSet<String> = containers.iter().cloned().collect();
    for color in containers.iter() {
        let mut indirect_colors = all_containers_for(rules, color);
        colors.extend(indirect_colors.drain());
    }
    colors
}

Afterword

I had a more difficult time today than I did on the previous days! First I went down a wrong path while working with scan_fmt!() because I didn’t realize the matchers were greedy instead of lazy. Then I had that weird error “cannot satisfy <usize as std::ops::Add<_>>::Output == usize” which threw me for a loop. Finally, I made several mistakes in the logic of the program which I could have made just as easily in other programming languages. I don’t know if this was just a particularly difficult puzzle, or if the puzzles are getting more difficult as we go along, or if I was just having a bad day.

Yesterday and today I’ve not been writing down the instances where I misspelled something or forgot some & operators. Earlier in the week, writing everything out, as it happened, really helped me think about what to do next, but as I mentioned in the beginning it’s not so helpful at this point.

Lastly, I did find that when I got the wrong answer, it was really useful to run the program on the example input in the puzzle, and make sure that I compute the example answer. Thinking about it more, I’m surprised that today is the first time I’ve done this. I think I should do this more often.


[1] Maybe less efficient, but for a one-day programming puzzle, I don’t care

[2] I know, I know, one of these days I will google “rust debugger” instead of printing things. Today is not that day

[3] It seems like there ought to be a more idiomatic way to say “insert if not already existing”, but I don’t know what it is

2 thoughts on “Advent of Rust 7: What Type is a sum()?

  1. In the final code, just above “afterward” line 27 consists of html maybe results from trying to render an emoji based on the ignored argument to the closure calling panic!(). The github version is fine.

    I’ve been using the test input approach from early on, because I was initially paranoid about entering the wrong answer into the AoC website. But yes, it is helpful in debugging via printfs, which I am also doing.

    I considered encoding the rules twice as you did. But ended up taking the part 2 approach, which seemed more natural based on the rule definitions. Then wrote a simple search using a recursive can_hold(color) function over all rules to containing bags colors. I figured this was NlogN, so not really too slow for one color, but if you wanted the answer for all colors, it would want the reverse rule table.

    This day’s problem was more difficult for me too (especially compared to day 6), so I’m guessing it is actually harder in some sense.

    Thanks again for blogging.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.