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//! letters 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 y in 1..grid.height - 1 {
41        for x in 1..grid.width - 1 {
42            let point = Point::new(x, y);
43
44            if grid[point] == b'A' {
45                // ASCII "M" is 77 and "S" is 83 so the absolute difference is 6.
46                // No other combination of letters causes this difference.
47                // "MS" on both diagonals is a match.
48                let diagonal = |corner| grid[point + corner].abs_diff(grid[point - corner]);
49                result += u32::from(diagonal(UP + LEFT) == 6 && diagonal(UP + RIGHT) == 6);
50            }
51        }
52    }
53
54    result
55}
56
57/// Searches a horizontal, vertical or diagonal line in both directions at once.
58fn scan_line(grid: &Grid<u8>, mut point: Point, direction: Point, size: i32) -> u32 {
59    let mut bytes = 0;
60    let mut result = 0;
61
62    for _ in 0..size {
63        bytes = (bytes << 8) | (grid[point] as u32);
64        point += direction;
65        // "XMAS" and "SAMX" in hex.
66        result += (bytes == 0x584d4153 || bytes == 0x53414d58) as u32;
67    }
68
69    result
70}
aoc/year2024/day04.rs

aoc/year2024/
day04.rs
