Advent of Rust 6: Please Continue

It’s that time again, time for the daily stream-of-consciousness log of me trying to teach myself the Rust programming language by doing programming puzzles at Advent of Code 2020.

In yesterday’s installment I talked about how people had been providing helpful and encouraging comments, which I appreciated! This time, I also got one unfriendly comment, complaining how I was increasing GNOME’s dependency on Microsoft with Rust. That’s just nonsense, and I don’t even understand how they got from here to there, but for avoidance of all doubt: this series is unconnected to GNOME or my volunteer work for the GNOME Foundation, and also unconnected to my employer (Igalia, not Microsoft.) It is a learning exercise for me personally.

That unpleasant formality out of the way, let’s get started!

Day 6, Part 1

Once again I start out with cargo new puzzle6 and copy over the boilerplate from yesterday.

Today’s puzzle is about customs forms: there are 26 yes-or-no questions on these forms, marked a to z. In the input file you get lines consisting of the letters for which each passenger on the plane has answered yes. The passengers are divided into groups separated by blank lines, and you need to compute for each group, how many questions were answered yes by at least one person. The answer to the puzzle is the sum of all these counts.

The line-by-line data divided into groups separated by blank lines looks a lot like Day 4, so I can reuse some code from there. Another similarity with Day 4 is that this problem seems to lend itself well to using a HashSet. If I can take the string on each line, and insert all the characters into a HashSet for each group, then I can get the per-group count by counting the number of the elements in the HashSet when we move on to the next group.

Here’s the code that I write:

let mut total = 0;
let mut current = HashSet::new();
for line in read_lines("input")? {
    if line == "" {
        total += current.len();
        current = HashSet::new();
    }
    current.extend(line.bytes());
}
total += current.len();
println!("{}", total);

This doesn’t compile because I forgot that each line is a Result, so I need to handle errors. I add two question marks:

for line in read_lines("input")? {
    if line? == "" {
        total += current.len();
        current = HashSet::new();
    }
    current.extend(line?.bytes());
}

Here I get an error that I haven’t seen yet:

error[E0382]: use of moved value: `line`
  --> src/main.rs:15:24
   |
