# Day 1 (Advent of Code 2020)

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!

Shell session
$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: Shell session $ cargo add anyhow
Updating 'https://github.com/rust-lang/crates.io-index' index

Cool bear's hot tip

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.

Rust code
// in day1/src/main.rs

fn main() -> anyhow::Result<()> {
dbg!(&s[..40]);

Ok(())
}


This reads the file and prints the first 40 bytes:

Shell session
$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: Rust code fn main() -> anyhow::Result<()> { let s = include_str!("input.txt"); dbg!(&s[..40]); Ok(()) }  Shell session $ 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:

Shell session
$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  Cool bear's hot tip 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: Rust code fn main() -> anyhow::Result<()> { let s = include_str!("input.txt").split("\n"); Ok(()) }  Cool bear's hot tip 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(): Rust code 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. Rust code fn main() -> anyhow::Result<()> { let mut s = include_str!("input.txt").split("\n"); dbg!(s.next()); dbg!(s.next()); dbg!(s.next()); Ok(()) }  Shell session $ 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:

json
{
"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:

Rust code
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>?

Cool bear's hot tip

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:

Rust code
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:

Shell session
$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: Shell session 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: Rust code 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: Shell session $ 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:

JavaScript code
["12", "34", "56"].map((x) => parseInt(x, 10))

Cool bear's hot tip

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:

Shell session
> ["12", "34", "56"].map((x) => parseInt(x, 10))
[ 12, 34, 56 ]


But this doesn't:

Shell session
> ["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,
),
)

Cool bear's hot tip

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>:

Rust code
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(())
}

Shell session
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:

Rust code
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(())
}

Shell session
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.

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.

Rust code
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(())
}

Shell session
$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? Rust code 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(()) }  Shell session $ 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:

Rust code
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:

Rust code
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:

Shell session
$cargo check Finished dev [unoptimized + debuginfo] target(s) in 0.01s  But it doesn't run: Shell session $ 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:

Rust code
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!

Shell session
$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: Rust code 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: Rust code 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: Rust code 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: Rust code 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. Rust code fn all_pairs(s: &[i64]) -> Vec<(i64, i64)> { todo!() }  Let's actually implement it: Rust code 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: Rust code 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": Rust code 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. Rust code 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. Shell session $ cargo add itertools


And then our whole solution becomes:

Rust code
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!

Rust code
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(())
}

Shell session
$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! Rust code 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(()) }  Shell session $ 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! 👋

If you liked what you saw, please support my work!

## Latest video

This is a video about video