path: root/2023/src/bin/day_21.rs

use nom::{
    branch::alt,
    character::complete::{char, line_ending},
    combinator::{map, value},
    multi::{many1, separated_list1},
    IResult,
};
use std::{collections::BTreeSet, fs, mem};

fn main() -> Result<(), Box<dyn std::error::Error>> {
    let input = fs::read_to_string("inputs/day_21.txt")?;
    let garden = WalledGarden::parser(&input).unwrap().1;

    dbg!(garden.count_closed_walls_walkable_after_steps(garden.center(), 64));
    dbg!(garden.count_open_walls_walkable_after_steps(26501365));

    // let mut open_garden = OpenGarden::parser(&input).unwrap().1;
    // let open_iters = 26501365;
    // for i in 0..open_iters {
    //     open_garden.next_mut();
    // }
    // dbg!(&open_garden.count_walkable());

    Ok(())
}

#[derive(Debug, Clone)]
struct WalledGarden {
    rocks: Vec<Vec<bool>>,
    walkable_to: Vec<Vec<bool>>,
    walkable_to_back: Vec<Vec<bool>>,
    odd_max_countable: usize,
    even_max_countable: usize,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum WalledGardenState {
    Empty,
    Walkable,
    Rock,
}

impl WalledGarden {
    fn new(tiles: Vec<Vec<WalledGardenState>>) -> WalledGarden {
        let mut odd_max_countable = 0;
        let mut even_max_countable = 0;
        let rocks: Vec<Vec<bool>> = tiles
            .iter()
            .map(|row| {
                row.iter()
                    .map(|t| *t == WalledGardenState::Rock)
                    .collect::<Vec<bool>>()
            })
            .collect();
        let walkable_to: Vec<Vec<bool>> = vec![vec![false; rocks[0].len()]; rocks.len()];

        let mut inner_figuring_out_max = WalledGarden {
            rocks: rocks.clone(),
            walkable_to_back: walkable_to.clone(),
            walkable_to: walkable_to.clone(),
            odd_max_countable: 0,
            even_max_countable: 0,
        };

        let mut unchanged_count = 0;
        for i in 1.. {
            inner_figuring_out_max.closed_walls_next_mut();

            if i % 2 == 0 {
                let new_even_max_countable = inner_figuring_out_max.count_walkable();
                if even_max_countable == new_even_max_countable {
                    unchanged_count += 1;
                } else {
                    even_max_countable = new_even_max_countable;
                }
            } else {
                let new_odd_max_countable = inner_figuring_out_max.count_walkable();
                if odd_max_countable == new_odd_max_countable {
                    unchanged_count += 1;
                } else {
                    odd_max_countable = new_odd_max_countable;
                }
            }

            if unchanged_count > 1 {
                break;
            }
        }

        WalledGarden {
            rocks,
            walkable_to_back: walkable_to.clone(),
            walkable_to: walkable_to.clone(),
            odd_max_countable,
            even_max_countable,
        }
    }

    fn parser(input: &str) -> IResult<&str, Self> {
        map(
            separated_list1(line_ending, many1(WalledGardenState::parser)),
            WalledGarden::new,
        )(input)
    }

    fn count_closed_walls_walkable_after_steps(
        &self,
        start: (usize, usize),
        steps: usize,
    ) -> usize {
        let mut garden = self.clone();
        garden.walkable_to[start.1][start.0] = true;
        for _ in 0..steps {
            garden.closed_walls_next_mut();
        }
        garden.count_walkable()
    }

    fn closed_walls_next_mut(&mut self) {
        for (y, row) in self.walkable_to_back.iter_mut().enumerate() {
            for (x, tile) in row.iter_mut().enumerate() {
                if !self.rocks[y][x] {
                    *tile = (y > 0 && self.walkable_to[y - 1][x])
                        || (y < self.walkable_to.len() - 1 && self.walkable_to[y + 1][x])
                        || (x > 0 && self.walkable_to[y][x - 1])
                        || (x < self.walkable_to[y].len() - 1 && self.walkable_to[y][x + 1]);
                }
            }
        }

        std::mem::swap(&mut self.walkable_to, &mut self.walkable_to_back);
    }

    fn count_walkable(&self) -> usize {
        self.walkable_to
            .iter()
            .flat_map(|row| row.iter())
            .filter(|s| **s)
            .count()
    }

    fn walkable_spots_when_full(&self, is_even: bool) -> usize {
        if is_even {
            self.even_max_countable
        } else {
            self.odd_max_countable
        }
    }

