pub enum FsRecord {
    File(usize),
    Dir(Box<Directory>),
}

use std::collections::HashMap;

pub struct Directory {
    records: HashMap<String, FsRecord>,
}

impl Directory {
    fn new() -> Directory {
        Directory {
            records: HashMap::new(),
        }
    }
    fn add_file(&mut self, path: &[String], size: usize) {
        if path.len() == 1 {
            self.records
                .insert(path[0].to_string(), FsRecord::File(size));
        } else if let Some(FsRecord::Dir(dir)) = self.records.get_mut(&path[0])
        {
            dir.add_file(&path[1..], size);
        }
    }
    fn add_dir(&mut self, path: &[String]) {
        if path.len() == 1 {
            self.records
                .entry(path[0].to_string())
                .or_insert_with(|| FsRecord::Dir(Box::new(Directory::new())));
        } else if let Some(FsRecord::Dir(dir)) = self.records.get_mut(&path[0])
        {
            dir.add_dir(&path[1..]);
        }
    }
    fn get_sizes<P>(&self, func: P) -> (usize, usize)
    where
        P: Fn(usize) -> usize + Clone,
    {
        let mut inner_size = 0;
        let mut inner_filtered = 0;
        for record in self.records.values() {
            match record {
                &FsRecord::File(size) => inner_size += size,
                FsRecord::Dir(subdir) => {
                    let (total, filtered) = subdir.get_sizes(func.clone());
                    inner_size += total;
                    inner_filtered += filtered;
                }
            }
        }
        inner_filtered += func(inner_size);
        (inner_size, inner_filtered)
    }
    fn get_best_size(&self, target: usize) -> (usize, usize) {
        let mut inner_size = 0;
        let mut best = 0;
        for record in self.records.values() {
            match record {
                &FsRecord::File(size) => inner_size += size,
                FsRecord::Dir(subdir) => {
                    let (total, current_best) = subdir.get_best_size(target);
                    inner_size += total;
                    if current_best > target
                        && (best == 0 || current_best < best)
                    {
                        best = current_best;
                    }
                }
            }
        }
        if best == 0 || (inner_size > target && inner_size < best) {
            best = inner_size;
        }
        (inner_size, best)
    }
}

pub fn parse_input(input: &str) -> Directory {
    let mut root = Directory::new();
    let mut path = vec![];
    for instruction in input.lines() {
        if instruction.starts_with("$ cd") {
            match &instruction[5..] {
                "/" => {
                    path.clear();
                }
                ".." => {
                    path.pop();
                }
                name => {
                    path.push(name.to_string());
                    root.add_dir(&path);
                }
            }
        } else if instruction != "$ ls" {
            //executing ls
            let mut instruction = instruction.split_whitespace();
            let typ = instruction.next().unwrap();
            let name = instruction.next().unwrap();
            path.push(name.to_string());
            if typ == "dir" {
                root.add_dir(&path);
            } else {
                root.add_file(&path, typ.parse().unwrap());
            }
            path.pop();
        }
    }
    root
}

pub fn task1(root: &Directory) -> usize {
    root.get_sizes(|size| if size <= 100_000 { size } else { 0 })
        .1
}

pub fn task2(root: &Directory) -> usize {
    let current_size = root.get_sizes(|_| 0).0;
    let unused = 70_000_000 - current_size;
    let needed = 30_000_000 - unused;
    root.get_best_size(needed).1
}

    dirsizes = {}
    cwd = '/'
    for line in sys.stdin:
        if m := re.match(r'^\$ cd \.\.$', line):
            cwd, _ = os.path.split(cwd)
        elif m := re.match(r'^\$ cd (\S+)$', line):
            cwd = os.path.join(cwd, m.group(1))
            dirsizes[cwd] = 0
        elif m := re.match(r'^([0-9]+) (\S+)$', line):
            size = int(m.group(1))
            for d in filter(cwd.startswith, dirsizes):
                dirsizes[d] += size

    print(sum(v for v in dirsizes.values() if v <= SIZE_BOUND))

    size_to_delete = SIZE_NEED - (SIZE_DISK - dirsizes['/'])
    print(min(v for v in dirsizes.values() if v >= size_to_delete))

pub fn parse_input(input: &str) -> Vec<Vec<i32>> {
    input
        .lines()
        .map(|line| {
            line.chars()
                .map(|c| c.to_digit(10).unwrap() as i32)
                .collect()
        })
        .collect()
}

pub fn task1(trees: &[Vec<i32>]) -> usize {
    let mut count = 0;
    for (y, row) in trees.iter().enumerate() {
        for (x, &h) in row.iter().enumerate() {
            if row[..x].iter().all(|&tree| tree < h)
                || row[x + 1..].iter().all(|&tree| tree < h)
                || trees[..y].iter().all(|row| row[x] < h)
                || trees[y + 1..].iter().all(|row| row[x] < h)
            {
                count += 1;
            }
        }
    }
    count
}

