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 10403 that is the answer.
15use crate::util::iter::*;
16use crate::util::parse::*;
17use std::cmp::Ordering::*;
18
19type Robot = [usize; 4];
20
21pub fn parse(input: &str) -> Vec<Robot> {
22    input
23        .iter_signed::<i32>()
24        .chunk::<4>()
25        .map(|[x, y, dx, dy]| {
26            [x as usize, y as usize, dx.rem_euclid(101) as usize, dy.rem_euclid(103) as usize]
27        })
28        .collect()
29}
30
31pub fn part1(input: &[Robot]) -> i32 {
32    let mut quadrants = [0; 4];
33
34    for [x, y, dx, dy] in input {
35        let x = (x + 100 * dx) % 101;
36        let y = (y + 100 * dy) % 103;
37
38        match (x.cmp(&50), y.cmp(&51)) {
39            (Less, Less) => quadrants[0] += 1,
40            (Less, Greater) => quadrants[1] += 1,
41            (Greater, Less) => quadrants[2] += 1,
42            (Greater, Greater) => quadrants[3] += 1,
43            _ => (),
44        }
45    }
46
47    quadrants.iter().product()
48}
49
50pub fn part2(robots: &[Robot]) -> usize {
51    // Search for times mod 101 when the tree could possibly exist using x coordinates only.
52    // and times mod 103 when the tree could possibly exist using y coordinates only.
53    let mut rows = Vec::new();
54    let mut columns = Vec::new();
55
56    for time in 0..103 {
57        let mut xs = [0; 101];
58        let mut ys = [0; 103];
59
60        for [x, y, dx, dy] in robots {
61            let x = (x + time * dx) % 101;
62            xs[x] += 1;
63            let y = (y + time * dy) % 103;
64            ys[y] += 1;
65        }
66
67        // Tree bounding box is 31x33.
68        if time < 101 && xs.iter().filter(|&&c| c >= 33).count() >= 2 {
69            columns.push(time);
70        }
71        if ys.iter().filter(|&&c| c >= 31).count() >= 2 {
72            rows.push(time);
73        }
74    }
75
76    // If there's only one combination then return answer.
77    if rows.len() == 1 && columns.len() == 1 {
78        let t = columns[0];
79        let u = rows[0];
80        // Combine indices using the Chinese Remainder Theorem to get index mod 10403.
81        return (5253 * t + 5151 * u) % 10403;
82    }
83
84    // Backup check looking for time when all robot positions are unique.
85    let mut floor = vec![0; 10403];
86
87    for &t in &columns {
88        'outer: for &u in &rows {
89            let time = (5253 * t + 5151 * u) % 10403;
90
91            for &[x, y, dx, dy] in robots {
92                let x = (x + time * dx) % 101;
93                let y = (y + time * dy) % 103;
94
95                let index = 101 * y + x;
96                if floor[index] == time {
97                    continue 'outer;
98                }
99                floor[index] = time;
100            }
101
102            return time;
103        }
104    }
105
106    unreachable!()
107}
aoc/year2024/day14.rs

aoc/year2024/
day14.rs
