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
20use crate::util::grid::*;
21use crate::util::point::*;
22
23type Input = Vec<(Vec<u32>, Vec<u32>)>;
24
25pub fn parse(input: &str) -> Input {
26    input
27        .split("\n\n")
28        .map(|block| {
29            let grid: Grid<_> = Grid::parse(block);
30            let bit = |point| u32::from(grid[point] == b'#');
31
32            let rows: Vec<_> = (0..grid.height)
33                .map(|y| (0..grid.width).fold(0, |n, x| (n << 1) | bit(Point::new(x, y))))
34                .collect();
35            let columns: Vec<_> = (0..grid.width)
36                .map(|x| (0..grid.height).fold(0, |n, y| (n << 1) | bit(Point::new(x, y))))
37                .collect();
38
39            (rows, columns)
40        })
41        .collect()
42}
43
44pub fn part1(input: &Input) -> usize {
45    reflect(input, 0)
46}
47
48pub fn part2(input: &Input) -> usize {
49    reflect(input, 1)
50}
51
52fn reflect(input: &Input, target: u32) -> usize {
53    input
54        .iter()
55        .map(|(rows, columns)| {
56            if let Some(x) = reflect_axis(columns, target) {
57                x
58            } else if let Some(y) = reflect_axis(rows, target) {
59                100 * y
60            } else {
61                unreachable!()
62            }
63        })
64        .sum()
65}
66
67fn reflect_axis(axis: &[u32], target: u32) -> Option<usize> {
68    let size = axis.len();
69
70    (1..size).find(|&i| {
71        // Only consider rows/columns within the boundary of the grid.
72        let smudges: u32 =
73            (0..i.min(size - i)).map(|j| (axis[i - j - 1] ^ axis[i + j]).count_ones()).sum();
74
75        smudges == target
76    })
77}
aoc/year2023/day13.rs

aoc/year2023/
day13.rs