10 |     for line in read_lines("input")? {
   |         ---- move occurs because `line` has type `std::result::Result<std::string::String, std::io::Error>`, which does not implement the `Copy` trait
11 |         if line? == "" {
   |            ----- `line` moved due to this method call
...
15 |         current.extend(line?.bytes());
   |                        ^^^^ value used here after move
   |
note: this function consumes the receiver `self` by taking ownership of it, which moves `line`

I did read about moving the other day when I was reading about ownership. As far as I can understand here, you can only use the ? operator once on a Result because it moves the value out of the Result. I try instead for line in read_lines("input")?.map(|s| s.unwrap()), and that works…

But I get a panic “No such file or directory” because I’ve forgotten to even download the input file! Once I’ve done that, I run the program again, and I get an answer, which according to the Advent of Code website, is correct!

This is a happy milestone for me. Although I can’t count on being able to write a program that compiles without errors the first time, still, I got most things right and didn’t have to change very much to make it work. I’m also noticing that I have a much better idea of where to look for things in the documentation than I did 6 days ago when I started.

Here’s the full code, without boilerplate:

fn main() -> Result<(), io::Error> {
    let mut total = 0;
    let mut current = HashSet::new();
    for line in read_lines("input")?.map(|s| s.unwrap()) {
        if line == "" {
            total += current.len();
            current = HashSet::new();
        }
        current.extend(line.bytes());
    }
    total += current.len();
    println!("{}", total);
    Ok(())
}

Day 6, Part 2

The second part of the puzzle is the same as the first, but you have to count the number of questions for which everyone in the group answered yes, instead of the questions for which anyone in the group answered yes. And once again like Day 4, this seems like a good opportunity to convert the HashSet of questions for which anyone answered yes, to a HashMap counting the number of people in the group who answered yes to each question.

I start out by reading the HashMap documentation again and notice something that I didn’t notice before: the Entry API. I’m somewhat familiar with this idiom from working on GJS, because it’s used in SpiderMonkey‘s hash maps inside the Firefox browser code. So I’m not actually all that surprised to see it in Rust, which originated as a Mozilla project.

From reading the documentation, it looks like this is how I’d increment the count of an element using the Entry API, inserting it if it wasn’t present yet:

let count = hashmap.entry(element).or_insert(0)
*count += 1;

So I figure what I can do is also keep track of the number of people in each group as I read the lines in from the file, and then when the group ends, change the HashMap into an iterator and filter on the counts that are equal to the number of people in the group — this should mean filtering down to the questions for which every person in the group answered yes.

First I want to refactor the program so that it uses the HashMap to count, but still computes the Part 1 answer. This is my attempt:

fn main() -> Result<(), io::Error> {
    let mut total = 0;
    let mut current = HashMap::new();
    for line in read_lines("input")?.map(|s| s.unwrap()) {
        if line == "" {
            total += count_answers(&current);
            current = HashMap::new();
        }
        for byte in line.bytes() {
            let count = current.entry(byte).or_insert(0);
            *count += 1;
        }
    }
    total += count_answers(&current);
    println!("{}", total);

    Ok(())
}

fn count_answers(group: &HashMap<u8, usize>) -> usize {
    group.len()
}

I’m a bit concerned about whether the compiler will be able to infer the type of the HashMap‘s values, or whether I need to explicitly specify usize, but apparently this is not a problem. It runs the first time, and I get the same answer I had before!

I refactored group.len() into count_answers() because that’s where I’m going to put the logic for Part 2. Here’s the first version that I write:

fn main() -> Result<(), io::Error> {
    let mut total = 0;
    let mut current = HashMap::new();
    let mut group_size = 0;
    for line in read_lines("input")?.map(|s| s.unwrap()) {
        if line == "" {
            total += count_answers(&current, group_size);
            current = HashMap::new();
            group_size = 0;
        }
        for byte in line.bytes() {
            let count = current.entry(byte).or_insert(0);
            *count += 1;
        }
        group_size += 1;
    }
    total += count_answers(&current, group_size);
    println!("{}", total);

    Ok(())
}

fn count_answers(group: &HashMap<u8, usize>, group_size: usize) -> usize {
    if is_part2() {
        group
            .iter()
            .filter(|(_, count): &(u8, usize)| usize == group_size)
            .count()
    } else {
        group.len()
    }
}

The first compiler error is an easily corrected mistake: I meant to write count == group_size, not usize == group_size. The second error is that once again I’ve gotten the type of a tuple in a map() or filter() function wrong: it should be &(&u8, &usize), and I still don’t understand why these pass-by-value parameters have to be borrowed. But I have learned from yesterday that I will need to dereference *count == group_size in that case, because you cannot compare &usize with usize, so I add that as well. But even now I get it wrong: I actually need to dereference it twice, **count == group_size, I guess because the tuple is borrowed as well as the elements of the tuple? This is a bit of a mystery to me.

With that, I can run the program and get an answer. The answer seems like it’s very small, and indeed when I put it into the Advent of Code website I find out that it’s wrong.

I wonder if I should start stepping through it in a debugger, but after staring at it for a while, I find that I’ve forgotten to put continue; inside the if line == "" clause! This was also a bit sloppy in Part 1, but it didn’t matter, because if the line was empty, the for byte in line.bytes() loop would also not run. But now I have group_size += 1 down below that loop, and that’s not supposed to be executed if the line was empty.

I add the continue; and get a different answer, which I put into the website and it’s correct.

Here’s the full code, minus the boilerplate:

use std::collections::HashMap;

fn main() -> Result<(), io::Error> {
    let mut total = 0;
    let mut current = HashMap::new();
    let mut group_size = 0;
    for line in read_lines("input")?.map(|s| s.unwrap()) {
        if line == "" {
            total += count_answers(&current, group_size);
            current = HashMap::new();
            group_size = 0;
            continue;
        }
        for byte in line.bytes() {
            let count = current.entry(byte).or_insert(0);
            *count += 1;
        }
        group_size += 1;
    }
    total += count_answers(&current, group_size);
    println!("{}", total);

    Ok(())
}

fn count_answers(group: &HashMap<u8, usize>, group_size: usize) -> usize {
    if is_part2() {
        group
            .iter()
            .filter(|(_, count): &(&u8, &usize)| **count == group_size)
            .count()
    } else {
        group.len()
    }
}

Afterword

Part 1 went very quickly, and Part 2 took a bit longer. This time there was a more balanced mix of Rust-beginner mistakes (that danged & operator every time!) and “normal” mistakes that I might make in another programming language (forgetting the continue statement).

I do think that I’m leaning very heavily on existing knowledge of things from other programming languages. For example, I guessed that Rust might have a continue statement without looking it up, because of all the other languages that have a continue statement. The knowledge I’m leaning most heavily on comes from C++ (for the general idea of RAII, the types that the language provides, references, and templates), and after that Python (for iterators and the idea of an extensive standard library); not so much from JavaScript or any of the other languages I’ve worked in. I might have mentioned this before, but I think progress would have been much slower had I not already been familiar with C++ and Python.

Onward to Day 7!


[0] No footnotes this time

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.