diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/day7.rs | 132 | ||||
| -rw-r--r-- | src/main.rs | 2 |
2 files changed, 134 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 diff --git a/src/main.rs b/src/main.rs index 0be4d7f..b370693 100644 --- a/src/main.rs +++ b/src/main.rs @@ -6,6 +6,7 @@ mod day3; mod day4; mod day5; mod day6; +mod day7; fn main() { day1::run(fs::read_to_string("input/day1.txt").expect("Failed to read input file!")); @@ -14,4 +15,5 @@ fn main() { day4::run(fs::read_to_string("input/day4.txt").expect("Failed to read input file!")); day5::run(fs::read_to_string("input/day5.txt").expect("Failed to read input file!")); day6::run(fs::read_to_string("input/day6.txt").expect("Failed to read input file!")); + day7::run(fs::read_to_string("input/day7.txt").expect("Failed to read input file!")); } |