.rs

use std::collections::HashMap;

#[derive(Default, Debug)]
struct Dir {
    name_and_parent: Option<(String, Box<Dir>)>,
    files: HashMap<String, usize>,
    subdirs: HashMap<String, Box<Dir>>,
    total_size: usize,
}

impl Dir {
    fn move_up(mut self: Box<Self>) -> Box<Self> {
        let Some((name, mut parent)) = self.name_and_parent.take() else {
            return self;
        };
        parent.total_size += self.total_size;
        parent.subdirs.insert(name, self);
        parent
    }

    fn move_to_root(self: Box<Self>) -> Box<Self> {
        if self.name_and_parent.is_none() { return self; }
        self.move_up().move_to_root()
    }

    fn move_down(mut self: Box<Self>, dir_name: &str) -> Box<Self> {
        let (name, mut subdir) = self.subdirs.remove_entry(dir_name).unwrap();
        self.total_size -= subdir.total_size;
        subdir.name_and_parent = Some((name, self));
        subdir
    }

    fn add_file(&mut self, name: String, size: usize) {
        self.files.insert(name, size);
        self.total_size += size;
    }

    fn add_dir(&mut self, name: String) {
        if !self.subdirs.contains_key(&name) {
            self.subdirs.insert(name, Box::default());
        }
    }
}

fn count_sum_of_sizes_up_to_100000(dir: &Dir) -> usize {
    let subdirs_result = dir.subdirs.values()
        .map(|subdir| count_sum_of_sizes_up_to_100000(subdir))
        .sum::<usize>();
    if dir.total_size <= 100000 {
        dir.total_size + subdirs_result
    } else {
        subdirs_result
    }
}

fn best_dir_to_delete(dir: &Dir, need_space: usize) -> Option<usize> {
    let best_from_subdirs = dir.subdirs.values()
        .filter_map(|subdir| best_dir_to_delete(subdir, need_space))
        .min();
    if best_from_subdirs.is_some() {
        best_from_subdirs
    } else if dir.total_size >= need_space {
        Some(dir.total_size)
    } else {
        None
    }
}

fn main() {
    let mut dir = Box::new(Dir::default());

    for line in std::io::stdin().lines().map(Result::unwrap) {
        let parts = line.split_whitespace().collect::<Vec<_>>();

        match (parts[0], parts[1]) {
            ("$", "cd") => match parts[2] {
                "/" => dir = dir.move_to_root(),
                ".." => dir = dir.move_up(),
                subdir => dir = dir.move_down(subdir),
            },
            ("$", _) => {},
            ("dir", dir_name) => dir.add_dir(dir_name.to_string()),
            (size_str, file_name) => {
                let size = size_str.parse::<usize>().unwrap();
                dir.add_file(file_name.to_string(), size);
            },
        }
    }

    dir = dir.move_to_root();
    println!("{:?}", best_dir_to_delete(&dir, 30000000 - (70000000 - dir.total_size)));
}