Advent of Rust 10: When All You Have is Itertools, Every Problem Looks like an Iter

Welcome back to episode 10 of the previously-stream-of-consciousness-now-abbreviated log of me trying to teach myself the Rust programming language, stumbling my way through the puzzles from Advent of Code 2020.

I have noticed that by now doing a puzzle each day and writing about it is somewhat tiring. I’ve found myself eager to solve the puzzle in the quickest way possible rather than to use each day’s puzzle as an excuse to learn a new language feature in Rust. But on the other hand I think that’s OK! Despite that, I am still enjoying it and looking forward each day to seeing what the new puzzle is.

It’s just fine to want to solve puzzles in a hacky way; once the puzzle is solved, it’s done!

Day 10, Part 1

The first part of the puzzle is to figure out how to chain “joltage” (a made-up kind of voltage?) adapters together. Each adapter is rated for a different number of “jolts” and they all have to be connected in increasing order such that there is no more than a difference of 3 jolts between them, and all the adapters are used. I think this is a roundabout way of describing that the list has to be sorted in ascending numerical order?!

The answer to the puzzle is the number of adapters with 1 jolt difference between them, times the number of adapters with 3 jolts difference between them. This reminds me of Day 5 when I wanted to find which seat number was missing from a list and so looked for the item that did not have a number one higher than its predecessor.

This sounds like a job for … Itertools!

The initial approach of forging ahead and writing the code that I think will work, compiling it until it runs, and then trying the answer on the website, has worked many times so far, so I try it again now. I will sort the input array, add the device’s built-in adapter which is always 3 jolts higher than the highest adapter in the list, calculate the differences between consecutive elements using tuple_windows(), and then count the number of occurrences of each of those differences.

It’s for the latter step that I spend some time browsing the Itertools documentation to see if there is a method that already does this. The closest I come is to sort the vector of differences and then use group_by() on it, helpfully copying the code from the example usage of group_by() in the documentation, and then count the length of each of the groups.

Here’s the code:

let mut adapters: Vec<u8> = read_lines(file).map(|s| s.parse().unwrap()).collect();
adapters.sort_unstable();
adapters.push(adapters.last().unwrap() + 3); // add built-in adapter

let mut differences: Vec<u8> = adapters
    .iter()
    .tuple_windows()
    .map(|(j1, j2)| j2 - j1)
    .collect();
differences.sort_unstable();

let mut occurrences = vec![0, 0, 0];
for (key, group) in &differences.iter().group_by(|d| *d) {
    occurrences[*key as usize - 1] = group.count();
}

println!("{}", occurrences[0] * occurrences[2]);

Clippy helpfully reminds me to use sort_unstable() instead of sort() for u8 which doesn’t need to preserve the order of equal elements, and to use count() instead of the much less readable collect::<Vec<&u8>>().len(). Also, the * operators that you see in the code above were definitely the compiler’s idea, not mine.

I get an answer and put it into the Advent of Code website, and it’s too low. I print out adapters, differences, and occurrences to see if they make sense, and they do, but I notice the problem: I’ve added the built-in adapter on one end, which is 3 jolts higher than the highest one in the list, but I’ve forgotten to add the charging outlet on the other end, which is always rated 0 jolts. I do this (add adapters.push(0); before the sort) and this time get the right answer.

Before going on to Part 2, I look at this code again and think that maybe this is maybe just a tiny a bit too much Itertools, and I’m trying too hard to be clever. I refactor it into this, which still gives me the correct answer but only iterates through the sorted adapters once:

fn main() -> Result<(), io::Error> {
    let file = fs::File::open("input")?;
    let mut adapters: Vec<u8> = read_lines(file).map(|s| s.parse().unwrap()).collect();
    adapters.push(0); // add charging outlet
    adapters.sort_unstable();
    adapters.push(adapters.last().unwrap() + 3); // add built-in adapter

    let mut ones = 0;
    let mut threes = 0;
    for difference in adapters.iter().tuple_windows().map(|(j1, j2)| j2 - j1) {
        match difference {
            1 => ones += 1,
            3 => threes += 1,
            _ => (),
        }
    }

    println!("{}", ones * threes);
    Ok(())
}

Day 10, Part 2

Part 2 is to figure out the number of possible configurations of adapters with which you can connect the charging outlet to the device. Each adapter must have a higher number than the one before it, but no more than 3 higher.

The way they describe the puzzle, it sounds like brute force is not an option here! I first start thinking of a tree structure, but quickly discard that idea, because if there are trillions of possible configurations, then the tree would need to have trillions of branches.

For quite a long time I stare at the worked example in the puzzle description which has 8 possible configurations, scrolling back and forth between the list of adapters and the list of configurations. In the list of configurations I notice that many of the numbers remain the same because you have only one choice for the adapter that goes there. Looking at all 8 configurations, they all follow this pattern:

0, 1, 4, 5?, 6?, 7, 10, 11?, 12, 15, 16, 19, 22

Only 5, 6 and 11 are optional. Each one may occur or it may not, so that’s 23 = 8 combinations. And in fact, when you have reached adapter 4 you have 3 choices for the next adapter (5, 6, or 7), when you have reached adapter 10 you have 2 choices for the next adapter (11 or 12), and all the other adapters only have one possible choice for the next adapter. So the number of combinations is the product of 2n − 1 for each adapter where n is the number of possible choices for the next adapter.

For a little while I think this is how to get the answer, but then I realize this can’t be true, because according to this formula the answer can only be a power of 2 (since it’s calculated by multiplying powers of 2 together.) The answer to the second worked example, however, is 19280, not a power of 2.

I suppose if you had the sequence 0, 3, 4, 5, 6, 7, 10 then things would be a bit different! (Unlike the first worked example, there are five adapters next to each other in the list with a difference of 1 between them, not four.)

These would be the valid configurations for that sequence:

0, 3, 4, 5, 6, 7, 10
0, 3, 4, 5,    7, 10
0, 3, 4,    6, 7, 10
0, 3, 4,       7, 10
0, 3,    5, 6, 7, 10
0, 3,    5,    7, 10
0, 3,       6, 7, 10

There are 7 of them, clearly not a power of 2. My scheme was thrown off because the number of choices at one adapter can affect the number of choices at another adapter. At 5 you can choose to skip 6, but you can’t skip 6 if you’ve already skipped 4.

I did notice when I debug-printed occurrences in Part 11, that there were no differences of 2 in the list. They were all differences of 1 or 3. My hunch is that a difference of 3 “resets” things, since the two numbers on either side of it must always occur. So we can consider each “run” of ones in isolation.

We know from the original worked example (differences of 1, 3, 1, 1, 1, 3, 1, 1, 3, 1, 3, 3) that a run of one one yields only one choice, a run of two ones yields two choices (10, 11?, 12), a run of three ones yields four choices (4, 5?, 6?, 7), and now we know from my new example above that a run of four ones yields seven choices.

I check what the valid configurations are for a run of five ones, let’s say 0, 3, 4, 5, 6, 7, 8, 11:

0, 3, 4, 5, 6, 7, 8, 11
0, 3, 4, 5, 6,    8, 11
0, 3, 4, 5,    7, 8, 11
0, 3, 4, 5,       8, 11
0, 3, 4,    6, 7, 8, 11
0, 3, 4,    6,    8, 11
0, 3, 4,       7, 8, 11
0, 3,    5, 6, 7, 8, 11
0, 3,    5, 6,    8, 11
0, 3,    5,    7, 8, 11
0, 3,    5,       8, 11
0, 3,       6, 7, 8, 11
0, 3,       6,    8, 11

There are 13 of them. And a run of six ones, let’s say 0, 3, 4, 5, 6, 7, 8, 9, 12:

0, 3, 4, 5, 6, 7, 8, 9, 12
0, 3, 4, 5, 6, 7,    9, 12
0, 3, 4, 5, 6,    8, 9, 12
0, 3, 4, 5, 6,       9, 12
0, 3, 4, 5,    7, 8, 9, 12
0, 3, 4, 5,    7,    9, 12
0, 3, 4, 5,       8, 9, 12
0, 3, 4,    6, 7, 8, 9, 12
0, 3, 4,    6, 7,    9, 12
0, 3, 4,    6,    8, 9, 12
0, 3, 4,    6,       9, 12
0, 3, 4,       7, 8, 9, 12
0, 3, 4,       7,    9, 12
0, 3,    5, 6, 7, 8, 9, 12
0, 3,    5, 6, 7,    9, 12
0, 3,    5, 6,    8, 9, 12
0, 3,    5, 6,       9, 12
0, 3,    5,    7, 8, 9, 12
0, 3,    5,    7,    9, 12
0, 3,    5,       8, 9, 12
0, 3,       6, 7, 8, 9, 12
0, 3,       6, 7,    9, 12
0, 3,       6,    8, 9, 12
0, 3,       6,       9, 12

Here, there are 24 possible combinations. Each time we start with 2n − 1 combinations, but eliminate a few due to having gaps larger than 3.

I don’t really see a pattern in the number of choices that have to be eliminated because of gaps larger than 3:

run lengthchoices
120 = 1
221 = 2
322 = 4
423 − 1 = 7
524 − 3 = 13
625 − 8 = 24
726 − 20 = 44
827 − 47 = 81

I do notice that any combinations eliminated in one row are also eliminated in all subsequent rows, so maybe it could be defined recursively in terms of doubling the previous entry and removing some more rows:

run length nchoices f(n)
11 = 1
22 × f(1) = 2
32 × f(2) = 4
42 × f(3) − 1 = 7
52 × f(4) − 1 = 13
62 × f(5) − 2 = 24
72 × f(6) − 4 = 44
82 x f(7) − 7 = 81

This is starting to make sense. When I write out the combinations in order to count the rows, the number of rows I have to remove each time consists of a pattern from one of the earlier entries but with three missing adapters in front of it. (I’m not sure if this is a good way to explain it, but maybe more visually: to get from the combinations for five ones to the combinations for six ones that I wrote out above, I add one to all the numbers except zero, insert a column of threes, copy all the lines and paste them below the existing lines, delete the threes from the newly-pasted lines, and then delete the last two rows since they start with 0, 3, 7 which is not allowed. The number of rows that I delete at the end corresponds to the number of rows in an earlier iteration of the pattern.) I predict that a run of nine ones is going to produce 149 choices, or 2 × 81 − 13, and when I write them out to make sure, that turns out to be correct: so I’m guessing that for larger n, f(n) = 2 × f(n − 1) − f(n − 4).

This is by no means a mathematical-level rigorous proof, but I have a working hypothesis that successfully predicted the next result, which is good enough for me to start coding. If this were not a one-off puzzle I would start by verifying the worked examples in the puzzle description, but I will just write the code and see if the first answer I get is correct.

I then laugh out loud as I realize that the totally unnecessary use of group_by() in Part 1 is actually a good way to implement Part 2.

let differences = adapters.iter().tuple_windows().map(|(j1, j2)| j2 - j1);
let groups = differences.group_by(|d| *d);
let total: u64 = groups
    .into_iter()
    .filter(|(key, _)| *key == 1)
    .map(|(_, group)| possible_configurations(group.count()))
    .product();
println!("{}", total);

// ...

fn possible_configurations(run_length: usize) -> u64 {
    match run_length {
        n if n < 1 => panic!("Bad value"),
        1 => 1,
        2 => 2,
        3 => 4,
        4 => 7,
        n => 2 * possible_configurations(n - 1) - possible_configurations(n - 4),
    }
}

I stumble over the return value of group_by() not being an iterator, and not having an iter() method like Vec but instead an into_iter() method. And as in Part 1, the *s are all the compiler’s idea.

Running this gives me the correct answer.

Afterword

I am now curious whether all the trouble I went to, to figure out the number of configurations for long runs of adapters with differences of 1 between them, was actually necessary. With a debug print I find that it wasn’t: the longest run of ones in the input is four. (And in hindsight I can tell that the n => line was never reached, because I initially forgot to multiply it by 2, but still got the correct answer!) I guess the lesson here is, when doing programming puzzles, check the input first, and see if you can get away with not handling cases that aren’t present!

That makes two paths that I took, and spent a lot of time on, that weren’t wrong as such, but were unnecessary. (The second one being, all the time I spent in Part 1 looking for an Itertools method that would count the occurrences in differences even though I knew how to write it with a simple for loop.) Both of them were caused by trying to be too clever. I should learn that for these Advent of Code puzzles, a clever solution doesn’t matter, it only matters that it’s correct! I should have taken my own advice that I wrote in the introduction to this blog post.

I also notice that today’s episode has been much more about figuring out what code to write, than about learning Rust. Once I had figured that out, I wrote the code, added whatever & or * operators the compiler told me to, and for the most part it worked.

I still wish I would understand enough to get the & and * operators right the first time. I suspect that if I set up my editor to show Rust types when hovering over an identifier, or something like that, then I’d be more aware of where I was working with a borrowed type, and be able to write the code accordingly.


[1] Debug printing is good for something, after all

Advent of Rust 9: Find That Number, (F)or Else

Welcome again to the not-so-stream-of-consciousness log, where the puns in the titles get worse every day. Today’s topic is the same as every day’s topic: me teaching myself the Rust programming language by doing programming puzzles from Advent of Code 2020.

Day 9, Part 1

Today’s puzzle is to analyze a long list of numbers, pretending that we are breaking an encryption scheme! The answer to the puzzle is the first number in the list (starting at position 26) that is not the sum of two numbers out of the “preamble” consisting of the previous 25 numbers in the list. Wow, that’s a technically correct but very confusing way to say it. Imagine, if you will, a snake moving through the list whose head is one number and whose tail is 25 numbers. If the snake’s head does not equal the sum of any two of the numbers from the snake’s tail, then the head number is the answer.1

As usual I start with cargo new puzzle9, download the input file, and set up puzzle9.rs with the boilerplate, as I did with puzzle8.rs yesterday.

Someone else might know a more efficient way to solve this,2 but I’m going to try to solve it with brute force and Itertools! I will use tuple_windows() to iterate through windows of length 26, and check the tuple_combinations() of the first 25 numbers of the window. I add itertools to Cargo.toml and use itertools::Itertools; to the top of the file.

First I write a map(|s| s.parse().unwrap()) that parses the numbers, then I try to iterate through windows. I’m soon disappointed that tuple_windows() only supports up to a window length of 4! I put the items into a vector instead and implement the window iteration myself, by taking a slice of &numbers[from..to].

Since I need to stop the tuple_combinations() loop when a sum is found, but stop the tuple_windows() loop when the inner loop is not stopped, I am wondering if Rust has a for-else construct like Python does. I google “rust for else” but find that it does not, although I do read that the loop expression (which I am seeing now for the first time) can actually return a value by using break value;, which is something I’ve never encountered before in a programming language! I wonder if the for loop can do this too? I read a bit more and find that no, it cannot.

Ugh, I don’t much like the found = true idiom ever since I learned about Python’s for-else, but nothing to do I guess, unless I want to refactor this into a separate function. And I don’t! I just cram it all in one main() function:

fn main() -> Result<(), io::Error> {
    let file = fs::File::open("input")?;
    let numbers: Vec<u64> = read_lines(file).map(|s| s.parse().unwrap()).collect();

    let window_size = 25;
    let mut answer = None;
    for ix in window_size..numbers.len() {
        let preamble = &numbers[(ix - window_size)..ix];
        let mut valid = false;
        for (a, b) in preamble.iter().tuple_combinations() {
            if a + b == numbers[ix] {
                valid = true;
                break;
            }
        }
        if !valid {
            answer = Some(numbers[ix]);
            break;
        }
    }

    println!("{}", answer.unwrap());

    Ok(())
}

Some interesting mistakes that I made:

  • I originally tried to parse the file as a list of u32 because I didn’t scroll down far enough and see that there were huge numbers, so I got a panic on parse().
  • I made the window_size 5 initially instead of 25, because I was confused with the example given in the text.
  • I forgot all the muts on my variables.
  • I thought I was being clever by making answer an Option, but then I was not clever enough to remember to assert that the answer was actually found, with unwrap().

Despite the mistakes I was happy to see that the compiler could infer the type of parse() without having to specify parse::<u64>().

This program gives me the answer, and so I can unlock Part 2 of the puzzle.

Day 9, Part 2

This is the first Part 2 of a puzzle that actually uses the answer from Part 1! So I don’t need the is_part2() function today.

This time, I must find a contiguous set of at least two numbers in the list that add up to the answer of Part 1. The answer to Part 2 is the sum of the smallest and largest number in that set.

I’m going to have to do a lot more iteration over sliding windows of the list in this one! That tuple_windows() iterator sure would be nice. I do a bit more searching and find what I hadn’t realized before: you can do sliding windows of arbitrary size with windows(), on a slice, just not on an iterator. I’d really prefer to use windows(),3 so maybe I can refactor Part 1 to do that before I write Part 2.

for window in numbers.windows(window_size + 1) {
    let preamble = &window[..window_size];
    let number = *window.last().unwrap();
    let mut valid = false;
    for (a, b) in preamble.iter().tuple_combinations() {
        if a + b == number {
            valid = true;
            break;
        }
    }
    if !valid {
        answer = Some(number);
        break;
    }
}

This is a bit more readable!

Now to write Part 2. I will start with sliding windows of 2 contiguous elements and keep increasing the window size until I find the answer:

fn encryption_weakness(numbers: &[u64], invalid_number: u64) -> Option<u64> {
    for window_size in 2..numbers.len() {
        for window in numbers.windows(window_size) {
            if window.iter().sum::<u64>() == invalid_number {
                return Some(window.first().unwrap() + window.last().unwrap());
            }
        }
    }
    None
}

I get this to compile without too much trouble. I have to specify the type of sum::<u64> and I don’t understand why, similar to an error I got a few days ago. Helpfully, cargo clippy tells me to use &[u64] as the type of the first parameter instead of &Vec<u64>. Nonetheless, it doesn’t work. The answer is wrong, and this time the website doesn’t say if it’s too high or too low (probably because it’s not relevant.) I debug-print the window of numbers to try to get a clue about why the answer is wrong, and I find out that I added the first and last number in the window, not the largest and smallest number as I was supposed to.

This is a nice excuse to use the Itertools minmax() method, which I scrolled past a few days ago and thought was cool! I now read that it has an enum return type, which luckily I learned about yesterday, so I think I should know how to get an answer out of it. I try this:

let itertools::MinMaxResult::MinMax(largest, smallest) = window.iter().minmax();

I wasn’t sure if let with an enum-pattern would even work, but I decided to try it, as I thought I had seen it elsewhere in an example. I originally thought this would assert that the result was not one of the other variants of the enum (NoElements or OneElement.) But instead, the compiler tells me “let bindings require an ‘irrefutable pattern’, like a struct or an enum with only one variant”, and suggests using if let. That seems like a good suggestion, but instead I peeked into the documentation for itertools::MinMaxResult and decided to use into_option() instead:

