1 files changed, 268 insertions, 0 deletions
diff --git a/day07b/src/main.rs b/day07b/src/main.rs
new file mode 100644
index 0000000..f9cd74c
--- /dev/null
+++ b/day07b/src/main.rs
@@ -0,0 +1,268 @@
+/// --- Part Two ---
+///
+/// Now, you're ready to choose a directory to delete.
+///
+/// The total disk space available to the filesystem is 70000000.  To run the update, you need
+/// unused space of at least 30000000.  You need to find a directory you can delete that will free
+/// up enough space to run the update.
+///
+/// In the example above, the total size of the outermost directory (and thus the total amount of
+/// used space) is 48381165; this means that the size of the unused space must currently be
+/// 21618835, which isn't quite the 30000000 required by the update.  Therefore, the update still
+/// requires a directory with total size of at least 8381165 to be deleted before it can run.
+///
+/// To achieve this, you have the following options:
+///
+///     Delete directory e, which would increase unused space by 584.
+///     Delete directory a, which would increase unused space by 94853.
+///     Delete directory d, which would increase unused space by 24933642.
+///     Delete directory /, which would increase unused space by 48381165.
+///
+/// Directories e and a are both too small; deleting them would not free up enough space. However,
+/// directories d and / are both big enough!  Between these, choose the smallest: d, increasing
+/// unused space by 24933642.
+///
+/// Find the smallest directory that, if deleted, would free up enough space on the filesystem to
+/// run the update.  What is the total size of that directory?
+use clap::Parser;
+use nom::branch::alt;
+use nom::bytes::streaming::tag;
+use nom::character::streaming::{char, newline, not_line_ending, space1, u64};
+use nom::combinator::{map, peek};
+use nom::error::{context, ContextError, ErrorKind as NomErrorKind, ParseError};
+use nom::multi::many_till;
+use nom::sequence::{delimited, preceded, terminated, tuple};
+use nom::IResult;
+
+use std::collections::HashMap;
+use std::fs::File;
+use std::io::prelude::*;
+use std::io::BufReader;
+use std::iter::*;
+use std::path::PathBuf;
+
+pub type Input<'a> = &'a str;
+pub type Result<'a, T> = IResult<Input<'a>, T, Error<Input<'a>>>;
+
+#[derive(Clone, Debug, PartialEq, Eq)]
+pub enum ErrorKind {
+    Nom(NomErrorKind),
+    Context(&'static str),
+    Custom(String),
+}
+
+#[derive(Clone, Debug, PartialEq, Eq)]
+pub struct Error<I> {
+    pub errors: Vec<(I, ErrorKind)>,
+}
+
+impl<I> ParseError<I> for Error<I> {
+    fn from_error_kind(input: I, kind: NomErrorKind) -> Self {
+        let errors = vec![(input, ErrorKind::Nom(kind))];
+        Self { errors }
+    }
+
+    fn append(input: I, kind: NomErrorKind, mut other: Self) -> Self {
+        other.errors.push((input, ErrorKind::Nom(kind)));
+        other
+    }
+}
+
+impl<I> ContextError<I> for Error<I> {
+    fn add_context(input: I, ctx: &'static str, mut other: Self) -> Self {
+        other.errors.push((input, ErrorKind::Context(ctx)));
+        other
+    }
+}
+
+const FILEPATH: &'static str = "examples/input.txt";
+const EOF_CHAR: char = '\0';
+const TOTALSPACE: u64 = 70000000;
+const NEEDEDSPACE: u64 = 30000000;
+
+#[derive(Parser, Debug)]
+#[clap(author, version, about, long_about = None)]
+struct Cli {
+    #[clap(short, long, default_value = FILEPATH)]
+    file: PathBuf,
+}
+
+#[derive(Clone, Debug)]
+enum Commands {
+    ChangeDir(String),
+    List(Vec<ListEntry>),
+}
+
+#[derive(Clone, Debug)]
+enum ListEntry {
+    File(FileEntry),
+    Folder(String),
+}
+
+#[derive(Clone, Debug)]
+struct FileEntry {
+    name: String,
+    size: u64,
+}
+
+#[derive(Clone, Debug)]
+struct Arena(Vec<Node>);
+
+#[derive(Clone, Debug)]
+struct Node {
+    size: u64,
+    parent: Option<usize>,
+    children: HashMap<String, usize>,
+}
+
+impl Node {
+    fn new() -> Self {
+        Node {
+            size: 0,
+            parent: None,
+            children: HashMap::new(),
+        }
+    }
+
+    fn with_parent(idx: usize) -> Self {
+        Node {
+            size: 0,
+            parent: Some(idx),
+            children: HashMap::new(),
+        }
+    }
+}
+
+impl Arena {
+    // NOTE: only call this once per node
+    fn consume(&mut self, idx: usize, ls: Vec<ListEntry>) {
+        for le in ls.into_iter() {
+            match le {
+                ListEntry::File(f) => {
+                    let mut iteridx = idx;
+                    loop {
+                        self.0[iteridx].size += f.size;
+                        iteridx = if let Some(pidx) = self.0[iteridx].parent {
+                            pidx
+                        } else {
+                            break;
+                        };
+                    }
+                }
+                ListEntry::Folder(f) => {
+                    let fidx = self.0.len();
+                    self.0.push(Node::with_parent(idx));
+                    self.0[idx].children.insert(f, fidx);
+                }
+            }
+        }
+    }
+
+    fn get(&mut self, idx: usize) -> &mut Node {
+        &mut self.0[idx]
+    }
+}
+
+fn parse_cd(input: &str) -> Result<Commands> {
+    context(
+        "parse_cd",
+        map(
+            delimited(tuple((tag("cd"), space1)), not_line_ending, newline),
+            |s: &str| Commands::ChangeDir(s.to_string()),
+        ),
+    )(input)
+}
+
+fn end_of_file_or_ls(input: &str) -> Result<char> {
+    alt((char(EOF_CHAR), peek(char('$'))))(input)
+}
+
+fn parse_ls(input: &str) -> Result<Commands> {
+    let (input, _) = context("parse_ls", terminated(tag("ls"), newline))(input)?;
+    let (input, (lsv, _)) = many_till(parse_ls_entry, end_of_file_or_ls)(input)?;
+    Ok((input, Commands::List(lsv)))
+}
+
+fn parse_ls_entry(input: &str) -> Result<ListEntry> {
+    context("parse_ls_entry", alt((parse_file, parse_folder)))(input)
+}
+
+fn parse_file(input: &str) -> Result<ListEntry> {
+    map(
+        terminated(tuple((u64, preceded(tag(" "), not_line_ending))), newline),
+        |(size, name): (u64, &str)| {
+            ListEntry::File(FileEntry {
+                name: name.to_string(),
+                size,
+            })
+        },
+    )(input)
+}
+
+fn parse_folder(input: &str) -> Result<ListEntry> {
+    map(
+        delimited(tag("dir "), not_line_ending, newline),
+        |s: &str| ListEntry::Folder(s.to_string()),
+    )(input)
+}
+
+fn parse_cmd(input: &str) -> Result<Commands> {
+    context(
+        "parse_cmd",
+        preceded(tuple((tag("$"), space1)), alt((parse_cd, parse_ls))),
+    )(input)
+}
+
+fn main() {
+    let args = Cli::parse();
+
+    let file = File::open(&args.file).unwrap();
+    let mut reader = BufReader::new(file);
+
+    let mut buf = String::new();
+    let mut cmds = Vec::new();
+    'block: loop {
+        let len = reader.read_line(&mut buf).unwrap();
+        if len == 0 {
+            buf.push(EOF_CHAR);
+        }
+        loop {
+            match parse_cmd(buf.as_str()) {
+                Ok((input, cmd)) => {
+                    cmds.push(cmd);
+                    if len == 0 && input.len() == 0 {
+                        break 'block;
+                    }
+                    let _ = buf.drain(..(buf.len() - input.len()));
+                }
+                Err(err) => match err {
+                    nom::Err::Incomplete(_) => continue 'block,
+                    e @ _ => panic!("buf={} err={}", buf, e),
+                },
+            }
+        }
+    }
+
+    let mut loc = 0;
+    let mut arena = Arena(Vec::new());
+    arena.0.push(Node::new());
+    for cmd in cmds.into_iter() {
+        match cmd {
+            Commands::ChangeDir(dir) => match dir.as_str() {
+                "/" => loc = 0,
+                ".." => loc = arena.get(loc).parent.unwrap(),
+                _ => loc = arena.get(loc).children[&dir],
+            },
+            Commands::List(lsv) => arena.consume(loc, lsv),
+        }
+    }
+
+    let rmdir_minsize = NEEDEDSPACE - (TOTALSPACE - arena.get(0).size);
+    let res: u64 = arena
+        .0
+        .into_iter()
+        .filter(|n| n.size >= rmdir_minsize)
+        .map(|n| n.size)
+        .min().unwrap();
+    println!("{res:?}");
+}