Home Log in

Dec 22, 2020

3 min #rust · #advent-of-code

Day 9 (Advent of Code 2020)

From the series Advent of Code 2020

14

👋 This page was last updated ~4 years ago. Just so you know.

Thanks to my sponsors: René Ribaud, Colin VanDervoort, Pete LeVasseur, Andy Gocke, Horváth-Lázár Péter, Mark Tomlin, you got maiL, Dylan Anthony, Elijah Voigt, Ivo Murrell, Aleksandre Khokhiashvili, jatescher, Matt Jadczak, Andy F, Ronen Cohen, David Cornu, Marcin Kołodziej, Josh Triplett, Geoffrey Thomas, James Leitch and 264 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:

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.

You're reading the Advent of Code 2020 series.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

Comment on /r/fasterthanlime

Thanks to my sponsors: Julian Schmid, Peter Shih, Braidon Whatley, Urs Metz, WeblWabl, Wojciech Smołka, Rufus Cable, Seth, Mark Tomlin, Daniel Wagner-Hall, Egor Ternovoi, Scott Steele, Kai Kaufman, Isak Sunde Singh, Adam Gutglick, Sean Bryant, Paige Ruten, Michael Alyn Miller, Chris Thackrey, Olly Swanson and 264 more

My work is sponsored by people like you. Donate now so it can keep going:

Continue with GitHub Continue with Patreon

Here's another article just for you:

Rust modules vs files

Jul 01, 2019

18 min #rust

A while back, I asked on Twitter what people found confusing in Rust, and one of the top topics was “how the module system maps to files”.

I remember struggling with that a lot when I first started Rust, so I’ll try to explain it in a way that makes sense to me.

Important note

All that follows is written for Rust 2021 edition. I have no interest in learning (or teaching) the ins and outs of the previous version, especially because it was a lot more confusing to me.