From 7383b348a746ac340e3058d733edc59a7c893e32 Mon Sep 17 00:00:00 2001
From: Martin Ashby <martin@ashbysoft.com>
Date: Wed, 7 Dec 2022 21:30:24 +0000
Subject: day7

This one was a little trickier, as the obvious solution for navigating back up a tree is to keep a reference to the parent.
However that's essentially a doubly linked list which is a pain in the ass in Rust.
Instead, use a separate variable for the current 'key' into the tree

I'm not especially happy with the terminal processing as well, since after the 'ls' command we need to 'peek' at the next entry to see if the 'ls' has finished and we're onto a next command
I couldn't think of a very good way to do this except loops and loops.
---
 src/day7.rs | 132 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 src/main.rs |   2 +
 2 files changed, 134 insertions(+)
 create mode 100644 src/day7.rs

(limited to 'src')

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!"));
 }
-- 
cgit v1.2.3-ZIG