timvisee/advent-of-code-2021

🎄 My Advent of Code solutions in Rust. http://adventofcode.com/2021

Advent of Code 2021 in Rust

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

I attempt to develop a standalone, elegant, compact and fast solution for each problem (two each day).

Previous year I did the same, solving everything in under a second:

• https://timvisee.com/blog/solving-aoc-2020-in-under-a-second/
• https://github.com/timvisee/advent-of-code-2020

Timings

Here is how long each solution runs. All solutions are measured (non scientifically) in bench.rs on an AMD Ryzen 9 5900X (24) @ 3.7GHz machine running Linux.

	part A	part B
day 1	0.025ms	0.024ms
day 2	0.024ms	0.025ms
day 3	0.021ms	0.023ms
day 4	0.075ms	0.106ms
day 5	0.110ms	0.220ms
day 6	0.0027ms	0.0028ms
day 7	0.013ms	0.013ms
day 8	0.008ms	0.026ms
day 9	0.012ms	0.036ms
day 10	0.011ms	0.015ms
day 11	0.019ms	0.039ms
day 12	0.015ms	0.272ms
day 13	0.038ms	0.044ms
day 14	0.007ms	0.008ms
day 15	1.05 ms	37.7 ms
day 16	0.002ms	0.007ms
day 17	0.0002ms	0.095ms
day 18	0.141ms	2.61 ms
day 19	1.03 ms	1.03 ms
day 20	0.042ms	3.10 ms
day 21	0.0008ms	0.016ms
day 22	0.083ms	1.74 ms

	one-by-one (1 CPU core)	parallel
everything	50.36 ms	39.53ms

Run solutions

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

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

# or run everything in parallel
cd ../runner
cargo +nightly run --release --bin runner-par

# or benchmark every day
cd ../runner
cargo +nightly run --release --bin bench

Some solutions require Rust Nightly, that's why +nightly is included.

Other years

• 2023
• 2022
• 2021 (current)
• 2020
• 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-2021's Issues

Day 01b

I'm using AoC this year to learn Rust, so I really appreciate the time you've put into doing this.

I'm already stuck on this though with array_windows, particularly these lines

.array_windows()
.filter(|[a, _, _, d]| a < d)

I'm very confused on how this works. My understanding is that array_windows creates a moving window iterable, and so I'm stumped on the following:

• how is it inferred that the window is 3 elements in length?
• where is the sum performed?
• how is array_windows different from windows?

I appreciate any help you can offer

Intuition behind Day 3 Part 1

Hey there Tim,

First of all, thank you very much for working on this year's advent of code in the open in Rust, it's really helping me learn.

I'm having quite a hard time grasping the intuition behind the bit-shifting going on in the first part of the day 3 solution. I understand that at a high level, a left bit shift multiplies by two and a right bit shift divides by two. What I don't understand is for example on line 12 where bits is ANDed with 1, shifted to the left i, then immediately shifted to the right by i, and finally added to the count.

Line 17 is also hard for me to understand and would love some explanation there as well.

Perhaps if you (or anybody else for that matter) has a spare moment and could help me understand what is going on that would be awesome!

I appreciate your work very much!

Where is hyperfine used?

Hello, thanks for putting these solutions!

I wish to ask where hyperfine is used in the codebase, as it is mentioned in the README. It seems to me that the runner rust programs are using the took crate instead.

Thanks for doing this!

Just wanted to say thanks for publishing all these! I'm learning a ton just from reading your solutions!

=)

https://github.com/timvisee/advent-of-code-2021#timings

yes .. perf life

Day08 Part B runs into unreachable code macro

The current code runs into the unreachable code macro.

I'm not sure why, but I think the &[u8] array was not split at this.split(|&b| b == b' ') command.

Day15b runtime can be improved by bucket queue

The pathfinding library implements classic dijkstra's algorithm by a BinaryHeap.

It can be further improved, some of my thoughts are:

1. We can use a bucket queue because all weights are small integer, so the cost must be an integer between (0, 9 * V), where V is the number of vertex.
2. We can pre-compute a tighter cost upper bound than 9 * V thanks to the graph setup. Generally we don't know the path from start to end without traversing. However in the aoc setup, we do know a path from start to end: so we can sum up the risk from (0, 0) -- (W - 1, 0) -- (W - 1, H - 1) and use that as the bucket size.

I implemented the bucket queue dijkstra and it's around 20% faster than the binary heap approach on day15b setup.

Question regarding day 9

Hi there,
I'm reading the solution of day 9 part A and I do not understand this line

                sum += (cell - b'0') as usize + 1;

What is b'0'?

I'm pretty new to Rust, and in this case I'm not finding anything in documentation.
...or I don't know where to look 😭

Thanks a lot!

Solution for day 7, part B is incorrect

For the input

1,1,1,1,1,1,20

the current code returns 172, while the correct minimal fuel consumption is 171. After doing a few estimates with paper and pencil, I believe it's enough to check the ceiled and floored arithmetic mean, but simply rounding to the nearest integer is not enough.

Note that the current code also fails on real-world Advent of Code inputs, notably on mine. :)

A solution I believe to be correct is here: https://github.com/smarnach/aoc2021/blob/master/src/bin/day07.rs

Question regarding day 6.

Hello! I'm reading your solution to day 6, and I can't figure out why did you add 7 when iterating through the days for the index. If you can explain that to me I'd be greatly appreciated!

Day17a runtime improvements

Thanks for your work!

One suggestion for day17a is to directly calculate the answer instead of "firing" a shot. The probe will hit the x-axis with a velocity of -by (start velocity). So in the next step it should not overshoot, therefore n(n+1)/2 = -(min(by))-1

fn main() {
    let input = "target area: x=269..292, y=-68..-44";
    let bounds: (i32, i32) = input[13..]
        .split_once(", ")
        .and_then(|(_,by)| {
            let (y, yy) = by.split_once("..").unwrap();
            Some((y[2..].parse::<i32>().unwrap(), yy.parse::<i32>().unwrap()))
        })
        .unwrap();
    // Solve n(n+1)/2 where n = -(min(by)) - 1
    let n = -bounds.0.min(bounds.1) - 1;
    println!("{}", (n*(n+1))/2);
}

Day 6 Intuition

Hey Tim it's me again 👋

If you have a moment, would love some explanation behind your day 6 optimized solution, purely out of curiosity. How did you come up with it? Thanks!

Absolutely no worries at all if you do not have time/desire to answer! But thought I'd ask just in case you do.