let (largest, smallest) = window.iter().minmax().into_option().unwrap();

Other than that, it worked well! I got the right answer and solved the puzzle.

Now that I have a nice-looking encryption_weakness() function, I’d really like to refactor Part 1 to remove this horrible valid = true thing. I create a function invalid_number and that lets me return instead of the outer break statement. In addition, I realize that I can use Iterator::any() to get rid of the inner break statement.

Full code:

use itertools::Itertools;
use std::fs;
use std::io::{self, BufRead};

fn main() -> Result<(), io::Error> {
    let file = fs::File::open("input")?;
    let numbers: Vec<u64> = read_lines(file).map(|s| s.parse().unwrap()).collect();

    let answer = invalid_number(&numbers, 25).unwrap();

    println!("Part 1: {}", answer);
    println!("Part 2: {}", encryption_weakness(&numbers, answer).unwrap());

    Ok(())
}

fn invalid_number(numbers: &[u64], window_size: usize) -> Option<u64> {
    for window in numbers.windows(window_size + 1) {
        let preamble = &window[..window_size];
        let number = window[window_size];
        if !preamble
            .iter()
            .tuple_combinations()
            .any(|(a, b)| a + b == number)
        {
            return Some(number);
        }
    }
    None
}

fn encryption_weakness(numbers: &[u64], invalid_number: u64) -> Option<u64> {
    for window_size in 2..numbers.len() {
        for window in numbers.windows(window_size) {
            if window.iter().sum::<u64>() == invalid_number {
                let (largest, smallest) = window.iter().minmax().into_option().unwrap();
                return Some(largest + smallest);
            }
        }
    }
    None
}

fn read_lines(file: fs::File) -> impl Iterator<Item = String> {
    io::BufReader::new(file).lines().map(|res| res.unwrap())
}

Afterword

I solved this puzzle fairly quickly. I can think of two reasons why: I was relatively familiar with Itertools because I’ve been using it often in the past few days, and I also managed to think of a solution for both parts of the puzzle that was able to be implemented by composing parts of Itertools and the standard library that I was already familiar with, or at least knew what to look for.

What can I say? I just love Itertools. I think having practiced solving Advent of Code puzzles with it, will also make me reach for Python’s itertools more often when I’m programming in Python.

Having now written two functions that return Option<u64>, I do wonder how Rust stores this type internally! Is it two 8-byte words with 63 wasted bits, or is it 9 bytes with 7 wasted bits?

I’m liking the abbreviated style that I’ve been using for the past couple of days and I think I’ll continue it.


[1] I’m not sure that’s clear either, but hopefully it will become clear from the code. Code might be difficult to read, but at least it’s unambiguous

[2] Writing this later, I wonder if a more efficient solution would involve sorting the arrays to eliminate some of the combinations? I don’t plan to spend time on it though

[3] Never thought I’d be writing those words on this blog

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

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

Advent of Rust 5: Help Arrives

Welcome to the latest installment of the stream-of-consciousness log of me trying to learn the Rust programming language by doing the programming puzzles on Advent of Code 2020.

I’ve noticed that these logs, while still long, are becoming shorter. On Day 1 I wrote 6000 words, on Day 2 5000, and on Day 3 and 4 just under 4000. (Today’s is a bit over 3000.) I think that’s because I’m solving the puzzles with fewer mistakes that I have to write about solving! Eventually I expect that I won’t keep writing one post per day because that level of detail won’t be interesting anymore, but let’s see how today goes.

I start off today having gotten several pieces of advice from commenters on the earlier blog posts and from the Rust ❤️ GNOME chat channel, and will use them to improve the boilerplate read_lines() and is_part2() functions that I copy every day. Jan Alexander Steffens noted that to return an iterator of Strings (the task that I failed at yesterday), I don’t have to specify the exact return type, which is what I struggled with, producing a long unreadable type signature that I couldn’t get correct in the end. Instead, I can specify impl Iterator<Item = String>, meaning that it returns a type that implements the iterator interface and the iterator yields String, but that you don’t care about the particulars. Nice!

Perry Lorier mentioned, among other things, that you can make the return type of main() a Result and so use the ? operator to pass errors back to the caller. This is the concise error handling that I was looking for originally on Day 1! Perry also pointed me at this diagram which looks very complicated, but after studying it a bit, I understand better what Ok() and Some() are for, and how to get from one type to the other. This diagram is particularly helpful for shortening the is_part2() function.

Day 5, Part 1

I start out as usual with cargo new puzzle5, copy over read_lines() and is_part2() from yesterday, and start to refactor them using the new knowledge that others have helped me acquire. After some experimentation which I forget to take notes on (but is mostly dealing with compiler errors telling me that I got the Result and Option types slightly wrong,) I have the following boilerplate to start with:

use std::env;
use std::fs;
use std::io::{self, BufRead};
use std::path;

fn main() -> Result<(), io::Error> {
    let lines = read_lines("input")?.collect::<Result<Vec<_>, _>>()?;

    if is_part2() {
        println!("Part 2");
    } else {
        println!("{:?}", &lines[..10]);
    }

    Ok(())
}

fn is_part2() -> bool {
    env::args().nth(1).map(|val| val == "2").unwrap_or(false)
}

fn read_lines<P>(filename: P) -> io::Result<io::Lines<io::BufReader<fs::File>>>
where
    P: AsRef<path::Path>,
{
    let file = fs::File::open(filename)?;
    Ok(io::BufReader::new(file).lines())
}

