aoc/year2024/day04.rs
1//! # Ceres Search
2//!
3//! For part one we search each vertical, horizontal and diagonal direction one at a time over the
4//! whole grid, checking for both "XMAS" and "SAMX" at every position. The newline padding prevents
5//! false positives at boundaries.
6//!
7//! For part two the difference of the ASCII values of "M" and "S" is 6. No other combination of
8//! letters has this value, so if both diagonals are 6 then we have a match.
9//!
10//! Both parts are written without branches, so the compiler auto-vectorizes each loop.
11pub fn parse(input: &str) -> &[u8] {
12 input.as_bytes()
13}
14
15pub fn part1(bytes: &[u8]) -> u32 {
16 let width = bytes.iter().position(|&b| b == b'\n').unwrap() + 1;
17
18 // Offsets for horizontal, vertical and both diagonals. Sweep the whole whole grid so that each
19 // loop auto-vectorizes. The newline separators prevent false positives on boundaries.
20 [1, width, width - 1, width + 1]
21 .iter()
22 .flat_map(|&step| {
23 bytes.iter().zip(&bytes[step..]).zip(&bytes[2 * step..]).zip(&bytes[3 * step..])
24 })
25 .map(|(((&a, &b), &c), &d)| {
26 let forward = a == b'X' && b == b'M' && c == b'A' && d == b'S';
27 let backward = a == b'S' && b == b'A' && c == b'M' && d == b'X';
28 u32::from(forward || backward)
29 })
30 .sum()
31}
32
33pub fn part2(bytes: &[u8]) -> u32 {
34 let width = bytes.iter().position(|&b| b == b'\n').unwrap() + 1;
35
36 // ASCII "M" is 77 and "S" is 83 so the absolute difference is 6.
37 // No other combination of letters causes this difference.
38 // "MS" on both diagonals is a match.
39 bytes
40 .iter()
41 .zip(&bytes[2..])
42 .zip(&bytes[width + 1..])
43 .zip(&bytes[2 * width..])
44 .zip(&bytes[2 * width + 2..])
45 .map(|((((&up_left, &up_right), ¢er), &down_left), &down_right)| {
46 let first = u32::from(up_left.abs_diff(down_right) == 6);
47 let second = u32::from(up_right.abs_diff(down_left) == 6);
48 u32::from(center == b'A') & first & second
49 })
50 .sum()
51}