pub fn parse_input(input: &str) -> Vec<(usize, usize, usize)> {
    input
        .lines()
        .map(|line| {
            let mut line = line.split(',');
            (
                line.next().unwrap().parse().unwrap(),
                line.next().unwrap().parse().unwrap(),
                line.next().unwrap().parse().unwrap(),
            )
        })
        .collect()
}

pub fn task1(input: &[(usize, usize, usize)]) -> usize {
    let mut space = vec![vec![vec![false; 20]; 20]; 20];
    for &(x, y, z) in input {
        space[x][y][z] = true;
    }
    input.len() * 6
        - input
            .iter()
            .map(|&(x, y, z)| {
                let mut res = 0;
                if x > 0 && space[x - 1][y][z] {
                    res += 1
                }
                if y > 0 && space[x][y - 1][z] {
                    res += 1
                }
                if z > 0 && space[x][y][z - 1] {
                    res += 1
                }
                if x < space.len() - 1 && space[x + 1][y][z] {
                    res += 1
                }
                if y < space[x].len() - 1 && space[x][y + 1][z] {
                    res += 1
                }
                if z < space[x][y].len() - 1 && space[x][y][z + 1] {
                    res += 1
                }
                res
            })
            .sum::<usize>()
}

#[derive(Clone, Copy, PartialEq, Eq)]
pub enum State {
    Empty,
    Outer,
    Lava,
}

fn floodfill(space: &mut [Vec<Vec<State>>]) {
    let mut stack = vec![(0, 0, 0)];
    while let Some((x, y, z)) = stack.pop() {
        if space[x][y][z] == State::Empty {
            space[x][y][z] = State::Outer;
            if x > 0 {
                stack.push((x - 1, y, z));
            }
            if y > 0 {
                stack.push((x, y - 1, z));
            }
            if z > 0 {
                stack.push((x, y, z - 1));
            }
            if x < space.len() - 1 {
                stack.push((x + 1, y, z));
            }
            if y < space[x].len() - 1 {
                stack.push((x, y + 1, z));
            }
            if z < space[x][y].len() - 1 {
                stack.push((x, y, z + 1));
            }
        }
    }
}

pub fn task2(input: &[(usize, usize, usize)]) -> usize {
    let mut space = vec![vec![vec![State::Empty; 22]; 22]; 22]; //adding planes around
    for &(x, y, z) in input {
        space[x + 1][y + 1][z + 1] = State::Lava;
    }

    floodfill(&mut space);

    input.len() * 6
        - input
            .iter()
            .map(|&(x, y, z)| {
                let (x, y, z) = (x + 1, y + 1, z + 1);
                let mut res = 0;
                if x > 0 && space[x - 1][y][z] != State::Outer {
                    res += 1
                }
                if y > 0 && space[x][y - 1][z] != State::Outer {
                    res += 1
                }
                if z > 0 && space[x][y][z - 1] != State::Outer {
                    res += 1
                }
                if x < space.len() - 1 && space[x + 1][y][z] != State::Outer {
                    res += 1
                }
                if y < space[x].len() - 1 && space[x][y + 1][z] != State::Outer
                {
                    res += 1
                }
                if z < space[x][y].len() - 1
                    && space[x][y][z + 1] != State::Outer
                {
                    res += 1
                }
                res
            })
            .sum::<usize>()
}

pub fn parse_input(input: &str) -> &str {
    input.trim()
}

const TUBE_WIDTH: usize = 7;

#[rustfmt::skip]
const FIGURES: &[&[&[u8]]] = &[
    &["####".as_bytes()],

    &[".#.".as_bytes(), 
      "###".as_bytes(), 
      ".#.".as_bytes()],

    &["###".as_bytes(),
      "..#".as_bytes(), 
      "..#".as_bytes()],

    &["#".as_bytes(), 
      "#".as_bytes(), 
      "#".as_bytes(), 
      "#".as_bytes()],

    &["##".as_bytes(), 
      "##".as_bytes()],
];

const EMPTY_LINE: &[u8] = ".......".as_bytes();

struct Tetris<'commands> {
    tube: std::collections::VecDeque<Vec<u8>>,
    figure_idx: usize,
    commands: &'commands [u8],
    commands_idx: usize,
    skipped: usize,
}

