Add day07, 2022

1 files changed, 216 insertions, 0 deletions

diff --git a/2022/rust/day07/src/main.rs b/2022/rust/day07/src/main.rs
new file mode 100644
index 0000000..520e5a0
--- /dev/null
+++ b/2022/rust/day07/src/main.rs
@@ -0,0 +1,216 @@
+use {
+    anyhow::{
+        anyhow,
+        Context,
+        Result,
+    },
+    regex::Regex,
+    std::{
+        collections::HashMap,
+        env::args,
+        fs::File,
+        io::{
+            BufRead,
+            BufReader,
+        },
+        path::Path,
+    },
+};
+
+#[derive(Debug,PartialEq)]
+struct FileDetails {
+    size: usize,
+}
+
+#[derive(Debug,PartialEq)]
+struct FileTree {
+    tree: HashMap<String, EntryNode>,
+}
+
+#[derive(Debug,PartialEq)]
+enum EntryNode {
+    File(FileDetails),
+    Directory(FileTree),
+}
+
+impl FileTree {
+    fn default() -> Self {
+        Self {
+            tree: HashMap::new(),
+        }
+    }
+
+    fn chdir(&mut self, path: &[String]) -> Option<&mut Self> {
+        if let Some((i, directory)) = path.iter().enumerate().find(|(_, name)| *name != "/") {
+            if let Some(node) = self.tree.get_mut(directory) {
+                match node {
+                    EntryNode::File(_) => panic!("Tried to chdir into a file."),
+                    EntryNode::Directory(tree) => tree.chdir(&path[(i + 1)..]),
+                }
+            } else {
+                None
+            }
+        } else {
+            Some(self)
+        }
+    }
+
+    fn size(&self) -> usize {
+        let mut size = 0;
+        for node in self.tree.values() {
+            match node {
+                EntryNode::File(file) => size += file.size,
+                EntryNode::Directory(directory) => size += directory.size(),
+            }
+        }
+
+        size
+    }
+
+    fn traverse(&self) -> TreeTraverse {
+        TreeTraverse::new(self)
+    }
+}
+
+struct TreeTraverse<'a> {
+    tree: &'a FileTree,
+    visited: Vec<&'a EntryNode>,
+}
+
+impl<'a> TreeTraverse<'a> {
+    fn new(tree: &'a FileTree) -> Self {
+        Self {
+            tree,
+            visited: vec![],
+        }
+    }
+
+    fn recurse(&mut self, tree: &'a FileTree) -> Option<&'a EntryNode> {
+        for node in tree.tree.values() {
+            if self.visited.contains(&node) {
+                continue;
+            }
+
+            match node {
+                EntryNode::File(_) => {
+                    self.visited.push(node);
+                    return Some(node);
+                },
+                EntryNode::Directory(subdir) => {
+                    return self.recurse(subdir).or_else(|| {
+                        self.visited.push(node);
+                        Some(node)
+                    });
+                }
+            }
+        }
+        None
+    }
+}
+
+impl<'a> Iterator for TreeTraverse<'a> {
+    type Item = &'a EntryNode;
+
+    fn next(&mut self) -> Option<&'a EntryNode> {
+        self.recurse(self.tree)
+    }
+}
+
+fn read_input<T: AsRef<Path>>(filename: T) -> Result<FileTree> {
+    let reader = BufReader::new(File::open(filename)?);
+    let re = Regex::new(r#"(?x)^
+        (\$\s+(?P<command>\S+)(\s+(?P<arg>\S+))?)|
+        (dir\s+(?P<directory>.+))|
+        ((?P<size>[0-9]+)\s+(?P<filename>\S+))
+    $"#).context("Could not compile regex.")?;
+
+    let mut root = FileTree::default();
+    let mut path = vec![];
+
+    for (lineno, v) in reader.lines().enumerate() {
+        let node = root.chdir(&path).ok_or_else(|| anyhow!("Path {path:?} does not exist"))?;
+        let s = v?;
+        let caps = re.captures(&s)
+            .ok_or_else(|| anyhow!("Regex matching failed on line {lineno}: '{s}'"))?;
+
+        if let Some(command) = caps.name("command") {
+            match command.as_str() {
+                "cd" => {
+                    if let Some(arg) = caps.name("arg") {
+                        let dir = arg.as_str();
+                        if dir == ".." {
+                            path.pop();
+                        } else if dir == "." {
+                            // Remain in current directory.
+                        } else {
+                            path.push(String::from(dir));
+                        }
+                    }
+                },
+                "ls" => { },
+                cmd => return Err(anyhow!("Unknown command: '{cmd}'.")),
+            }
+        } else if let Some(dir_cap) = caps.name("directory") {
+            let directory = dir_cap.as_str();
+            node.tree.insert(String::from(directory), EntryNode::Directory(FileTree::default()));
+        } else if let (Some(cap_f), Some(cap_s)) = (caps.name("filename"), caps.name("size")) {
+            let str_s = cap_s.as_str();
+            let size = str_s.parse().context("Parse error: {str_s}")?;
+            let filename = cap_f.as_str();
+            node.tree.insert(String::from(filename), EntryNode::File(FileDetails { size }));
+        } else {
+            unreachable!();
+        }
+    }
+
+    Ok(root)
+}
+
+fn part1(input: &FileTree) -> Result<usize> {
+    Ok(input.traverse().filter_map(|node|
+        if let EntryNode::Directory(directory) = node {
+            let size = directory.size();
+            if size <= 100000 {
+                Some(size)
+            } else {
+                None
+            }
+        } else {
+            None
+        }).sum())
+}
+
+fn part2(input: &FileTree) -> Result<usize> {
+    let capacity = 70000000;
+    let required = 30000000;
+    let used = input.size();
+    let reclaim = required + used - capacity;
+
+    input.traverse().filter_map(|node|
+        if let EntryNode::Directory(directory) = node {
+            let size = directory.size();
+            if size >= reclaim {
+                Some(size)
+            } else {
+                None
+            }
+        } else {
+            None
+        }).min().ok_or_else(|| anyhow!("No suitable directory found"))
+}
+
+fn main() -> Result<()> {
+    let ( do_part_1, do_part_2 ) = aoc::do_parts();
+
+    let filename = args().nth(1).ok_or_else(|| anyhow!("Missing input filename"))?;
+    let input = read_input(filename).context("Could not read input")?;
+    if do_part_1 {
+        let solution = part1(&input).context("No solution for part 1")?;
+        println!("Part1, solution found to be: {}", solution);
+    }
+    if do_part_2 {
+        let solution = part2(&input).context("No solution for part 2")?;
+        println!("Part2, solution found to be: {}", solution);
+    }
+    Ok(())
+}