1 files changed, 217 insertions, 0 deletions
diff --git a/aoc_2022/src/day_7.rs b/aoc_2022/src/day_7.rs
new file mode 100644
index 0000000..09eb1ef
--- /dev/null
+++ b/aoc_2022/src/day_7.rs
@@ -0,0 +1,217 @@
+use std::{collections::HashMap, fmt::Display, ops::Deref, str::FromStr};
+
+use anyhow::{anyhow, Context, Result};
+
+use aoc::{Problem, Solution};
+
+enum Cmd {
+    Root,
+    Parent,
+    Child(String),
+    LS(Vec<Entry>),
+}
+
+impl FromStr for Cmd {
+    type Err = anyhow::Error;
+
+    fn from_str(s: &str) -> Result<Self, Self::Err> {
+        let (cmd, arg) = s.trim().split_at(2);
+        let cmd_arg = (cmd.trim(), arg.trim());
+        match cmd_arg {
+            ("cd", "/") => Ok(Self::Root),
+            ("cd", "..") => Ok(Self::Parent),
+            ("cd", child) => Ok(Self::Child(child.to_owned())),
+            ("ls", arg) => {
+                let entries = arg
+                    .trim()
+                    .lines()
+                    .map(Entry::from_str)
+                    .collect::<Result<Vec<_>>>()?;
+                Ok(Cmd::LS(entries))
+            }
+            _ => Err(anyhow!("Failed to parse Command from str: {}", s)),
+        }
+    }
+}
+
+enum Entry {
+    Dir(String),
+    File((String, usize)),
+}
+
+impl FromStr for Entry {
+    type Err = anyhow::Error;
+
+    fn from_str(s: &str) -> Result<Self, Self::Err> {
+        let (entry_type, name) = s
+            .split_once(' ')
+            .context(format!("Failed to parse Command from str: {}", s))?;
+        match entry_type {
+            "dir" => Ok(Self::Dir(name.to_owned())),
+            t => Ok(Self::File((name.to_owned(), t.parse()?))),
+        }
+    }
+}
+
+#[derive(Default, Debug)]
+struct FileSystem {
+    entries: HashMap<Vec<String>, usize>,
+    cwd: Vec<String>,
+}
+
+impl FileSystem {
+    fn add(&mut self, size: usize) {
+        self.entries
+            .entry(self.cwd.to_owned())
+            .and_modify(|n| *n += size)
+            .or_insert(size);
+    }
+
+    fn pop_and_add(&mut self) -> Option<String> {
+        let size = *self.entries.get(&self.cwd).unwrap_or(&0);
+        let value = self.cwd.pop();
+        self.add(size);
+        value
+    }
+
+    fn exec_cmd(&mut self, cmd: Cmd) {
+        match cmd {
+            Cmd::Root => self.cwd = vec![],
+            Cmd::Parent => {
+                self.pop_and_add();
+            }
+            Cmd::Child(d) => self.cwd.push(d),
+            Cmd::LS(entries) => {
+                for entry in entries.into_iter() {
+                    match entry {
+                        Entry::File((_, size)) => self.add(size),
+                        Entry::Dir(_) => {}
+                    }
+                }
+            }
+        }
+    }
+}
+
+impl Deref for FileSystem {
+    type Target = HashMap<Vec<String>, usize>;
+
+    fn deref(&self) -> &Self::Target {
+        &self.entries
+    }
+}
+
+impl FromStr for FileSystem {
+    type Err = anyhow::Error;
+
+    fn from_str(s: &str) -> Result<Self, Self::Err> {
+        s.split('$')
+            .filter_map(|l| match l.trim() {
+                _ if l.is_empty() => None,
+                l => Some(l),
+            })
+            .flat_map(Cmd::from_str)
+            .collect::<Vec<Cmd>>()
+            .try_into()
+    }
+}
+
+impl TryFrom<Vec<Cmd>> for FileSystem {
+    type Error = anyhow::Error;
+
+    fn try_from(value: Vec<Cmd>) -> Result<Self, Self::Error> {
+        let mut fs = Self::default();
+        for cmd in value {
+            fs.exec_cmd(cmd)
+        }
+
+        while !fs.cwd.is_empty() {
+            fs.exec_cmd(Cmd::Parent)
+        }
+
+        Ok(fs)
+    }
+}
+
+impl Display for FileSystem {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+        writeln!(f, "path\tsize")?;
+        for (path, size) in &self.entries {
+            writeln!(f, "/{}\t{}", path.join("/"), size)?;
+        }
+        Ok(())
+    }
+}
+
+pub struct Day7;
+
+impl Problem for Day7 {
+    const DAY: u8 = 7;
+
+    const INPUT: &'static str = include_str!("../input/day_7.txt");
+}
+
+impl Solution for Day7 {
+    type Answer1 = usize;
+
+    type Answer2 = usize;
+
+    fn part_1(input: &str) -> Result<Self::Answer1> {
+        let fs: FileSystem = input.parse()?;
+        Ok(fs.values().filter(|&s| *s < 100_000).sum())
+    }
+
+    fn part_2(input: &str) -> Result<Self::Answer2> {
+        let fs: FileSystem = input.parse()?;
+        let used = *fs.get(&Vec::new()).context("Failed to get root size")?;
+
+        fs.values()
+            .filter_map(|&dir_size| match dir_size {
+                k if used - k < 40_000_000 => Some(k),
+                _ => None,
+            })
+            .min()
+            .context("No directory found")
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    const TEST_INPUT: &str = indoc::indoc! {r#"
+            $ cd /
+            $ ls
+            dir a
+            14848514 b.txt
+            8504156 c.dat
+            dir d
+            $ cd a
+            $ ls
+            dir e
+            29116 f
+            2557 g
+            62596 h.lst
+            $ cd e
+            $ ls
+            584 i
+            $ cd ..
+            $ cd ..
+            $ cd d
+            $ ls
+            4060174 j
+            8033020 d.log
+            5626152 d.ext
+            7214296 k
+        "#};
+
+    #[test]
+    fn test_part_1_example() -> Result<()> {
+        Ok(assert_eq!(95437, Day7::part_1(TEST_INPUT)?))
+    }
+
+    #[test]
+    fn test_part_2_example() -> Result<()> {
+        Ok(assert_eq!(24933642, Day7::part_2(TEST_INPUT)?))
+    }
+}