The final thing that Perry told me about is cargo clippy, which seems to be a command that checks your code and makes suggestions on how to write it more idiomatically. It tells me, for example, that the .and_then(|val| Some(val == "2") that I had at one point in is_part2(), is more cleanly expressed as .map(|val| val == "2").

Now, on to the puzzle! Today’s puzzle is to figure out seat numbers on a weirdly-numbered airplane, where there are 128 rows with 8 seats each, and your boarding pass has seat designations like FBFBBFFRLR where the first F tells you to go to the front half of the airplane, the second character B tells you to go to the back quarter of the front half, etc. The first 7 characters are F or B, telling you which row to go to, and the last three are similarly L or R telling you which seat in that row to sit in (right or left.) Each seat has a “seat ID” that is row × 8 + seat. The answer to the puzzle is the highest seat ID in the given input file containing boarding pass codes.

I spend a moment thinking about how to calculate the range of row numbers that is the back quarter of the front half. Since the airplane has 128 rows, the ranges will all be powers of 2. I briefly think about using nested match statements but that jogs something in my memory and I think: maybe these are actually binary digits in disguise. So I go to my JavaScript console1 and input the example code FBFBBFFRLR as 0b0101100101 — replacing each F and L with a zero, and B and R with a one, and indeed I get 357, which is the seat ID given in the example. I try the next example, BFFFBBFRRR, which is 0b1000110111 or 567, and it checks out too. If this were a real application I’d want to think about it some more, but as it is, I’m satisfied enough to start writing the program.

There are two approaches I could take here: manually turning each B and R into the appropriate power of 2 and adding them all together, or I could use a string replace, followed by parse() (which I know about from Day 1, and I assume it ought to be able to parse binary numbers as well as decimal.) I decide on the latter. Even though it is probably less efficient, it’s not so inefficient that it will make a difference, and I expect it will be faster to write.

For the first time, I’m feeling like I don’t need to google anything, but instead I can go straight to the API documentation. I need to look at the documentation for String to find out how the replace() method works, and how to specify a different arithmetic base to the parse() method. I also guess that there will probably be an iterator method that will exhaust the iterator and give me the largest item, but if there isn’t then I can write one with reduce(), which I’m familiar with from JavaScript.

First I read about replace() but then I realize that since I’m replacing every character in the string anyway, I don’t need it. I actually need something like map(), which I don’t see in the list of methods. But I do know that map() is an iterator method, and to get an iterator over the characters of a string I can use chars(). Then I see char_indices() which will give me each character along with its position in the string, and that makes me think that it might be easier after all to turn the letters into powers of 2 and add them together. And then I see bytes(), which would be even more appropriate because there are only four possible one-byte characters in the strings, but I don’t see a corresponding byte_indices() method. But anyway, it doesn’t matter, because we can use enumerate() on the iterator returned from bytes().

I will then need to get the sum of the elements in one iterator (the powers of 2), and the greatest element of the other iterator (the boarding pass codes in the file), and so I click through to the Iterator documentation and see that these methods are called sum() and max(), respectively.

There is one thing that I do have to google: how to do exponentiation and/or bit shifts in Rust. I find that there is a left-shift << operator which will work fine for me.

Here’s the program I write:

let lines = read_lines("input")?;
let largest_seat_id = lines.map(|s| code_to_seat_id(s?)).max();
println!("{}", largest_seat_id);

// [...]

fn code_to_seat_id(line: String) -> u16 {
    let maxbyte = line.len() - 1;
    line.bytes()
        .enumerate()
        .map(|(index, byte): (usize, &u8)| {
            let digit = match byte {
                b'B' | b'R' => 1,
                _ => 0,
            };
            digit << (maxbyte - index);
        })
        .sum()
}

I was so hoping that I might have understood things well enough to write a program that ran the first time, but no such luck:

error[E0277]: the `?` operator can only be used in a closure that returns `Result` or `Option` (or another type that implements `Try`)
  --> src/main.rs:12:61
   |
12 |         let largest_seat_id = lines.map(|s| code_to_seat_id(s?)).max();
   |                                         --------------------^^-
   |                                         |                   |
   |                                         |                   cannot use the `?` operator in a closure that returns `u16`
   |                                         this function should return `Result` or `Option` to accept `?`
   |
   = help: the trait `Try` is not implemented for `u16`
   = note: required by `from_error`

error[E0277]: `Option<u16>` doesn't implement `std::fmt::Display`
  --> src/main.rs:13:24
   |
13 |         println!("{}", largest_seat_id);
   |                        ^^^^^^^^^^^^^^^ `Option<u16>` cannot be formatted with the default formatter
   |
   = help: the trait `std::fmt::Display` is not implemented for `Option<u16>`
   = note: in format strings you may be able to use `{:?}` (or {:#?} for pretty-print) instead
   = note: required by `std::fmt::Display::fmt`
   = note: this error originates in a macro (in Nightly builds, run with -Z macro-backtrace for more info)

error[E0631]: type mismatch in closure arguments
  --> src/main.rs:23:10
   |
23 |         .map(|(index, byte): (usize, &u8)| {
   |          ^^^ ----------------------------- found signature of `for<'r> fn((usize, &'r u8)) -> _`
   |          |
   |          expected signature of `fn((usize, u8)) -> _`

error[E0599]: no method named `sum` found for struct `Map<Enumerate<std::str::Bytes<'_>>, [closure@src/main.rs:23:14: 29:10]>` in the current scope
   --> src/main.rs:30:10
    |
23  |           .map(|(index, byte): (usize, &u8)| {
    |                -----------------------------
    |                |
    |                doesn't satisfy `<_ as FnOnce<((usize, u8),)>>::Output = _`
    |                doesn't satisfy `_: FnMut<((usize, u8),)>`
...
30  |           .sum()
    |            ^^^ method not found in `Map<Enumerate<std::str::Bytes<'_>>, [closure@src/main.rs:23:14: 29:10]>`
    |
    = note: the method `sum` exists but the following trait bounds were not satisfied:
            `<[closure@src/main.rs:23:14: 29:10] as FnOnce<((usize, u8),)>>::Output = _`
            which is required by `Map<Enumerate<std::str::Bytes<'_>>, [closure@src/main.rs:23:14: 29:10]>: Iterator`
            `[closure@src/main.rs:23:14: 29:10]: FnMut<((usize, u8),)>`
            which is required by `Map<Enumerate<std::str::Bytes<'_>>, [closure@src/main.rs:23:14: 29:10]>: Iterator`
            `Map<Enumerate<std::str::Bytes<'_>>, [closure@src/main.rs:23:14: 29:10]>: Iterator`
            which is required by `&mut Map<Enumerate<std::str::Bytes<'_>>, [closure@src/main.rs:23:14: 29:10]>: Iterator`

The third and fourth errors I’ve dealt with before; in that case I was missing a & operator on the tuple type of the argument of the function that I passed to map(). Here, though, judging from the error message, it seems I have an & operator that isn’t supposed to be there, so I remove it and the last two error messages disappear. I’m not sure why this is; it seems like the byte should be owned by the string, but maybe bytes are passed by value?

For the first error, I understand why it’s complaining: I need to use unwrap() there, because |s| code_to_seat_id(...) doesn’t return a Result or Option, so I cannot use the ? operator to handle errors.

The second error I do understand what it’s asking me to do, but I don’t understand why, until I go and read the documentation for max() again, and see that it returns an Option which is None in the case where the iterator is empty. This is a really nice example of how Rust forces you to handle all possible errors, because that is definitely a case that I would have forgotten about! So I add an extra ? to the end of that line.

Now I have two new errors:

error[E0277]: `?` couldn't convert the error to `std::io::Error`
  --> src/main.rs:12:79
   |
6  | fn main() -> Result<(), io::Error> {
   |              --------------------- expected `std::io::Error` because of this
...
12 |         let largest_seat_id = lines.map(|s| code_to_seat_id(s.unwrap())).max()?;
   |                                                                               ^ the trait `From<NoneError>` is not implemented for `std::io::Error`
   |
   = note: the question mark operation (`?`) implicitly performs a conversion on the error value using the `From` trait
   = help: the following implementations were found:
             <std::io::Error as From<ErrorKind>>
             <std::io::Error as From<IntoInnerError<W>>>
             <std::io::Error as From<NulError>>
   = note: required by `from`
help: consider converting the `Option<T>` into a `Result<T, _>` using `Option::ok_or` or `Option::ok_or_else`
   |
12 |         let largest_seat_id = lines.map(|s| code_to_seat_id(s.unwrap())).max().ok_or_else(|| /* error value */)?;
   |                                                                               ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

error[E0277]: the trait bound `u16: Sum<()>` is not satisfied
  --> src/main.rs:30:10
   |
30 |         .sum()
   |          ^^^ the trait `Sum<()>` is not implemented for `u16`
   |
   = help: the following implementations were found:
             <u16 as Sum<&'a u16>>
             <u16 as Sum>

It seems that my last adjustment wasn’t correct, the ? unwraps the Option but the return type of main() is Result, not Option. So I guess I can’t directly use the ? operator there either. The compiler suggests providing the Error value using ok_or_else(), but I decide to unwrap() this as well.

I have to stare at the second error for a while, but the () in Sum<()>, which I learned a few days ago means “the empty type”, finally gives me the clue. I have put a semicolon at the end of digit << (maxbyte - index) and if I delete the semicolon, the program works. I’m guessing the semicolon turns that line into a statement which doesn’t do anything, instead of the expression to be returned from the function! This makes it seem like you have to be really careful when writing an inline function without an explicit return type! This seems like something that the compiler could generate a better error message about. For example, my function here is used as an argument to map(), and it seems probable that you would want the mapped function to return a value.

Anyway, the answer I get is the correct answer according to the Advent of Code website, so on to Part 2.

Here’s the correct code (without the boilerplate):

fn main() -> Result<(), io::Error> {
    let lines = read_lines("input")?;
    let largest_seat_id = lines.map(|s| code_to_seat_id(s.unwrap())).max().unwrap();
    println!("{}", largest_seat_id);
    Ok(())
}

fn code_to_seat_id(line: String) -> u16 {
    let maxbyte = line.len() - 1;
    line.bytes()
        .enumerate()
        .map(|(index, byte): (usize, u8)| {
            let digit = match byte {
                b'B' | b'R' => 1,
                _ => 0,
            };
            digit << (maxbyte - index)
        })
        .sum()
}

Day 5, Part 2

Part 2 seems really simple at first glance, but that probably means it’s more difficult than it looks. The puzzle is to find your seat ID. Some seats at the front and the back of the plane are missing, but all the others are full, and you know you are not sitting in the very first or very last seat. So your seat ID is the one that is missing in the input file, but with the IDs on either side of it present.

I think we should probably start by sorting the seat IDs. I look up in the Vec documentation how to sort a vector, and I read under sort() that sort_unstable() is preferred if it’s OK for equal elements to be reordered. We should not have any equal elements at all in this vector anyway, so I use that. I change the main() function into this:

fn main() -> Result<(), io::Error> {
    let lines = read_lines("input")?;
    let seat_ids = lines.map(|s| code_to_seat_id(s.unwrap()));

    if is_part2() {
        let sorted = seat_ids.collect().sort_unstable();
        println!("{:?}", sorted);
    } else {
        let largest_seat_id = seat_ids.max().unwrap();
        println!("{}", largest_seat_id);
    }

    Ok(())
}

There’s one error, suggesting that I should specify the type on collect(), which is actually an error I’ve run into before. Perry explained to me why this happens: collect() can actually do several things, so sometimes you need to specify the type so that it knows which thing you want it to do. I change it to collect::<Vec<u16>>() and the program runs.

I get no output though! Or, to be precise, I get the output () which is the empty type. I go back and read again about what sort_unstable() does: the signature is sort_unstable(&mut self) and I don’t see a return value! So it’s a method that changes the original vector. I change that line to the following, also taking the opportunity to specify the type as an annotation on the variable sorted instead of as a type parameter to collect():

let mut sorted: Vec<u16> = seat_ids.collect();
sorted.sort_unstable();

I run the program and get a bunch of numbers! Looks like it’s working. Theoretically, if I spotted the missing number in here, then I’d have the answer to the problem — but I don’t happen to see it, and I don’t want to search through 800 numbers.

I think a simple way to find out which number is missing would be to iterate through the list and stop at the first number that isn’t equal to the previous number plus one. If this were Python and I was using NumPy, I might have the data in an ndarray, where I could rotate the array by 1 and subtract the rotated array from the original array; but I assume Rust arrays don’t work like that.

Instead I remember seeing a method for examining successive elements in an iterator, when I was browsing the itertools package on Day 1. I go to the documentation and find the method, which is called tuple_windows(). I can use that to iterate over all windows of two adjacent seat numbers, and then use find_position() to give me the first one where the two numbers are not sequential!

Here’s what I write:

let seat_number = sorted
    .iter()
    .tuple_windows()
    .find_position(|seats: &(u16, u16)| seats.1 != seats.0 + 1)
    .unwrap()
    .1
     .0
    + 1;
println!("{}", seat_number);

The .1.0 + 1 at the end is a bit cryptic: find_position().unwrap() will give me a tuple of (position, item) from the iterator, which is iterating over pairs of u16, so the type is something like (usize, (u16, u16)). I add one at the end, because .1.0 gives me the seat before the missing seat, so I add one to get the missing seat ID.

Of course it doesn’t work the first time; I’ve forgotten to add use itertools::Itertools; But after doing that I get the following errors:

error[E0271]: type mismatch resolving `<(u16, u16) as itertools::tuple_impl::TupleCollect>::Item == &u16`
  --> src/main.rs:16:14
   |
16 |             .tuple_windows()
   |              ^^^^^^^^^^^^^ expected `u16`, found `&u16`

error[E0271]: type mismatch resolving `<(u16, u16) as itertools::tuple_impl::TupleCollect>::Item == &u16`
  --> src/main.rs:17:14
   |
17 |             .find_position(|seats: &(u16, u16)| seats.1 != seats.0 + 1)
   |              ^^^^^^^^^^^^^ expected `u16`, found `&u16`
   |
   = note: required because of the requirements on the impl of `Iterator` for `TupleWindows<std::slice::Iter<'_, u16>, (u16, u16)>`

error[E0271]: type mismatch resolving `<(u16, u16) as itertools::tuple_impl::TupleCollect>::Item == &u16`
  --> src/main.rs:14:27
   |
14 |           let seat_number = sorted
   |  ___________________________^
15 | |             .iter()
16 | |             .tuple_windows()
17 | |             .find_position(|seats: &(u16, u16)| seats.1 != seats.0 + 1)
   | |_______________________________________________________________________^ expected `u16`, found `&u16`

I’m still not getting the & operators right! I think this might mean that the type of seats has to be &(&u16, &u16), which I don’t understand, because I just had to remove the & operator from something similar in Part 1! Maybe an explanation that makes sense could be that the tuple_windows() values are borrowed from the original iterator? When I make that change, the errors disappear, and I get a different error:

error[E0277]: can't compare `&u16` with `u16`
  --> src/main.rs:17:59
   |
17 |             .find_position(|seats: &(&u16, &u16)| seats.1 != seats.0 + 1)
   |                                                           ^^ no implementation for `&u16 == u16`
   |
   = help: the trait `PartialEq<u16>` is not implemented for `&u16`

Now this error I find really puzzling. Why shouldn’t I be able to compare a reference to u16 with a u16? I google “rust compare u16 with &u16” and I find a Stack Overflow post with the relevant title “Why isn’t it possible to compare a borrowed integer to a literal integer?” The answer isn’t all that satisfying because I’m skeptical of the rationale that the answer gives, but it does tell me what to do: seats.1.clone() or *seats.1.

I also take the opportunity to refactor the code to use destructuring to get rid of that ugly .1.0:

let (_, (seat_before, _)) = sorted
    .iter()
    .tuple_windows()
    .find_position(|seats: &(&u16, &u16)| *seats.1 != seats.0 + 1)
    .unwrap();
println!("{}", seat_before + 1);

This gives me an answer, which I put in to the Advent of Code website, and it’s correct! Hooray!

Here’s the full code, again minus boilerplate:

use itertools::Itertools;

fn main() -> Result<(), io::Error> {
    let lines = read_lines("input")?;
    let seat_ids = lines.map(|s| code_to_seat_id(s.unwrap()));

    if is_part2() {
        let mut sorted: Vec<u16> = seat_ids.collect();
        sorted.sort_unstable();
        let (_, (seat_before, _)) = sorted
            .iter()
            .tuple_windows()
            .find_position(|seats: &(&u16, &u16)| *seats.1 != seats.0 + 1)
            .unwrap();
        println!("{}", seat_before + 1);
    } else {
        let largest_seat_id = seat_ids.max().unwrap();
        println!("{}", largest_seat_id);
    }

    Ok(())
}

fn code_to_seat_id(line: String) -> u16 {
    let maxbyte = line.len() - 1;
    line.bytes()
        .enumerate()
        .map(|(index, byte): (usize, u8)| {
            let digit = match byte {
                b'B' | b'R' => 1,
                _ => 0,
            };
            digit << (maxbyte - index)
        })
        .sum()
}

Afterword

I am starting to feel more and more confident writing Rust. I do still feel like the code I write is clunky and not idiomatic, and probably will for quite some time yet! So by “confident” I don’t mean I’m a good Rust programmer, but what I mean is I’m just starting to lose the feeling of having no idea what I’m doing.

Work From Home Reaction GIF - Find & Share on GIPHY
This is what Day 1 looked like

It has been very helpful to get comments on these posts, as I was able to put some of the tips to good use today. It’s good to not be learning in a vacuum! Another thing that really made today’s exercises go faster was the experience of getting errors that I had already encountered a few days ago, and knowing roughly how to solve them.


[1] Is there a Rust REPL?

Advent of Rust 4: It’s Hard to Return an Iterator

Welcome again to this stream-of-consciousness log about learning the Rust programming language by doing the programming puzzles in Advent of Code 2020, or as I like to call it, On the Code by Jack Kerouac.1 Let’s get on with it!

Day 4, Part 1

I start with cargo new puzzle4 and copying over the code from yesterday, but this time I’d like to refactor it a bit. I would like to write a function is_part2() that tells you whether the solution for Part 2 of the puzzle was requested or not, and I would like to change read_lines() so that it already does the expect() calls that I am copy-pasting every day, rather than returning a Result of an iterator of Results of strings.

Changing read_lines() really does not work for me. I can’t figure out how to return an iterator from the function! Well, clearly the function is already returning an iterator, but I can’t figure out how to express the iterator that I want to return, as a return type.

What I want is this:

fn read_lines<P>(filename: P) -> ???
where
    P: AsRef<path::Path>,
{
    let file = fs::File::open(filename).expect("Bad file");
    io::BufReader::new(file)
        .lines()
        .map(|s| s.expect("Bad line in file"))
}

where ??? ought to be something like Iterator<String>. But I cannot figure out how to write an iterator type. The iterator types that are returned from standard library functions all seem to be type aliases of some sort. For example, io::Lines is the iterator that lines() returns, and I know it is an iterator of Results of strings, because the documentation says so, but I don’t know how to build my own iterator type.

I google “rust return iterator” and the first result is encouragingly titled “Returning Rust Iterators”. This article suggests asking the compiler by returning the empty type () and letting it suggest what to return instead, so I do that.

Unfortunately, I get a type that I don’t think I can put into my program! The compiler says “expected unit type (), found struct Map<std::io::Lines<BufReader<File>>, [closure@src/main.rs:31:14: 31:46]>” I am guessing that referring to a type by the file in which it’s found and the lines and columns that it spans, is not legal Rust syntax!

So I try poking around with no success. By trying things and following the compiler’s suggestions, I end up with the awkward return type of iter::Map<io::Lines<io::BufReader<fs::File>>, dyn FnMut(io::Result<&String>) -> &String>, but this is still producing errors about lifetimes that I don’t understand. So I give up on this idea.

However, maybe I can write read_lines() so that it at least calls expect() on the io::Lines iterator that it returns:

fn read_lines<P>(filename: P) -> io::Lines<io::BufReader<fs::File>>
where
    P: AsRef<path::Path>,
{
    let file = fs::File::open(filename).expect("Bad file");
    io::BufReader::new(file).lines()
}

To be clear, I don’t really understand the P: AsRef<path::Path> part either. I guess I will try to refactor this again in a few days when I have learned a bit more.

Writing is_part2(), on the other hand, is quite straightforward:

fn is_part2() -> bool {
    let args: Vec<String> = env::args().collect();
    let default = String::from("1");
    let arg = args.get(1).unwrap_or(&default);
    arg == "2"
}

This works, but I actually think that I might be able to make this even nicer by using a match statement. I haven’t encountered the match statement directly yet, but I’ve seen it in several google results over the past few days. I google “rust match syntax”, land here, and come up with this:

fn is_part2() -> bool {
    match env::args().nth(1) {
        Some("2") => true,
        _ => false,
    }
}

This almost works, but I have to replace "2" with String::from("2"), and then the compiler tells me that I have to take it out of the match statement, because function calls are not allowed in pattern matching. So in the end it looks like this:

fn is_part2() -> bool {
    let string2 = String::from("2");
    match env::args().nth(1) {
        Some(string2) => true,
        _ => false,
    }
}

The funny thing is, though, that the compiler warns that string2 is an unused variable in both of the places that it is used! It seems like I haven’t understood this well enough. I google “rust match string” and land on a Stack Overflow question titled “How to match a String against string literals in Rust?”, but that is actually only good for when you know that you already have a String! But I have an Option<String>, so I google “rust match option string”, and find another Stack Overflow post with the topic “How can I pattern match against an Option<String>?”. The helpful answer says this is a known limitation of pattern-matching, but suggests two things to do instead. The second solution looks good to me, so I implement it:

fn is_part2() -> bool {
    match env::args().nth(1) {
        Some(s) if s == "2" => true,
        _ => false,
    }
}

This works, and looks like what I had in mind. Time to start on the puzzle!

Today’s puzzle is processing records that represent “passports”. These records consist of whitespace-separated key:value pairs, and records are separated by blank lines. There are eight possible keys, each consisting of three letters. The cid key is optional, and all the others are required. A record is valid if it contains all the required keys. The answer to the puzzle is the number of valid passports in the input file.

I start out by downloading the input file and put it in the project directory, as usual.

So first I think a bit about how I will process the data into records. My usual approach so far has been to split the file into lines and process each line using a chain of iterators, but maybe it’s better to let go of that approach for today. I could read the whole file into a string and split it on the blank lines in order to get an array where each element is a record, and then process each record. Or I could still process the file line-by-line, and use a for loop while keeping the notion of a “current” record, which I push into a vector when it is completed. I think I like that idea best so far.

The records can be hash sets, where I store the keys. That’s a bit wasteful since really all I need is one bit for each of the 8 possible keys, to tell whether the record has it or not! (I can ignore the values for now, since I only need to look at the keys.) But I decide to be wasteful nonetheless, for two reasons: first, I suspect Part 2 of the puzzle will require me to do something with the values, but if Rust is like other languages, a hash set will be easy enough to refactor into a hash map. Second, stuffing the string keys into a hash set or hash map is simple, and I won’t have to write code that translates key strings into record fields.

To make a first attempt, I google “rust hash set” and read the Rust by Example page. It’s interesting that you don’t have to specify the type of a HashSet, the compiler can figure it out by what you insert into it!

I also have to look in the API documentation for how to split a string on whitespace, but it seems there is conveniently a split_whitespace() method.

Here’s my attempt:

use std::collections::HashSet;
use std::env;
use std::fs;
use std::io::{self, BufRead};
use std::path;

fn main() {
    let mut passports = vec![];
    let mut current = HashSet::new();
    for line in read_lines("input").map(|s| s.expect("Bad line in file")) {
        if line == "" {
            passports.push(current);
            current = HashSet::new();
        }
        current = current.union(get_keys_from_line(&line));
    }

    if is_part2() {
        println!("part 2");
    } else {
        println!("the first passport is {:?}", passports[0]);
    }
}

fn get_keys_from_line(line: &str) -> HashSet<String> {
    let mut new_keys = HashSet::new();
    for pair in line.split_whitespace() {
        new_keys.insert(String::from(&pair[..3]));
    }
    new_keys
}

It looks like I got several & operators right this time, even though I still got one wrong:

error[E0308]: mismatched types
  --> src/main.rs:15:33
   |
15 |         current = current.union(get_keys_from_line(&line));
   |                                 ^^^^^^^^^^^^^^^^^^^^^^^^^
   |                                 |
   |                                 expected `&HashSet<_>`, found struct `HashSet`
   |                                 help: consider borrowing here: `&get_keys_from_line(&line)`
   |
   = note: expected reference `&HashSet<_>`
                 found struct `HashSet<String>`

error[E0308]: mismatched types
  --> src/main.rs:15:19
   |
15 |         current = current.union(get_keys_from_line(&line));
   |                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `HashSet`, found struct `std::collections::hash_set::Union`
   |
   = note: expected struct `HashSet<_>`
              found struct `std::collections::hash_set::Union<'_, _, RandomState>`

I need a & on the return value of get_keys_from_line(), and it appears I didn’t read the documentation of union() well enough because it returns an iterator, not another hash set, so I need to add collect() after it. I’m momentarily confused since I thought collect() created a vector from an iterator, not a hash set! But I see that the examples in the documentation for union() are doing it like that, so I assume it must be OK. I’m also wondering if there isn’t a more idiomatic way to do what I’m trying to do (I’m thinking of Python’s dict.update()) but I decide to leave it for now.

Now I get this error:

error[E0277]: a value of type `HashSet<String>` cannot be built from an iterator over elements of type `&String`
  --> src/main.rs:15:61
   |
15 |         current = current.union(&get_keys_from_line(&line)).collect();
   |                                                             ^^^^^^^ value of type `HashSet<String>` cannot be built from `std::iter::Iterator<Item=&String>`
   |
   = help: the trait `FromIterator<&String>` is not implemented for `HashSet<String>`

At least I think I know enough to understand this error message now; the union() iterator is giving me the &String values that are owned by the original two hash sets (current and the temporary object returned from get_keys_from_line()). I don’t own them, so I can’t insert them into a hash set of values that I’m supposed to own.

Hmm, this is not what I wanted at all. What I actually wanted was an update() method that would move the elements from the second set into the first set. I start to think this might have been easier after all if I’d used 8 bits to store whether the keys were present… 😝

I google “rust hashset update” and land on this encouragingly titled Stack Overflow post: “How can I insert all values of one HashSet into another HashSet?” It comes as a surprise to me that there is an extend() method for this! I guess as the commenter says under that post,

Plus it teaches me that I should not only look at the ‘methods’ section of the doc to find methods, but also into the traits a struct implements.

I guess I’ve learned that too now! Wow, that really is confusing, that a note down at the bottom of the API documentation page saying only impl<T, S> Extend<T> for HashSet<T, S> is actually telling you that there is an extend() method.

Regardless, I change the line to read current.extend(&get_keys_from_line(&line)); and I don’t quite get what I want either:

error[E0716]: temporary value dropped while borrowed
  --> src/main.rs:15:25
   |
12 |             passports.push(current);
   |                            ------- borrow later used here
...
15 |         current.extend(&get_keys_from_line(&line));
   |                         ^^^^^^^^^^^^^^^^^^^^^^^^^ - temporary value is freed at the end of this statement
   |                         |
   |                         creates a temporary which is freed while still in use
   |
   = note: consider using a `let` binding to create a longer lived value

This is another head-scratcher. I don’t see why it should matter that the temporary value is freed, when I thought I was moving all the elements out of it and into current! From reading about ownership yesterday, I thought I understood that ownership of values is always moved into function calls, unless they are borrowed with the & operator.

But while I was browsing the HashSet documentation I do remember coming across the drain() method and wondering if that would be useful. Maybe the problem is that the ownership of the values isn’t getting transferred, and I need to drain() them out of the temporary object so that current owns them. I change the line to current.extend(get_keys_from_line(&line).drain()); and it works!

So, I file away the knowledge that the operation I think of as a.update(b) is written as a.extend(b.drain()) in Rust. I wonder if that is actually the idiomatic way to do it?

Now that I have the data in the form that I wanted, I can write the code to get the answer:

let count = passports.iter().filter(passport_is_valid).count();
println!("{}", count);

// [...]

fn passport_is_valid(passport: &HashSet<String>) -> bool {
    let n_keys = passport.len();
    n_keys == 8 || (n_keys == 7 && !passport.contains("cid"))
}

But this doesn’t work:

error[E0631]: type mismatch in function arguments
  --> src/main.rs:21:45
   |
21 |         let count = passports.iter().filter(passport_is_valid).count();
   |                                             ^^^^^^^^^^^^^^^^^ expected signature of `for<'r> fn(&'r &HashSet<String>) -> _`
...
26 | fn passport_is_valid(passport: &HashSet<String>) -> bool {
   | -------------------------------------------------------- found signature of `for<'r> fn(&'r HashSet<String>) -> _`

error[E0599]: no method named `count` found for struct `Filter<std::slice::Iter<'_, HashSet<String>>, for<'r> fn(&'r HashSet<String>) -> bool {passport_is_valid}>` in the current scope
    --> src/main.rs:21:64
     |
21   |           let count = passports.iter().filter(passport_is_valid).count();
     |                                                                  ^^^^^ method not found in `Filter<std::slice::Iter<'_, HashSet<String>>, for<'r> fn(&'r HashSet<String>) -> bool {passport_is_valid}>`
     |
     = note: the method `count` exists but the following trait bounds were not satisfied:
             `<for<'r> fn(&'r HashSet<String>) -> bool {passport_is_valid} as FnOnce<(&&HashSet<String>,)>>::Output = bool`
             which is required by `Filter<std::slice::Iter<'_, HashSet<String>>, for<'r> fn(&'r HashSet<String>) -> bool {passport_is_valid}>: Iterator`
             `for<'r> fn(&'r HashSet<String>) -> bool {passport_is_valid}: FnMut<(&&HashSet<String>,)>`
             which is required by `Filter<std::slice::Iter<'_, HashSet<String>>, for<'r> fn(&'r HashSet<String>) -> bool {passport_is_valid}>: Iterator`
             `Filter<std::slice::Iter<'_, HashSet<String>>, for<'r> fn(&'r HashSet<String>) -> bool {passport_is_valid}>: Iterator`
             which is required by `&mut Filter<std::slice::Iter<'_, HashSet<String>>, for<'r> fn(&'r HashSet<String>) -> bool {passport_is_valid}>: Iterator`

Well, I saw an error just like this yesterday, and it was a missing & operator on the type of the function parameter. But I already have a & there! I try putting a second one (since the error message also has two of them) and sure enough, it works. I get an answer, but it’s the wrong answer.

According to the Advent of Code website, my answer is too low. I look over my code again and I see that I forgot to add the last passport to my vector of passports! Maybe that’s the problem? I add passports.push(current); below the loop, run the program again, and yes, I get an answer that’s one more than the previous answer. This time, it’s correct according to the website.

Here’s the full code (I’ll start leaving out the definitions of is_part2() and read_lines() each time unless they change, though):

use std::collections::HashSet;

fn main() {
    let mut passports = vec![];
    let mut current = HashSet::new();
    for line in read_lines("input").map(|s| s.expect("Bad line in file")) {
        if line == "" {
            passports.push(current);
            current = HashSet::new();
        }
        current.extend(get_keys_from_line(&line).drain());
    }
    passports.push(current);

    if is_part2() {
        println!("part 2");
    } else {
        let count = passports.iter().filter(passport_is_valid).count();
        println!("{}", count);
    }
}

fn passport_is_valid(passport: &&HashSet<String>) -> bool {
    let n_keys = passport.len();
    n_keys == 8 || (n_keys == 7 && !passport.contains("cid"))
}

fn get_keys_from_line(line: &str) -> HashSet<String> {
    let mut new_keys = HashSet::new();
    for pair in line.split_whitespace() {
        new_keys.insert(String::from(&pair[..3]));
    }
    new_keys
}

Day 4, Part 2

Well, as I suspected, the second part of the puzzle does require looking at the values. So I will start by refactoring the hash set into a hash map, that saves the values as well as the keys.

This refactor is pretty straightforward, I look up the documentation for HashMap to check if the methods are different (contains() has to change to contains_key()) but other than that, I just have to change HashSet to HashMap throughout. (I also originally overlooked that the correct type is HashMap<String, String>, not HashMap<String>, but the compiler helpfully reminded me.)

use std::collections::HashMap;

fn main() {
    let mut passports = vec![];
    let mut current = HashMap::new();
    for line in read_lines("input").map(|s| s.expect("Bad line in file")) {
        if line == "" {
            passports.push(current);
            current = HashMap::new();
        }
        current.extend(get_pairs_from_line(&line).drain());
    }
    passports.push(current);

    if is_part2() {
        println!("part 2");
    } else {
        let count = passports.iter().filter(passport_is_valid).count();
        println!("{}", count);
    }
}

fn passport_is_valid(passport: &&HashMap<String, String>) -> bool {
    let n_keys = passport.len();
    n_keys == 8 || (n_keys == 7 && !passport.contains_key("cid"))
}

fn get_pairs_from_line(line: &str) -> HashMap<String, String> {
    let mut new_pairs = HashMap::new();
    for pair in line.split_whitespace() {
        new_pairs.insert(String::from(&pair[..3]), String::from(&pair[4..]));
    }
    new_pairs
}

Now I can start changing passport_is_valid() to implement the rules for each field. I’ll make it look something like this:

    (n_keys == 8 || (n_keys == 7 && !passport.contains_key("cid")))
        && valid_birth_year(&passport["byr"])
        && valid_issue_year(&passport["iyr"])
        && valid_expiry_year(&passport["eyr"])
        && valid_height(&passport["hgt"])
        && valid_hair_color(&passport["hcl"])
        && valid_eye_color(&passport["ecl"])
        && valid_passport_id(&passport["pid"])

Then I can write a function for each validation criterion. To start with I write all these functions but make them only contain true, so I can write them one by one but still run the program. (This went pretty smoothly although the compiler did have to remind me to add the & operators before passing each passport data field into each function.)

I wonder for a bit whether I should use scan_fmt! like I did on Day 2, or regular expressions, or parse(). I decide that maybe it’s time for me to use some regular expressions in Rust. It’s new for me, would be useful to learn, and these regular expressions will be simple. But for the fields where I need to check that the numbers are between certain ranges, I’ll also need to use parse().

Let’s start at the top. Birth year must be a 4-digit number between 1920 and 2002 inclusive. (What happens to the 17-year-old or 101-year-old travelers?) I google “rust regex” and find out that you need to install a package for regular expressions, so I add regex = "1" to Cargo.toml and use regex::Regex; to my program. I start reading the documentation for the regex package.

I already know regular expression syntax, which will be very helpful for completing this task. The one thing that I should take note of is that patterns match anywhere in the string, so I need to use ^ and $ to anchor them if I only want them to match the whole string. (That is, matching is like re.search() and not re.match() in Python.)

I come up with this as a first attempt:

fn valid_birth_year(byr: &str) -> bool {
    let re = Regex::new(r"^[12]\d{3}$").unwrap();
    if !re.is_match(byr) {
        return false;
    }
    let year = byr.parse::<u16>();
    year >= 1920 && year <= 2002
}

It seems the only thing I’ve forgotten is to unwrap() the result of parse(), which I had learned on Day 1 but forgot about. So I add that. Then, since issue year and expiry year are validated in a very similar way, just with different maximum and minimum years, I extract that into a valid_year() function:

fn valid_birth_year(byr: &str) -> bool {
    valid_year(byr, 1920, 2002)
}

fn valid_issue_year(iyr: &str) -> bool {
    valid_year(iyr, 2010, 2020)
}

fn valid_expiry_year(eyr: &str) -> bool {
    valid_year(eyr, 2020, 2030)
}

fn valid_year(y: &str, min: u16, max: u16) -> bool {
    let re = Regex::new(r"^[12]\d{3}$").unwrap();
    if !re.is_match(y) {
        return false;
    }
    let year = y.parse::<u16>().unwrap();
    year >= min && year <= max
}

(I initially forgot the -> bool on the new function. I’m so used to either not having a return type on functions (Python, JavaScript) or having the return type come before the name (C, C++) that I forget this a lot!)

Next I write a first attempt at valid_height(), using the match statement that I learned earlier today, and browsing the regex documentation to find that I have to use captures() to get the values of the regular expression’s capture groups:

fn valid_height(hgt: &str) -> bool {
    let re = Regex::new(r"^(\d{2,3})(cm|in)$").unwrap();
    let groups = re.captures(hgt);
    let height = groups[1].parse::<u8>().unwrap();
    match &groups[2] {
        "cm" => height >= 150 && height <= 193,
        "in" => height >= 59 && height <= 76,
    }
}

The compiler tells me that I forgot to unwrap() the result from captures(), and after I do that, it tells me that my match pattern is “non-exhaustive” — I guess this means that I don’t provide any instructions for what to do if the unit is neither cm nor in. I remember from earlier that a default case is written as _ =>, so I add _ => false to the match statement.

Now it runs! But it panics at unwrapping the return value of captures(). I look at the captures() documentation again, and it says that it will return None if the regex doesn’t match. So I decide to do some quick’n’dirty println!("{}", hgt) debugging to see what the string is that doesn’t match. It’s 97, without a unit after it, so indeed it doesn’t match. A string that doesn’t match should make the function return false, not panic.

I’m sure there’s a nice idiom for “return if None, unwrap otherwise” that I’m not yet aware of. I google “rust option return if none” and I learn a bit more about the ? operator, but since I’m not returning a Result from this function that doesn’t help me. However, another thing I learn is that the body of a match statement doesn’t actually have to be the same type as the expression! You can put return false in there and it will return from the function. How nice! So, the captures() call becomes:

let groups = match re.captures(hgt) {
    Some(groups) => groups,
    None => return false,
};

Next comes hair color. This is very similar to the year validation that I’ve done already, only without having to parse the string:

fn valid_hair_color(hcl: &str) -> bool {
    let re = Regex::new(r"^#[0-9a-f]{6}$").unwrap();
    re.is_match(hcl)
}

Eye color doesn’t actually need to use a regular expression:

fn valid_eye_color(ecl: &str) -> bool {
    ecl == "amb"
        || ecl == "blu"
        || ecl == "brn"
        || ecl == "gry"
        || ecl == "grn"
        || ecl == "hzl"
        || ecl == "oth"
}

This works, but I wonder if I could take this opportunity to apply something that I think I remember, from reading about match earlier:

fn valid_eye_color(ecl: &str) -> bool {
    match ecl {
        "amb" | "blu" | "brn" | "gry" | "grn" | "hzl" | "oth" => true,
        _ => false,
    }
}

This also works, and looks much nicer!

Finally, there is the passport ID, which is a nine-digit number:

fn valid_passport_id(pid: &str) -> bool {
    let re = Regex::new(r"^\d{9}$").unwrap();
    re.is_match(pid)
}

I should now be able to get my answer! Before I check whether it’s correct on the Advent of Code website, I would like to make one improvement that was mentioned in the regex documentation. Running the program takes an almost noticeably long time, and it’s probably because I’m rebuilding the same Regex objects once for each passport in the file, several hundred times. The documentation mentions you can use the lazy_static package to build them only once, and so I add that to Cargo.toml and follow the example in the regex documentation.

According to the example, I need to add this to the top of the file:

#[macro_use]
extern crate lazy_static;

And change this:

let re = Regex::new(r"^[12]\d{3}$").unwrap();

to this:

lazy_static! {
    static ref YEAR_REGEX: Regex = Regex::new(r"^[12]\d{3}$").unwrap();
}

I initially forget to add the type : Regex and the compiler’s error message isn’t so helpful:

error: no rules expected the token `=`
  --> src/main.rs:57:23
   |
57 |         static ref re = Regex::new(r"^[12]\d{3}$").unwrap();
   |                       ^ no rules expected this token in macro call

I still don’t quite know how macros work in Rust, or why lazy_static! is a macro and not a function, but my guess is that it’s harder to generate good error messages for macros.

I also try to keep the name re for the regular expressions, but the compiler helpfully tells me that it’s bad style for static variables to have lower case names! So I rename them.

My program seems to run faster now, and still gives me the same answer. So I put that answer into the Advent of Code website, and it’s correct! Hooray!

Here’s the program, quite long this time because of all the validation rules:

use regex::Regex;
use std::collections::HashMap;

#[macro_use]
extern crate lazy_static;

fn main() {
    let mut passports = vec![];
    let mut current = HashMap::new();
    for line in read_lines("input").map(|s| s.expect("Bad line in file")) {
        if line == "" {
            passports.push(current);
            current = HashMap::new();
        }
        current.extend(get_pairs_from_line(&line).drain());
    }
    passports.push(current);

    let count = passports.iter().filter(passport_is_valid).count();
    println!("{}", count);
}

fn passport_is_valid(passport: &&HashMap<String, String>) -> bool {
    let n_keys = passport.len();
    (n_keys == 8 || (n_keys == 7 && !passport.contains_key("cid")))
        && (!is_part2()
            || valid_birth_year(&passport["byr"])
                && valid_issue_year(&passport["iyr"])
                && valid_expiry_year(&passport["eyr"])
                && valid_height(&passport["hgt"])
                && valid_hair_color(&passport["hcl"])
                && valid_eye_color(&passport["ecl"])
                && valid_passport_id(&passport["pid"]))
}

fn valid_birth_year(byr: &str) -> bool {
    valid_year(byr, 1920, 2002)
}

fn valid_issue_year(iyr: &str) -> bool {
    valid_year(iyr, 2010, 2020)
}

fn valid_expiry_year(eyr: &str) -> bool {
    valid_year(eyr, 2020, 2030)
}

fn valid_year(y: &str, min: u16, max: u16) -> bool {
    lazy_static! {
        static ref YEAR_REGEX: Regex = Regex::new(r"^[12]\d{3}$").unwrap();
    }
    if !YEAR_REGEX.is_match(y) {
        return false;
    }
    let year = y.parse::<u16>().unwrap();
    year >= min && year <= max
}

fn valid_height(hgt: &str) -> bool {
    lazy_static! {
        static ref HEIGHT_REGEX: Regex = Regex::new(r"^(\d{2,3})(cm|in)$").unwrap();
    }
    let groups = match HEIGHT_REGEX.captures(hgt) {
        Some(groups) => groups,
        None => return false,
    };
    let height = groups[1].parse::<u8>().unwrap();
    match &groups[2] {
        "cm" => height >= 150 && height <= 193,
        "in" => height >= 59 && height <= 76,
        _ => false,
    }
}

fn valid_hair_color(hcl: &str) -> bool {
    lazy_static! {
        static ref HAIR_REGEX: Regex = Regex::new(r"^#[0-9a-f]{6}$").unwrap();
    }
    HAIR_REGEX.is_match(hcl)
}

fn valid_eye_color(ecl: &str) -> bool {
    match ecl {
        "amb" | "blu" | "brn" | "gry" | "grn" | "hzl" | "oth" => true,
        _ => false,
    }
}

fn valid_passport_id(pid: &str) -> bool {
    lazy_static! {
        static ref ID_REGEX: Regex = Regex::new(r"^\d{9}$").unwrap();
    }
    ID_REGEX.is_match(pid)
}

fn get_pairs_from_line(line: &str) -> HashMap<String, String> {
    let mut new_pairs = HashMap::new();
    for pair in line.split_whitespace() {
        new_pairs.insert(String::from(&pair[..3]), String::from(&pair[4..]));
    }
    new_pairs
}

Afterword

I don’t have that much to reflect on, this time. I did still forget the & operators all over the place, but less often than I did on the previous days, and I had a better understanding of the errors when they occurred.

I’m still a bit mystified about why it’s so difficult to express the type of an iterator in Rust. It seems like it shouldn’t be that hard, so maybe I’m missing something or approaching it the wrong way?

Finally, it seems like I’m reading the API documentation more often, and googling less. I think this is a sign that I have a better idea of where to look and what I’m looking for in the API documentation, but googling is still useful when I need to figure out how to do something that’s not covered by the examples in the API documentation, like a.extend(b.drain()).


[1] I don’t, in fact, like to call it that

Advent of Rust 3: Once in ‘a Lifetime

Well, this is another long stream-of-consciousness chronicle of my attempt to learn how to program in Rust by doing the daily programming puzzles on Advent of Code 2020. It’s long, but on the plus side, this is the first time ever that I’ve published two blog posts in two days, let alone three in three days. And you know what they say, if I’d had more time, I would’ve written you a shorter letter.

I thought a bit about why it should even be interesting or valuable to write about my mistakes and thought process. Or put more bluntly, isn’t this just a waste of time? Who is this useful for?

Well, for one thing, at my job I’ve been working on Temporal, a standards-track proposal to add a modern API for dates and times to the JavaScript language. Earlier this year I conducted a survey of people who had tried out the proposed Temporal API, and one of the purposes was to try to figure out what was easy to understand and what was hard, for someone coming to Temporal with no prior knowledge. Even though I had been in exactly that position myself only a few months before, I had become so accustomed to using Temporal that I could literally remember nothing of my own experience.

It’s sometimes called the curse of knowledge. I’m sure I will look back in a year, or two years, when I have written lots of Rust code, and not remember any of this either, and I’ll be glad that I wrote it down. But maybe it’ll be valuable in the meantime to someone else!

Day 3, Part 1

Today we get a roguelike puzzle! We are sliding on a toboggan down a horizontally repeating grid of open spaces (.) and trees (#) that is defined in our input file. We slide at a certain angle (3 cells across for every 1 cell down), and the answer to Part 1 is how many trees we crash into by the time we get to the bottom.

By this time I’m familiar with how to start — cargo new puzzle3, download the input file and put it in the project directory, and copy the relevant code from yesterday. This time I’m not only copying the read_lines() function, but also the code that determines from the command line argument whether I want to run the code for Part 1 or Part 2.

Here’s what I start out with:

use std::env;
use std::fs;
use std::io::{self, BufRead};
use std::path;

fn main() {
    let args: Vec<String> = env::args().collect();
    let mut part2 = false;
    let default = String::from("1");
    let arg = args.get(1).unwrap_or(&default);
    if arg == "2" {
        part2 = true;
    }
    let lines: Vec<String> = read_lines("input")
        .expect("Bad file")
        .map(|s| s.expect("Bad line in file"))
        .collect();
    println!("grid is {} × {}", lines[0].len(), lines.len());
}

fn read_lines<P>(filename: P) -> io::Result<io::Lines<io::BufReader<fs::File>>>
where
    P: AsRef<path::Path>,
{
    let file = fs::File::open(filename)?;
    Ok(io::BufReader::new(file).lines())
}

I still made a few minor mistakes when adapting this code from yesterday’s code: I forgot to add the Vec<String> type to lines, I forgot to handle errors with .map(|s| s.expect("Bad line in file")), and I guessed wrong that the length of a vector was length() and not len(). Happily, I am getting accustomed enough to this, that I’m able to correct those mistakes fairly quickly.

I will once again use my approach from the last two days, where I first try to get the data into the right data structure. Now that I’m no longer struggling with knowing what data structures even exist in Rust, and how do I even write Rust code, I can afford to think about this before I start writing any code.

It seems like the appropriate data structure is a two-dimensional array of booleans – true if there is a tree in the cell, false if the cell is an open space. I don’t know if Rust has two-dimensional arrays or vectors, so I first start by googling “rust two dimensional array”. I find several results (1, 2, 3, and the array2d package) but none of them really stand out as saying “this is the way to do it.”

What I do understand so far is that I’d use an array if the size was known at compile time, and a Vec of Vecs if I wanted to have variable-length rows or columns. The array2d package from my search results does look interesting because it seems like it gives you a rectangular array, where the length of each row and column is the same for the whole array, but doesn’t necessarily have to be known at compile time. In theory I do know the width and length at compile time, because I can look in the file and count the number of lines and the length of each line! I have a feeling that that would make my code too tied-up with this particular data file, though, and might mean that I would have to refactor the whole thing for Part 2, so I’d prefer not to take that approach.

(I think briefly about using a one-dimensional array and checking through it with a stride of width + 3, but because the grid repeats in the horizontal direction, I think that wouldn’t work.)

Taking the two-dimensional array approach would mean that unlike yesterday, I would not use iterators very much. Hmm, I feel like I’ve just gotten comfortable with iterators in Rust, I wonder what a solution would look like if it were based on iterators?

Maybe that would actually be easier! Thinking about it some more, I don’t actually need to store the entire grid in a 2-D array. I just need to read in each row, figure out my horizontal position on that row, and store a boolean indicating whether I have hit a tree on that row. I believe it can be done just by operating on the string representing each row, with a map(), filter(), and count().

Let’s see if my guess about how to do it is correct. Here’s the first version that I come up with:

fn main() {
    // [...args...]
    let trees_hit = read_lines("input")
        .expect("Bad file")
        .enumerate()
        .filter(hits_tree)
        .count();
    println!("{}", trees_hit);
}

fn hits_tree(row_index: usize, row: String) -> bool {
    let col_index = row_index * 3 % row.len();
    row.as_bytes()[col_index] == '#'
}

Here, I’m assuming that it’s OK to index the string as bytes, because the only characters allowed are # and .. (I learned from yesterday’s exercise what the difference was between indexing a string by byte and iterating through it by character.) I’m taking a guess that '#' (with single quotes instead of double quotes) will give me a single byte rather than a string, like it does in C.

The compiler gives me quite a lot of errors, but I think I know what most of them mean:

error[E0593]: function is expected to take 1 argument, but it takes 2 arguments
  --> src/main.rs:17:17
   |
17 |         .filter(hits_tree)
   |                 ^^^^^^^^^ expected function that takes 1 argument
...
22 | fn hits_tree(row_index: usize, row: String) -> bool {
   | --------------------------------------------------- takes 2 arguments

error[E0599]: no method named `count` found for struct `Filter<Enumerate<std::io::Lines<BufReader<File>>>, fn(usize, String) -> bool {hits_tree}>` in the current scope
    --> src/main.rs:18:10
     |
18   |           .count();
     |            ^^^^^ method not found in `Filter<Enumerate<std::io::Lines<BufReader<File>>>, fn(usize, String) -> bool {hits_tree}>`
     |
     = note: the method `count` exists but the following trait bounds were not satisfied:
             `<fn(usize, String) -> bool {hits_tree} as FnOnce<(&(usize, std::result::Result<String, std::io::Error>),)>>::Output = bool`
             which is required by `Filter<Enumerate<std::io::Lines<BufReader<File>>>, fn(usize, String) -> bool {hits_tree}>: Iterator`
             `fn(usize, String) -> bool {hits_tree}: FnMut<(&(usize, std::result::Result<String, std::io::Error>),)>`
             which is required by `Filter<Enumerate<std::io::Lines<BufReader<File>>>, fn(usize, String) -> bool {hits_tree}>: Iterator`
             `Filter<Enumerate<std::io::Lines<BufReader<File>>>, fn(usize, String) -> bool {hits_tree}>: Iterator`
             which is required by `&mut Filter<Enumerate<std::io::Lines<BufReader<File>>>, fn(usize, String) -> bool {hits_tree}>: Iterator`

error[E0308]: mismatched types
  --> src/main.rs:24:34
   |
24 |     row.as_bytes()[col_index] == '#'
   |                                  ^^^ expected `u8`, found `char`

The first error is probably because I need to make hits_tree() take a tuple of (row_index, row) as its one argument, instead of two arguments. The second error (reminiscent of those long template errors that you get from C++ compilers) I don’t understand, but it seems like it might be a consequence of the first error, and might go away if I solve that one? The third error shows that my guess that '#' is a byte, is wrong. I was close, it is a char, but a byte is type u8.

The third error seems like the easiest to solve, so first I google “rust byte literal” and land here, which makes me think that b'#' might be correct — and it is!

Next I need to make hits_tree() take a tuple as an argument. I wonder if I can destructure this tuple as I would be able to in JavaScript: function hits_tree([row_index, row]) { ... } I google “rust tuple function argument”, and I get this Stack Overflow answer which makes me think that I should be able to do (row_index, row): (usize, String).

But before I run that, I would like to try to get the & operator right this time. After yesterday, when every time I compiled my code, the compiler told me to add a &, I did spend some time reading the “Understanding Ownership” page. Now I feel like I should be better equipped to avoid these mistakes, or at least understand them when I do make them.

So for the first time in this series, I actually go to the API documentation for a function intentionally, instead of googling it and landing there! First I check enumerate() to check that usize is really the correct type for the index (it is,) then I check lines() to check that String is really the correct type for the row (it isn’t.) The type is actually io::Result<String> which reminds me that I need to expect() the value, so I add .map(|s| s.expect("Bad line in file")) before the call to enumerate().

Then there’s the question of whether the row parameter should be a reference or not. I remember reading this:

A more experienced Rustacean would write [s: &str] instead [of s: &String] because it allows us to use the same function on both &String values and &str values.

But on the other hand, I’m not sure that this parameter is actually a reference! It seems to me that since we get a io::Result<String> from read_lines(), the ownership of the string is passed from function to function in the iterator chain, so I would guess (but with only a little more than 50% confidence)1 that String is correct and &str is not. So I make the change of (row_index, row): (usize, String) and run it.

Unfortunately, sitting down and thinking about it is rewarded with an error that I really don’t understand:

error[E0631]: type mismatch in function arguments
  --> src/main.rs:18:17
   |
18 |         .filter(hits_tree)
   |                 ^^^^^^^^^ expected signature of `for<'r> fn(&'r (usize, String)) -> _`
...
23 | fn hits_tree((row_index, row): (usize, String)) -> bool {
   | ------------------------------------------------------- found signature of `fn((usize, String)) -> _`

I know from the reading I’ve done that 'r is a “lifetime”, but the page that I read told me that lifetimes were an advanced feature that would be explained later in the Rust book. Oops, I guess I should have read that chapter too!

I wonder if I can just fake it ’til I make it, by adding for<'r> and &'r to the function signature as the compiler is suggesting. I try that, but it’s a syntax error, “expected item, found keyword for“. I try removing the for<'r>, and I get another error about “unexpected lifetime” which makes me think that I should put the &'r on (usize, String) instead of (row_index, row). (That makes sense, somewhat, because it’s part of the type, not part of the destructured function arguments.) So I try that, and I get another error, but this one tells me exactly what to do:

error[E0261]: use of undeclared lifetime name `'r`
  --> src/main.rs:23:33
   |
23 | fn hits_tree((row_index, row): &'r (usize, String)) -> bool {
   |             -                   ^^ undeclared lifetime
   |             |
   |             help: consider introducing lifetime `'r` here: `<'r>`

Sure enough, when I add <'r>, it works (with some warnings about not using the part2 variable, which I’ll use soon enough) and I get a number out! I put the number into the Advent of Code website and it’s correct!

The lifetime thing is fairly unsatisfying: I have no idea what it does, why it’s necessary, or why it’s even called r!

I’ll try one more thing. Maybe I was wrong about the row needing to be a String. For example, I look back at yesterday’s code and see fn parse_line(line: &str), so maybe in today’s code I also need &str. So I try changing the function signature to fn hits_tree((row_index, row): (usize, &str)) -> bool, without any lifetimes. But I get the old errors back. I do notice one interesting thing in the error message this time:

error[E0631]: type mismatch in function arguments
  --> src/main.rs:18:17
   |
18 |         .filter(hits_tree)
   |                 ^^^^^^^^^ expected signature of `for<'r> fn(&'r (usize, String)) -> _`
...
23 | fn hits_tree((row_index, row): (usize, &str)) -> bool {
   | ----------------------------------------------------- found signature of `for<'r> fn((usize, &'r str)) -> _`

Now, for some reason, it thinks that my function signature already has a lifetime in it, even though I didn’t put one in! I wonder if the lifetime is implicitly when you include a reference. But it definitely wants a String and not a str. So I try changing the type of the argument to (usize, &String) without the lifetime. That doesn’t work either, but interestingly it does continue to think that the type of my function includes a lifetime. It’s telling me that the reference needs to be on the tuple, not on the string, so I try &(usize, String), once more without a lifetime, and that works.

So the message about having to add a lifetime was strange and confusing, but it turns out that I didn’t need to have it after all. Unfortunately I had to discover this by putting & operators in random places until my code compiled, which I had intended to stop doing today ☹️

On the plus side, I got the correct answer, so that’s the end of Part 1! Here’s the full code:

use std::env;
use std::fs;
use std::io::{self, BufRead};
use std::path;

fn main() {
    let args: Vec<String> = env::args().collect();
    let mut part2 = false;
    let default = String::from("1");
    let arg = args.get(1).unwrap_or(&default);
    if arg == "2" {
        part2 = true;
    }
    let trees_hit = read_lines("input")
        .expect("Bad file")
        .map(|s| s.expect("Bad line in file"))
        .enumerate()
        .filter(hits_tree)
        .count();
    println!("{}", trees_hit);
}

fn hits_tree((row_index, row): &(usize, String)) -> bool {
    let col_index = row_index * 3 % row.len();
    row.as_bytes()[col_index] == b'#'
}

fn read_lines<P>(filename: P) -> io::Result<io::Lines<io::BufReader<fs::File>>>
where
    P: AsRef<path::Path>,
{
    let file = fs::File::open(filename)?;
    Ok(io::BufReader::new(file).lines())
}

Day 3, Part 2

My guess was that Part 2 of the puzzle might be to do the same thing but with the toboggan at a sharper angle such that you would have to skip rows entirely. (For example, 1 right for every 3 down.) I was both right and wrong. It’s actually that you have to check a list of five angles including a sharper one that makes you skip rows, and the answer to the puzzle is the results from those angles all multiplied together. So, my approach of using iterators for the whole thing should actually be refactored, because I don’t want to read the file five times!

I briefly think about using array2d to store the map of the trees after all, but I decide that Vec<String> would be more convenient since I can get it from my existing iterator pipeline by capping it after the expect() call with collect(), and I expect my existing code will continue to work on that with few modifications.

So before I start on Part 2 I decide to refactor it this way:

let landscape: Vec<String> = read_lines("input")
    .expect("Bad file")
    .map(|s| s.expect("Bad line in file"))
    .collect();

let trees_hit = landscape.iter().enumerate().filter(hits_tree).count();

But oh no…

error[E0631]: type mismatch in function arguments
  --> src/main.rs:19:57
   |
19 |     let trees_hit = landscape.iter().enumerate().filter(hits_tree).count();
   |                                                         ^^^^^^^^^ expected signature of `for<'r> fn(&'r (usize, &String)) -> _`
...
23 | fn hits_tree((row_index, row): &(usize, String)) -> bool {
   | -------------------------------------------------------- found signature of `for<'r> fn(&'r (usize, String)) -> _`

OK, I’m back to adding & operators in random places! At least as far as I can tell from the error message, I will need to keep the one on the tuple, and add a second one to &String. And indeed that works.

Next I want to refactor the second part of that into a function count_trees_hit(landscape, right, down) so I can call it several times on the list of angles expressed as (right, down) pairs. I’ll start by omitting the down parameter and just making sure that the existing code works:

fn main() {
    // ...
    let trees_hit = count_trees_hit(&landscape, 3);
    println!("{}", trees_hit);
}

fn count_trees_hit(landscape: &Vec<String>, right: usize) -> usize {
    landscape
        .iter()
        .enumerate()
        .filter(|(row_index, row): &(usize, &String)| hits_tree(row_index, row, right))
        .count()
}

fn hits_tree(row_index: usize, row: &String, right: usize) -> bool {
    let col_index = row_index * right % row.len();
    row.as_bytes()[col_index] == b'#'
}

It looks like this almost works, but I get one error:

error[E0308]: mismatched types
  --> src/main.rs:27:65
   |
27 |         .filter(|(row_index, row): &(usize, &String)| hits_tree(row_index, row, right))
   |                                                                 ^^^^^^^^^
   |                                                                 |
   |                                                                 expected `usize`, found `&usize`
   |                                                                 help: consider dereferencing the borrow: `*row_index`

Since usize is an integer type I’m not sure why it has a reference, but I try changing the type of the row_index parameter to &usize and it works. It also works if I do what the compiler says and add *, but that’s an operator that I haven’t learned about (the page I read mentioned that it existed, but I don’t have a good idea of how it works.)

Next I want to add a down parameter. I think if we move multiple rows downwards for every column that we move to the right, then we can simply skip those rows. So it seems to me that I should be able to add another filter() step that skips the row if its index modulo down is not zero.

This new step doesn’t even need access to the row data so I wonder if I can simplify my code by ignoring the string parameter. I google “rust ignore parameter” and land on “Pattern Syntax” which I skim, and it looks like I should be able to use either .. or _ to ignore that parameter. I’ll try both and see what the compiler says. After a couple of tries, what works is: .filter(|(row_index, ..): &(usize, _)| *row_index % down == 0).

Now I have this code:

    let trees_hit = count_trees_hit(&landscape, 1, 2);
    println!("{}", trees_hit);
}

fn count_trees_hit(landscape: &Vec<String>, right: usize, down: usize) -> usize {
    landscape
        .iter()
        .enumerate()
        .filter(|(row_index, ..): &(usize, _)| *row_index % down == 0)
        .filter(|(row_index, row): &(usize, &String)| hits_tree(*row_index, row, right))
        .count()
}

fn hits_tree(row_index: usize, row: &String, right: usize) -> bool {
    let col_index = row_index * right % row.len();
    println!("{}, {}", col_index, row_index);
    row.as_bytes()[col_index] == b'#'
}

I am a bit suspicious that I might be getting the wrong row_index in the second filter() step, because I am filtering out the already-enumerated rows. So for testing, I try it with right 1 and down 2, and add the println!() statement in hits_tree() to print out the row index and column index.

It turns out my suspicion was correct. The indices that are printed out, are 0, 0, 2, 2, 4, 4, 6, 6 etc., while they should be 0, 0, 1, 2, 2, 4, 3, 6. I think what I need to do to fix this, is un-enumerate the items after the first filter() step and then re-enumerate them. I could write the un-enumerate step with map, but I have a feeling that there might be a built-in iterator method to take only the second element of a tuple, so I look at the API documentation for iterators again. I don’t see anything likely there. I look at the API documentation for Itertools as well, but don’t see anything there either. I try googling a few things (such as “rust iterator drop tuple element”) but that doesn’t give me any likely-looking results, so I decide to just write it myself. I insert .map(unenumerate).enumerate() into the iterator pipeline, after the first filter(), and define my unenumerate() function as follows:

fn unenumerate((.., row): &(_, &String)) -> &String {
    row
}

I get two errors that I haven’t seen before:

error[E0106]: missing lifetime specifier
  --> src/main.rs:34:45
   |
34 | fn unenumerate((.., row): &(_, &String)) -> &String {
   |                           -------------     ^ expected named lifetime parameter
   |
   = help: this function's return type contains a borrowed value, but the signature does not say which one of argument 1's 2 lifetimes it is borrowed from
help: consider introducing a named lifetime parameter
   |
34 | fn unenumerate<'a>((.., row): &'a (_, &String)) -> &'a String {
   |               ^^^^            ^^^^^^^^^^^^^^^^     ^^^

error[E0121]: the type placeholder `_` is not allowed within types on item signatures
  --> src/main.rs:34:29
   |
34 | fn unenumerate((.., row): &(_, &String)) -> &String {
   |                             ^ not allowed in type signatures
   |
help: use type parameters instead
   |
34 | fn unenumerate<T>((.., row): &(T, &String)) -> &String {
   |               ^^^              ^

From what I can understand from these errors, first it’s asking me to add a lifetime parameter, and second it seems like the .. trick is not allowed in named functions, only in inline functions?

The suggestion to use type parameters makes me think of how this might work in C++, so I try the following instead:

fn unenumerate<First, Second>((.., second): &(First, Second)) -> Second {
    second
}

Here, confusingly, the compiler does not want the & on the tuple type, so after a few tries of adding and removing & operators I do get this to compile and produce the debug output that I was expecting.

A bit too late, I realize that I could have done this much quicker with only one filter() step, skipping the rows by returning false in hits_tree(). Although what I have already works, this seems like it’s potentially a big enough improvement that I should try it:

fn count_trees_hit(landscape: &Vec<String>, right: usize, down: usize) -> usize {
    landscape
        .iter()
        .enumerate()
        .filter(|(row_index, row): &(usize, &String)| hits_tree(*row_index, row, right, down))
        .count()
}

fn hits_tree(row_index: usize, row: &String, right: usize, down: usize) -> bool {
    if row_index % down != 0 {
        return false;
    }
    let col_index = row_index / down * right % row.len();
    println!("{}, {}", col_index, row_index);
    row.as_bytes()[col_index] == b'#'
}

Apart from forgetting the braces on the if statement (apparently, you cannot omit them in Rust for a single-statement block as you can in C-like languages) I get the same result as my previous code that used unenumerate(), so I feel good about this.

It’s time to remove the debug println!() and actually write the Part 2 code, that tries several different angles and multiplies the answers together:

if part2 {
    let total = count_trees_hit(&landscape, 1, 1)
        * count_trees_hit(&landscape, 3, 1)
        * count_trees_hit(&landscape, 5, 1)
        * count_trees_hit(&landscape, 7, 1)
        * count_trees_hit(&landscape, 1, 2);
    println!("{}", total);
} else {
    let trees_hit = count_trees_hit(&landscape, 3, 1);
    println!("{}", trees_hit);
}

With this, cargo run 2 gives me an answer, which I put into the Advent of Code website, and it’s correct. And as a nice note to end on, this last change marks the first time in this series that I actually write some Rust code that compiles right away!

The full code, also pushed to GitHub:

use std::env;
use std::fs;
use std::io::{self, BufRead};
use std::path;

fn main() {
    let args: Vec<String> = env::args().collect();
    let mut part2 = false;
    let default = String::from("1");
    let arg = args.get(1).unwrap_or(&default);
    if arg == "2" {
        part2 = true;
    }
    let landscape: Vec<String> = read_lines("input")
        .expect("Bad file")
        .map(|s| s.expect("Bad line in file"))
        .collect();

    if part2 {
        let total = count_trees_hit(&landscape, 1, 1)
            * count_trees_hit(&landscape, 3, 1)
            * count_trees_hit(&landscape, 5, 1)
            * count_trees_hit(&landscape, 7, 1)
            * count_trees_hit(&landscape, 1, 2);
        println!("{}", total);
    } else {
        let trees_hit = count_trees_hit(&landscape, 3, 1);
        println!("{}", trees_hit);
    }
}

fn count_trees_hit(landscape: &Vec<String>, right: usize, down: usize) -> usize {
    landscape
        .iter()
        .enumerate()
        .filter(|(row_index, row): &(usize, &String)| hits_tree(*row_index, row, right, down))
        .count()
}

fn hits_tree(row_index: usize, row: &String, right: usize, down: usize) -> bool {
    if row_index % down != 0 {
        return false;
    }
    let col_index = row_index / down * right % row.len();
    row.as_bytes()[col_index] == b'#'
}

fn read_lines<P>(filename: P) -> io::Result<io::Lines<io::BufReader<fs::File>>>
where
    P: AsRef<path::Path>,
{
    let file = fs::File::open(filename)?;
    Ok(io::BufReader::new(file).lines())
}

Afterword

I can tell that I’m starting to get more comfortable in Rust, which feels good. But I’m a bit disappointed that even though I did some extra studying about ownership and the & operator, I was still confused, still couldn’t understand some errors, and basically had to either do exactly what the compiler said without understanding why, or else add or delete & operators arbitrarily until the code compiled.

Maybe what I should do next is read the page in the Rust book on lifetimes, and read about the * operator. Even though the page on ownership said those were advanced topics, both of those came up today in error messages that I didn’t understand.


[1] It occurs to me that — at least for this series — I’m glad I haven’t set up my editor to show Rust compiler errors inline, because otherwise I wouldn’t consciously think about these things

Advent of Rust 2: You Forgot the & Operator!

I’m half-surprised to find myself continuing on this half-baked plan to do a programming puzzle every day to learn Rust and write a stream-of-consciousness blog post detailing all the mistakes I make!

I’m not sure if I’ll keep up the blogging every day, especially because I hope that I’ll make fewer mistakes and wrong turns as the month goes on, and then it won’t be so interesting to blog about. But for now, here’s day 2 of Advent of Code 2020, in which we examine some bizarre password policies.

Day 2, Part 1

Remembering from yesterday how to create a new Rust project, I do cargo new puzzle2. Since the two parts of the puzzle were so similar yesterday, I’m assuming that’ll happen today as well. So I’m going to try to have one project for both parts of today’s puzzle. I’ll even use it as an excuse to learn how to handle command line arguments in Rust, so I can do cargo run 2 to get the second answer.

Today’s puzzle is to read lines from the input file, which look like 1-3 a: abcde. The part before the colon is the “password policy”, in this example meaning “the password must have between one and three a characters in it.” The part after the colon is the “password”, and the task is to check whether the password complies with the password policy. The answer to the puzzle is the total number of passwords in the file that are valid.

To get started, I’m going to take a look at the input file. First I download it and put it in the puzzle2 directory.

How the file looks will determine how I try to solve the problem. If the numbers are all only one digit, then I can process the lines just by character position; in other words, the minimum will always be at position 0, the maximum will always be at position 2, the required letter will always be at position 4, and the password will always be from position 7 until the end of the line. That’s very simple to do in most programming languages, so it should be the same in Rust. On the other hand, if the numbers can be more than one digit, then I will have to use something more complicated to extract them out of the string. In C, I might use sscanf(), and in JavaScript I might use a regular expression, or String.split().

I look at the file, and see that the numbers can be more than one digit, so I will have to take the more complicated approach.

Before I do anything else, I will copy the code that I wrote yesterday, to read the lines from a file. Then I should start by googling something, but I’m not sure what to google. Since I’m familiar with the sscanf() function in C, and I want to do something similar in Rust, maybe I should google “rust sscanf.” I do that, and land on a Stack Overflow question with a promising title: “Does Rust have anything like scanf?”

This tells me that a function like this is not built-in to Rust, but it nonetheless usefully tells me that there are several possible solutions! In order of upvotes, they are:

  • Write a macro to do it, that uses split() internally
  • Use the text_io package
  • Use the scan_fmt package
  • Use a regular expression

Now I have to decide which approach to take. I think I can eliminate the first option because writing a macro sounds more complicated than is needed for this task. I might use a regular expression if the two packages don’t look promising, but I do tend to think that regular expressions are overpowered for tasks like this one, and they are also hard to debug, especially if you have to come back to one several months after you wrote it. So I will first try to avoid regular expressions, meaning I have to choose whether to use the text_io package or the scan_fmt package. I click through the links and read the descriptions of the packages. They both seem like they would do the job, or at least I don’t know enough to say that one would be better than the other. But according to the download statistics at the bottom of the pages, scan_fmt was created more recently1 but is nonetheless about 6× as popular as text_io, so I’d guess I’m more likely to be able to get good help with scan_fmt.

It’s decided, I’ll use scan_fmt for this task! I add it to my Cargo.toml file (I remember how to do this from yesterday). as a first attempt, I cobble together the following code from reading the scan_fmt README file and the snippets in the Stack Overflow post:

#[macro_use]
extern crate scan_fmt;

fn main() {
    read_lines("input").map(parse_line);
};

fn parse_line(line: str) {
    let (min, max, letter, password) = scan_fmt!(line, "{d}-{d} {1}: {}", u32, u32, String, String);
    println!(
        "min:",
        min, "max:", max, "letter:", letter, "password:", password
    );
}

I get a lot of errors on this one! First of all I accidentally typed an extra semicolon in line 6, so I remove it. I also totally forgot how println!() worked from yesterday, and I thought I was using console.log() in JavaScript for a moment! I replace it with println!("min: {} max: {} letter: {} password: {}", min, max, letter, password);.

From reading the error messages, it also looks like I forgot to do error handling, so I add some unwrap() calls to the parsed variables: min.unwrap(), max.unwrap(), letter.unwrap(), password.unwrap(). (This is another thing that I learned yesterday. I didn’t quite remember what it did, so I went back to yesterday’s blog post to check.) That’s still not right, according to the compiler; it says that the result of scan_fmt!() has the type std::result::Result<(u32, u32, String, String), ScanError>, so maybe I need to unwrap() or expect() it before destructuring it? I do so, and the error vanishes, so I guess that was the problem.

The function parse_line now looks like this:

fn parse_line(line: str) {
    let (min, max, letter, password) =
        scan_fmt!(line, "{d}-{d} {1}: {}", u32, u32, String, String).expect("Bad format");
    println!(
        "min: {} max: {} letter: {} password: {}",
        min, max, letter, password
    );
}

It still doesn’t work though! I’ve solved all the compiler errors that I knew what to do with, but there are still some that are a mystery to me:

error[E0631]: type mismatch in function arguments
  --> src/main.rs:9:29
   |
9  |     read_lines("input").map(parse_line);
   |                             ^^^^^^^^^^ expected signature of `fn(std::io::Lines<BufReader<File>>) -> _`
...
12 | fn parse_line(line: str) {
   | ------------------------ found signature of `fn(str) -> _`

error[E0277]: the size for values of type `str` cannot be known at compilation time
 --> src/main.rs:9:29
  |
9 |     read_lines("input").map(parse_line);
  |                             ^^^^^^^^^^ doesn't have a size known at compile-time
  |
  = help: the trait `Sized` is not implemented for `str`
  = note: all function arguments must have a statically known size

error[E0277]: the size for values of type `str` cannot be known at compilation time
  --> src/main.rs:12:15
   |
12 | fn parse_line(line: str) {
   |               ^^^^ doesn't have a size known at compile-time
   |
   = help: the trait `Sized` is not implemented for `str`
   = help: unsized locals are gated as an unstable feature
help: function arguments must have a statically known size, borrowed types always have a known size
   |
12 | fn parse_line(line: &str) {
   |                     ^

error[E0308]: mismatched types
  --> src/main.rs:13:50
   |
13 |     let (min, max, letter, password) = scan_fmt!(line, "{d}-{d} {1}: {}", u32, u32, String, String).expect("Bad format");
   |                                                  ^^^^
   |                                                  |
   |                                                  expected `&str`, found `str`
   |                                                  help: consider borrowing here: `&line`

The compiler gives two suggestions involving the & operator. I’m still not sure what that operator is for, but I’ll try following the suggestions. They were good suggestions, because that eliminates all but the first error!

Now that my terminal is not full of errors, I can more easily read that the compiler is telling me that the parse_line function is not the right type to pass to map(). I wonder whether I might need to change the signature of the function, but the signature that it’s telling me in the error message, just seems like… not what the function is supposed to do! I also wonder if I should not be using the map() method because my function is not returning a value, and maybe I need something more like JavaScript’s Array.forEach(). I google “rust iterator foreach” but don’t see anything that looks like it would solve my problem. Then I realize that I forgot to copy the expect("Bad file") from yesterday’s program, so maybe this is just another case of missing error handling? I’ll try fixing that first, before I try anything more complicated.

read_lines("input").expect("Bad file").map(parse_line); still gives me a type mismatch error, but a different one, that I understand better. I think I need to expect() each line individually before I pass it to parse_line(), so I again look at yesterday’s program and come up with map(|s| parse_line(s.expect("Bad line in file"))). That’s still an error, but the compiler has another helpful suggestion involving the & operator. (Clearly this & operator is important, because I keep leaving it out from places where it should be present. This is something that I should try to read about when I’m done with the exercise.)

Now it compiles, but there are still two problems: first of all, I get a warning, “unused Map that must be used”. Second, the program does nothing. I’d expect that even if there was a warning, it should still run correctly. But then I notice in the warning message, “note: iterators are lazy and do nothing unless consumed.” I think what happened is that because I didn’t run any methods on the result of map(), it never actually scanned the lines. So these two problems are actually the same problem.

I go back to googling “rust iterator foreach” and read a bit more. It looks like there was an RFC to add such a method, which was eventually closed. In that RFC I read that although there is no foreach() method in Rust iterators, you can use a for loop for that purpose. But also, the count() method is a quick hack that will consume the iterator. Although I generally don’t like quick hacks, I think I will go for the quick hack this time, for two reasons. One is that I believe I might be able to solve the rest of the puzzle using iterator methods, so it would be inconvenient to go from iterator methods to a for loop and then back to iterator methods. The other reason is that the eventual solution to the puzzle is actually a count of valid passwords, so ending the code with the count() method seems appropriate and I hope I’ll be able to use it later!

After adding count(), the program compiles and runs, but it panics at an expect() call because the scan_fmt!() call returns an error. Time for a coffee break!

After a break, coming back to look at this with fresh eyes, I wonder if the {1} in the format string (which I had intended to mean “read a string of at most 1 character”) was just me trying to be too clever for my own good, haha! The documentation for scan_fmt!() shows {2d} for at most 2 digits, but it doesn’t actually mention {2}. Sure enough, I remove the 1, and it works. I get a long list of lines such as: min: 3 max: 4 letter: l password: vdcv

Great! Now I want to create a struct (or class, or record, or whatever it is called in Rust) to hold each of these entries. I google “rust struct” and I land on another helpful-looking chapter of the Rust book, “Defining Structs”. I spend some time reading this page and learn a few things: the syntax for defining structs and creating instances of them, and I learn from the note down at the bottom that I should use String instead of str in structs because String is an “owned type” (I assume this means that it copies the string when it is created, and manages the memory itself, or in other words String is to str as std::string is to char* in C). It’s possible to use &str (there’s that & operator again!) but that requires using “lifetimes”, which according to this page is an advanced feature. Well, this is just more reinforcement that I’ll have to learn about the & operator soon, but for now I’ll do what the hint says and use String.

After reading that page, I’m able to write some code:

struct PasswordRule {
    min: u32,
    max: u32,
    letter: String,
    password: String,
}

fn main() {
    read_lines("input")
        .expect("Bad file")
        .map(|s| parse_line(&s.expect("Bad line in file")))
        .map(|rule| println!("{}", rule))
        .count();
}

fn parse_line(line: &str) {
    let (min, max, letter, password) =
        scan_fmt!(&line, "{d}-{d} {}: {}", u32, u32, String, String).expect("Bad format");
    PasswordRule {
        min,
        max,
        letter: String::from(letter),
        password: String::from(password),
    }
}

This almost works the first time! The compiler gives me two errors, but they both have good suggestions: I need to add the return type -> PasswordRule to parse_line(), and I can’t just print out PasswordRule with println!(). (I kind of expected that might not be possible, but I decided to try it anyway to see if it would work.) The return type is easy to add, and it has two suggestions for how to solve the second error: use {:?} instead (I remember wondering what this did yesterday) or implement the std::fmt::Display trait in PasswordRule.

i don’t know what a trait is, so I’ll try using {:?} first. This now tells me to implement a different trait, Debug, but it also tells me that I can add #[derive(Debug)] to my struct. I’ll try that and see what happens. It works! I have lots of lines that look like PasswordRule { min: 4, max: 5, letter: "c", password: "ccchc" }.

I’m still not sure what a trait is, but now I have a vague idea that it adds functionality to a type, and in this case I guess I was adding the functionality of printing a representation with println!()? Kind of like __repr__() in Python.

So now I have all the data in a data structure. This reminds me of the quote from The Mythical Man-Month2 by Fred Brooks:

Show me your flowcharts and conceal your tables, and I shall continue to be mystified. Show me your tables, and I won’t usually need your flowcharts; they’ll be obvious.3

It occurs to me that what I’ve done both yesterday and today is to get the data into the right form first, and then figure out how to solve the problem. And indeed at this point, the outline of a solution is starting to become clear: I’ll filter() the invalid passwords out of the iterator (assuming Rust iterators have a filter() method) and then count() the remaining items to get my answer.

A quick google of “rust filter iterator” shows that there is indeed a filter() method, and it does what I expect.

I wonder if I can add a method to the PasswordRule struct that tells if the password is valid? I start out to google “rust struct method” but before I do, I realize that the page about structs that I’m already looking at has a section on “Method Syntax”, and that looks like what I need. So I click on that instead and spend some time reading it.

Here’s what I come up with, after reading about how to write struct methods:

impl PasswordRule {
    fn is_valid(&self) -> bool {
        false
    }
}

fn main() {
    let count = read_lines("input")
        .expect("Bad file")
        .map(|s| parse_line(&s.expect("Bad line in file")))
        .filter(|rule| rule.is_valid())
        .count();
    println!("{}", count);
}

I want to check if this even works first, before I spend time writing the body of the method, so I make it always return false. When I run this program, I expect it to print the number zero, since it will think all the passwords are invalid. And it does!

So now for the body of is_valid(). Essentially what I want to do is count the number of occurrences of the letter in the password, and make sure it is not less than min and not more than max. I am pretty sure I would know how to do the second part, so I google “rust count character in string”, quickly realize that those search results will get confused with how to get the length of a string, and so google “rust count occurrences in string” instead. I land on a result from programming-idioms.org which gives me the concise s.matches(t).count(). That’s interesting, I got a useful result from Programming Idioms yesterday too, but two days ago I’d never heard of this site.

Here’s what I come up with:

fn is_valid(&self) -> bool {
    let count = self.password.matches(self.letter).count();
    count >= self.min && count <= self.max
}

Of course this doesn’t compile the first time. The compiler tells me that I should use the & operator (there it is again!) on self.letter. After I do that, it tells me that I’m doing an illegal comparison between count (of type usize) and self.min/self.max (of type u32). This is good to know; I just chose u32 kind of arbitrarily as the type for min and max, so I’ll change it to usize throughout. That did it and I got my answer!

Here’s the full code:

use std::fs;
use std::io::{self, BufRead};
use std::path;

#[macro_use]
extern crate scan_fmt;

#[derive(Debug)]
struct PasswordRule {
    min: usize,
    max: usize,
    letter: String,
    password: String,
}

impl PasswordRule {
    fn is_valid(&self) -> bool {
        let count = self.password.matches(&self.letter).count();
        count >= self.min && count <= self.max
    }
}

fn main() {
    let count = read_lines("input")
        .expect("Bad file")
        .map(|s| parse_line(&s.expect("Bad line in file")))
        .filter(|rule| rule.is_valid())
        .count();
    println!("{}", count);
}

fn parse_line(line: &str) -> PasswordRule {
    let (min, max, letter, password) =
        scan_fmt!(&line, "{d}-{d} {}: {}", usize, usize, String, String).expect("Bad format");
    PasswordRule {
        min,
        max,
        letter: String::from(letter),
        password: String::from(password),
    }
}

fn read_lines<P>(filename: P) -> io::Result<io::Lines<io::BufReader<fs::File>>>
where
    P: AsRef<path::Path>,
{
    let file = fs::File::open(filename)?;
    Ok(io::BufReader::new(file).lines())
}

Day 2, Part 2

Like yesterday, the second part of the puzzle involves processing the same input file but with different rules. Now we have to interpret the two numbers as positions in the password (starting from 1, not 0!) For the password to be valid, exactly one of those positions must contain the given letter, not both.

Before I start programming that, I want to figure out how to read command-line arguments in Rust, so that ideally I can just say cargo run 2 to get the answer to Part 2 of the puzzle and I don’t have to make a whole copy of my Part 1 code. Three guesses how I start out: but you only needed one, right? I google “rust command line arguments” and land here. This is a useful page and I spend a bit of time reading it.

Here’s my first attempt:

use std::env;

impl PasswordRule {
    fn is_valid(&self, part2) -> bool {
        if part2 {
            false
        } else {
            let count = self.password.matches(&self.letter).count();
            count >= self.min && count <= self.max
        }
    }
}

fn main() {
    let args: Vec<String> = env::args().collect();
    let mut part2 = false;
    if args[1] == "2" {
        part2 = true;
    }
    let count = read_lines("input")
        .expect("Bad file")
        .map(|s| parse_line(&s.expect("Bad line in file")))
        .filter(|rule| rule.is_valid(day2))
        .count();
    println!("{}", count);
}

So if I do cargo run then I’d expect the same answer that I already got for Part 1, and if I do cargo run 2 I expect zero. That’s almost what happens: first the compiler tells me I need to add : bool to the part2 parameter of is_valid(). Once I do that, I do get zero if I do cargo run 2; but I get a panic if I do cargo run. But I think I understand why! Instead of accessing args[1] which may not exist, what I need is some method that will give me either args[1] if it exists, or a default value if it doesn’t.

So, I go back to the Vec documentation page that I was reading yesterday. But that doesn’t tell me if such a method exists. I google “rust vec checked access” and find a different Vec documentation page. (I am finding the Rust documentation really good, but it would certainly be better if there weren’t so many different pages on the same topic!) This tells me I should use the get() method which will check whether the index is within the bounds of the vector. It returns an Option and I think I even remember from yesterday that I can use the unwrap_or() method of Option to provide a default value! Here’s my attempt:

let arg = args.get(1).unwrap_or("1");
if arg == "2" {
    part2 = true;
}

This is almost correct but I get a type mismatch error, that I don’t understand at first:

error[E0308]: mismatched types
  --> src/main.rs:31:37
   |
31 |     let arg = args.get(1).unwrap_or("1");
   |                                     ^^^ expected struct `String`, found `str`
   |
   = note: expected reference `&String`
              found reference `&'static str`

But then I remember reading earlier about the difference between String and str. I’m not quite sure why I need to use the owned String type here, but I do remember how to convert str into String: String::from(). And I should almost expect at this point that I’m missing an & operator, but the compiler tells me so. (I also initially mistyped it as String.from(), but the compiler had a helpful message about that too.)

Unusually, this time, adding the & where the compiler says to add it, doesn’t make the program run correctly! I get this error:

error[E0716]: temporary value dropped while borrowed
  --> src/main.rs:31:38
   |
31 |     let arg = args.get(1).unwrap_or(&String::from("1"));
   |                                      ^^^^^^^^^^^^^^^^^ - temporary value is freed at the end of this statement
   |                                      |
   |                                      creates a temporary which is freed while still in use
32 |     if arg == "2" {
   |        --- borrow later used here
   |
   = note: consider using a `let` binding to create a longer lived value

I’m not entirely clear on what “borrow” means but I do have a vague idea of what is going on. But once I write it out in this log, it becomes much clearer to me: String::from(1) creates a temporary value, and it’s destructed after the unwrap_or() call, leaving arg as a dangling reference to the temporary object. So the compiler won’t allow it.

Here’s my attempt at solving this:

let default = String::from("1");
let arg = args.get(1).unwrap_or(&default);

I have a strong feeling that this is probably not idiomatic Rust, but for now it works as I expected it to.

Now to actually solve Part 2 of the problem. I remove the false from the if part2 statement in is_valid(), because this is where I’m going to put my code. What I want to do is, get the password character at index min − 1 and the character at index max − 1, and check that one but not both are equal to the letter. So I’m wondering:

  • Can I index a String using the [] operator in Rust?
  • If I can, then does that give me a length-1 String or some sort of character type?
  • Does Rust have a logical XOR (“one, but not both”) operator?

I google “rust xor operator” but then I realize from reading the synopsis of one of the results, that I can use the != operator on two booleans. I’m embarrassed, I had actually learned already that this is why you don’t really need a logical XOR operator, but it took a google search to remind me!

As for the answers to the other two questions, I think I’ll just test and find out whether it works. Here’s my first attempt at Part 2 code:

let first = self.password[self.min];
let second = self.password[self.max];
(first == letter) != (second == letter)

The compiler helpfully reminds me that I forgot self.letter, and it also tells me “String cannot be indexed by usize“. I guess that’s the answer I was looking for! So what can it be indexed by? I google “rust index string” and find this Stack Overflow answer which is actually very helpful! It tells me that strings in Rust are UTF-8, so if you are indexing position n you have to decide explicitly whether you want to have the n-th byte (which is fast, but may be only part of a character) or the n-th character (which is slower). I actually like this feature because when you’re using C it’s actually quite easy to forget that strings are byte arrays and so you write code that crashes as soon as your string contains an emoji.

I think in this case the passwords are all ASCII characters, so it doesn’t actually matter whether we index by bytes or by characters, but I’m pretty sure that indexing by characters is the right thing to do here. So now I try this:

let chars = self.password.chars();
let first = chars.nth(self.min).unwrap();
let second = chars.nth(self.max).unwrap();
(first == self.letter) != (second == self.letter)

And now the compiler gives me some errors which answer my second question as well:

error[E0277]: can't compare `char` with `String`
  --> src/main.rs:23:20
   |
23 |             (first == self.letter) != (second == self.letter)
   |                    ^^ no implementation for `char == String`
   |
   = help: the trait `PartialEq<String>` is not implemented for `char`

Indexing the string apparently does give you a character type, char. Now that I know that this char type exists, I wonder if it would be better to store the letter as a char in my PasswordRule struct, rather than a String. And that almost works! I have to add a let letter = String::from(self.letter); in the Part 1 code, because the matches() method does need a String, but I make some progress! Now this is the error that I get:

error[E0596]: cannot borrow `chars` as mutable, as it is not declared as mutable
  --> src/main.rs:21:25
   |
20 |             let chars = self.password.chars();
   |                 ----- help: consider changing this to be mutable: `mut chars`
21 |             let first = chars.nth(self.min).unwrap();
   |                         ^^^^^ cannot borrow as mutable

error[E0596]: cannot borrow `chars` as mutable, as it is not declared as mutable
  --> src/main.rs:22:26

I don’t understand why chars has to be mutable, since I’m only getting a character from the string, not changing it!

I consider doing what it says and making chars mutable, but I’m curious about why this is needed, so instead I browse the documentation for iterator methods. I have a vague idea that I might be able to make it work using the skip(), take(), next(), and last() methods, but I try a version of that and it doesn’t work right away, so I decide to give up on it and just go back to what I had, and make chars mutable. That works, but I get a panic on one of the unwrap()s because I indexed the string out of bounds!

Then I remember, the numbers in the file are 1-based, and indexing is 0-based, so I need to subtract 1 from each number. But I do that, and it still panics on that same line! Oh, but now I have a guess for why the iterator has to be mutable! My guess is that .nth(self.min - 1) exhausts that number of iterations from the iterator, so then when I do .nth(self.max - 1) it isn’t starting from 0 anymore, and it runs off the end of the string! In other words, nth() changes the internal state of the iterator, which is why it must be declared mutable, and that’s what the compiler was trying to tell me! (And if only I’d read the documentation of nth(), then I might have known that, haha!)

So instead, of saving self.password.chars() in a mutable variable, I just write it twice. I’m sure there’s probably a more efficient way to do this, but I do want to be done with the exercise at this point. And indeed, I get an answer which the Advent of Code website tells me is correct.

Here’s the full code, which I’ve also pushed to GitHub:

use std::env;
use std::fs;
use std::io::{self, BufRead};
use std::path;

#[macro_use]
extern crate scan_fmt;

#[derive(Debug)]
struct PasswordRule {
    min: usize,
    max: usize,
    letter: char,
    password: String,
}

impl PasswordRule {
    fn is_valid(&self, part2: bool) -> bool {
        if part2 {
            let first = self.password.chars().nth(self.min - 1).unwrap();
            let second = self.password.chars().nth(self.max - 1).unwrap();
            (first == self.letter) != (second == self.letter)
        } else {
            let letter = String::from(self.letter);
            let count = self.password.matches(&letter).count();
            count >= self.min && count <= self.max
        }
    }
}

fn main() {
    let args: Vec<String> = env::args().collect();
    let mut part2 = false;
    let default = String::from("1");
    let arg = args.get(1).unwrap_or(&default);
    if arg == "2" {
        part2 = true;
    }
    let count = read_lines("input")
        .expect("Bad file")
        .map(|s| parse_line(&s.expect("Bad line in file")))
        .filter(|rule| rule.is_valid(part2))
        .count();
    println!("{}", count);
}

fn parse_line(line: &str) -> PasswordRule {
    let (min, max, letter, password) =
        scan_fmt!(&line, "{d}-{d} {}: {}", usize, usize, char, String).expect("Bad format");
    PasswordRule {
        min,
        max,
        letter,
        password: String::from(password),
    }
}

fn read_lines<P>(filename: P) -> io::Result<io::Lines<io::BufReader<fs::File>>>
where
    P: AsRef<path::Path>,
{
    let file = fs::File::open(filename)?;
    Ok(io::BufReader::new(file).lines())
}

Afterword

Compared to yesterday, it seems to be happening more today that I’m drawing on knowledge of other programming languages, where I see something in Rust and can say “hey, that looks like such-and-such in C++!”

I never consciously realized this before, but the approach of “show me your tables and the flowcharts will be obvious” is what I often reach for, and it’s been successful both yesterday and today.

It also occurred to me that it’s been really useful both yesterday and today to know what iterators are in other programming languages, and how to use them. Iterators seem to be so common in Rust, that if I was coming to learn Rust but hadn’t encountered iterators before, I’d have a really hard time.

Similarly, I think I also would have had a hard time if I hadn’t been familiar with the family of built-in types that C and C++ provide. It was easy enough for me to recognize that usize is probably the same as size_t, and u32 is probably the same as uint32_t, and that there is such a thing as a char type (there isn’t one in other languages such as JavaScript.)

Finally, it’s very clear that I need to learn what the & operator does! It seems like every time I write any code, the compiler tells me “add the & operator here, here, and here” and I just blindly do that. That’s not a good feeling! But at least it’s a good feeling that the compiler knows this stuff; I’d be totally lost if the error messages were less helpful.

I mentioned Julia Evans’ blog yesterday as an inspiration for this series of posts, and it so happens that she has a blog post about that topic! But that post might be too advanced for me at this point, because it talks about the audience being someone who has read the page in the Rust book on lifetimes. So instead, I think I will start by reading the “Understanding Ownership” page in the Rust book, before I start tomorrow’s puzzle.


[1] It actually was created earlier, but I only figured that out later, because the earlier versions were hidden behind an expander

[2] Which I totally haven’t read

[3] Where “flowcharts” is an old-fashioned word for “source code,” and “tables” is an old-fashioned word for “data structures”

Advent of Rust

I have a bit of time off and I decided to participate in Advent of Code 2020 after my coworker Adrián shared a link to it. I’ve heard that people use challenges like these as an excuse to learn a new programming language, and I have wanted to learn Rust for quite a long time now.

Why Rust? From what I’ve heard, it’s a programming language oriented towards high performance and systems programming, like C or C++; but unlike those languages, it was designed in such a way to make it difficult or impossible to make mistakes such as buffer overflows or memory leaks. I have heard that it’s a lot more enjoyable to use than C++ as well.

I did write a “Hello World” program in Rust some time ago, and I have heard things about Rust from others, so I wouldn’t be coming to it completely fresh. Nonetheless, fresh enough that I decided that the experience of writing something from scratch, in a new programming language, was unusual enough for me that I would keep a log while I was doing it.

So here is that log. It’s a bit stream-of-consciousness. I’ve edited it so that it consists of complete sentences instead of just notes, but I’ve left in the mistakes and dead ends. I made this mainly so that I can look back later when I’ve learned more, and see what mistakes I made.

The reason I’m actually writing this log with all my mistakes in public though, is because I often see things on Twitter like:

RT if you are a senior developer who still Googles to remember syntax stuff

I think sharing facts like those is an important part of busting the myth of the “10x developer”. Developers google things all the time! Just to drive that point home, I thought it would be interesting to share just how much I googled during this afternoon of trying to learn a new programming language.1

At the same time, as you gain experience, you begin to see patterns, you start to know which search results are likely to help you; and other little things like, even if you don’t know what an error message means, you start being able to form a vague idea of where to look. I found that I drew on a lot of this sort of knowledge while trying to find my way around Rust as a newbie, and I’ve tried to note those thoughts down in the log. For example, “oh, this looks like this other thing I’m familiar with, so I’ll try such-and-such.”

I also really appreciate posts by Julia Evans where she chronicles her attempt to learn something new, and those are also an inspiration for turning this log into a blog post.

Day 1, Part 1

Each day’s puzzle is divided into two parts, and you get the second part once you complete the first part. The first part of the first day’s puzzle is to take a file, named input, with a list of numbers, one on each line, and find two numbers in that file that add up to 2020. The answer to the puzzle is what you get when you multiply those two numbers together.

First of all, I download the input file and put it in a directory: advent2020/1.1 (1.1 means Day 1, Part 1). To get started, let’s see if I can even write a Rust program to read the input file, get an array of numbers, and print it out. If I can get that first without bothering with the puzzle, then I’ll be able to start thinking about solving the puzzle afterward.

I google “rust program getting started” and land here, which looks like part of the official Rust documentation. The first thing to do is install Rust. I already had it installed because of trying to write a Hello World at some point in the past, so I skip the first few lines, and do rustup update to get the latest version. This downloads a bunch of stuff.

The Geting Started page says to use Cargo to set up my program. I know roughly what Cargo is, from having read or heard about it somewhere: a package manager. I wonder if a package manager is really necessary for tiny programs like this one, but I’ll go with the flow so that I can just follow the instructions.

The instructions do have a picture of a directory structure that Cargo will create when you run cargo new, and the src/ directory looks a bit inconvenient for a one-file program like I’m planning to write. Let’s see if I can get Cargo to set up my program so that it doesn’t put the source code in a src/ subdirectory. I do cargo new --help — for some reason, that’s not the real help, and it tells me to run cargo help new instead, so I do that.

OK, from the help I learn that Cargo will create a Git repository if there isn’t one already, and I certainly don’t want each puzzle to be in its own Git repository, so instead I initialize one in the advent2020/ directory. I do git init and git checkout -b main.

Also reading the help, I learn that Cargo will create a project directory, so I move the input file elsewhere, and remove the 1.1 directory that I already created, so that I can recreate it with Cargo. I don’t learn how to prevent creating a src/ directory, so I just leave that for now and go with the flow.

I have some trouble creating the project, because it’s not allowed to be named 1.1:

$ cargo new 1.1
error: the name `1.1` cannot be used as a crate name, the name cannot start with a digit
If you need a crate name to not match the directory name, consider using --name flag.
$ cargo new puzzle1.1
error: invalid character `.` in crate name: `puzzle1.1`, characters must be Unicode XID characters (numbers, `-`, `_`, or most letters)
If you need a crate name to not match the directory name, consider using --name flag.
$ cargo new puzzle1-1
     Created binary (application) `puzzle1-1` package

Hmph. I do know roughly what a crate is for the same reason I know roughly what Cargo is, but if I didn’t, this would be total gibberish to me. Anyway, my project is now named puzzle1-1, I guess.

Finally, I do cd puzzle1-1 and cargo run. The Hello World program that Cargo automatically generated, works! I can compile and execute Rust code, so now I can actually start writing it.

It’s time to find out how to read the input file. I copy it back into the puzzle1-1 directory and google “rust read file”. I land on another part of the Rust documentation, helpfully called “Reading a File”. (The last rust-lang.org result that I clicked on was good, so I’ll click on another one.)

I adapt the code given there, and end up with this:

use std::fs;

fn main() {
    let contents = fs::read_to_string("input").expect("Error reading file");
    println!("File contents:\n{}", contents);
}

As an aside, I dimly recall that Cargo has some sort of tool to automatically reformat your source code. I try typing cargo format and I get an error, but it also suggested to try cargo fmt, so I was close enough! That’s one win in favour of using Cargo, because now I don’t have to worry about formatting.

Anyway, I do cargo run and it builds and runs the program, and prints out the contents of the file. I see all the numbers!

So this is something, but it’s probably not correct. It gives me the whole file contents as a string, which I print out. I need the numbers, not one big string! What I actually want is to read each line of the file one at a time, and convert it to an integer, so that I end up with an array of integers, which I can use to solve the puzzle. How do I do that?

I google “rust read file line by line”, and the most likely-looking result is another Rust documentation page. This one is called “Rust by Example”. That sounds useful, examples are exactly what I want!

Once again I adapt the example code, and I end up with this:

use std::fs;
use std::io;
use std::path;

fn main() {
    if let Ok(lines) = read_lines("input") {
        for line in lines {
            if let Ok(ip) = line {
                println!("{}", ip);
            }
        }
    }
}

fn read_lines<P>(filename: P) -> io::Result<io::Lines<io::BufReader<fs::File>>>
where
    P: AsRef<path::Path>,
{
    let file = fs::File::open(filename)?;
    Ok(io::BufReader::new(file).lines())
}

This doesn’t compile:

error[E0599]: no method named `lines` found for struct `BufReader<File>` in the current scope
    --> src/main.rs:18:33
     |
18   |     Ok(io::BufReader::new(file).lines())
     |                                 ^^^^^ method not found in `BufReader<File>`
     |
     = help: items from traits can only be used if the trait is in scope
help: the following trait is implemented but not in scope; perhaps add a `use` for it:
     |
1    | use std::io::BufRead;
     |

At first I wonder if my version of Rust is different from the one used in the documentation? But from reading the error message, I also get a vague idea that my use std::whatever; statements that import the standard library modules must be wrong, because the error message is suggesting to add use std::io::BufRead;. That’s the main thing that I did differently than the example, so probably that’s what I messed up.

Why would I do that differently from the example? In general, but especially when working in a new programming language, I tend to prefer to call APIs by their fully qualified name, so instead of const { read } = require('fs') in Node.js or using std::cout; in C++, I prefer to type out fs.read() and std::cout << every time, so that I don’t get confused by all these bare identifiers in my program and have to wonder where they came from. I was trying to do that in this program as well, but apparently importing std::io::BufRead, even though I don’t use the BufRead identifier, is still necessary to provide the lines() method. Interesting, that means that my mental model of imports in Rust is wrong, and I’m not sure what is wrong about it. That will have to remain a mystery for the time being.

I could add another line saying use std::io::BufRead; as the error message suggests, but I see use std::io::{self, BufRead} in the example that I adapted, and since self has special syntax highlighting, I’m guessing that’s a shorthand for use std::io; use std::io::BufRead;. And indeed, if I change that, then the program works! I once again see all the numbers from the file.

Now for a bit of refactoring, because I’m not fond of the error handling pyramid in this code (like, println! indented at 4 indentation levels.) The previous example that I copied had this nice expect() call which I guess probably did some error handling under the hood, and there’s this ? operator in read_lines() which is probably abstracting away some error handling as well. I’ve dimly heard about the ? operator and the Result type before, so I’m not starting entirely from zero; I have a vague expectation that error handling in Rust should be concise. I will try changing the ifs in main() to the ? operator:

let lines = read_lines("input")?;
for line in lines {
    let ip = line?;
    println!("{}", ip);
}

This doesn’t work, but the error message is helpful about why not: “the ? operator can only be used in a function that returns Result or Option (or another type that implements Try)”.

What I actually want is to just abort the program if there’s an error, because for a short program like this I don’t actually care about recovering from errors. Maybe expect() will do that? Here’s what I will try next:

let lines = read_lines("input").expect("Bad file");
for line in lines {
    let ip = line.expect("Bad line in file");
    println!("{}", ip);
}

Great, this works. And to double-check what it does in the case of an error, I temporarily change input to inputzzzzz and indeed, the program “panics” (I guess “panic” means what I would call “assert” or “abort”?), and the panic message includes the string “Bad file”.

Confident that I know roughly how to deal with runtime errors, the next thing I want to change is that instead of printing each line as a string, I want to convert each line to an integer, and store it in an array of integers, and then print the array.

From other programming languages, I know roughly what I’ll have to do:

  • Figure out how to create an array when I don’t know the length in advance
  • Figure out how to convert a string to an integer
  • Figure out how to store an element in an array

I think I’ll start with the second item on that list, that seems easiest.

Maybe this time instead of googling, since the Rust documentation has already been so helpful, I’ll try to look this up in the “Rust by Example” page that I still have open in my browser. I go to Chapter 6, “Conversion”, and section 6.3, “To and from strings”. That looks promising.

Hmm, actually this is a bit confusing, it’s talking about “implementing traits” and “turbofish” (???) Aside from all that, from reading this page it looks like strings have a parse() method that converts them into integers, but I think I’ll google it after all, just to get a second opinion. Here’s where I land — this corroborates that I should use parse(), and as a bonus, gives a better explanation of what unwrap() does. So here’s my loop that prints integers:

for line in lines {
    let ip = line.expect("Bad line in file").parse::<i32>().unwrap();
    println!("{}", ip * 10);
}

(I added * 10 to make sure that I am actually printing integers and not strings. If I can multiply it by 10, then it must be a number.)

OK, now to create an array. First I google “rust array”, and click on another chapter of Rust by Example. From reading this, it seems that what I want is called a “slice”, not an array, because arrays have a length known in advance, and slices don’t.

But, unfortunately this example doesn’t tell how to create a slice except if you already have an array. So after two misses, I make a mental note to maybe avoid Rust by Example and stick to other parts of the Rust documentation.

Maybe what I want is more like what would be called a “vector” in C++? I google “rust vector” and land on another Rust by Example page after all! But this does look relevant, in fact it looks like exactly what I wanted. Vectors are called Vec in Rust.

Cribbing from the Vec example, my first attempt looks like this:

let entries: Vec<i32>;
for line in lines {
    entries.push(line.expect("Bad line in file").parse::<i32>().unwrap());
}
println!("{:?}", entries);

(I don’t know what the {:?} does differently than {}, but the example code uses it to print out vectors, so I do it too.)

This code doesn’t compile. The error message is “use of possibly-uninitialized entries“. At first I thought it was because lines might be empty and so you wouldn’t push any integer into entries before printing it out, but the error actually points to the push line. Apparently, Rust’s vector is not like C++ where std::vector<int> entries; has a default constructor that gives you an empty vector. I guess I need to know how to get an empty vector.

I click on the documentation link at the bottom, where it says “More Vec methods can be found under the std::vec module”. Now I’m really in the formal API documentation. This is not where I prefer to be when learning, I’d rather look at example code, but maybe this will help me. Sure enough, it does, and it looks like you can get an empty vector with vec![].

(As an aside, I’m wondering why there are these random exclamation marks scattered throughout Rust code, like in vec! and println!. It reminds me of Scheme code, where I also don’t understand the random exclamation marks. I wonder if they’re the same thing. The documentation page refers to vec! as a macro, so I’m guessing that might be it.)

I make that change and recompile, and the next error is that I didn’t declare entries as mutable. I go back to the Rust by Example page and see that if I’d read the example code more carefully I’d have noticed that I had to do that. So the line should read let mut entries: Vec<i32> = vec![]; and when I make that change, it works! I see the list of numbers printed out between square brackets and separated by commas, so it must be printing the vector.

I wonder if this can be done better? The example code says something about “collecting” an iterator into a vector with the collect() method, and I do know from reading the previous example that lines is an iterator! I wonder if it’s possible to take lines, map it through a string-to-int conversion function, and collect the result into my vector. The equivalent of what I’m thinking in Python would be entries = list(map(int, lines)).

First I’ll have to check if there’s a map() method similar to JavaScript’s Array.map() method or Python’s map() function. I google “rust iterator map”, and land here. I scroll down a bit, but this looks promising. The map() method looks like it does what I would expect from other languages, and as a bonus, now I know what the syntax for an inline function looks like in Rust.

Here’s my next attempt, and it looks much nicer:

let entries: Vec<i32> = read_lines("input")
    .expect("Bad file")
    .map(|s| s.expect("Bad line in file").parse::<i32>().unwrap())
    .collect();

I made one mistake before it would compile; I left out the type of entries. I thought maybe it could be inferred to be Vec<i32> since I am “collecting” an iterator of i32s, but I guess that’s not the case. Anyhow, this works, and it seems to be what I wanted!

Now that I’ve accomplished all the three things on my list, we have the mechanics out of the way, and I have to start thinking about how to solve the actual problem. It’s taken longer than I thought it might to get to this point, but that’s to be expected when learning a new language, and I think I should actually be surprised that it’s going this quickly!

So the puzzle is to find the two numbers in the list that add up to 2020, and multiply them. For this, I will need to check every pair of numbers in the list until I find the right pair, but the order doesn’t matter, so I can use a triangle pattern. (I know there’s an actual name for this, not “triangle pattern”, but I can’t think of it right now.) For example if the list had 4 numbers:

check 1 with 2, 3, 4
check 2 with    3, 4
check 3 with       4

In other words, the pairs are 1-2, 1-3, 1-4, 2-3, 2-4, and 3-4. Put more generally, I will need to loop from 0 to length − 2, inclusive2, and check the item at that index paired with each item that comes after it in the list.

Having read about slices earlier, I wonder if I can get a slice from a vector? Ideally it might look something like this in pseudocode:

for index, first in entries[start..length - 2, inclusive]:
    for second in entries[index + 1..end]:
        if first + second == 2020:
            print first * second
            exit with success
fail

Back to Google it is! I google “rust slice from vector” and land here. This looks promising! It seems that &vec[start..end] gives you a slice of vec, and the start and end indices are optional, defaulting to the start and end of the vector. I’m not sure if end is inclusive or exclusive, so I google “rust dot dot operator” and I find that .. is the “exclusive range operator”, whereas ..= is the “inclusive range operator”. I think it would be more expressive to write it as an inclusive range, so I start writing my first attempt. I also remember from reading the Vec page that you can get a pair of index and element by calling the enumerate() method of an iterator, so I use that in my outer loop because I need the index as well. Here’s the loop:

for (ix, first) in &entries[..=entries.len() - 2].enumerate() {
    for second in &entries[ix + 1..] {
        if (first + second == 2020) {
            println!("{} × {} = {}", first, second, first * second);
        }
    }
}

(I had seen earlier on the vec page that you get the length of a vector with len().) I’ll look up later how to exit the program once I find the result, but for now it’s OK to continue iterating even after I find the answer.

However, this doesn’t compile. For one thing I’m warned that I don’t need parentheses around the condition of the if statement — thanks, compiler! But the actual error is that enumerate() isn’t working, and this gives me the first error message I’ve seen so far that isn’t very helpful:

error[E0599]: no method named `enumerate` found for slice `[i32]` in the current scope
  --> src/main.rs:10:55
   |
10 |     for (ix, first) in &entries[..=entries.len() - 2].enumerate() {
   |                                                       ^^^^^^^^^ method not found in `[i32]`
   |
   = note: the method `enumerate` exists but the following trait bounds were not satisfied:
           `[i32]: Iterator`
           which is required by `&mut [i32]: Iterator`

I try using rustc --explain E0599 to find out what’s going on here, but it only tells me how to implement a nonexistent method on a type that I’ve defined. But I didn’t define the type [i32] myself, it’s a slice of integers, so I’m not sure how to add a method to it, and anyway that’s probably not the road I want to travel down! I have a feeling that this is a task where it’s overwhelmingly likely that there’s a built-in way to do it, and I just haven’t found it yet, so I really don’t want to go down a rabbit hole of extending built-in types.

So, time to go back to the documentation. I google “rust slice” and this time click through to the API docs3. I wonder if what I need is the iter() method, since the word “enumerate” is not present in this page according to Ctrl+F, and the error message is saying that enumerate() is an iterator method. Indeed, I change it to .iter().enumerate() and it still doesn’t work, but I get a different error which makes me think I’ve made some progress.

Here’s what the new error says:

error[E0277]: `&Enumerate<std::slice::Iter<'_, i32>>` is not an iterator
  --> src/main.rs:10:24
   |
10 |     for (ix, first) in &entries[..=entries.len() - 2].iter().enumerate() {
   |                        -^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |                        |
   |                        `&Enumerate<std::slice::Iter<'_, i32>>` is not an iterator
   |                        help: consider removing the leading `&`-reference
   |
   = help: the trait `Iterator` is not implemented for `&Enumerate<std::slice::Iter<'_, i32>>`
   = note: `Iterator` is implemented for `&mut std::iter::Enumerate<std::slice::Iter<'_, i32>>`, but not for `&std::iter::Enumerate<std::slice::Iter<'_, i32>>`
   = note: required by `into_iter`

I’m not sure I understand this error, in fact I’m not actually sure what the & operator is for in Rust, but I’ll try doing what it says: remove the &. That makes the program work, hooray! I get an answer, and I enter it into the Advent of Code website, and it’s correct! So I’ve solved the puzzle.

I’d still like to try to make the program a bit better. We still need to exit when the answer is found, and also the ..=entries.len() - 2 looks kind of unreadable.

Tackling the latter point first, I wonder if Rust can do negative slice indices like Python does (for example, in Python arr[:-5] slices from the start to 5 before the end)? To find this out, I try googling a few things but fail to learn anything. Eventually I land on this Stack Overflow post.

(Hmm, the first Stack Overflow result! Normally when I google things, I get a lot more Stack Overflow. This could be because the Rust documentation is really comprehensive. Later as I edit these notes, it occurs to me that it could be because I’m googling very basic things that are generally covered in a language’s documentation, or maybe because Rust isn’t as popular as, say, JavaScript, where the basic questions are all answered multiple times on Stack Overflow.)

Anyway, it looks like negative slice indices are not possible. But from that Stack Overflow post, I click through to the documentation for split_last().

This looks complicated, so I think I’ll google “rust exit” first and come back to this later. I land in the documentation for std::process::exit. It seems I can use std::process; and process::exit(0), and for good measure I print out “Not found” and exit with code 1 if no solution is found.

OK, now back to split_last(). Since split_last() returns a tuple consisting of the last element and a slice of all the other elements, my first attempt looks like this: entries.split_last()[1].iter().enumerate(). This gives me the error “cannot index into a value of type Option<(&i32, &[i32])>” which I guess means that I have to handle the case where there aren’t enough elements. So, next I try entries.split_last().expect("Empty")[1].iter().enumerate() and that gives me this error:

error[E0608]: cannot index into a value of type `(&i32, &[i32])`
  --> src/main.rs:11:24
   |
11 |     for (ix, first) in entries.split_last().expect("Empty")[1].iter().enumerate() {
   |                        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ help: to access tuple elements, use: `entries.split_last().expect("Empty").1`

Once again the compiler’s help is very helpful here. I replace [1] with .1 and it works.

I’m satisfied with this now, it could probably be made a lot better, but it finds the answer and it seems reasonably tidy (here, I’d define “tidy” as “doesn’t reimplement things that we can use the language facilities and standard library for”.)

This is the full code:

use std::fs;
use std::io::{self, BufRead};
use std::path;
use std::process;

fn main() {
    let entries: Vec<i32> = read_lines("input")
        .expect("Bad file")
        .map(|s| s.expect("Bad line in file").parse::<i32>().unwrap())
        .collect();
    for (ix, first) in entries.split_last().expect("Empty").1.iter().enumerate() {
        for second in &entries[ix + 1..] {
            if first + second == 2020 {
                println!("{} × {} = {}", first, second, first * second);
                process::exit(0);
            }
        }
    }
    println!("Not found");
    process::exit(1);
}

fn read_lines<P>(filename: P) -> io::Result<io::Lines<io::BufReader<fs::File>>>
where
    P: AsRef<path::Path>,
{
    let file = fs::File::open(filename)?;
    Ok(io::BufReader::new(file).lines())
}

Day 1, Part 2

The second part of the Day 1 puzzle is a slightly more complicated variation on the first part: now we have to find the three numbers in the list that add up to 2020, and multiply all three of them together for the answer.

There’s probably a smart way to do this, but … (train of thought derails)

I was just about to write “I’m going to do it the most straightforward way and just do another triangle iteration”, but then I thought, hmm, maybe this isn’t as “tidy” as I thought it was after all. If I were doing this in Python, it seems like Python’s itertools module would have a way to iterate over all possible pairs in a list, and I wonder if Rust has something similar that would be generalizable to triplets? Suddenly I remember the word I was trying to think of in Part 1 when I said “triangle pattern”: permutations. I google “rust iterate over permutations” and find out that Rust also has an itertools module in the standard library. (Actually permutations is wrong, we actually want combinations and you’d think that as a former physicist I’d know that!4 Luckily, itertools has a method for both of them, so I land in the right place anyway.)

So, it seems that instead of working on the second part of the puzzle, surprise! I will actually go back and improve the first part! To start out, I go read the documentation for Itertools.combinations(). My first attempt is to add use itertools::Itertools; to the top of the file, and make the loop look like this:

for (first, second) in entries.iter().combinations(2) {
    if first + second == 2020 {
        println!("{} × {} = {}", first, second, first * second);
        process::exit(0);
    }
}

However, that doesn’t compile: “use of undeclared crate or module itertools“. I guess I read it wrong, Itertools is not actually part of the standard library, it’s a package.

So how do I include a package in my program? I’m pretty sure Cargo has something to do with it. I go back to the “getting started with Rust” page that I visited several hours ago, because I remember it said something about this. And indeed, it tells me to add the package to the Cargo.toml file that cargo new automatically generated.

I open Cargo.toml and add itertools under [dependencies] — the example adds a version number as well, but I hope that just putting the name will get me the latest version. I find out that it does not, and what’s more, it’s even invalid syntax. So I add itertools = "0.9.0" instead, which I determined from the Itertools documentation is the latest version as of this writing.

This build takes longer — presumably because it’s downloading itertools — and now I get this error:

error[E0308]: mismatched types
  --> src/main.rs:12:9
   |
12 |     for (first, second) in entries.iter().combinations(2) {
   |         ^^^^^^^^^^^^^^^    ------------------------------ this expression has type `Vec<&i32>`
   |         |
   |         expected struct `Vec`, found tuple
   |
   = note: expected struct `Vec<&i32>`
               found tuple `(_, _)`

Hmmm, I understand about half of what this means. Reading the documentation for combinations() a bit more carefully, it looks like the n-tuples it returns are vectors, and apparently you can’t use destructuring assignment on vectors like that in Rust.

I start to google “rust destructure vector” but then I notice in the Itertools documentation that there’s a tuple_combinations() method that does the same thing as combinations(), only with tuples. That sounds like what I need, so I try that replacing combinations() with tuple_combinations().

That doesn’t work either, and the error message tells me that tuple_combinations() takes no arguments. Huh, no arguments? How does it know how long to make the tuples then? But once again I go back and read the documentation more carefully, and it looks like the tuple length is a template parameter (or whatever that is called in Rust) instead of an argument. I guess that makes sense, because the compiler has to know the length at compile time. I try tuple_combinations<2>() and apparently that’s a C++-ism because it doesn’t work either, but the compiler helpfully tells me to insert a double-colon: tuple_combinations::<2>().

However, that’s not right either: it wants a type parameter, not a number. For the third time I go back and read the documentation more carefully, which I really should have done in the first place, haha! What I now think I understand is that it will infer the length of the tuple from the number of variables that I destructure it into. So, my first assumption about <2> was totally wrong, and I probably got it from C++. In the end, this is what works: for (first, second) in entries.iter().tuple_combinations() { and with that I get back my original correct answer.

Now I notice that we are calling collect() on an iterator to make it into a vector, only to call iter() on it and make it back into an iterator. It seems like I should be able to avoid that. I try this because it seems like it ought to work:

let pairs = read_lines("input")
    .expect("Bad file")
    .map(|s| s.expect("Bad line in file").parse::<i32>().unwrap())
    .tuple_combinations();
for (first, second) in pairs {

But this gives me a confusing error about Clone not being implemented, and I decide not to pursue this any longer, because I want to get on to the second part of the puzzle which I think I can solve easily now. So I put collect() and iter() back in.

Here’s the full code of my new, improved solution to the first part of the puzzle:

use itertools::Itertools;
use std::fs;
use std::io::{self, BufRead};
use std::path;
use std::process;

fn main() {
    let entries: Vec<i32> = read_lines("input")
        .expect("Bad file")
        .map(|s| s.expect("Bad line in file").parse::<i32>().unwrap())
        .collect();
    for (first, second) in entries.iter().tuple_combinations() {
        if first + second == 2020 {
            println!("{} × {} = {}", first, second, first * second);
            process::exit(0);
        }
    }
    println!("Not found");
    process::exit(1);
}

fn read_lines<P>(filename: P) -> io::Result<io::Lines<io::BufReader<fs::File>>>
where
    P: AsRef<path::Path>,
{
    let file = fs::File::open(filename)?;
    Ok(io::BufReader::new(file).lines())
}

Now to solve the second puzzle, with triplets instead of pairs, I should just be able to change the loop to this:

for (first, second, third) in entries.iter().tuple_combinations() {
    if first + second + third == 2020 {
        println!(
            "{} × {} × {} = {}",
            first,
            second,
            third,
            first * second * third
        );
        process::exit(0);
    }
}

Let’s see if it works! (It does, hooray!)

Just for posterity, I change the code in puzzle1-1 back to pairs, and create a new project (cargo new puzzle1-2), copy over the files, and then put the triplet code into puzzle1-2. (Later, I published it to GitHub if you want to browse it.)

I’m happy with this solution! There are probably ways it could be improved, like the collect()/iter() dead-end that I ran into, and those expect()s littered throughout the code don’t look idiomatic, but it got me the correct answers to the puzzles and it doesn’t look too clunky.

Having said that about not being too clunky; just for comparison, here’s what I’d write in a language that I’m more familiar with, like Python (although this is with the benefit of hindsight, after having done the exercise in Rust; I always forget to reach for itertools first in Python when I have an iterator-like problem. The code below is definitely not something that I’d just bust out in a few minutes normally.)

import itertools
import sys

with open('input', 'r') as lines:
    pairs = itertools.combinations(map(int, lines), 2)
    for first, second in pairs:
        if first + second == 2020:
            print(f'{first} × {second} = {first * second}')
            sys.exit(0)
print('Not found')
sys.exit(1)

You can see that the Python code is still quite a lot more streamlined than the Rust code, so I suspect I’m not yet writing very good Rust code. I hope that improves as I continue the exercises!

Afterword

From writing these notes I even learned something new about my thought process: that when I google up some documentation, I don’t read it as carefully as I thought I did!

Another thing that I noticed is that while it was important to know what permutations and combinations are, I didn’t actually have to know how to compute them, let alone an algorithm to compute them efficiently. I tried a simple algorithm which worked, but I could have saved myself a lot of time and trouble if I hadn’t even tried to write the algorithm myself, and instead just looked for Itertools! (This is why it’s always a mystery to me why some technical interviewers expect you to have algorithm knowledge at your fingertips. Maybe I’m biased because I don’t have a computer science degree, but I don’t think it’s how programmers realistically do their jobs!)

It’s also interesting to note that this took me the whole afternoon, but I think five years ago, in 2015, it would have taken a lot longer. When I thought about what I was thinking about all afternoon, I realized a surprising thing! A big part of the reason I could do this exercise in one afternoon is not that I have become better at programming, but that I have become better at knowing what to google.

Ten years ago, in 2010, I wouldn’t even have dared to try this exercise with a new programming language! I remember it clearly because 2010 was when I learned Python for the first time. I did it by going through the tutorial in the Python documentation. Even that was a novel experience that left me unsure of myself, because at the time I still believed that the only way for me to learn a programming language was to get a reference book, and read it cover to cover.5 But who has time for that anymore, anyway? Certainly not me!

I wouldn’t say by any means that doing a programming exercise like this means I’ve “learned” Rust, but what I hope to achieve by doing Advent of Code is that by the end, I’ll have gained enough practical experience in Rust that I might feel confident enough to reach for it the next time I need to solve a real-life programming problem for which I might otherwise use C or C++. And that will be the next step to really learning it.


[1] Interestingly, I think I actually googled less than I normally would, because the error messages from the Rust compiler are so helpful ↩️

[2] Minus 2 because the last item in the list is at index length − 1, and by the time I get there I won’t have any numbers left to pair it with ↩️

[3] I didn’t realize until editing my notes into a blog post, that there are actually two different documentation pages about slices, std::slice and “primitive slice type” ↩️

[4] You might think that, but you’d be wrong ↩️

[5] I learned C that way, and it stuck; I also learned Perl that way, and it didn’t. After doing the Python tutorial I did eventually get a Python book and inhaled it, but the seed of a new way of life was already planted ↩️