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 = lines.next()?.parse()?;
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`
--> puzzle13.rs:7:39
|
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`
--> puzzle13.rs:9:36
|
6 | fn main() -> Result<(), impl Error> {
| ---------------------- expected `impl std::error::Error` because of this
...
9 | let arrival: u64 = lines.next()?.parse()?;
| ^ 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 = lines.next().ok_or_else(|| /* error value */)?.parse()?;
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
error[E0277]: `?` couldn't convert the error to `impl std::error::Error`
--> puzzle13.rs:9:45
|
6 | fn main() -> Result<(), impl Error> {
| ---------------------- expected `impl std::error::Error` because of this
...
9 | let arrival: u64 = lines.next()?.parse()?;
| ^ 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
--> puzzle13.rs:6:25
|
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 = lines.next()?.parse()?;
| - - 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 = lines.next().unwrap().parse()?;
let (bus_number, wait_time) = lines
.next()
.unwrap()
.split(',')
.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)
.unwrap();
println!("{}", bus_number * wait_time);
Ok(())
}
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`
--> puzzle13.rs:15:17
|
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
.enumerate()
.filter_map(|(ix, s)| s.parse::<u64>().map(|n| (ix, n)).ok()) // (index, bus_number)
.collect();
constraints.sort_unstable_by_key(|(_, bus_number)| *bus_number);
constraints.reverse();
loop {
if constraints
.iter()
.all(|(ix, bus)| t + *ix as u64 % *bus == 0)
{
break;
}
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
.iter()
.skip(1)
.all(|(delay, bus)| {
println!(" {} + {} % {} == {}", t, *delay, *bus, (t + *delay as u64) % *bus);
(t + *delay as u64) % *bus == 0
})
{
break;
}
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
.iter()
.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.
Afterword
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 ↩
The Mad Scientist Review 
Pingback: Advent of Rust, Day 22 and 23: Profiling, Algorithms, and Data Structures | The Mad Scientist Review