Day 9 (Advent of Code 2020)

This article is part of the Advent of Code 2020 series.

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.

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

Shell session
$ 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!

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

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

Rust code
let answer3 = set.iter().max().unwrap() + set.iter().min().unwrap(); dbg!(answer3);
Shell session
$ 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.

This article was made possible thanks to my patrons: Christian Oudard, Ronen Cohen, Matt Welke, Ivan Towlson, Nathan Lincoln, Daniel Wagner-Hall, Felix Weis, Henrik Sylvester Pedersen, Thor Kamphefner, VALENTIN MARIETTE, Kamran Khan, Cole Kurkowski, Arjen Laarhoven, Jeremy Kaplan, Jon Reynolds, Vicente Bosch, Chirag Jain, Ville Mattila, Marie Janssen, Vladyslav Batyrenko, Cameron Clausen, Pierre Guillaume Herveou, Agam Brahma, spike grobstein, Daniel Franklin, Jon Gjengset, Tex, Nick Thomas, Blaž Tomažič, Johan, Paul Marques Mota, Jakub Fijałkowski, Mitchell Hamilton, Ruben Duque, Brad Luyster, Max von Forell, Jake S, Justin, Dimitri Merejkowsky, Chris Biscardi, mrcowsy, René Ribaud, Alex Doroshenko, Julian, Vincent, Steven McGuire, Jack DeNeut, Chad Birch, Martin-Louis Bright, Chris Emery, Bob Ippolito, Jomer, John Van Enk, metabaron, Isak Sunde Singh, DaVince, Philipp Gniewosz, Richard Hill, Simon Rüegg, Roman Levin, V, Max Fermor, Mads Johansen, lukvol, Ives van Hoorne, Greg Stoll, Jan De Landtsheer, Scott Munro, Михаил Захаркин, Daniel Strittmatter, Evgeniy Dubovskoy, Sandro, Alex Rudy, Jake Rodkin, Shane Lillie, Romet Tagobert, Geekingfrog, Douglas Creager, Corey Alexander, Molly Howell, Jeff Crocker, knutwalker, Zachary Dremann, Olivier Peyrusse, Sebastian Ziebell, Julien Roncaglia, eigentourist, Amber Kowalski, Charlton Eivind Rodda, Jan Schiefer, Edil Kratskih, Chris Emerson, Matthew Campbell, Krasimir Slavkov, Juniper Wilde, Paul Kline, Pascal Hartig, Samir Talwar, TD, Kristoffer Ström, Henning Schmick, Ryan Levick, Antoine Boegli, Astrid Bek, Ryan, Yoh Deadfall, Justin Ossevoort, Jeremy, Tomáš Duda, playest, Meghana Gupta, Sebastian Dröge, Adam, Nick Gerace, Jeremy Banks, Rasmus Larsen, exelotl, Ramnivas Laddad, Yury Mikhaylov, Torben Clasen, Sam Rose, Nickolas Fotopoulos, C J Silverio, Walther, Pete Bevin, Shane Sveller, Marcel Jackwerth, Brian Dawn, Clara Schultz, Robert Cobb, jer, Wonwoo Choi, Hawken Rives, João Veiga, Dave Gauer, David Cornu, Richard Pringle, Adam Perry, Yann Schwartz, Jaseem Abid, Zinahe Asnake, Ryan Blecher, Benjamin Röjder Delnavaz, Grégoire Hubert, Matt Jadczak, Nazar Mokrynskyi, Julian Hofer, Mara Bos, Brandon, Jonathan Knapp, Maximilian, Seth Stadick, brianloveswords, Sean Bryant, Ember, Sebastian Zimmer, Makoto Nakashima, Geert Depuydt, Geoff Cant, Geoffroy Couprie, Michael Alyn Miller, Vengarioth, o0Ignition0o, Zaki, Raphael Gaschignard, Romain Ruetschi, Ignacio Vergara, Pascal, Cassie Jones, Pat Monaghan, Jane Lusby, Nicolas Goy, Suhib Sam Kiswani, Henry Goffin, Ted Mielczarek, Random832, Ryszard Sommefeldt, Jesús Higueras, Aurora.

This article is part 9 of the Advent of Code 2020 series.

Read the next part

If you liked this article, please support my work on Patreon!

Become a Patron