aoc/year2024/
day20.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
//! # Race Condition
//!
//! Examining the input shows that there is only a single path from start to finish with
//! no branches. This simplifies checking for shortcuts as any empty space will be on the shortest
//! path from start to end. The cheating rules allow us to "warp" up to `n` squares away to any
//! empty space as measured by [manhattan distance](https://en.wikipedia.org/wiki/Taxicab_geometry).
//!
//! For part one this is a distance of 2. When checking surrounding squares we make 2 optimizations:
//!
//! * Don't check any squares only 1 away as we can always just move to these normally.
//! * Checking from point `p => q` is always the negative of `q => p`, e.g if `p = 30, q = 50` then
//!   `p => q = 20` and `q => p = -20`. This means we only ever need to check any pair once.
//! * Additionally we only need to check down and right. Previous rows and columns will already
//!   have checked points above and to the left when we reach an empty square.
//!
//! ```none
//!       #         .
//!      ###       ...
//!     ##P## =>  ....#
//!      ###       ...
//!       #         #
//! ```
//!
//! For part two the distance is increased to 20 and the shape now resembles a wonky diamond.
//! This shape ensures complete coverage without duplicating checks.
//!
//! ```none
//!      #        .
//!     ###      ...
//!    ##P## => ..P##
//!     ###      ###
//!      #        #
//! ```
use crate::util::grid::*;
use crate::util::point::*;
use crate::util::thread::*;
use std::sync::atomic::{AtomicU32, Ordering};

/// Create a grid the same size as input with the time taken from start to any location.
pub fn parse(input: &str) -> Grid<i32> {
    let grid = Grid::parse(input);
    let start = grid.find(b'S').unwrap();
    let end = grid.find(b'E').unwrap();

    let mut time = grid.same_size_with(i32::MAX);
    let mut elapsed = 0;

    // Find starting direction, assuming start position is surrounded by 3 walls.
    let mut position = start;
    let mut direction = ORTHOGONAL.into_iter().find(|&o| grid[position + o] != b'#').unwrap();

    while position != end {
        time[position] = elapsed;
        elapsed += 1;

        // There are no branches so we only ever need to go straight ahead or turn left or right.
        direction = [direction, direction.clockwise(), direction.counter_clockwise()]
            .into_iter()
            .find(|&d| grid[position + d] != b'#')
            .unwrap();
        position += direction;
    }

    time[end] = elapsed;
    time
}

pub fn part1(time: &Grid<i32>) -> u32 {
    let mut cheats = 0;

    for y in 1..time.height - 1 {
        for x in 1..time.width - 1 {
            let point = Point::new(x, y);

            // We only need to check 2 points to the right and down as previous empty squares
            // have already checked up and to the left.
            if time[point] != i32::MAX {
                cheats += check(time, point, Point::new(2, 0));
                cheats += check(time, point, Point::new(0, 2));
            }
        }
    }

    cheats
}

/// Searches for all cheats up to distance 20, parallelizing the work over multiple threads.
pub fn part2(time: &Grid<i32>) -> u32 {
    let mut items = Vec::with_capacity(10_000);

    for y in 1..time.height - 1 {
        for x in 1..time.width - 1 {
            let point = Point::new(x, y);

            if time[point] != i32::MAX {
                items.push(point);
            }
        }
    }

    // Use as many cores as possible to parallelize the remaining search.
    let total = AtomicU32::new(0);
    spawn_parallel_iterator(&items, |iter| worker(time, &total, iter));
    total.into_inner()
}

fn worker(time: &Grid<i32>, total: &AtomicU32, iter: ParIter<'_, Point>) {
    let mut cheats = 0;

    // (p1, p2) is the reciprocal of (p2, p1) so we only need to check each pair once.
    for &point in iter {
        for x in 2..21 {
            cheats += check(time, point, Point::new(x, 0));
        }

        for y in 1..21 {
            for x in (y - 20)..(21 - y) {
                cheats += check(time, point, Point::new(x, y));
            }
        }
    }

    // Update global total.
    total.fetch_add(cheats, Ordering::Relaxed);
}

// Check if we save enough time warping to another square.
#[inline]
fn check(time: &Grid<i32>, first: Point, delta: Point) -> u32 {
    let second = first + delta;

    (time.contains(second)
        && time[second] != i32::MAX
        && (time[first] - time[second]).abs() - first.manhattan(second) >= 100) as u32
}