impl<'commands> Tetris<'commands> {
    fn new(commands: &str) -> Tetris {
        Tetris {
            tube: std::collections::VecDeque::new(),
            figure_idx: 0,
            commands: commands.as_bytes(),
            commands_idx: 0,
            skipped: 0,
        }
    }
    fn play(&mut self) {
        let mut x = 2;
        let mut y = -4;
        loop {
            let next_x = x + match self.commands[self.commands_idx] {
                b'>' => 1,
                b'<' => -1,
                dir => unimplemented!("Invalid move {}", dir),
            };
            self.commands_idx += 1;
            if self.commands_idx == self.commands.len() {
                self.commands_idx = 0;
            }
            if self.fits(next_x, y) {
                x = next_x;
            }
            let next_y = y + 1;
            if self.fits(x, next_y) {
                y = next_y;
            } else {
                break;
            }
        }
        self.fix_figure(x, y);
        self.figure_idx += 1;
        if self.figure_idx == FIGURES.len() {
            self.figure_idx = 0;
        }
    }
    fn fits(&self, x: i32, y: i32) -> bool {
        if x < 0 || x as usize + FIGURES[self.figure_idx][0].len() > TUBE_WIDTH
        {
            return false;
        }
        if y < 0 {
            return true;
        }
        if y >= self.tube.len() as i32 {
            return false;
        }
        FIGURES[self.figure_idx]
            .iter()
            .enumerate()
            .all(|(fy, fline)| {
                fline.iter().enumerate().all(|(fx, &fchar)| {
                    fchar != b'#'
                        || y - (fy as i32) < 0
                        || self.tube[(y - fy as i32) as usize]
                            [(x + fx as i32) as usize]
                            != b'#'
                })
            })
    }
    fn fix_figure(&mut self, x: i32, y: i32) {
        for f_y in 0..FIGURES[self.figure_idx].len() {
            if (y - f_y as i32) < 0 || self.tube.is_empty() {
                self.tube.push_front(EMPTY_LINE.to_vec());
            }
            for f_x in 0..FIGURES[self.figure_idx][f_y].len() {
                if FIGURES[self.figure_idx][f_y][f_x] == b'#' {
                    self.tube[(y - f_y as i32).max(0) as usize]
                        [(x as usize + f_x) as usize] = b'#';
                }
            }
        }
    }
    fn tower_height(&self) -> usize {
        self.skipped + self.tube.len()
    }
    fn print_top_n(&self, n: usize) {
        println!("-----------------");
        for line in self.tube.iter().take(n) {
            println!("{}", std::str::from_utf8(line).unwrap());
        }
    }
    fn gaps(&self) -> impl Iterator<Item = usize> + '_ {
        (0..TUBE_WIDTH).map(|i| {
            self.tube
                .iter()
                .map(|line| line[i])
                .take_while(|&x| x != b'#')
                .count()
        })
    }
}

impl PartialEq for Tetris<'_> {
    fn eq(&self, other: &Self) -> bool {
        self.figure_idx == other.figure_idx
            && self.commands_idx == other.commands_idx
            && self.gaps().cmp(other.gaps()) == std::cmp::Ordering::Equal
    }
}

pub fn task1(input: &str) -> usize {
    let mut tetris = Tetris::new(input);
    for _ in 0..2022 {
        tetris.play();
    }
    tetris.tower_height()
}

pub fn task2(input: &str) -> usize {
    let mut hare = Tetris::new(input);
    let mut tortoise = Tetris::new(input);

    //Floyd's algorithm
    //First meet
    for _ in 0.. {
        hare.play();
        hare.play();
        tortoise.play();
        if hare == tortoise {
            break;
        }
    }
    //Find the interval until looping starts
    let mut start = 0;
    hare = Tetris::new(input);
    for i in 0.. {
        hare.play();
        tortoise.play();
        if hare == tortoise {
            start = i;
            break;
        }
    }
    //Find the period
    let mut period = 0;
    for i in 0.. {
        hare.play();
        if hare == tortoise {
            period = i + 1;
            break;
        }
    }

    //Let hare run one last time
    hare = Tetris::new(input);
    for _ in 0..start {
        hare.play();
    }
    let start_height = hare.tower_height();
    for _ in 0..period {
        hare.play();
    }
    let period_height = hare.tower_height() - start_height;
    let remains = (1_000_000_000_000 - start) % period;
    for _ in 0..remains {
        hare.play();
    }
    let remains_height = hare.tower_height() - start_height - period_height;
    start_height
        + (1_000_000_000_000 - start - remains) / period * period_height
        + remains_height
}

type Yell = u64;

pub enum Monkey {
    Value(Yell),
    Operation(String, char, String),
}

use std::collections::HashMap;

