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 mut rows = Vec::with_capacity(grid.height as usize);
31            let mut columns = Vec::with_capacity(grid.width as usize);
32
33            for y in 0..grid.height {
34                let mut n = 0;
35
36                for x in 0..grid.width {
37                    n = (n << 1) | (grid[Point::new(x, y)] == b'#') as u32;
38                }
39
40                rows.push(n);
41            }
42
43            for x in 0..grid.width {
44                let mut n = 0;
45
46                for y in 0..grid.height {
47                    n = (n << 1) | (grid[Point::new(x, y)] == b'#') as u32;
48                }
49
50                columns.push(n);
51            }
52
53            (rows, columns)
54        })
55        .collect()
56}
57
58pub fn part1(input: &Input) -> usize {
59    reflect(input, 0)
60}
61
62pub fn part2(input: &Input) -> usize {
63    reflect(input, 1)
64}
65
66fn reflect(input: &Input, target: u32) -> usize {
67    input
68        .iter()
69        .map(|(rows, columns)| {
70            if let Some(x) = reflect_axis(columns, target) {
71                x
72            } else if let Some(y) = reflect_axis(rows, target) {
73                100 * y
74            } else {
75                unreachable!()
76            }
77        })
78        .sum()
79}
80
81fn reflect_axis(axis: &[u32], target: u32) -> Option<usize> {
82    let size = axis.len();
83
84    for i in 1..size {
85        let mut smudges = 0;
86
87        // Only consider rows/columns within the boundary of the grid.
88        for j in 0..i.min(size - i) {
89            smudges += (axis[i - j - 1] ^ axis[i + j]).count_ones();
90        }
91
92        if smudges == target {
93            return Some(i);
94        }
95    }
96
97    None
98}
aoc/year2023/day13.rs

aoc/year2023/
day13.rs