pub fn task2(trees: &[Vec<i32>]) -> usize {
    let mut best = 0;

    for (y, row) in trees.iter().enumerate() {
        for (x, &h) in row.iter().enumerate() {
            let mut score = 1;

            let mut count = 0;
            let mut max = 0;
            for &tree in row[..x].iter().rev() {
                count += 1;
                if tree > max {
                    max = tree;
                }
                if max >= h {
                    break;
                }
            }
            score *= count;

            let mut count = 0;
            let mut max = 0;
            for &tree in &row[x + 1..] {
                count += 1;
                if tree > max {
                    max = tree;
                }
                if max >= h {
                    break;
                }
            }
            score *= count;

            let mut count = 0;
            let mut max = 0;
            for r in trees[..y].iter().rev() {
                count += 1;
                if r[x] > max {
                    max = r[x];
                }
                if max >= h {
                    break;
                }
            }
            score *= count;

            let mut count = 0;
            let mut max = 0;
            for r in trees[y + 1..].iter() {
                count += 1;
                if r[x] > max {
                    max = r[x];
                }
                if max >= h {
                    break;
                }
            }
            score *= count;

            best = std::cmp::max(best, score);
        }
    }
    best
}

motions = open("input.txt").read().split("\n")
routes = {"R": (1, 0), "L": (-1, 0), "U": (0, 1), "D": (0, -1)}


def touching(knots, i):
    if not knots[i]:
        return (0, 0)

    px, py = knots[i - 1]
    mx, my = knots[i]
    kx, ky = knots[i]

    for x in (mx - 1, mx, mx + 1):
        for y in (my - 1, my, my + 1):
            if x == px and y == py:
                return knots[i]

    if kx == px:
        ky += 1 if py - ky > 0 else -1

    if ky == py:
        kx += 1 if px - kx > 0 else -1

    if kx == mx and ky == my:
        kx += 1 if px - kx > 0 else -1
        ky += 1 if py - ky > 0 else -1

    return (kx, ky)


def simulation(knots: int = 1) -> int:
    knots = [(0, 0)] + [None for _ in range(knots)]
    history = set()

    for motion in motions:
        route, steps = motion.split(" ")

        for _ in range(int(steps)):
            knots[0] = list(map(lambda a, b: a + b, knots[0], routes[route]))

            for i in range(1, len(knots), 1):
                knots[i] = touching(knots, i)

            history.add(knots[-1])

    return len(history)


print(simulation())  # Part One: 6470
print(simulation(9))  # Part Two: 2658

#[derive(Clone)]
pub enum Operation {
    Add(usize),
    Mult(usize),
    Square,
}

impl Operation {
    fn apply(&self, item: usize) -> usize {
        match self {
            Operation::Add(x) => item + x,
            Operation::Mult(x) => item * x,
            Operation::Square => item * item,
        }
    }
}

#[derive(Clone)]
pub struct Monkey {
    items: std::collections::VecDeque<usize>,
    operation: Operation,
    test: usize,
    if_true: usize,
    if_false: usize,
    inspected: usize,
}

pub fn parse_input(input: &str) -> Vec<Monkey> {
    let mut monkeys = vec![];
    let mut input = input.lines();
    loop {
        input.next();
        let items = input
            .next()
            .unwrap()
            .split(": ")
            .nth(1)
            .unwrap()
            .split(", ")
            .map(|item| item.parse().unwrap())
            .collect();

        let operator: String;
        let operand: String;
        text_io::scan!(
            input.next().unwrap().bytes() =>
            "  Operation: new = old {} {}",
            operator,
            operand
        );
        let operation = if operator == "+" {
            Operation::Add(operand.parse().unwrap())
        } else if operand == "old" {
            Operation::Square
        } else {
            Operation::Mult(operand.parse().unwrap())
        };

        let test;
        text_io::scan!(input.next().unwrap().bytes() => "  Test: divisible by {}", test);

        let if_true;
        text_io::scan!(input.next().unwrap().bytes() => "    If true: throw to monkey {}", if_true);

        let if_false;
        text_io::scan!(
            input.next().unwrap().bytes() =>
            "    If false: throw to monkey {}",
            if_false
        );

        monkeys.push(Monkey {
            items,
            operation,
            test,
            if_true,
            if_false,
            inspected: 0,
        });

        if input.next().is_none() {
            break;
        }
    }
    monkeys
}

fn simulate(monkeys: &[Monkey], time: usize, div3: bool) -> usize {
    let mut monkeys = monkeys.to_owned();
    let common: usize = monkeys.iter().map(|m| m.test).product();
    for _round in 0..time {
        for i in 0..monkeys.len() {
            while let Some(item) = monkeys[i].items.pop_front() {
                let item = if div3 {
                    monkeys[i].operation.apply(item) / 3
                } else {
                    monkeys[i].operation.apply(item) % common
                };
                monkeys[i].inspected += 1;
                let target = if item % monkeys[i].test == 0 {
                    monkeys[i].if_true
                } else {
                    monkeys[i].if_false
                };
                monkeys[target].items.push_back(item);
            }
        }
    }
    let mut inspected: Vec<_> = monkeys.iter().map(|m| m.inspected).collect();
    inspected.sort();
    inspected[inspected.len() - 1] * inspected[inspected.len() - 2]
}

