Day 1 (Advent of Code 2020)
👋 This page was last updated ~4 years ago. Just so you know.
I was not planning on doing anything specific this December, but a lot of folks around me (on Twitter, at work) have chosen this Advent of Code to pick up Rust, and I've got big FOMO energy, so, let's see where this goes.
I'll be doing all of these on Linux, so there may be some command-line tools involved, but don't worry about them - the code itself should run on all platforms no problem.
If you want to follow along, you'll want to install VS Code with the Rust Analyzer extension, and you'll want to install Rust, too.
On Windows you may have to install the VS2019 Build Tools, which can be a little annoying - sorry about that!
Part 1
The puzzle input looks something like:
1721 979 366 299 675 1456
And our task is to find the two entries that sum to 2020
, and multiply
them. Let's go for it!
$ cargo new day1 Created binary (application) `day1` package
First off, let me paste my puzzle input into a file at day-1/src/input.txt
. Mine
looks something like this:
1470 1577 1054 (cut) 1911 1282 1306
...but yours may look different.
Then, we'll want to read that file. We have a couple options here, we could do it at runtime:
$ cargo add anyhow Updating 'https://github.com/rust-lang/crates.io-index' index Adding anyhow v1.0.35 to dependencies
cargo add
is provided by cargo-edit,
which we'll be using throughout this whole series.
If you're following along, you can simply install it with cargo install cargo-edit
.
// in `day1/src/main.rs` fn main() -> anyhow::Result<()> { let s = std::fs::read_to_string("./src/input.txt")?; dbg!(&s[..40]); Ok(()) }
This reads the file and prints the first 40 bytes:
$ cargo run --quiet [src/main.rs:3] &s[..40] = "1470\n1577\n1054\n1962\n1107\n1123\n1683\n1680\n"
...but opening the file at runtime means it can fail, and we need to ensure that
the input.txt
file is always next to the executable.
So instead, we can just include it at compile-time:
fn main() -> anyhow::Result<()> { let s = include_str!("input.txt"); dbg!(&s[..40]); Ok(()) }
$ cargo run --quiet [src/main.rs:3] &s[..40] = "1470\n1577\n1054\n1962\n1107\n1123\n1683\n1680\n"
Now the string is part of our executable:
$ xxd target/debug/day1 | grep "1470.15" -A 5 0003b000: 4572 726f 723a 200a 3134 3730 0a31 3537 Error: .1470.157 0003b010: 370a 3130 3534 0a31 3936 320a 3131 3037 7.1054.1962.1107 0003b020: 0a31 3132 330a 3136 3833 0a31 3638 300a .1123.1683.1680. 0003b030: 3131 3736 0a31 3931 370a 3137 3836 0a31 1176.1917.1786.1 0003b040: 3536 350a 3134 3634 0a31 3039 370a 3133 565.1464.1097.13 0003b050: 3633 0a31 3039 310a 3130 3732 0a31 3832 63.1091.1072.182
xxd is a pretty basic (and antique) hexdump tool that ships with most Linux distributions.
So far, we have one big String
. We want to deal with each line separately,
so, let's split it by newlines:
fn main() -> anyhow::Result<()> { let s = include_str!("input.txt").split("\n"); Ok(()) }
You may want to use .lines()
instead of .split("\n")
so that this works with
CRLF line endings too (Windows). The rest of the article was written in split
in mind, but they both give you iterators, so you'll still be able to follow.
What this gives us is not an array of strings, rather, it gives us a concrete
type (Split<&str>
) that implements Iterator<Item = &str>
.
Wait, &str
? I thought we had a String
?
We did! And the elements our iterator is returning now are borrowed from that
original String
. They're slices from the original String
, so that no
copying is involved.
Wait, no!
When we used std::fs::read_to_string
, we did have a String
:
But wait... when we changed to include_str!
, we got an &str
:
Oh right! When we "bake the string in the executable", what we get is also borrowed, we're just borrowing it from the executable.
"The executable" being...? (Asking for a friend)
That file in target/debug/day1
, that's
ELF on Linux, PE on Windows, and
Mach-O on macOS, which is the result of compiling our program (via cargo build
, or cargo run
, which ultimately all calls the Rust compiler
rustc
).
Right.
So, we have a Split<&str>
, that implements Iterator<Item = &str>
.
Iterator
is a trait, the most important required method is next()
:
fn next(&mut self) -> Option<Self::Item>
So if we call s.next()
, we'll get either a Some(a_slice)
, or a None
, if
we ran out of elements.
fn main() -> anyhow::Result<()> { let mut s = include_str!("input.txt").split("\n"); dbg!(s.next()); dbg!(s.next()); dbg!(s.next()); Ok(()) }
$ cargo run --quiet [src/main.rs:3] s.next() = Some( "1470", ) [src/main.rs:4] s.next() = Some( "1577", ) [src/main.rs:5] s.next() = Some( "1054", )
Hold on a second, I'm getting a warning:
Whoa, you have inline error messages?
Yeah, it's the Error Lens vscode extension, it's pretty neat!
Okay so, about that error - it's not really an error, it's a diagnostic from clippy, which... did I mention you should install clippy?
Well, you should - and you should check it as rust-analyzer's default "check on save" command, in your VSCode user settings:
{ "rust-analyzer.checkOnSave.command": "clippy", }
What clippy is trying to tell us here is that '\n'
is just a character,
which is a nice and tiny value, for which splitting is highly optimized,
whereas "\n"
is a string literal, which could be any length (it just
happens to be of length 1), and so we're forcing .split
to use a more
generic (and slower) approach.
No problem, we can fix that easily, by clicking the lightbulb (💡) icon,
or just hitting Ctrl+.
(probably Cmd+.
on macOS):
And then we have:
fn main() -> anyhow::Result<()> { let mut s = include_str!("input.txt").split('\n'); dbg!(s.next()); dbg!(s.next()); dbg!(s.next()); Ok(()) }
Which gives us the same output as before.
So... what where we trying to do again? Let's look at the problem statement again:
Specifically, they need you to find the two entries that sum to 2020 and then multiply those two numbers together.
Right!
Well, there's one issue - we don't have numbers right now, we have strings.
Luckily, that's something str::parse can do!
So, we're starting off with an Iterator<Item = &str>
, and we'd like... an
Iterator<Item = i64>
?
i64
is a signed 64-bit integer - which seems like a safe bet when we're not
worried about memory usage and we're not sure how big numbers can get.
Transforming all the items of an iterator is called "mapping", and it's
performed with the .map
method, provided by the Iterator
trait.
We can pass it a function directly: here, we pass it str::parse
:
fn main() -> anyhow::Result<()> { let mut s = include_str!("input.txt").split('\n').map(str::parse); dbg!(s.next()); dbg!(s.next()); dbg!(s.next()); Ok(()) }
Except that doesn't work:
$ cargo run --quiet error[E0283]: type annotations needed for `Map<std::str::Split<'_, char>, for<'r> fn(&'r str) -> std::result::Result<F, <F as FromStr>::Err> {core::str::<impl str>::parse::<F>}>` --> src/main.rs:2:59 | 2 | let mut s = include_str!("input.txt").split('\n').map(str::parse); | ----- ^^^^^^^^^^ cannot infer type for type parameter `F` declared on the associated function `parse` | | | consider giving `s` the explicit type `Map<std::str::Split<'_, char>, for<'r> fn(&'r str) -> std::result::Result<F, <F as FromStr>::Err> {core::str::<impl str>::parse::<F>}>`, where the type parameter `F` is specified | ::: /home/amos/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/str/mod.rs:2202:21 | 2202 | pub fn parse<F: FromStr>(&self) -> Result<F, F::Err> { | ------- required by this bound in `core::str::<impl str>::parse` | = note: cannot satisfy `_: FromStr` help: consider specifying the type argument in the function call | 2 | let mut s = include_str!("input.txt").split('\n').map(str::parse::<F>); | ^^^^^
What an absolute chonker of an error. Remarkable.
Well, the last help
bit is the most helpful one:
help: consider specifying the type argument in the function call | 2 | let mut s = include_str!("input.txt").split('\n').map(str::parse::<F>); | ^^^^^
See, str::parse
can parse a string into many different things - we could be
parsing an IP address, like 127.0.0.1
, or we could be parsing a
floating-point value, like 3.1415926535
, etc.
So, with a little help from our friend the turbo-fish,
we can explicitly say: what we want to parse is an i64
- a signed 64-bit
integer:
fn main() -> anyhow::Result<()> { let mut s = include_str!("input.txt").split('\n').map(str::parse::<i64>); dbg!(s.next()); dbg!(s.next()); dbg!(s.next()); Ok(()) }
And then it does work:
$ cargo run --quiet [src/main.rs:3] s.next() = Some( Ok( 1470, ), ) [src/main.rs:4] s.next() = Some( Ok( 1577, ), ) [src/main.rs:5] s.next() = Some( Ok( 1054, ), )
What we've done is similar, but not exactly the same as the following JavaScript:
["12", "34", "56"].map((x) => parseInt(x, 10))
Quick JavaScript gotcha: parseInt
takes multiple arguments, including the
radix of the number to parse, so we can't just pass it to map, which passes
the item and the index.
This works:
> ["12", "34", "56"].map((x) => parseInt(x, 10)) [ 12, 34, 56 ]
But this doesn't:
> ["12", "34", "56"].map(parseInt) [ 12, NaN, NaN ]
...well, it only works properly for the first (index 0) and eleventh (index 10) elements, otherwise it's trying to parse numbers in base 1, base 2, base 3 11) etc.
Isn't JavaScript fun?
Because in JavaScript, map
operates on an array and returns an array.
But here, we're operating on iterators: streams of items. We don't yet have
random access to them, which is why we have to call .next()
repeatedly,
and they can always return None
.
In fact, if we look closer at our output, we notice that what we're printing
each time is in fact a Option<Result<i64, E>>
[src/main.rs:3] s.next() = Some( Ok( 1470, ), )
An Option<T>
can be either Some(T)
or None
- iter.next()
will return None
when there are no items left.
A Result<T, E>
can be either Ok(T)
or Err(E)
- here all our lines are numbers,
so we only ever see Ok(i64)
.
So, how do we end up with "an array of numbers"?
Well, if we call .unwrap()
on the result of s.next()
, we'll go from an Option<Result<i64, E>>
to just a Result<i64, E>
:
fn main() -> anyhow::Result<()> { let mut s = include_str!("input.txt").split('\n').map(str::parse::<i64>); dbg!(s.next().unwrap()); dbg!(s.next().unwrap()); dbg!(s.next().unwrap()); Ok(()) }
cargo run --quiet [src/main.rs:5] s.next().unwrap() = Ok( 1470, ) [src/main.rs:6] s.next().unwrap() = Ok( 1577, ) [src/main.rs:7] s.next().unwrap() = Ok( 1054, )
And if we call .unwrap()
once more, then we just get plain i64
values:
fn main() -> anyhow::Result<()> { let mut s = include_str!("input.txt").split('\n').map(str::parse::<i64>); dbg!(s.next().unwrap().unwrap()); dbg!(s.next().unwrap().unwrap()); dbg!(s.next().unwrap().unwrap()); Ok(()) }
cargo run --quiet [src/main.rs:3] s.next().unwrap().unwrap() = 1470 [src/main.rs:4] s.next().unwrap().unwrap() = 1577 [src/main.rs:5] s.next().unwrap().unwrap() = 1054
So close! But.. what's happening here exactly?
Well, Option<T>::unwrap()
either panics (if it encounters the None
variant), or returns a T
.
Panics?! Isn't that bad?
It's not that bad! In the case of our program, we can't do anything useful if one of the lines isn't a number, so we may as well stop the program safely - ie., panic.
Fair enough. What about the second unwrap()
?
That one is Result<T, E>::unwrap()
- it works similarly. If it encounters
the Err
variant, it panics (with a message formatted from E
, the error
type). Otherwise, it also returns a T
.
Okay. Quick question: couldn't we pass unwrap
to map
so that we unwrap
all the items, as they're retrieved from the iterator?
Yes we could! Let's do it.
fn main() -> anyhow::Result<()> { let mut s = include_str!("input.txt") .split('\n') .map(str::parse::<i64>) .map(Result::unwrap); dbg!(s.next().unwrap()); dbg!(s.next().unwrap()); dbg!(s.next().unwrap()); Ok(()) }
$ cargo run --quiet [src/main.rs:6] s.next().unwrap() = 1470 [src/main.rs:7] s.next().unwrap() = 1577 [src/main.rs:8] s.next().unwrap() = 1054
Okay so... checks notes now s
is an Iterator<Item = i64>
, right?
That's correct!
So why are we still unwrapping?
Well, because we can still run out of items - so .next()
is still returning
Option<i64>
.
Uhhh can you show me when that would happen?
fn main() -> anyhow::Result<()> { let mut s = include_str!("input.txt") .split('\n') .map(str::parse::<i64>) .map(Result::unwrap) .skip(198); // new! dbg!(s.next().unwrap()); dbg!(s.next().unwrap()); dbg!(s.next().unwrap()); Ok(()) }
$ cargo run --quiet [src/main.rs:8] s.next().unwrap() = 1282 [src/main.rs:9] s.next().unwrap() = 1306 thread 'main' panicked at 'called `Option::unwrap()` on a `None` value', src/main.rs:10:19 note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
Ohh, right - only 200 lines in our input.txt
file, so if we keep
calling .next()
after that, we finally get a None
. Gotcha.
So, let's keep moving with our probl-
Hold on, hold on - sorry to interrupt, but.. what if I didn't want
to call Result::unwrap
- what if instead of panicking, I wanted to
return a neat error?
Let's come back to this in a little while. Pinky promise!
Ffffine.
So! The problem. We need to find a pair of numbers in the input, whose sum is 2020 - and then multiply them.
Let's try some type-driven development:
fn find_pair_whose_sum_is_2020(s: Vec<i64>) -> Option<(i64, i64)> { todo!() }
So, given a Vec<i64>
- which arguably is as close as we'll come to an "array"
today, this function should try to find two numbers whose sum is 2020, and return
them as a tuple, like so: (2019, 1)
.
However it's not simply returning an (i64, i64)
because it's entirely
possible that such a pair does not exist! If our input is just vec![1, 3, 5]
, well, no combination of two numbers will add up to 2020.
Before we implement this function, let's try and figure out how we'd use it.
So far, all we have is an Iterator<Item = i64>
. But this function wants
random access to any item in our collection, so it asks for a Vec<i64>
.
Iterator::collect is the tool for the job.
Our main
function becomes:
fn main() -> anyhow::Result<()> { let pair = find_pair_whose_sum_is_2020( include_str!("input.txt") .split('\n') .map(str::parse::<i64>) .map(Result::unwrap) .collect(), ); dbg!(pair); Ok(()) } fn find_pair_whose_sum_is_2020(s: Vec<i64>) -> Option<(i64, i64)> { todo!() }
This compiles:
$ cargo check Finished dev [unoptimized + debuginfo] target(s) in 0.01s
But it doesn't run:
$ cargo run --quiet thread 'main' panicked at 'not yet implemented', src/main.rs:17:5 note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
Ohhh, so that's what todo!()
does?
Right! It lets us mark something as "to be done later", and it'll compile
(instead of complaining that we're not returning the right type, which
would've happened if we had left find_pair_whose_sum_is_2020
empty)
Groovy. And it ends in a !
because?
Because it's a macro, not a function.
So now all we have to do is implement that function!
Well, Vec<i64>
is suspiciously array-like, so we have things like .len()
,
that give us the number of items it has, as an usize
value, and then we can
index it with []
, just like in JavaScript.
So, let's give it a shot:
fn find_pair_whose_sum_is_2020(s: Vec<i64>) -> Option<(i64, i64)> { for i in 0..s.len() { for j in 0..s.len() { if i == j { continue; } if s[i] + s[j] == 2020 { return Some((s[i], s[j])); } } } None }
What's happening here? Nested loops?
Yeah! We want all possible pairs of numbers in the input.
And the continue
is there because...?
Because if our first item is 1010
, we don't want to add it
to itself and find 2020
. The pairs have to be made up of
different items.
Ah, makes sense.
This solution actually works!
$ cargo run --quiet [src/main.rs:11] pair = Some( ( 376, 1644, ), ) $ echo $((376 + 1644)) 2020
Hurray! Can we improve on it?
Well, I have a few modifications in mind...
First off, let's actually address bear's polite request for "proper error handling".
Just as we have collected an Iterator<Item = i64>
into a Vec<i64>
, so can
we collect an Iterator<Item = Result<i64, E>>
into a Result<Vec<i64>, E>
.
Oooooh. So it's a different implementation of collect
, and that one simply
stops on the first error?
Yes! If none of the items were the Err
variant, then you get an Ok(some_vec)
,
otherwise, you get an Err(first_error)
.
Let's try it:
fn main() -> anyhow::Result<()> { let pair = find_pair_whose_sum_is_2020( include_str!("input.txt") .split('\n') .map(str::parse::<i64>) .collect::<Result<Vec<_>, _>>()?, ); dbg!(pair); Ok(()) }
(This code has the exact same output - I'm going to stop showing shell sessions now.)
Nice! Also, that's a big turbofish.
What's that ?
for again? After the collect()
?
It's sort of like unwrap()
, in the sense that it takes a Result<T, E>
and "returns" ("evaluates to", really) a T
.
But it doesn't panic?
It doesn't panic. It returns an Err(E)
if the Result
is the Err
variant.
Ahh, so it only works in functions that themselves return Result<T, E>
?
Right!
But our function returns an... anyhow::Result<()>
? Where's the E
?
Well, anyhow
is a crate that helps with error handling - it comes with
an error type that can contain any other error, really.
So the definition of anyhow::Result
is actually:
pub type Result<T, E = Error> = core::result::Result<T, E>;
And the Error
here is anyhow::Error
.
Right. And what's that ()
in our Result<()>
?
The empty tuple!
See how our find_pair_whose_sum_is_2020
function returns an Option<(i64, i64)>
? Well, same thing - except with 0 fields instead of two.
And that type, ()
, has size...
Zero. It's free.
Okay! So, our code is in good shape, I think:
fn main() -> anyhow::Result<()> { let pair = find_pair_whose_sum_is_2020( include_str!("input.txt") .split('\n') .map(str::parse::<i64>) .collect::<Result<Vec<_>, _>>()?, ); dbg!(pair); Ok(()) } fn find_pair_whose_sum_is_2020(s: Vec<i64>) -> Option<(i64, i64)> { for i in 0..s.len() { for j in 0..s.len() { if i == j { continue; } if s[i] + s[j] == 2020 { return Some((s[i], s[j])); } } } None }
...but I want to show y'all some more stuff.
See, find_pair_whose_sum_is_2020
sorta bothers me. You know what would be
cool? A function that returns all pairs, like that:
fn pairs(s: Vec<i64>) -> Vec<(i64, i64)> { todo!() }
Mhh.. do we really need to take a Vec<i64>
here? What about other
collection types? Could this not work on a [i64; 12]
for example?
A fixed-size array?
It could! We could take a slice instead.
fn all_pairs(s: &[i64]) -> Vec<(i64, i64)> { todo!() }
Let's actually implement it:
fn all_pairs(s: &[i64]) -> Vec<(i64, i64)> { let mut pairs: Vec<_> = Default::default(); for i in 0..s.len() { for j in 0..s.len() { pairs.push((s[i], s[j])) } } pairs }
And then we can use it from find_pair_whose_sum_is_2020
:
fn find_pair_whose_sum_is_2020(s: Vec<i64>) -> Option<(i64, i64)> { for (a, b) in all_pairs(&s[..]) { if a + b == 2020 { return Some((a, b)); } } None }
And that version still works!
Cool, cool. But I'm thinking... what if we find a pair really early on?
In that case, wouldn't it be a waste to compute "all the pairs" if we're only going to use the first few pairs?
Indeed! Any ideas on how to fix this?
Well, instead of returning a Vec<(i64, i64)>
from all_pairs
, we could
return... an Iterator<Item = (i64, i64)>
?
We could! In fact, you can iterate over a Vec
, so we can already
use it "iterator-style":
fn find_pair_whose_sum_is_2020(s: Vec<i64>) -> Option<(i64, i64)> { all_pairs(&s[..]).into_iter().find(|(a, b)| a + b == 2020) }
Whoa.
We're still building the whole Vec
though - even if we "find" a
pair that sums to 2020 early on.
Correct! Let's fix that, too.
fn all_pairs(s: &[i64]) -> impl Iterator<Item = (i64, i64)> + '_ { s.iter() .copied() .enumerate() .map(move |(a_index, a)| { s.iter() .copied() .enumerate() .filter_map(move |(b_index, b)| { if a_index == b_index { None } else { Some((a, b)) } }) }) .flatten() }
Whew, that's... kind of gnarly.
Can we write it some other way?
We could! Definitely could. Or we could just use the itertools
crate.
$ cargo add itertools Adding itertools v0.9.0 to dependencies
And then our whole solution becomes:
use itertools::Itertools; fn main() -> anyhow::Result<()> { let pair = find_pair_whose_sum_is_2020( include_str!("input.txt") .split('\n') .map(str::parse::<i64>) .collect::<Result<Vec<_>, _>>()?, ); dbg!(pair); Ok(()) } fn find_pair_whose_sum_is_2020(s: Vec<i64>) -> Option<(i64, i64)> { s.into_iter() .tuple_combinations() .find(|(a, b)| a + b == 2020) }
Whoa. At this point, do we even need find_pair_whose_sum_is_2020
as a separate
function?
Not really, no!
use itertools::Itertools; fn main() -> anyhow::Result<()> { let (a, b) = include_str!("input.txt") .split('\n') .map(str::parse::<i64>) .collect::<Result<Vec<_>, _>>()? .into_iter() .tuple_combinations() .find(|(a, b)| a + b == 2020) .expect("no pair had a sum of 2020"); dbg!(a + b); dbg!(a * b); Ok(()) }
$ cargo run --quiet [src/main.rs:13] a + b = 2020 [src/main.rs:14] a * b = 618144
Super neat!
Why do we need that .collect
though? I know we need to handle errors,
but couldn't we just use something like itertools::process_results?
We couldn't, because tuple_combinations needs the Iterator to be Clone
.
Ah, because it's iterating through the input several times to make up the combinations...
...and you can't do that with a single iterator, since once you retrieve a value, it's removed from the iterator.
So we're done with part 1?
I sure hope so!
Part 2
Let's check out the second part of the problem statement:
In your expense report, what is the product of the three entries that sum to 2020?
Wait, wait! I can do this one!
use itertools::Itertools; fn main() -> anyhow::Result<()> { let (a, b, c) = include_str!("input.txt") .split('\n') .map(str::parse::<i64>) .collect::<Result<Vec<_>, _>>()? .into_iter() .tuple_combinations() .find(|(a, b, c)| a + b + c == 2020) .expect("no tuple of length 3 had a sum of 2020"); dbg!(a + b + c); dbg!(a * b * c); Ok(()) }
$ cargo run --quiet [src/main.rs:13] a + b + c = 2020 [src/main.rs:14] a * b * c = 173538720
Nicely done bear! Good thing we brought in itertools.
Bye now! 👋
Thanks to my sponsors:
If you liked what you saw, please support my work!
Here's another article just for you:
I've been banging the same drum for years: APIs must be carefully designed.
This statement doesn't resonate the same way with everyone. In order to really understand what I mean by "careful API design", one has to have experienced both ends of the spectrum.
But there is a silver lining - once you have experienced "good design", it's really hard to go back to the other kind. Even after acknowledging that "good design" inevitably comes at a cost, whether it's cognitive load, compile times, making hiring more challenging, etc.