aoc/year2023/
day13.rs

1//! # Point of Incidence
2//!
3//! We store each row of a grid as a binary number. For example `#.##..##.` becomes `101100110`.
4//! Then to count smudges we bitwise XOR the respective rows together and count one bits
5//! using the [`count_ones`] function.
6//!
7//! For example:
8//! ```none
9//!  ..##..###     001100111 ^ 000100111 = 00100000 => 1
10//! v#####.##.v => 111110110 ^ 111110110 = 00000000 => 0
11//! ^#####.##.^
12//!  ...#..###
13//! ```
14//!
15//! To handle columns we transpose the grid then convert into integers the same way. For part one
16//! we look for a reflection axis with 0 smudges and for part two 1 smudge, allowing the same
17//! code to be reused.
18//!
19//! [`count_ones`]: u32::count_ones
20type Input = Vec<(Vec<u32>, Vec<u32>)>;
21
22pub fn parse(input: &str) -> Input {
23    input
24        .split("\n\n")
25        .map(|block| {
26            let grid: Vec<_> = block.lines().map(str::as_bytes).collect();
27            let (width, height) = (grid[0].len(), grid.len());
28            let bit = |x: usize, y: usize| u32::from(grid[y][x] == b'#');
29
30            let rows =
31                (0..height).map(|y| (0..width).fold(0, |n, x| (n << 1) | bit(x, y))).collect();
32            let columns =
33                (0..width).map(|x| (0..height).fold(0, |n, y| (n << 1) | bit(x, y))).collect();
34
35            (rows, columns)
36        })
37        .collect()
38}
39
40pub fn part1(input: &Input) -> usize {
41    reflect(input, 0)
42}
43
44pub fn part2(input: &Input) -> usize {
45    reflect(input, 1)
46}
47
48fn reflect(input: &Input, target: u32) -> usize {
49    input
50        .iter()
51        .map(|(rows, columns)| {
52            reflect_axis(columns, target)
53                .unwrap_or_else(|| 100 * reflect_axis(rows, target).unwrap())
54        })
55        .sum()
56}
57
58fn reflect_axis(axis: &[u32], target: u32) -> Option<usize> {
59    let size = axis.len();
60
61    (1..size).find(|&i| {
62        // Only consider rows/columns within the boundary of the grid.
63        let smudges: u32 =
64            (0..i.min(size - i)).map(|j| (axis[i - j - 1] ^ axis[i + j]).count_ones()).sum();
65
66        smudges == target
67    })
68}
aoc/year2023/day13.rs

aoc/year2023/
day13.rs
