day7.rs (4372B)
1 use std::{collections::HashMap}; 2 3 // Making a recursive data structure in Rust is a pain in the ass. 4 // So don't bother, just link one way (nodes own their children) 5 // And we'll separately track our 'current working directory' with a 6 // vector of keys into the tree 7 #[derive(Debug)] 8 struct Node { 9 children: HashMap<String, Node>, 10 // Intrinsic size of the file at this location. 11 size: Option<u32>, 12 // Is the location a directory. Technically should be able to tell by presence/absence of children, but 13 // empty directories are a thing. 14 isdir: bool, 15 } 16 17 impl Node { 18 fn new(isdir: bool) -> Node { 19 Node { 20 children: HashMap::new(), 21 size: None, 22 isdir: isdir, 23 } 24 } 25 fn set(&mut self, path: &Vec<&str>, size: Option<u32>, isdir: bool) { 26 let mut cn = self; 27 for ch in path { 28 cn = cn.children.entry((*ch).to_owned()).or_insert(Node::new(true)); 29 } 30 cn.size = size; 31 cn.isdir = isdir; 32 } 33 /** 34 * Returns a map of total, recursive directory sizes,by relative path from the current directory 35 * Empty string key is the current directory size 36 */ 37 fn dir_sizes(self) -> HashMap<String, u32> { 38 let mut res: HashMap<String, u32> = HashMap::new(); 39 let mut mysize: u32 = 0; 40 for (name, nn) in self.children { 41 if let Some(fz) = nn.size { 42 // It's a file, just add the size 43 mysize += fz; 44 } else { 45 // It's a directory, add the size _and_ all the entries with subdir prefixed 46 let child_ds = nn.dir_sizes(); 47 let child_sz = child_ds[""]; 48 mysize += child_sz; 49 for (cn, sz) in child_ds { 50 res.insert(format!("{}/{}", name, cn), sz); 51 } 52 } 53 } 54 res.insert("".to_owned(), mysize); 55 res 56 } 57 } 58 59 pub fn run(input: String) { 60 let mut root = Node::new(true); 61 let mut cwd: Vec<&str>= vec![]; 62 let lines: Vec<&str> = input.lines().collect(); 63 let mut i = 0; 64 loop { 65 if i >= lines.len() { 66 break; 67 } 68 let line = lines[i]; 69 let toks: Vec<&str> = line.split_whitespace().collect(); 70 if toks[0] != "$" { 71 panic!("expected a command, got {}",line); 72 } 73 match toks[1] { 74 "cd" => { 75 i += 1; 76 let dirname = toks[2]; 77 if dirname == "/" { 78 cwd.clear(); 79 } else if dirname == ".." { 80 cwd.pop(); 81 } else { 82 cwd.push(dirname); 83 } 84 root.set(&cwd, None, true); 85 } 86 "ls" => { 87 i += 1; 88 loop { 89 if i >= lines.len() { 90 break; 91 } 92 let lsline = lines[i]; 93 let lstoks: Vec<&str> = lsline.split_whitespace().collect(); 94 if lstoks[0] == "$" { 95 // This is the next command, loop back to the top without incrementing! 96 break; 97 } 98 let (fsize, isdir) = if lstoks[0] == "dir" { 99 (None, true) 100 } else { 101 (Some(lstoks[0].parse().expect("filesize wasn't a u32!")), false) 102 }; 103 let fname = lstoks[1]; 104 cwd.push(fname); 105 root.set(&cwd, fsize, isdir); 106 cwd.pop(); 107 i += 1; 108 } 109 } 110 cmd => { 111 panic!("unknown command {}", cmd) 112 } 113 } 114 } 115 let ds = root.dir_sizes(); 116 // let mut tot: u32 = 0; 117 // for (_, sz) in ds { 118 // if sz <= 100000 { 119 // tot += sz; 120 // } 121 // } 122 // println!("Day 7: {}", tot); 123 let fs_size:u32 = 70000000; 124 let total_used = ds.get("").unwrap(); 125 let total_free = fs_size - total_used; 126 let update_size:u32 = 30000000; 127 let need_to_free = update_size - total_free; 128 let ddsz = ds.values() 129 .filter(|sz| { **sz >= need_to_free }) 130 .fold(fs_size, |acc, e| { acc.min(*e) }); 131 println!("Day 7: {}", ddsz); 132 }