pub fn task1(monkeys: &[Monkey]) -> usize {
    simulate(monkeys, 20, true)
}

pub fn task2(monkeys: &[Monkey]) -> usize {
    simulate(monkeys, 10000, false)
}

use serde_json::Value;

pub fn parse_input(input: &str) -> Vec<Value> {
    input
        .lines()
        .filter_map(|line| {
            if line.is_empty() {
                None
            } else {
                Some(serde_json::from_str(line).unwrap())
            }
        })
        .collect()
}

fn cmp(left: &Value, right: &Value) -> std::cmp::Ordering {
    match (left, right) {
        (Value::Number(left), Value::Number(right)) => {
            left.as_i64().unwrap().cmp(&right.as_i64().unwrap())
        }
        (Value::Number(_), Value::Array(_)) => {
            cmp(&Value::Array(vec![left.clone()]), right)
        }
        (Value::Array(_), Value::Number(_)) => {
            cmp(left, &Value::Array(vec![right.clone()]))
        }
        (Value::Array(left), Value::Array(right)) => {
            if let Some(c) = left
                .iter()
                .zip(right.iter())
                .map(|(l, r)| cmp(l, r))
                .find(|&c| c != std::cmp::Ordering::Equal)
            {
                c
            } else {
                left.len().cmp(&right.len())
            }
        }
        _ => unimplemented!(),
    }
}

pub fn task1(input: &[Value]) -> usize {
    input
        .chunks(2)
        .enumerate()
        .filter_map(|(i, pair)| {
            if cmp(&pair[0], &pair[1]) == std::cmp::Ordering::Less {
                Some(i + 1)
            } else {
                None
            }
        })
        .sum()
}

pub fn task2(input: &[Value]) -> usize {
    let mut packets = input.to_vec();
    let start: Value = serde_json::from_str("[[2]]").unwrap();
    let end: Value = serde_json::from_str("[[6]]").unwrap();
    packets.push(start.clone());
    packets.push(end.clone());
    packets.sort_by(cmp);
    let start = packets.iter().position(|v| v == &start).unwrap() + 1;
    let end = packets.iter().position(|v| v == &end).unwrap() + 1;
    start * end
}

pub fn parse_input(input: &str) -> Vec<Vec<u8>> {
    let input = input
        .lines()
        .map(|line| {
            line.split(" -> ")
                .map(|pair| {
                    let (x, y);
                    text_io::scan!(pair.bytes()=>"{},{}", x, y);
                    (x, y)
                })
                .collect::<Vec<_>>()
        })
        .collect::<Vec<_>>();
    let (max_x, max_y) = input.iter().flat_map(|line| line.iter()).fold(
        (i32::MIN, i32::MIN),
        |(max_x, max_y), &(x, y)| {
            (std::cmp::max(max_x, x), std::cmp::max(max_y, y))
        },
    );
    let width = (2 * max_x) as usize;
    let height = (max_y + 1) as usize;
    let mut map = vec![vec![b' '; width]; height];
    for line in input {
        for pair in line.windows(2) {
            if pair[0].0 == pair[1].0 {
                let range = if pair[0].1 <= pair[1].1 {
                    pair[0].1..=pair[1].1
                } else {
                    pair[1].1..=pair[0].1
                };
                for y in range {
                    map[y as usize][pair[0].0 as usize] = b'#';
                }
            } else {
                let range = if pair[0].0 <= pair[1].0 {
                    pair[0].0..=pair[1].0
                } else {
                    pair[1].0..=pair[0].0
                };
                for x in range {
                    map[pair[0].1 as usize][x as usize] = b'#';
                }
            }
        }
    }
    map
}

pub fn task1(map: &[Vec<u8>]) -> usize {
    let mut map = map.to_vec();
    for sandgrain in 0.. {
        assert_eq!(map[0][500], b' ');
        let (mut x, mut y) = (500, 0);
        loop {
            if y == map.len() - 1 {
                return sandgrain;
            } else if map[y + 1][x] == b' ' {
            } else if map[y + 1][x - 1] == b' ' {
                x -= 1;
            } else if map[y + 1][x + 1] == b' ' {
                x += 1;
            } else {
                map[y][x] = b'o';
                break;
            }
            y += 1;
        }
    }
    unreachable!()
}

pub fn task2(map: &[Vec<u8>]) -> usize {
    let mut map = map.to_vec();
    map.push(vec![b' '; map[0].len()]);
    for sandgrain in 0.. {
        if map[0][500] != b' ' {
            return sandgrain;
        }
        let (mut x, mut y) = (500, 0);
        loop {
            if y == map.len() - 1 {
                map[y][x] = b'o';
                break;
            } else if map[y + 1][x] == b' ' {
            } else if map[y + 1][x - 1] == b' ' {
                x -= 1;
            } else if map[y + 1][x + 1] == b' ' {
                x += 1;
            } else {
                map[y][x] = b'o';
                break;
            }
            y += 1;
        }
    }
    unreachable!()
}