    fn count_open_walls_walkable_after_steps(&self, steps: usize) -> usize {
        let (size_x, size_y) = self.size();
        let (center_x, center_y) = self.center();

        let max_y_deviance = ((steps - center_y) / size_y) as isize;

        let mut total_walkable = 0;

        // The paths straight up / down, and left / right from the middle and
        // edges are clear, so it's possible to find the shortest path into
        // another chunk trivially, and looking at only that chunk is
        // equivalent.
        for chunk_y in -max_y_deviance..=max_y_deviance {
            dbg!(chunk_y);
            let y_distance = if chunk_y == 0 {
                0
            } else {
                center_y + 1 + (chunk_y.abs() as usize - 1) * size_y
            };
            let max_x_deviance = ((steps - y_distance - center_x) / size_x) as isize;
            for chunk_x in -max_x_deviance..=max_x_deviance {
                dbg!(chunk_x);
                let x_distance = if chunk_x == 0 {
                    0
                } else {
                    center_x + 1 + (chunk_x.abs() as usize - 1) * size_x
                };

                let steps_in_chunk = steps - y_distance - x_distance;

                // TODO: Identify fully walkable gardens to use the walkable_spots_when_full. Maybe for full rows at a time?
                //
                // if steps_in_chunk > 100 {
                //     total_walkable += self.walkable_spots_when_full(steps_in_chunk % 2 == 0);
                // }

                let starting_x = match chunk_x.cmp(&0) {
                    std::cmp::Ordering::Less => size_x - 1,
                    std::cmp::Ordering::Equal => center_x,
                    std::cmp::Ordering::Greater => 0,
                };
                let starting_y = match chunk_y.cmp(&0) {
                    std::cmp::Ordering::Less => size_y - 1,
                    std::cmp::Ordering::Equal => center_y,
                    std::cmp::Ordering::Greater => 0,
                };
                let starting_point = (starting_x, starting_y);
                total_walkable +=
                    self.count_closed_walls_walkable_after_steps(starting_point, steps_in_chunk);
            }
        }

        total_walkable
    }

    fn size(&self) -> (usize, usize) {
        (self.rocks[0].len(), self.rocks.len())
    }

    fn center(&self) -> (usize, usize) {
        let (size_x, size_y) = self.size();
        (size_x / 2, size_y / 2)
    }
}

impl WalledGardenState {
    fn parser(input: &str) -> IResult<&str, Self> {
        alt((
            value(WalledGardenState::Empty, char('.')),
            value(WalledGardenState::Walkable, char('S')),
            value(WalledGardenState::Rock, char('#')),
        ))(input)
    }
}

#[derive(Debug)]
struct OpenGarden {
    rockmap_size: (isize, isize),
    rocks: BTreeSet<(isize, isize)>,
    walkable: BTreeSet<(isize, isize)>,
}

impl OpenGarden {
    fn parser(input: &str) -> IResult<&str, Self> {
        map(
            separated_list1(line_ending, many1(WalledGardenState::parser)),
            |walled_garden_map| OpenGarden {
                rockmap_size: (
                    walled_garden_map.len() as isize,
                    walled_garden_map[0].len() as isize,
                ),
                rocks: walled_garden_map
                    .iter()
                    .enumerate()
                    .flat_map(|(y, row)| {
                        row.iter().enumerate().filter_map(move |(x, s)| {
                            (*s == WalledGardenState::Rock).then(|| (y as isize, x as isize))
                        })
                    })
                    .collect(),
                walkable: walled_garden_map
                    .iter()
                    .enumerate()
                    .flat_map(|(y, row)| {
                        row.iter().enumerate().filter_map(move |(x, s)| {
                            (*s == WalledGardenState::Walkable).then(|| (y as isize, x as isize))
                        })
                    })
                    .collect(),
            },
        )(input)
    }

    fn next_mut(&mut self) {
        let walkable = mem::take(&mut self.walkable);
        self.walkable = walkable
            .iter()
            .flat_map(|(y, x)| [(y - 1, *x), (y + 1, *x), (*y, x - 1), (*y, x + 1)])
            .filter(|(y, x)| !self.is_rock(*y, *x))
            .collect();
    }

    fn is_rock(&self, y: isize, x: isize) -> bool {
        let y = y.rem_euclid(self.rockmap_size.0);
        let x = x.rem_euclid(self.rockmap_size.1);
        self.rocks.contains(&(y, x))
    }

    fn count_walkable(&self) -> usize {
        self.walkable.len()
    }
}