use std::{collections::HashMap};

// Making a recursive data structure in Rust is a pain in the ass.
// So don't bother, just link one way (nodes own their children)
// And we'll separately track our 'current working directory' with a 
// vector of keys into the tree
#[derive(Debug)]
struct Node {
    children: HashMap<String, Node>,
    // Intrinsic size of the file at this location.
    size: Option<u32>,
    // Is the location a directory. Technically should be able to tell by presence/absence of children, but 
    // empty directories are a thing.
    isdir: bool,
}

impl Node {
    fn new(isdir: bool) -> Node {
        Node {
            children: HashMap::new(),
            size: None,
            isdir: isdir,
        }
    }
    fn set(&mut self, path: &Vec<&str>, size: Option<u32>, isdir: bool) {
        let mut cn = self;
        for ch in path {
            cn = cn.children.entry((*ch).to_owned()).or_insert(Node::new(true));
        }
        cn.size = size;
        cn.isdir = isdir;
    }
    /**
     * Returns a map of total, recursive directory sizes,by relative path from the current directory
     * Empty string key is the current directory size
     */ 
    fn dir_sizes(self) -> HashMap<String, u32> {
        let mut res: HashMap<String, u32> = HashMap::new();
        let mut mysize: u32 = 0;
        for (name, nn) in self.children {
            if let Some(fz) = nn.size {
                // It's a file, just add the size
                mysize += fz;
            } else {
                // It's a directory, add the size _and_ all the entries with subdir prefixed
                let child_ds = nn.dir_sizes();
                let child_sz = child_ds[""];
                mysize += child_sz;
                for (cn, sz) in child_ds {
                    res.insert(format!("{}/{}", name, cn), sz);
                }
            }
        }
        res.insert("".to_owned(), mysize);
        res
    }
}

pub fn run(input: String) {
    let mut root = Node::new(true);
    let mut cwd: Vec<&str>= vec![];
    let lines: Vec<&str> = input.lines().collect();
    let mut i = 0;
    loop {
        if i >= lines.len() {
            break;
        }
        let line = lines[i];
        let toks: Vec<&str> = line.split_whitespace().collect();
        if toks[0] != "$" {
            panic!("expected a command, got {}",line);
        }
        match toks[1] {
            "cd" => {
                i += 1;
                let dirname = toks[2];
                if dirname == "/" {
                    cwd.clear();
                } else if dirname == ".." {
                    cwd.pop();
                } else {
                    cwd.push(dirname);
                }
                root.set(&cwd, None, true);
            }
            "ls" => {
                i += 1;
                loop {
                    if i >= lines.len() {
                        break;
                    }
                    let lsline = lines[i];
                    let lstoks: Vec<&str> = lsline.split_whitespace().collect();
                    if lstoks[0] == "$" {
                        // This is the next command, loop back to the top without incrementing!
                        break;
                    }
                    let (fsize, isdir) = if lstoks[0] == "dir" {
                        (None, true)
                    } else {
                        (Some(lstoks[0].parse().expect("filesize wasn't a u32!")), false)
                    };
                    let fname = lstoks[1];
                    cwd.push(fname);
                    root.set(&cwd, fsize, isdir);
                    cwd.pop();
                    i += 1;
                }
            }
            cmd => {
                panic!("unknown command {}", cmd)
            }
        }
    }
    let ds = root.dir_sizes();
    // let mut tot: u32 = 0;
    // for (_, sz) in ds {
    //     if sz <= 100000 {
    //         tot += sz;
    //     }
    // }
    // println!("Day 7: {}", tot);
    let fs_size:u32 = 70000000;
    let total_used = ds.get("").unwrap();
    let total_free = fs_size - total_used;
    let update_size:u32 = 30000000;
    let need_to_free = update_size - total_free;
    let ddsz = ds.values()
        .filter(|sz| { **sz >= need_to_free })
        .fold(fs_size, |acc, e| { acc.min(*e) });
    println!("Day 7: {}", ddsz);
}