adventofcode23/src/day13.rs

//! Day 13

use grid::Grid;
use itertools::Itertools;

pub const DAY: u8 = 13;
pub const TITLE: &str = "Point of Incidence";

#[derive(Debug, Clone, Copy)]
enum Reflection {
    Horizontal(usize),
    Vertical(usize),
}

impl Reflection {
    fn n(self) -> usize {
        match self {
            Reflection::Horizontal(n) => n * 100,
            Reflection::Vertical(n) => n,
        }
    }
}

fn parse(input: Vec<String>) -> Vec<Grid<bool>> {
    input
        .split(|l| l.is_empty())
        .map(|gl| {
            let mut grid = Grid::new(gl.len(), gl[0].len());
            for (y, line) in gl.iter().enumerate() {
                for (x, c) in line.chars().enumerate() {
                    if c == '#' {
                        grid[(y, x)] = true;
                    }
                }
            }
            grid
        })
        .collect()
}

fn find_reflection(grid: &Grid<bool>, smudge: bool) -> Option<Reflection> {
    let cols = grid
        .iter_cols()
        .map(|col| {
            col.fold(0_u64, |mut acc, x| {
                if *x {
                    acc |= 1;
                }
                acc <<= 1;
                acc
            })
        })
        .collect_vec();
    if let Some(x) = find_ref(&cols, smudge) {
        return Some(Reflection::Vertical(x));
    }

    let rows = grid
        .iter_rows()
        .map(|col| {
            col.fold(0_u64, |mut acc, x| {
                if *x {
                    acc |= 1;
                }
                acc <<= 1;
                acc
            })
        })
        .collect_vec();
    if let Some(y) = find_ref(&rows, smudge) {
        return Some(Reflection::Horizontal(y));
    }
    None
}

fn find_ref(v: &[u64], smudge: bool) -> Option<usize> {
    if smudge {
        find_ref_smudge(v)
    } else {
        find_ref_normal(v)
    }
}

fn find_ref_normal(v: &[u64]) -> Option<usize> {
    let mut last = 0;
    for (i, n) in v.iter().copied().enumerate() {
        if n == last {
            // Could be mirror position
            if v[..i - 1]
                .iter()
                .rev()
                .zip(v[i + 1..].iter())
                .all(|(a, b)| a == b)
            {
                return Some(i);
            }
        }
        last = n;
    }
    None
}

fn find_ref_smudge(v: &[u64]) -> Option<usize> {
    let mut last = 0;
    for (i, n) in v.iter().copied().enumerate() {
        if i == 0 {
        } else if n == last {
            // Could be mirror position with 1 smudge
            let mut got_smudge = false;
            let mut ok = true;
            for (a, b) in v[..i - 1].iter().rev().zip(v[i + 1..].iter()) {
                if !got_smudge && smudge_eq(*a, *b) {
                    got_smudge = true;
                } else if a != b {
                    ok = false;
                    break;
                }
            }
            if ok && got_smudge {
                return Some(i);
            }
        } else if smudge_eq(n, last) {
            // Could be mirror position
            if v[..i - 1]
                .iter()
                .rev()
                .zip(v[i + 1..].iter())
                .all(|(a, b)| a == b)
            {
                return Some(i);
            }
        }
        last = n;
    }
    None
}

fn smudge_eq(a: u64, b: u64) -> bool {
    let d = a ^ b;
    d > 0 && (d & (d - 1)) == 0
}

pub fn part1(input: Vec<String>) -> String {
    let grids = parse(input);

    grids
        .iter()
        .map(|g| find_reflection(g, false).unwrap().n())
        .sum::<usize>()
        .to_string()
}

pub fn part2(input: Vec<String>) -> String {
    let grids = parse(input);

    grids
        .iter()
        .map(|g| find_reflection(g, true).unwrap().n())
        .sum::<usize>()
        .to_string()
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn t_smudge_eq() {
        assert!(smudge_eq(1, 0));
        assert!(smudge_eq(0b10001100, 0b10000100));
        assert!(!smudge_eq(0b10001100, 0b10001100));
    }

    #[test]
    fn t_example1() {
        assert_eq!(part1(crate::read_example(DAY, 1)), "405");
    }

    #[test]
    fn t_part1() {
        assert_eq!(part1(crate::read_input(DAY)), "35210");
    }

    #[test]
    fn t_example2() {
        assert_eq!(part2(crate::read_example(DAY, 2)), "400");
    }

    #[test]
    fn t_part2() {
        assert_eq!(part2(crate::read_input(DAY)), "31974");
    }
}