aoc/year2024/
day14.rs

1//! # Restroom Redoubt
2//!
3//! For part one we jump straight to the final position by multiplying the velocity by 100.
4//! The image appears in part two when the positions of all robots are unique.
5//!
6//! The x coordinates repeat every 101 seconds and the y coordinates repeat every 103 seconds.
7//! For part two, we can treat the coordinates independently, searching for a time when the
8//! [variance](https://en.wikipedia.org/wiki/Variance) of the robots' coordinates is at a minimum.
9//!
10//! Using the [Chinese Remainder Theorem](https://en.wikipedia.org/wiki/Chinese_remainder_theorem)
11//! we combine the two times into a single time mod 10,403 that is the answer.
12use std::cmp::Ordering::*;
13
14use crate::util::iter::*;
15use crate::util::parse::*;
16
17const WIDTH: i32 = 101;
18const HEIGHT: i32 = 103;
19
20type Axis = Vec<(i32, i32)>;
21type Input = (Axis, Axis);
22
23pub fn parse(input: &str) -> Input {
24    input
25        .iter_signed::<i32>()
26        .chunk::<4>()
27        .map(|[x, y, dx, dy]| ((x, dx.rem_euclid(WIDTH)), (y, dy.rem_euclid(HEIGHT))))
28        .unzip()
29}
30
31pub fn part1(input: &Input) -> i32 {
32    let (xs, ys) = input;
33    let mut quadrants = [0; 4];
34
35    for (&(x, dx), &(y, dy)) in xs.iter().zip(ys) {
36        let x = (x + 100 * dx) % WIDTH;
37        let y = (y + 100 * dy) % HEIGHT;
38
39        match (x.cmp(&50), y.cmp(&51)) {
40            (Less, Less) => quadrants[0] += 1,
41            (Less, Greater) => quadrants[1] += 1,
42            (Greater, Less) => quadrants[2] += 1,
43            (Greater, Greater) => quadrants[3] += 1,
44            _ => (),
45        }
46    }
47
48    quadrants.iter().product()
49}
50
51pub fn part2(input: &Input) -> i32 {
52    let (xs, ys) = input;
53
54    // Search for times modulo WIDTH when the tree could possibly exist using x coordinates only,
55    // and times modulo HEIGHT when the tree could possibly exist using y coordinates only.
56    let t = minimum_variance::<WIDTH>(xs);
57    let u = minimum_variance::<HEIGHT>(ys);
58
59    // Combine indices using the Chinese Remainder Theorem to get index mod 10,403.
60    (5_253 * t + 5_151 * u) % (WIDTH * HEIGHT)
61}
62
63/// Calculate the [population variance](https://en.wikipedia.org/wiki/Variance#Population_variance)
64/// for each time in the period, returning the time when at the minimum variance.
65///
66/// Const generics allow the compiler to optimize the modulus calculation, making it 3 times faster.
67fn minimum_variance<const PERIOD: i32>(axis: &Axis) -> i32 {
68    let n = axis.len() as i32;
69    (0..PERIOD)
70        .min_by_key(|time| {
71            let mut sum = 0;
72            let mut sum2 = 0;
73
74            for &(position, velocity) in axis {
75                let robot = (position + velocity * time) % PERIOD;
76                sum += robot;
77                sum2 += robot * robot;
78            }
79
80            // Variance scaled by n² in order to keep values integer.
81            n * sum2 - sum * sum
82        })
83        .unwrap()
84}
aoc/year2024/day14.rs

aoc/year2024/
day14.rs
