aoc/year2024/
day04.rs

1//! # Ceres Search
2//!
3//! For part one we search each vertical, horizontal and diagonal line individually.
4//! By using a `u32` bitmask of ASCII values we can check in both directions efficiently at the
5//! same time.
6//!
7//! For part two the difference of the ASCII values of "M" and "S" is 6. No other combination of
8//! letter has this value, so if both diagonals are a 6 then we have a match.
9use crate::util::grid::*;
10use crate::util::point::*;
11
12pub fn parse(input: &str) -> Grid<u8> {
13    Grid::parse(input)
14}
15
16pub fn part1(grid: &Grid<u8>) -> u32 {
17    let size = grid.width;
18    let mut result = 0;
19
20    // Horizontal and vertical
21    for i in 0..size {
22        result += scan_line(grid, Point::new(i, 0), DOWN, size);
23        result += scan_line(grid, Point::new(0, i), RIGHT, size);
24    }
25
26    // Diagonals
27    for i in 0..size - 3 {
28        result += scan_line(grid, Point::new(i, 0), DOWN + RIGHT, size - i);
29        result += scan_line(grid, Point::new(0, i + 1), DOWN + RIGHT, size - 1 - i);
30        result += scan_line(grid, Point::new(size - 1 - i, 0), DOWN + LEFT, size - i);
31        result += scan_line(grid, Point::new(size - 1, i + 1), DOWN + LEFT, size - 1 - i);
32    }
33
34    result
35}
36
37pub fn part2(grid: &Grid<u8>) -> u32 {
38    let mut result = 0;
39
40    for x in 1..grid.width - 1 {
41        for y in 1..grid.height - 1 {
42            let point = Point::new(x, y);
43
44            if grid[point] == b'A' {
45                let ul = grid[Point::new(x - 1, y - 1)];
46                let ur = grid[Point::new(x + 1, y - 1)];
47                let dl = grid[Point::new(x - 1, y + 1)];
48                let dr = grid[Point::new(x + 1, y + 1)];
49                // ASCII "M" is 77 and "S" is 53 so the absolute difference is 6.
50                // No other combination of letters causes this difference.
51                // "MS" on both diagonals is a match.
52                result += (ul.abs_diff(dr) == 6 && ur.abs_diff(dl) == 6) as u32;
53            }
54        }
55    }
56
57    result
58}
59
60/// Searches a horizontal, vertical or diagonal line in both directions at once.
61fn scan_line(grid: &Grid<u8>, mut point: Point, direction: Point, size: i32) -> u32 {
62    let mut bytes = 0;
63    let mut result = 0;
64
65    for _ in 0..size {
66        bytes = (bytes << 8) | (grid[point] as u32);
67        point += direction;
68        // "XMAS" and "SAMX" in hex.
69        result += (bytes == 0x584d4153 || bytes == 0x53414d58) as u32;
70    }
71
72    result
73}
aoc/year2024/day04.rs

aoc/year2024/
day04.rs
