# Day 10 (Advent of Code 2020)

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

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)]structResults{ones:usize,threes:usize, }fnmain(){letmutnumbers: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();ifletSome(&max)= numbers.iter().max(){// numbers is still sorted after thisnumbers.push(max +3);}letresults = numbers.windows(2).fold(Results::default(), |acc, s| {iflet[x, y]= s {matchy - 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!

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

fnmain(){letmutnumbers:Vec<_>= std::iter::once(0).chain(// this file contains 1, 2, 3, 5, 6include_str!("input2.txt").lines().map(|x| x.parse::<usize>().unwrap()),).collect();numbers.sort_unstable();// numbers is still sorted after thisnumbers.push(numbers.iter().max().unwrap()+3);letmutnum_paths =HashMap::new();letn = numbers.len();num_paths.insert(numbers.last().copied().unwrap(),1);foriin(0..(numbers.len()-1)).into_iter().rev(){leti_val = numbers[i];letrange =(i +1)..=std::cmp::min(i +3, n -1);letnum_neighbors:usize= range.filter_map(|j| {letj_val = numbers[j];letgap = 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&ninnumbers.iter().rev(){let&m = num_paths.get(&n).unwrap();println!("from {}, there's {} {}", n, m,ifm ==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!

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 10 of the Advent of Code 2020 series.

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