timvisee/advent-of-code-2020

:christmas_tree: My Advent of Code solutions in Rust. http://adventofcode.com/2020

Advent of Code 2020 in Rust

My Advent of Code 2020 solutions in the Rust programming language. This repository holds a separate Rust project for each day and part.

This year I attempt to develop a standalone, short, compact and fast solution for each problem (day part).

I've written an article about my solutions here: https://timvisee.com/blog/solving-aoc-2020-in-under-a-second/

Timings

Here is how long each solution takes to run to completion. All solutions are measured (non scientifically) with hyperfine on a i5-4670k @ 3.8Ghz machine running Linux. Timings include binary loading, execution, input and output timings.

	part A	part B
day 1	0.170ms	0.007ms
day 2	0.553ms	0.069ms
day 3	0.009ms	0.013ms
day 4	0.157ms	0.185ms
day 5	0.004ms	0.011ms
day 6	0.031ms	0.056ms
day 7	0.002ms	1.71 ms
day 8	0.022ms	0.131ms
day 9	0.043ms	0.025ms
day 10	0.004ms	0.005ms
day 11	0.007ms	6.56 ms
day 12	0.011ms	0.011ms
day 13	0.002ms	0.004ms
day 14	0.276ms	6.10 ms
day 15	0.227ms	511 ms
day 16	0.209ms	0.526ms
day 17	0.357ms	7.98 ms
day 18	0.246ms	0.228ms
day 19	0.364ms	0.523ms
day 20	0.111ms	0.460ms
day 21	0.464ms	0.293ms
day 22	0.003ms	3.42 ms
day 23	0.005ms	192 ms
day 24	0.105ms	43.2 ms
day 25	27.9 ms

	one-by-one	parallel
everything	699ms	511ms

Run solutions

Each Rust project contains a input.txt file, holding the puzzle input. Simply run the project to see the solution appear.

# One solution requires large stack size, set to allow unlimited size
ulimit -s unlimited

# Switch to day 1a, and run it
cd day01a
cargo run --release

# Or run everything in parallel
cd ../runner
cargo run --release --bin runner-par

# Or benchmark every day
cd ../runner
cargo run --release --bin bench

Some solutions might require Rust Nightly.

Other years

• 2023
• 2022
• 2021
• 2020 (current)
• 2019
• 2018
• 2017

License

This project is released under the GNU GPL-3.0 license. Check out the LICENSE file for more information.

advent-of-code-2020's Issues

day10 solution is not correct and I found a faster one

Hi,

first: Many thanks for sharing your solution and your very insightful webpage, explaining the thinking process. This helped me tremendously.

On my way to solve the puzzle I implemented your solution to have an oracle, and came up with different test scenarios. When I finally got it, I discovered that your solution is not correct. In particular, the hard-coded part, where based on the length of the individual chunks you derive the possible combinations.

With this input it would lead to a wrong result:
0, 2, 4, 6, 8
there is only one way to walk through these adapters.
Your solution discovered one chunk of length 4, being hardcoded to 7 combinations.
This would be correct for
0, 1, 2, 3, 4

My solution is a simple O(n) walk through. I need to sort the array as well, but as I don't build pairs, filter for 3-distance and don't add the starting 0, I ultimately save some time.

On my machine (M1 Pro), with the arc-runner crate, the times are:

Day 10 - Part 2 - combinations_recursive_o_n: 6908379398144
        generator: 20.416µs,
        runner: 27.541µs

Day 10 - Part 2 - hardcoded: 6908379398144
        generator: 20.75µs,
        runner: 38.125µs

Here is my code (only the solving function):

fn combinations_recursive_o_n(input: &[usize]) -> usize {
    let mut adapters = input.to_vec();

    match adapters.len() {
        0 | 1 => 1,
        2 => {
            // only if the higher number can be reached from the start (0) there is an alternative path
            if adapters[0].abs_diff(adapters[1]) <= 3 {
                2
            } else {
                1
            }
        }
        _ => {
            // sorted_adapters.push(0); //add the outlet
            adapters.sort_unstable();
            let sorted_adapters = adapters;

            // println!("adapter sequence: 0-{:?}", sorted_adapters);

            // set up first three nodes
            let mut n_1 = sorted_adapters[1];
            let mut n_2 = sorted_adapters[0];
            let mut n_3 = 0_usize;
            let mut pathes_to_n_1 = if n_1 > 3 { 1_usize } else { 2_usize };
            let mut pathes_to_n_2 = 1_usize;
            let mut pathes_to_n_3 = 1_usize;

            // find ways to reach the last asapter, going through each adapter
            let mut pathes_to_adapter = 0_usize;
            sorted_adapters[2..].iter().for_each(|adapter| {
                pathes_to_adapter = pathes_to_n_1;
                if adapter - n_2 <= 3 {
                    pathes_to_adapter += pathes_to_n_2;
                }
                if adapter - n_3 <= 3 {
                    pathes_to_adapter += pathes_to_n_3;
                }
                // println!("{} ways to adapter {}", pathes_to_adapter, *adapter);
                //update paths
                n_3 = n_2;
                n_2 = n_1;
                n_1 = *adapter;
                pathes_to_n_3 = pathes_to_n_2;
                pathes_to_n_2 = pathes_to_n_1;
                pathes_to_n_1 = pathes_to_adapter;
            });
            pathes_to_adapter
        }
    }
}

Hope that after all these years you still enjoy reading my post. Thanks again for inspiring!!

day04 input parsing will panic for some violations

Hi Tim, I admire your elegant, idiomatic solutions, however sometimes you got lucky.

For example in day04 parsing at

advent-of-code-2020/day04b/src/main.rs

Line 26 in 0dd2865

"byr" => value.parse::<usize>().unwrap().wrapping_sub(1920) <= 82,

you would panic due to calling unwrap() in case the token following byr: is not a sequence of 4 digits (which the task description asked us to check):

https://adventofcode.com/2020/day/4

You can continue to ignore the cid field, but each other field has strict rules about what values are valid for automatic validation:

byr (Birth Year) - four digits; at least 1920 and at most 2002.

Example input:

hgt:157cm byr:hugo ecl:grn iyr:2012
eyr:2030 hcl:#18171d pid:173cm

(Just stumbled upon your solution when trying to improve my Rust coding style to become more idiomatic and looking at other people's solutions)