aoc/year2024/
day20.rs

1//! # Race Condition
2//!
3//! Examining the input shows that there is only a single path from start to finish with
4//! no branches. This simplifies checking for shortcuts as any empty space will be on the shortest
5//! path from start to end. The cheating rules allow us to "warp" up to `n` squares away to any
6//! empty space as measured by [manhattan distance](https://en.wikipedia.org/wiki/Taxicab_geometry).
7//!
8//! For part one this is a distance of 2. When checking surrounding squares we make 2 optimizations:
9//!
10//! * Don't check any squares only 1 away as we can always just move to these normally.
11//! * Checking from point `p => q` is always the negative of `q => p`, e.g if `p = 30, q = 50` then
12//!   `p => q = 20` and `q => p = -20`. This means we only ever need to check any pair once.
13//! * Additionally we only need to check down and right. Previous rows and columns will already
14//!   have checked points above and to the left when we reach an empty square.
15//!
16//! ```none
17//!       #         .
18//!      ###       ...
19//!     ##P## =>  ....#
20//!      ###       ...
21//!       #         #
22//! ```
23//!
24//! For part two the distance is increased to 20 and the shape now resembles a wonky diamond.
25//! This shape ensures complete coverage without duplicating checks.
26//!
27//! ```none
28//!      #        .
29//!     ###      ...
30//!    ##P## => ..P##
31//!     ###      ###
32//!      #        #
33//! ```
34use crate::util::grid::*;
35use crate::util::point::*;
36use crate::util::thread::*;
37use std::sync::atomic::{AtomicU32, Ordering};
38
39/// Create a grid the same size as input with the time taken from start to any location.
40pub fn parse(input: &str) -> Grid<i32> {
41    let grid = Grid::parse(input);
42    let start = grid.find(b'S').unwrap();
43    let end = grid.find(b'E').unwrap();
44
45    let mut time = grid.same_size_with(i32::MAX);
46    let mut elapsed = 0;
47
48    // Find starting direction, assuming start position is surrounded by 3 walls.
49    let mut position = start;
50    let mut direction = ORTHOGONAL.into_iter().find(|&o| grid[position + o] != b'#').unwrap();
51
52    while position != end {
53        time[position] = elapsed;
54        elapsed += 1;
55
56        // There are no branches so we only ever need to go straight ahead or turn left or right.
57        direction = [direction, direction.clockwise(), direction.counter_clockwise()]
58            .into_iter()
59            .find(|&d| grid[position + d] != b'#')
60            .unwrap();
61        position += direction;
62    }
63
64    time[end] = elapsed;
65    time
66}
67
68pub fn part1(time: &Grid<i32>) -> u32 {
69    let mut cheats = 0;
70
71    for y in 1..time.height - 1 {
72        for x in 1..time.width - 1 {
73            let point = Point::new(x, y);
74
75            // We only need to check 2 points to the right and down as previous empty squares
76            // have already checked up and to the left.
77            if time[point] != i32::MAX {
78                cheats += check(time, point, Point::new(2, 0));
79                cheats += check(time, point, Point::new(0, 2));
80            }
81        }
82    }
83
84    cheats
85}
86
87/// Searches for all cheats up to distance 20, parallelizing the work over multiple threads.
88pub fn part2(time: &Grid<i32>) -> u32 {
89    let mut items = Vec::with_capacity(10_000);
90
91    for y in 1..time.height - 1 {
92        for x in 1..time.width - 1 {
93            let point = Point::new(x, y);
94
95            if time[point] != i32::MAX {
96                items.push(point);
97            }
98        }
99    }
100
101    // Use as many cores as possible to parallelize the remaining search.
102    let total = AtomicU32::new(0);
103    spawn_parallel_iterator(&items, |iter| worker(time, &total, iter));
104    total.into_inner()
105}
106
107fn worker(time: &Grid<i32>, total: &AtomicU32, iter: ParIter<'_, Point>) {
108    let mut cheats = 0;
109
110    // (p1, p2) is the reciprocal of (p2, p1) so we only need to check each pair once.
111    for &point in iter {
112        for x in 2..21 {
113            cheats += check(time, point, Point::new(x, 0));
114        }
115
116        for y in 1..21 {
117            for x in (y - 20)..(21 - y) {
118                cheats += check(time, point, Point::new(x, y));
119            }
120        }
121    }
122
123    // Update global total.
124    total.fetch_add(cheats, Ordering::Relaxed);
125}
126
127// Check if we save enough time warping to another square.
128#[inline]
129fn check(time: &Grid<i32>, first: Point, delta: Point) -> u32 {
130    let second = first + delta;
131
132    (time.contains(second)
133        && time[second] != i32::MAX
134        && (time[first] - time[second]).abs() - first.manhattan(second) >= 100) as u32
135}
aoc/year2024/day20.rs

aoc/year2024/
day20.rs
