Day 10 (Advent of Code 2020)
fasterthanlime
This article is part of the Advent of Code 2020 series.
- Part 2
Contents
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:
#[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);
}
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!
$ 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:
$ 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:
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" }
);
}
}
$ 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:
$ 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!
This article is part 10 of the Advent of Code 2020 series.
If you liked what you saw, please support my work!
