Home
Log in
Avatar for fasterthanlime fasterthanlime
Dec 23, 2020 clock icon 9 min #rust · #advent-of-code

Day 10 (Advent of Code 2020)

From the series Advent of Code 2020
1
2
3
4
5
6
7
8
9
10
11
12
13
14

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

Bear

Day, 10! Day, 10!

Okay, Day 10.

Again, the problem statement is very confusing - but what it all boils down to is this. We have a list of numbers:

16
10
15
5
1
11
7
19
6
12
4

To which we need to add 0 and whatever the maximum was, plus three:

16
10
15
5
1
11
7
19
6
12
4
0
22

From there on, if we take them in order, we'll have gaps of 1 and gaps of 3:

0
1 // 1
4 // 3
5 // 1
6 // 1
7 // 1
10 // 3
11 // 1
12 // 1
15 // 3
16 // 1
19 // 3
22 // 3

And we need to multiply the amount of 1-gaps with the amount of 3-gaps we find.

We can use some of the techniques we've very recently seen: use some types to represent the results, use windows on a slice to deal with contiguous sets of items, and a couple new tricks:

Rust code
#[derive(Default, Clone, Copy, Debug)]
struct Results {
    ones: usize,
    threes: usize,
}

fn main() {
    let mut numbers: Vec<_> = std::iter::once(0)
        .chain(
            include_str!("input.txt")
                .lines()
                .map(|x| x.parse::<usize>().unwrap()),
        )
        .collect();
    // clippy told me to use `sort_unstable`
    numbers.sort_unstable();

    if let Some(&max) = numbers.iter().max() {
        // numbers is still sorted after this
        numbers.push(max + 3);
    }

    let results = numbers.windows(2).fold(Results::default(), |acc, s| {
        if let [x, y] = s {
            match y - x {
                1 => Results {
                    ones: acc.ones + 1,
                    ..acc
                },
                3 => Results {
                    threes: acc.threes + 1,
                    ..acc
                },
                gap => panic!("invalid input (found {} gap)", gap),
            }
        } else {
            unreachable!()
        }
    });
    dbg!(results, results.ones * results.threes);
}
Cool bear's hot tip

Note that if we used Rust nightly, we could use array_windows instead, which would give us an [usize; 2] and then we wouldn't need an if let because it would be an irrefutable pattern!

Shell session
$ cargo run --quiet
[src/main.rs:40] results = Results {
    ones: 7,
    threes: 5,
}
[src/main.rs:40] results.ones * results.threes = 35

Let's try it with the real input:

Shell session
$ cargo run --quiet
[src/main.rs:40] results = Results {
    ones: 75,
    threes: 37,
}
[src/main.rs:40] results.ones * results.threes = 2775

And we're done with the first part!

Part 2

The next problem is: what are all the possible ways in which we can connect our adapters? All the valid chains?

Say we have:

1
2
3
5
6

We can have [1, 2, 3, 5, 6], [1, 2, 3, 6], [1, 2, 5, 6], [1, 3, 5, 6], or [1, 3, 6].

Just like in Day 7, we pretty much have a DAG here:

But, unlike Day 7, we're not interested in walking all the nodes of a subgraph, we're interested in all the different ways we can traverse that graph!

But we're not interested in exactly what those paths are, we're interested in how many paths exist - so I think we can be a little smart this time. As a treat.

Consider the last node, 6 - there's only one way to traverse the graph from there, because there are no edges starting from it.

Now consider 5 - there's again, only one way to traverse the graph from there: we can only go to 6.

For 3, we can go either to 5 or to 6, so the number of ways we can traverse the graph if we start from 3 is the sum of the ways we can traverse the graph if we start from 5 or if we start from 6, ie. 1 + 1 = 2.

We're starting to have a mapping from "node" to "number of ways to traverse the graph starting from it":

node_6 = 1
node_5 = node_6 = 1
node_3 = node_5 + node_6 = 1 + 1 = 2
node_2 = node_3 + node_5 = 2 + 1 = 3
node_1 = node_2 + node_3 = 3 + 2 = 5

That sounds like something that's both inexpensive and rather uncomplicated to compute! Note that our results will be slightly different because we need to take into account an additional initial node of 0 and a final node of max + 3, so we're going to end up with more paths:

Rust code
fn main() {
    let mut numbers: Vec<_> = std::iter::once(0)
        .chain(
            // this file contains 1, 2, 3, 5, 6
            include_str!("input2.txt")
                .lines()
                .map(|x| x.parse::<usize>().unwrap()),
        )
        .collect();
    numbers.sort_unstable();

    // numbers is still sorted after this
    numbers.push(numbers.iter().max().unwrap() + 3);

    let mut num_paths = HashMap::new();

    let n = numbers.len();
    num_paths.insert(numbers.last().copied().unwrap(), 1);
    for i in (0..(numbers.len() - 1)).into_iter().rev() {
        let i_val = numbers[i];
        let range = (i + 1)..=std::cmp::min(i + 3, n - 1);

        let num_neighbors: usize = range
            .filter_map(|j| {
                let j_val = numbers[j];
                let gap = j_val - i_val;
                if (1..=3).contains(&gap) {
                    Some(num_paths.get(&j_val).unwrap())
                } else {
                    None
                }
            })
            .sum();
        num_paths.insert(i_val, num_neighbors);
    }

    for &n in numbers.iter().rev() {
        let &m = num_paths.get(&n).unwrap();
        println!(
            "from {}, there's {} {}",
            n,
            m,
            if m == 1 { "path" } else { "paths" }
        );
    }
}
Shell session
$ cargo run --quiet
from 9, there's 1 path
from 6, there's 1 path
from 5, there's 1 path
from 3, there's 2 paths
from 2, there's 3 paths
from 1, there's 5 paths
from 0, there's 10 paths

