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//! First we check for times when the robot x coordinates could form the left and right columns
8//! of the tree's bounding box. This gives a time `t` mod 101.
9//!
10//! Then we check the y coordinates looking for the top and bottom rows of the bounding box,
11//! giving a time `u` mod 103.
12//!
13//! Using the [Chinese Remainder Theorem](https://en.wikipedia.org/wiki/Chinese_remainder_theorem)
14//! we combine the two times into a single time mod 10,403 that is the answer.
15use std::cmp::Ordering::*;
16
17use crate::util::iter::*;
18use crate::util::parse::*;
19
20type Robot = [usize; 4];
21
22pub fn parse(input: &str) -> Vec<Robot> {
23    input
24        .iter_signed::<i32>()
25        .chunk::<4>()
26        .map(|[x, y, dx, dy]| {
27            [x as usize, y as usize, dx.rem_euclid(101) as usize, dy.rem_euclid(103) as usize]
28        })
29        .collect()
30}
31
32pub fn part1(input: &[Robot]) -> i32 {
33    let mut quadrants = [0; 4];
34
35    for &[x, y, dx, dy] in input {
36        let x = (x + 100 * dx) % 101;
37        let y = (y + 100 * dy) % 103;
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(robots: &[Robot]) -> usize {
52    // Search for times mod 101 when the tree could possibly exist using x coordinates only,
53    // and times mod 103 when the tree could possibly exist using y coordinates only.
54    let mut rows = Vec::new();
55    let mut columns = Vec::new();
56
57    for time in 0..103 {
58        let mut xs = [0; 101];
59        let mut ys = [0; 103];
60
61        for &[x, y, dx, dy] in robots {
62            let x = (x + time * dx) % 101;
63            xs[x] += 1;
64            let y = (y + time * dy) % 103;
65            ys[y] += 1;
66        }
67
68        // Tree bounding box is 31x33.
69        if time < 101 && xs.iter().filter(|&&c| c >= 33).count() >= 2 {
70            columns.push(time);
71        }
72        if ys.iter().filter(|&&c| c >= 31).count() >= 2 {
73            rows.push(time);
74        }
75    }
76
77    // If there's only one combination then return answer.
78    if rows.len() == 1 && columns.len() == 1 {
79        let t = columns[0];
80        let u = rows[0];
81        // Combine indices using the Chinese Remainder Theorem to get index mod 10_403.
82        return (5_253 * t + 5_151 * u) % 10_403;
83    }
84
85    // Backup check looking for time when all robot positions are unique.
86    let mut floor = vec![0; 10_403];
87
88    for &t in &columns {
89        'outer: for &u in &rows {
90            let time = (5_253 * t + 5_151 * u) % 10_403;
91
92            for &[x, y, dx, dy] in robots {
93                let x = (x + time * dx) % 101;
94                let y = (y + time * dy) % 103;
95
96                let index = 101 * y + x;
97                if floor[index] == time {
98                    continue 'outer;
99                }
100                floor[index] = time;
101            }
102
103            return time;
104        }
105    }
106
107    unreachable!()
108}
aoc/year2024/day14.rs

aoc/year2024/
day14.rs
