Day 9 (Advent of Code 2020)
👋 This page was last updated ~5 years ago. Just so you know.
Thanks to my sponsors: Lena Schönburg, Chris, David Barsky, avborhanian, Michal Hošna, Jim, Herman J. Radtke III, Valentin Mariette, Andy Gocke, Chris Emery, Isak Sunde Singh, René Ribaud, Michael, Antoine PESTEL-ROPARS, Romain Kelifa, Aleksandre Khokhiashvili, Nicolas Riebesel, Tabitha, Horváth-Lázár Péter, Marcin Kołodziej and 266 more
Day 9’s problem statement is convoluted - the “ah maybe that’s why I don’t usually do Advent of Code” kind of convoluted, but let’s give it a go anyway.
So, we have a series of numbers, like so:
35
20
15
25
47
40
62
55
65
95
102
117
150
182
127
219
299
277
309
576
And uh the first N numbers are a “preamble” and every number that comes after that must be the sum of any two of the numbers that come before it.
For the example above, N is 5. So, again, there’s probably a smart and fast way to solve this, but I’ll go again for a simple and correct solution instead.
One thing I like about this problem is that it lets me showcase a bunch of cool methods.
We’re going to iterate over windows of size n+1 - so here, elements 0..=5 (inclusive), then 1..=6, then 2..=7, and so on. Then we’re going to get all possible combinations of elements 0..5 (exclusive), 1..6, 2..7, and see if the sum of any of those combinations is equal to the last element of our window.
use itertools::Itertools;
fn main() {
let numbers = include_str!("input.txt")
.lines()
.map(|x| x.parse::<usize>().unwrap())
.collect::<Vec<_>>();
let n = 5;
let answer = numbers.windows(n + 1).find_map(|s| {
if (&s[..n])
.iter()
.tuple_combinations()
.any(|(a, b)| a + b == s[n])
{
None
} else {
Some(s[n])
}
});
println!("answer = {:?}", answer);
}
$ cargo run --quiet
answer = Some(127)
Cool, this matches the example! I guess we’re already done?
Let’s try it with n = 25
and the actual input:
$ cargo run --quiet
answer = Some(26134589)
Hey, that’s the correct answer!
Onwards!
Part 2
The next part asks us to find “a contiguous set of at least two numbers in our list which sum to the invalid number from step 1”.
Well, that doesn’t seem too hard either. One thing we can do is to sum all the windows of size 2, then all the windows of size 3, and so on - and sum the items in all of these. As soon as we reach the answer, we’re done!
let answer = answer.unwrap();
let answer2 = (2..numbers.len())
.into_iter()
.map(|n| numbers.windows(n).map(|s| s.iter().sum::<usize>()))
.flatten()
.find(|&n| n == answer);
println!("answer2 = {:?}", answer2);
$ cargo run --quiet
answer2 = Some(26134589)
Ok, so we did find a contiguous set of numbers whose sum is the same as the answer we found in part 1, but we don’t know where or how large the set was.
Let’s address that:
let answer2 = (2..numbers.len())
.into_iter()
.map(|n| {
numbers
.windows(n)
.enumerate()
.map(move |(i, s)| (n, i, s.iter().sum::<usize>()))
})
.flatten()
.find(|&(_, _, sum)| sum == answer);
let (n, i, _) = answer2.unwrap();
let set = &numbers[i..][..n];
println!("sum({:?}) = {}", set, answer);
$ cargo run --quiet
sum([1503494, 978652, 1057251, 1142009, 1239468, 1407633, 1048040, 1484541, 1164289, 1432864, 1792914, 2556472, 2464510, 1750429, 1753116, 1673488, 1685419]) = 26134589
That’s better.
Now we need to add together the smallest and largest number in this contiguous range:
let answer3 = set.iter().max().unwrap() + set.iter().min().unwrap();
dbg!(answer3);
$ cargo run --quiet
[src/main.rs:39] answer3 = 3535124
Aaand we’re done! That was easy, I don’t know what I was worried about.
Here's another article just for you:
Proc macro support in rust-analyzer for nightly rustc versions
I don’t mean to complain. Doing software engineering for a living is a situation of extreme privilege. But there’s something to be said about how alienating it can be at times.
Once, just once, I want to be able to answer someone’s “what are you working on?” question with “see that house? it wasn’t there last year. I built that”.
Instead for now, I have to answer with: “well you see… support for proc macros was broken in rust-analyzer for folks who used a nightly rustc toolchain, due to incompatibilities in the bridge (which is an unstable interface in the first place), and it’s bound to stay broken for the foreseeable future, not specifically because of technical challenges, but mostly because of human and organizational challenges, and I think I’ve found a way forward that will benefit everyone.”