Let's try this on my actual puzzle input:

Shell session
$ cargo run --quiet
from 186, there's 1 path
from 183, there's 1 path
from 182, there's 1 path
from 181, there's 2 paths
from 180, there's 4 paths
from 177, there's 4 paths
from 176, there's 4 paths
from 173, there's 4 paths
from 170, there's 4 paths
from 167, there's 4 paths
from 166, there's 4 paths
from 165, there's 8 paths
from 164, there's 16 paths
from 163, there's 28 paths
from 160, there's 28 paths
from 157, there's 28 paths
from 154, there's 28 paths
from 153, there's 28 paths
from 152, there's 56 paths
from 151, there's 112 paths
from 148, there's 112 paths
from 145, there's 112 paths
from 144, there's 112 paths
from 143, there's 224 paths
from 142, there's 448 paths
from 141, there's 784 paths
from 138, there's 784 paths
from 137, there's 784 paths
from 136, there's 1568 paths
from 135, there's 3136 paths
from 134, there's 5488 paths
from 131, there's 5488 paths
from 128, there's 5488 paths
from 127, there's 5488 paths
from 126, there's 10976 paths
from 125, there's 21952 paths
from 122, there's 21952 paths
from 121, there's 21952 paths
from 118, there's 21952 paths
from 115, there's 21952 paths
from 114, there's 21952 paths
from 113, there's 43904 paths
from 112, there's 87808 paths
from 111, there's 153664 paths
from 108, there's 153664 paths
from 107, there's 153664 paths
from 106, there's 307328 paths
from 103, there's 307328 paths
from 102, there's 307328 paths
from 101, there's 614656 paths
from 100, there's 1229312 paths
from 99, there's 2151296 paths
from 96, there's 2151296 paths
from 95, there's 2151296 paths
from 94, there's 4302592 paths
from 93, there's 8605184 paths
from 92, there's 15059072 paths
from 89, there's 15059072 paths
from 86, there's 15059072 paths
from 85, there's 15059072 paths
from 84, there's 30118144 paths
from 83, there's 60236288 paths
from 82, there's 105413504 paths
from 79, there's 105413504 paths
from 78, there's 105413504 paths
from 77, there's 210827008 paths
from 76, there's 421654016 paths
from 73, there's 421654016 paths
from 72, there's 421654016 paths
from 71, there's 843308032 paths
from 70, there's 1686616064 paths
from 69, there's 2951578112 paths
from 66, there's 2951578112 paths
from 63, there's 2951578112 paths
from 60, there's 2951578112 paths
from 59, there's 2951578112 paths
from 58, there's 5903156224 paths
from 57, there's 11806312448 paths
from 54, there's 11806312448 paths
from 53, there's 11806312448 paths
from 52, there's 23612624896 paths
from 51, there's 47225249792 paths
from 48, there's 47225249792 paths
from 45, there's 47225249792 paths
from 42, there's 47225249792 paths
from 41, there's 47225249792 paths
from 40, there's 94450499584 paths
from 39, there's 188900999168 paths
from 38, there's 330576748544 paths
from 35, there's 330576748544 paths
from 34, there's 330576748544 paths
from 33, there's 661153497088 paths
from 32, there's 1322306994176 paths
from 31, there's 2314037239808 paths
from 28, there's 2314037239808 paths
from 25, there's 2314037239808 paths
from 24, there's 2314037239808 paths
from 23, there's 4628074479616 paths
from 22, there's 9256148959232 paths
from 19, there's 9256148959232 paths
from 18, there's 9256148959232 paths
from 17, there's 18512297918464 paths
from 14, there's 18512297918464 paths
from 13, there's 18512297918464 paths
from 12, there's 37024595836928 paths
from 11, there's 74049191673856 paths
from 10, there's 129586085429248 paths
from 7, there's 129586085429248 paths
from 6, there's 129586085429248 paths
from 3, there's 129586085429248 paths
from 2, there's 129586085429248 paths
from 1, there's 259172170858496 paths
from 0, there's 518344341716992 paths

And there we have it! 518344341716992 is our final answer.

Until next time, be kind with yourself!

You're reading the Advent of Code 2020 series.
1
2
3
4
5
6
7
8
9
10
11
12
13
14

Reddit logo Comment on /r/fasterthanlime

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

Github logo Donate on GitHub Patreon logo Donate on Patreon

Here's another article just for you:

Peeking inside a Rust enum
Aug 28, 2020
clock icon 1 hour 14 min #rust · #c · #memory

During a recent Rust Q&A Session on my twitch channel, someone asked a question that seemed simple: why are small string types, like SmartString or SmolStr, the same size as String, but small vec types, like SmallVec, are larger than Vec?

Now I know I just used the adjective simple, but the truth of the matter is: to understand the question, we're going to need a little bit of background.

Read more