day20.rs

use core::fmt::Debug;
use std::{
    collections::{HashSet, VecDeque},
    io::BufRead,
};

#[derive(PartialEq)]
enum Tile {
    Nothing,
    Wall,
    Floor,
}

impl Debug for Tile {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            Self::Nothing => write!(f, "  "),
            Self::Wall => write!(f, "\x1B[40m  \x1B[0m"),
            Self::Floor => write!(f, "\x1B[48;5;252m  \x1B[0m"),
        }
    }
}

#[derive(Debug)]
struct Portal {
    name: String,
    position: (i16, i16),
    depth: i16,
}

struct Map {
    tiles: Vec<Vec<Tile>>,
    portals: Vec<Portal>,
}

impl Map {
    pub fn from_stdin() -> Self {
        let stdin = std::io::stdin();
        let lines: Vec<_> = stdin.lock().lines().flatten().collect();
        dbg!(&lines);

        // Parse the tiles
        let tiles: Vec<Vec<_>> = lines[2..lines.len() - 2]
            .iter()
            .map(|line| {
                let chars: Vec<_> = line.chars().collect();
                chars[2..chars.len() - 2]
                    .iter()
                    .map(|c| match c {
                        '#' => Tile::Wall,
                        '.' => Tile::Floor,
                        _ => Tile::Nothing,
                    })
                    .collect()
            })
            .collect();

        // Find out the torus size
        let mut torus_width = 0;
        for (y, row) in tiles.iter().enumerate() {
            let mid = row.len() / 2;
            if row[mid] == Tile::Nothing {
                torus_width = y;
                break;
            }
        }
        dbg!(torus_width);

        // Parse the portals
        let width = lines[0].len();
        let height = lines.len();
        let mut portals = Vec::new();

        // Top and bottom, outside
        let y = 0;
        for (x, c) in lines[y].chars().enumerate() {
            let c2 = lines[y + 1].chars().nth(x).unwrap();
            if c.is_ascii_alphanumeric() && c2 != ' ' {
                portals.push(Portal {
                    name: [c, c2].iter().collect(),
                    position: (x as i16 - 2, y as i16),
                    depth: -1,
                });
            }
        }

        let y = height - 2;
        for (x, c) in lines[y].chars().enumerate() {
            let c2 = lines[y + 1].chars().nth(x).unwrap();
            if c.is_ascii_alphanumeric() && c2 != ' ' {
                portals.push(Portal {
                    name: [c, c2].iter().collect(),
                    position: (x as i16 - 2, y as i16 - 3),
                    depth: -1,
                });
            }
        }

        // Top and bottom, inside
        let y = torus_width + 2;
        let chars: Vec<_> = lines[y].chars().collect();
        for (x, c) in chars[2..width - 2].iter().enumerate() {
            if c.is_ascii_alphanumeric() {
                let c2 = lines[y + 1].chars().nth(x + 2).unwrap();
                portals.push(Portal {
                    name: [*c, c2].iter().collect(),
                    position: (x as i16, y as i16 - 3),
                    depth: 1,
                });
            }
        }

        let y = height - torus_width - 3;
        let chars: Vec<_> = lines[y].chars().collect();
        for (x, c) in chars[2..width - 2].iter().enumerate() {
            if c.is_ascii_alphanumeric() {
                let c2 = lines[y - 1].chars().nth(x + 2).unwrap();
                portals.push(Portal {
                    name: [c2, *c].iter().collect(),
                    position: (x as i16, y as i16 - 1),
                    depth: 1,
                });
            }
        }

        // Left and right, outside
        for (y, line) in lines.iter().enumerate() {
            let chars: Vec<_> = line.chars().collect();

            if chars[0].is_ascii_alphanumeric() {
                portals.push(Portal {
                    name: chars[..2].iter().collect(),
                    position: (0, y as i16 - 2),
                    depth: -1,
                });
            }

            if chars[width - 2].is_ascii_alphanumeric() {
                portals.push(Portal {
                    name: chars[width - 2..].iter().collect(),
                    position: (width as i16 - 5, y as i16 - 2),
                    depth: -1,
                });
            }
        }

        // Left and right, inside
        for (y, line) in lines[2..height - 2].iter().enumerate() {
            let chars: Vec<_> = line.chars().collect();

            let x = torus_width + 2;
            if chars[x].is_ascii_alphanumeric() {
                portals.push(Portal {
                    name: chars[x..x + 2].iter().collect(),
                    position: (x as i16 - 3, y as i16),
                    depth: 1,
                });
            }

            let x = width - torus_width - 3;
            if chars[x].is_ascii_alphanumeric() {
                portals.push(Portal {
                    name: chars[x - 1..x + 1].iter().collect(),
                    position: (x as i16 - 1, y as i16),
                    depth: 1,
                });
            }
        }

        // for portal in portals.iter() {
        //     let (x, y) = portal.position;
        //     assert_eq!(tiles[y as usize][x as usize], Tile::Floor);
        // }

        Self { tiles, portals }
    }

