diff options
Diffstat (limited to 'src/day7.rs')
| -rw-r--r-- | src/day7.rs | 132 |
1 files changed, 132 insertions, 0 deletions
diff --git a/src/day7.rs b/src/day7.rs new file mode 100644 index 0000000..e0df644 --- /dev/null +++ b/src/day7.rs @@ -0,0 +1,132 @@ +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); +}
\ No newline at end of file |