Advent of Rust 13: Lucky Numbers

It’s time for the 13th installment of the chronicle of me doing programming puzzles from Advent of Code 2020 to teach myself the Rust programming language.

Looking at the lessons that I learned from previous days, today I resolve to be more systematic about debugging. If I get the wrong answer I will try my program on the example input first, before changing up a bunch of other things.

Day 13, Part 1

Today’s puzzle is about which bus to take from the airport. We get an input file consisting of only two lines of text: our arrival time at the airport, and a list of bus line numbers that are in service, with some xs denoting bus lines that are not in service. Each bus line departs from the airport at an interval of minutes equal to its number, so bus 77 departs when time % 77 == 0.

Since there are only two lines of text in the input file, and they both mean something different, I’m not looping over read_lines() today. To read the arrival time, I would really like to do this:

let arrival: u32 =;

But, just as on Day 8, I can’t figure out how to get these dang error types to line up, without a lot of boilerplate (for example, implement From for every library error that I intend to handle, as I did and regretted on Day 8.) In my mind at least, this really ought to work:

fn main() -> Result<(), impl error::Error>

But I already tried that on Day 8 and it didn’t work, giving me errors such as:

error[E0277]: `?` couldn't convert the error to `impl std::error::Error`
6 | fn main() -> Result<(), impl Error> {
  |              ---------------------- expected `impl std::error::Error` because of this
7 |     let file = fs::File::open("input")?;
  |                                       ^ the trait `From<std::io::Error>` is not implemented for `impl std::error::Error`
  = note: the question mark operation (`?`) implicitly performs a conversion on the error value using the `From` trait
  = note: required by `from`

error[E0277]: `?` couldn't convert the error to `impl std::error::Error`
6 | fn main() -> Result<(), impl Error> {
  |              ---------------------- expected `impl std::error::Error` because of this
9 |     let arrival: u64 =;
  |                                    ^ the trait `From<NoneError>` is not implemented for `impl std::error::Error`
  = note: the question mark operation (`?`) implicitly performs a conversion on the error value using the `From` trait
  = note: required by `from`
help: consider converting the `Option<T>` into a `Result<T, _>` using `Option::ok_or` or `Option::ok_or_else`
9 |     let arrival: u64 =|| /* error value */)?.parse()?;
  |                                    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

error[E0277]: `?` couldn't convert the error to `impl std::error::Error`
6 | fn main() -> Result<(), impl Error> {
  |              ---------------------- expected `impl std::error::Error` because of this
9 |     let arrival: u64 =;
  |                                             ^ the trait `From<ParseIntError>` is not implemented for `impl std::error::Error`
  = note: the question mark operation (`?`) implicitly performs a conversion on the error value using the `From` trait
  = note: required by `from`

error[E0720]: cannot resolve opaque type
6  | fn main() -> Result<(), impl Error> {
   |                         ^^^^^^^^^^ recursive opaque type
7  |     let file = fs::File::open("input")?;
   |                                       - returning here with type `std::result::Result<(), impl std::error::Error>`
8  |     let mut lines = read_lines(file);
9  |     let arrival: u64 =;
   |                                    -        - returning here with type `std::result::Result<(), impl std::error::Error>`
   |                                    |
   |                                    returning here with type `std::result::Result<(), impl std::error::Error>`
51 |     Ok(())
   |     ------ returning here with type `std::result::Result<(), impl std::error::Error>`

As far as I can tell, the first three error messages mean I’d need to implement the From trait on each of those errors, and I don’t understand the final error message.

Since I wish so badly that I could do this, I spend a bit more time searching, and find this. It’s not quite relevant to me, although I do learn some interesting facts about the Termination trait and why we can have different return types for main(). But I do see Box<Error> in some example code there, which I try instead of impl Error. The compiler tells me to use Box<dyn Error> instead. That actually works for the io::Error and ParseIntError, but I still have to unwrap() the Option from Iterator::next() — that doesn’t automatically convert into an Error.

I read about NoneError which is an experimental API, so maybe that will be possible in the future?

Anyway, I’m pleased at least that I can now use ? on Result types that carry different error types, so it’s progress, even though what I was hoping for is not (yet) possible. I guess -> Result<(), Box<dyn Error>> will become my new idiom.

Back to the puzzle! Here’s the program that I write:

use std::error::Error;

fn main() -> Result<(), Box<dyn Error>> {
    let file = fs::File::open("input")?;
    let mut lines = read_lines(file);
    let arrival: u32 =;

    let (bus_number, wait_time) = lines
        .filter_map(|s| s.parse::<u32>().ok()) // available bus lines
        .map(|interval| (interval, interval - arrival % interval)) // (bus_number, wait time)
        .min_by_key(|(_, wait_time)| *wait_time)

    println!("{}", bus_number * wait_time);

I write this without any major complications, and it gives the correct answer. I learn the filter_map() and min_by_key() iterator methods along the way.

This input had so few entries that it may well have been faster to calculate it by hand, though! But then again, it’s basically a one-liner with these fantastic Iterator methods, and I didn’t even need Itertools this time.

Day 13, Part 2

The second part of the puzzle is to find a time that satisfies a number of constraints. Given the example input 17,x,13,19, you have to find a time t at which bus 17 departs, bus 13 departs 2 minutes later, and bus 19 departs 3 minutes later. (The x means there are no restrictions on what buses might depart one minute after t.) Additionally, the puzzle description gives the hint that t is at least 100000000000000, so I start by changing the integer types in my program to u64 because that won’t fit in a u32.

I first decide to try a brute force solution, because as I learned on Day 10, I might spend a lot of time dissecting the puzzle when I just could have written a program to do it without trying to be clever.

Writing my program, I’m a bit surprised about this:

error: literal out of range for `i32`
15 |         let t = 100000000000000;
   |                 ^^^^^^^^^^^^^^^
   = note: `#[deny(overflowing_literals)]` on by default
   = note: the literal `100000000000000` does not fit into the type `i32` whose range is `-2147483648..=2147483647`

Why can’t the compiler infer that t is used later in other expressions of type u64, or at least guess a default type for t that’s big enough to fit the literal, or at the very least suggest adding a type annotation?

Here’s the brute force program that I write:

let mut t: u64 = 100000000000000;
let mut constraints: Vec<(usize, u64)> = entries
    .filter_map(|(ix, s)| s.parse::<u64>().map(|n| (ix, n)).ok()) // (index, bus_number)
constraints.sort_unstable_by_key(|(_, bus_number)| *bus_number);

loop {
    if constraints
        .all(|(ix, bus)| t + *ix as u64 % *bus == 0)
    t += 1;

println!("{}", t);

Many minutes later, after a coffee break, it’s still running! Clearly this will not do.

While the program is running for so long I do decide to check if it works on the example input, to carry out my resolution from the beginning of the day. In fact, the example input does not give the correct result. I am missing parentheses in (t + *ix as u64) % *bus. With the missing parentheses added, all the example inputs on the puzzle page do produce the correct answer. But given the real input, the program still runs for many minutes without finding an answer.

Taking the example input 17,x,13,19 again, we have a system where we have to determine t from the following equations, where cn are positive integers:

t = 17 × c1
t + 2 = 13 × c2
t + 3 = 19 × c3

Here we have a system with 3 equations and 4 unknowns, so we cannot solve it directly,1 because there is more than one solution. There is also the constraint that t must be the smallest possible solution that’s greater than 0 (or, greater than 100000000000000 with the real input), which fixes our solution unambiguously.

Put more generally, we have a system of equations of the form

t + bn = an × cn

where an and bn are given.

The lowest common multiple is a special case of this system where all bn = 0. Interesting that it’s so easy to calculate the lowest common multiple and not easy to calculate this!

My partner points out that all the an in the puzzle input are prime, and that there would be no answer to the puzzle if, for example, all the an were even and any of the bn were odd.

I try to speed the program up by not bothering to check numbers that I know won’t satisfy the first constraint. I set the starting number to the first number which satisfies the first constraint, skip checking the first constraint, and use a step size of the first bus line number instead of 1:

let (first_delay, first_bus) = &constraints[0];
t += (*first_bus - t % *first_bus);
t -= *first_delay as u64;
loop {
    println!("trying {}", t);
    if constraints
        .all(|(delay, bus)| {
            println!("  {} + {} % {} == {}", t, *delay, *bus, (t + *delay as u64) % *bus);
            (t + *delay as u64) % *bus == 0
    t += first_bus;

This speeds up the calculation of the example inputs noticeably, but the calculation of the actual puzzle answer is still taking a long time.

I try running it again on the example input 17,x,13,19 and looking at the debug output to see if there are patterns. In the case of the program above, this means: the step is 19, the constraints are [(3, 19), (0, 17), (2, 13)], and the first constraint is always satisfied. I notice that the iterations that satisfy the second constraint are always 17 steps apart. This suggests to me that once I find a number that satisfies the second constraint, I can continue with a step of 19 × 17 = 323 until I find a number that satisfies the third constraint as well. In fact, this is generalizable to include the speedup that I just wrote: I can start with a step of 1, iterate until I satisfy the first constraint, multiply the step by 19 (giving 19), iterate until I satisfy the second constraint, multiply the step by 17 (giving 323), and then iterate until I satisfy the third constraint, at which point I have the answer.

After a few false starts, I manage to write the following loop:

let mut step = 1;
let mut constraints_satisfied = 0;
loop {
    match constraints
        .position(|(delay, bus)| (t + *delay as u64) % *bus != 0)
        None => break,
        Some(ix) => {
            if ix > constraints_satisfied {
                constraints_satisfied += 1;
                step *= constraints[ix - 1].1;
    t += step;

The position() method is a new thing that I’ve learned while doing this, I found it by googling “rust find index” because I was doing something like constraints.iter().enumerate().find(...) and taking the position from there. (Maybe cargo clippy should look for this pattern.)

This gives the correct output on all the example inputs, and finds the correct answer to the puzzle in a very short time. The full code is on the repository.


Today I actually found the opposite of what I found a few days ago: writing the brute force program first was not actually that helpful, and I did have to sit down and think a lot more about the problem, and explore the input, before I was able to get the answer.

I suspect it’s still worth it to write the brute force program first when doing programming puzzles, though. It’s only not helpful in a case like this, where brute force calculation is really not feasible.

[1] It doesn’t matter that we don’t actually care about the values of cn; they are still unknowns


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.push(adapters.last().unwrap() + 3); // add built-in adapter

let mut differences: Vec<u8> = adapters
    .map(|(j1, j2)| j2 - j1)

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.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);

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
    .filter(|(key, _)| *key == 1)
    .map(|(_, group)| possible_configurations(group.count()))
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.


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