AoC23/src/day13.rs

use std::fmt::Debug;

use itertools::Itertools;

pub fn run() {
    let input = include_str!("../input/day13.txt");
    // let input = r#"#.##..##.
    // ..#.##.#.
    // ##......#
    // ##......#
    // ..#.##.#.
    // ..##..##.
    // #.#.##.#.

    // #...##..#
    // #....#..#
    // ..##..###
    // #####.##.
    // #####.##.
    // ..##..###
    // #....#..#"#;

    dbg!(count_reflections(input, false));
    dbg!(count_reflections(input, true));
}

fn count_reflections(s: &str, fixing_smudges: bool) -> usize {
    let grids: Vec<Grid> = s.split("\n\n").map(|s| s.into()).collect();
    let mut horiz = 0;
    let mut vert = 0;
    for g in grids {
        vert += g
            .find_vertical_mirrors(fixing_smudges)
            .iter()
            .sum::<usize>();
        horiz += g
            .find_horizontal_mirrors(fixing_smudges)
            .iter()
            .sum::<usize>();
    }
    (horiz * 100) + vert
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Tile {
    Ash,
    Rock,
}

#[derive(Clone)]
struct Grid {
    tiles: Vec<Vec<Tile>>,
    width: usize,
    height: usize,
}

impl From<&str> for Grid {
    fn from(value: &str) -> Self {
        let tiles = value
            .trim()
            .lines()
            .map(|l| {
                l.trim()
                    .chars()
                    .map(|c| match c {
                        '.' => Tile::Ash,
                        '#' => Tile::Rock,
                        _ => panic!("invalid char {:?}", c),
                    })
                    .collect::<Vec<_>>()
            })
            .collect::<Vec<_>>();
        let width = tiles[0].len();
        let height = tiles.len();
        Self {
            tiles,
            width,
            height,
        }
    }
}

impl Debug for Grid {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        let s = self
            .tiles
            .iter()
            .map(|row| {
                row.iter()
                    .map(|t| match t {
                        Tile::Ash => '.',
                        Tile::Rock => '#',
                    })
                    .collect::<String>()
            })
            .join("\n");
        write!(f, "Grid(\n{})", s)
    }
}

impl Grid {
    fn find_vertical_mirrors(&self, fixing_smudges: bool) -> Vec<usize> {
        find_mirrors(&self.tiles, fixing_smudges)
    }

    fn find_horizontal_mirrors(&self, fixing_smudges: bool) -> Vec<usize> {
        let transposed = transpose(&self.tiles);
        find_mirrors(&transposed, fixing_smudges)
    }
}

fn find_mirrors<T: Eq>(v: &Vec<Vec<T>>, fixing_smudges: bool) -> Vec<usize> {
    (1..v[0].len())
        .filter(|&mirror_idx| {
            let mut mismatched_indices = 0;
            for inner in v.iter() {
                let (before, after) = inner.split_at(mirror_idx);
                let len = before.len().min(after.len());
                let inner_mismatched =
                    find_mismatched_indices(before.iter().rev().take(len), after.iter().take(len));
                if fixing_smudges {
                    mismatched_indices += inner_mismatched.len();
                } else if !inner_mismatched.is_empty() {
                    return false;
                }
            }
            if fixing_smudges {
                mismatched_indices == 1
            } else {
                true
            }
        })
        .collect()
}

fn find_mismatched_indices<T: Eq>(
    a: impl Iterator<Item = T>,
    b: impl Iterator<Item = T>,
) -> Vec<usize> {
    let mut mismatched = vec![];
    for (i, (a, b)) in a.zip(b).enumerate() {
        if a != b {
            mismatched.push(i);
        }
    }
    mismatched
}

fn transpose<T: Copy>(orig: &Vec<Vec<T>>) -> Vec<Vec<T>> {
    let mut new = vec![];
    for col in 0..orig[0].len() {
        let mut new_row = vec![];
        for row in 0..orig.len() {
            new_row.push(orig[row][col]);
        }
        new.push(new_row);
    }
    new
}

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

    #[test]
    fn test_vertical_reflection() {
        let g: Grid = r#"#.##..##.
..#.##.#.
##......#
##......#
..#.##.#.
..##..##.
#.#.##.#."#
            .into();
        assert_eq!(g.find_vertical_mirrors(false), vec![5]);
    }

    #[test]
    fn test_horizontal_reflection() {
        let g: Grid = r#"#...##..#
#....#..#
..##..###
#####.##.
#####.##.
..##..###
#....#..#"#
            .into();
        assert_eq!(g.find_horizontal_mirrors(false), vec![4]);
    }

    #[test]
    fn test_count() {
        let input = r#"#.##..##.
..#.##.#.
##......#
##......#
..#.##.#.
..##..##.
#.#.##.#.

#...##..#
#....#..#
..##..###
#####.##.
#####.##.
..##..###
#....#..#"#;
        assert_eq!(count_reflections(input, false), 405);
    }

    #[test]
    fn test_count_fixing_smudges() {
        let input = r#"#.##..##.
..#.##.#.
##......#
##......#
..#.##.#.
..##..##.
#.#.##.#.

#...##..#
#....#..#
..##..###
#####.##.
#####.##.
..##..###
#....#..#"#;
        assert_eq!(count_reflections(input, true), 400);
    }

    #[test]
    fn test_grid2() {
        let g: Grid = r#"
..#.###
#.#####
#.#####
..#..##
#......
##..###
..#....
"#
        .into();
        assert_eq!(g.find_vertical_mirrors(false), vec![6]);
        assert_eq!(g.find_horizontal_mirrors(false), vec![]);
    }

    #[test]
    fn test_transpose() {
        let orig = vec![vec![1, 2, 3], vec![3, 4, 5]];
        assert_eq!(transpose(&orig), vec![vec![1, 3], vec![2, 4], vec![3, 5]]);
    }

    #[test]
    fn test_fixing_smudges() {
        let g: Grid = r#"#.##..##.
..#.##.#.
##......#
##......#
..#.##.#.
..##..##.
#.#.##.#."#
            .into();
        assert_eq!(g.find_horizontal_mirrors(true), vec![3]);
    }
}