    fn width(&self) -> usize {
        self.tiles[0].len()
    }

    fn height(&self) -> usize {
        self.tiles.len()
    }
}

impl Debug for Map {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        writeln!(f)?;
        for (y, row) in self.tiles.iter().enumerate() {
            'x: for (x, cell) in row.iter().enumerate() {
                for portal in self.portals.iter() {
                    if portal.position == (x as i16, y as i16) {
                        if portal.depth == 1 {
                            write!(f, "\x1B[48;5;252;91m{:<2}\x1B[0m", portal.name)?;
                        } else {
                            write!(f, "\x1B[48;5;252;92m{:<2}\x1B[0m", portal.name)?;
                        }
                        continue 'x;
                    }
                }
                write!(f, "{:?}", cell)?;
            }
            writeln!(f)?;
        }
        Ok(())
    }
}

type Position = (i16, i16, i16);

fn solve(map: &Map, position: (i16, i16)) -> Option<i16> {
    let position = (position.0, position.1, 0);

    let mut queue: VecDeque<(Position, i16)> = VecDeque::new();
    queue.push_back((position, 0));
    let mut visited = HashSet::new();

    while let Some((position, depth)) = queue.pop_front() {
        if !visited.insert(position) {
            continue;
        }

        let (x, y, z) = position;
        if x < 0 || y < 0 || x >= map.width() as i16 || y >= map.height() as i16 {
            continue;
        }

        let tile = &map.tiles[y as usize][x as usize];
        if tile == &Tile::Wall || tile == &Tile::Nothing {
            continue;
        }

        if let Some(portal) = map.portals.iter().find(|portal| portal.position == (x, y)) {
            if portal.name == "ZZ" {
                if z == 0 {
                    println!("[{:>4}] found ZZ at {:?}", depth, position);
                    return Some(depth);
                } else {
                    // on other levels than 0, ZZ is a wall
                    continue;
                }
            }

            // find other portal
            if let Some(other_portal) = map
                .portals
                .iter()
                .find(|p| p.name == portal.name && p.position != portal.position)
            {
                if z + portal.depth >= 0 {
                    let (ox, oy) = other_portal.position;
                    queue.push_back(((ox, oy, z + portal.depth), depth + 1));
                }
            }
        }

        queue.push_back(((x, y - 1, z), depth + 1));
        queue.push_back(((x, y + 1, z), depth + 1));
        queue.push_back(((x - 1, y, z), depth + 1));
        queue.push_back(((x + 1, y, z), depth + 1));
    }

    None
}

fn main() {
    let map = Map::from_stdin();
    dbg!(&map);

    let start = map
        .portals
        .iter()
        .find(|portal| portal.name == "AA")
        .unwrap();

    let depth = solve(&map, start.position).unwrap();
    dbg!(depth);
}