impl Monkey {
    fn new(input: &str) -> Monkey {
        if let Ok(value) = input.parse() {
            Monkey::Value(value)
        } else {
            let (left, op, right): (String, char, String);
            text_io::scan!(input.bytes()=>"{} {} {}",left, op, right);
            Monkey::Operation(left, op, right)
        }
    }
    fn yell(&self, monkeys: &HashMap<String, Monkey>) -> Yell {
        match self {
            Monkey::Value(yell) => *yell,
            Monkey::Operation(left, op, right) => {
                let left = monkeys[left].yell(monkeys);
                let right = monkeys[right].yell(monkeys);
                match op {
                    '+' => left + right,
                    '-' => left - right,
                    '*' => left * right,
                    '/' => left / right,
                    _ => unimplemented!(),
                }
            }
        }
    }
    fn has_humn(&self, monkeys: &HashMap<String, Monkey>) -> bool {
        match self {
            Monkey::Value(_) => false,
            Monkey::Operation(left, _, right) => {
                left == "humn"
                    || right == "humn"
                    || monkeys[left].has_humn(monkeys)
                    || monkeys[right].has_humn(monkeys)
            }
        }
    }
    fn find_humn(
        &self,
        monkeys: &HashMap<String, Monkey>,
        value: Yell,
    ) -> Yell {
        println!("Looking for humn to ouput {}", value);
        match self {
            Monkey::Operation(left, op, right) => {
                if left == "humn" || monkeys[left].has_humn(monkeys) {
                    let right = monkeys[right].yell(monkeys);
                    let to_left = match op {
                        '+' => value - right,
                        '-' => value + right,
                        '*' => value / right,
                        '/' => value * right,
                        _ => unimplemented!(),
                    };
                    monkeys[left].find_humn(monkeys, to_left)
                } else {
                    let left = monkeys[left].yell(monkeys);
                    let to_right = match op {
                        '+' => value - left,
                        '-' => left - value,
                        '*' => value / left,
                        '/' => left / value,
                        _ => unimplemented!(),
                    };
                    monkeys[right].find_humn(monkeys, to_right)
                }
            }
            Monkey::Value(_) => value, //this means it's humn
        }
    }
}

pub fn parse_input(input: &str) -> HashMap<String, Monkey> {
    input
        .lines()
        .map(|line| {
            let mut parts = line.split(": ");
            let name = parts.next().unwrap();
            let yell = parts.next().unwrap();
            (name.to_owned(), Monkey::new(yell))
        })
        .collect()
}

pub fn task1(map: &HashMap<String, Monkey>) -> Yell {
    map[&"root".to_owned()].yell(map)
}

pub fn task2(map: &HashMap<String, Monkey>) -> Yell {
    if let Monkey::Operation(left, _, right) = &map["root"] {
        if map[left].has_humn(map) {
            map[left].find_humn(map, map[right].yell(map))
        } else {
            map[right].find_humn(map, map[left].yell(map))
        }
    } else {
        unreachable!()
    }
}

#[cfg(test)]
mod test {
    use super::*;
    const INPUT: &str = "root: pppw + sjmn
dbpl: 5
cczh: sllz + lgvd
zczc: 2
ptdq: humn - dvpt
dvpt: 3
lfqf: 4
humn: 5
ljgn: 2
sjmn: drzm * dbpl
sllz: 4
pppw: cczh / lfqf
lgvd: ljgn * ptdq
drzm: hmdt - zczc
hmdt: 32";

    #[test]
    fn test_task1() {
        assert_eq!(task1(&parse_input(INPUT)), 152);
    }

    #[test]
    fn test_task2() {
        assert_eq!(task2(&parse_input(INPUT)), 301);
    }
}

import copy, math, operator, re

monkeys = []

for line in open("input.txt").readlines():
    line = line.strip()

    if line.startswith("Monkey"):
        monkeys.append([])
        continue

    if line.startswith("Start"):
        monkeys[-1].append(list(map(int, re.findall("\d+", line))))
        continue

    if line.startswith(("Test", "If")):
        monkeys[-1].append(int(re.search(r"\d+", line).group()))
        continue

    if line == "":
        continue

    monkeys[-1].append(line.split("= old ")[-1].split(" "))

ops = {
    "+": operator.add,
    "-": operator.sub,
    "*": operator.mul,
    "/": operator.truediv,
}


def operation(old, new):
    op, val = new
    val = old if val == "old" else int(val)
    return ops[op](old, val)


def inspecting(isridiculous: bool = True):
    inspectors = copy.deepcopy(monkeys)
    activities = [0] * len(inspectors)
    magic = math.prod([inspector[2] for inspector in inspectors]) if isridiculous else 3

    for _ in range(10_000 if isridiculous else 20):
        for m, (worries, new, isdiv, yeah, nope) in enumerate(inspectors):
            if len(worries) == 0:
                continue

            activities[m] += len(worries)

            for worry in worries:
                worry = operation(worry, new)
                worry = worry % magic if isridiculous else worry // magic
                inspectors[nope if worry % isdiv else yeah][0].append(worry)

            inspectors[m][0] = []

    activities = sorted(activities)
    print(activities[-1] * activities[-2])

inspecting(False) # Part One: 56120
inspecting() # Part Two: 24389045529