use std::io;
use std::io::BufRead;
use std::iter;
use std::collections::HashMap;

const DO_COMPARE_GRIDS: bool = true;

fn parse_ch(c: char) -> u8 {
    match c {
        '.' => 0,
        '|' => 1,
        '#' => 2,
        _ => unreachable!(),
    }
}

fn res_value(grid: &Vec<Vec<u8>>) -> i32 {
    let mut num1 = 0;
    let mut num2 = 0;

    for row in grid {
        for cell in row {
            num1 += (*cell == 1) as i32;
            num2 += (*cell == 2) as i32;
        }
    }

    return num1 * num2;
}

fn compute_step(grid: &Vec<Vec<u8>>, grid2: &mut Vec<Vec<u8>>) -> u64 {
    let mut hash: u64 = 0;
    let mut rotating_shift = 0;

    for y in 1..grid.len()-1 {
        for x in 1..grid[0].len()-1 {
            let mut tots = [0, 0, 0];

            for dy in -1..2 {
                for dx in -1..2 {
                    if dy == 0 && dx == 0 { continue; }
                    tots[grid[(y as isize + dy) as usize][(x as isize + dx) as usize] as usize] += 1;
                }
            }

            let v = match (grid[y][x], tots[0], tots[1], tots[2]) {
                (0, _, n, _) if n >= 3           => 1,
                (1, _, _, n) if n >= 3           => 2,
                (2, _, n, m) if n >= 1 && m >= 1 => 2,
                (2, _, _, _)                     => 0,
                (v, _, _, _)                     => v,
            };

            grid2[y][x] = v;

            hash ^= u64::from(v) << rotating_shift | (tots[0] ^ tots[1] ^ tots[2]) << rotating_shift;
            rotating_shift = (rotating_shift + 1) % 64;
        }
    }

    hash
}

fn grid_equal(grid1: &Vec<Vec<u8>>, grid2: &Vec<Vec<u8>>) -> bool {
    for (row1, row2) in grid1.iter().zip(grid2.iter()) {
        for (&v1, &v2) in row1.iter().zip(row2.iter()) {
            if v1 != v2 {
                return false;
            }
        }
    }

    true
}

fn simulate(mut grid: Vec<Vec<u8>>, nsteps: usize) -> i32 {
    let mut grid2 = grid.clone();

    let mut hash_vals = Vec::new();
    let mut res_vals = Vec::new();
    let mut res_map = HashMap::new();

    let mut cycle = None;

    for step in 0..nsteps {
        let hash = compute_step(&grid, &mut grid2);
        std::mem::swap(&mut grid, &mut grid2);

        hash_vals.push(hash);
        let res = res_value(&grid);
        res_vals.push(res);

        if let Some((cycle_start, cycle_length, ref start_grid)) = cycle {
            if step - cycle_start == cycle_length {
                if !DO_COMPARE_GRIDS || grid_equal(&grid, &start_grid) {
                    // println!("Check at {}: grids equal", step);
                    return res_vals[cycle_start + (nsteps - 1 - cycle_start) % cycle_length];
                } else {
                    println!("Grids not equal");
                    cycle = None;
                }
            }
        } else if let Some(&prev_step) = res_map.get(&res) {
            let length = step - prev_step;
            if prev_step >= length {
                if (0..length).all(|i| hash_vals[prev_step - i] == hash_vals[step - i]
                                        && res_vals[prev_step - i] == res_vals[step - i]) {
                    // println!("cycle: {} length={}", step, length);
                    cycle = Some((step, length, if DO_COMPARE_GRIDS { grid.clone() } else { Vec::new() }));
                }
            }
        }

        res_map.insert(res, step);
    }

    res_value(&grid)
}

pub fn main<T: BufRead>(reader: T) -> io::Result<(String, String)> {
    let mut grid = {
        iter::once(vec![0; 0])
            .chain(reader.lines().map(|l|
                iter::once(0)
                    .chain(l.unwrap().chars().map(|c| parse_ch(c)))
                    .chain(iter::once(0)).collect()
            ))
            .chain(iter::once(vec![0; 0]))
            .collect::<Vec<Vec<_>>>()
    };

    let w = grid[1].len();
    let h = grid.len();
    grid[0].resize(w, 0);
    grid[h-1].resize(w, 0);

    let part1 = simulate(grid.clone(), 10);
    let part2 = simulate(grid, 1000000000);

    Ok((part1.to_string(), part2.to_string()))
}