diff options
Diffstat (limited to '2022/src/bin/day_7.rs')
| -rw-r--r-- | 2022/src/bin/day_7.rs | 227 |
1 files changed, 227 insertions, 0 deletions
diff --git a/2022/src/bin/day_7.rs b/2022/src/bin/day_7.rs new file mode 100644 index 0000000..8933816 --- /dev/null +++ b/2022/src/bin/day_7.rs @@ -0,0 +1,227 @@ +use nom::{ + branch::alt, + bytes::complete::tag, + character::complete::{line_ending, not_line_ending, u32 as nom_u32}, + combinator::map, + multi::separated_list1, + sequence::{preceded, tuple}, + IResult, +}; +use std::fs; + +fn main() -> Result<(), Box<dyn std::error::Error>> { + let input = fs::read_to_string("inputs/day_7.txt")?; + let terminal_log = TerminalLog::parser(&input).unwrap().1; + let dir_tree = terminal_log.process_to_dir_tree(); + + dbg!(dir_tree.sum_sizes_below_threshhold(100000)); + + let required_disk_usage = 70000000 - 30000000; + let required_deletion = dir_tree.size() - required_disk_usage; + dbg!(dir_tree.find_min_size_greater_than(required_deletion)); + + Ok(()) +} + +#[derive(Debug, PartialEq, Eq, Clone)] +struct TerminalLog(Vec<TerminalLogItem>); + +#[derive(Debug, PartialEq, Eq, Clone)] +enum TerminalLogItem { + Command(TerminalLogCommand), + Output(TerminalLogOutput), +} + +#[derive(Debug, PartialEq, Eq, Clone)] +enum TerminalLogCommand { + CdRoot, + CdUp, + CdDown(String), + List, +} + +#[derive(Debug, PartialEq, Eq, Clone)] +enum TerminalLogOutput { + Dir(String), + File(u32, String), +} + +impl TerminalLog { + fn parser(input: &str) -> IResult<&str, TerminalLog> { + map( + separated_list1(line_ending, TerminalLogItem::parser), + TerminalLog, + )(input) + } + + fn process_to_dir_tree(&self) -> DirTree { + use TerminalLogCommand::*; + use TerminalLogItem::*; + use TerminalLogOutput::*; + + let mut dir_tree_root = DirTree::root(); + let mut dir_path = Vec::new(); + + for log in &self.0 { + match log { + Command(CdRoot) => dir_path.clear(), + Command(CdUp) => { + dir_path.pop(); + } + Command(CdDown(dir_name)) => { + dir_path.push(dir_name.clone()); + } + Command(List) => {} + Output(Dir(dir_name)) => { + let dir = DirTree::new(dir_name.clone()); + dir_tree_root.push_dir(&dir_path, dir); + } + Output(File(size, name)) => { + let file = DirTreeFile { + name: name.clone(), + size: size.clone(), + }; + dir_tree_root.push_file(&dir_path, file); + } + } + } + + dir_tree_root + } +} + +impl TerminalLogItem { + fn parser(input: &str) -> IResult<&str, TerminalLogItem> { + alt(( + map( + preceded(tag("$ "), TerminalLogCommand::parser), + TerminalLogItem::Command, + ), + map(TerminalLogOutput::parser, TerminalLogItem::Output), + ))(input) + } +} + +impl TerminalLogCommand { + fn parser(input: &str) -> IResult<&str, TerminalLogCommand> { + alt(( + map(tag("cd /"), |_| TerminalLogCommand::CdRoot), + map(tag("cd .."), |_| TerminalLogCommand::CdUp), + map(preceded(tag("cd "), name_parser), |name| { + TerminalLogCommand::CdDown(name) + }), + map(tag("ls"), |_| TerminalLogCommand::List), + ))(input) + } +} + +impl TerminalLogOutput { + fn parser(input: &str) -> IResult<&str, TerminalLogOutput> { + alt(( + map(preceded(tag("dir "), name_parser), |name| { + TerminalLogOutput::Dir(name) + }), + map( + tuple((nom_u32, tag(" "), name_parser)), + |(size, _, name)| TerminalLogOutput::File(size, name), + ), + ))(input) + } +} + +fn name_parser(input: &str) -> IResult<&str, String> { + map(not_line_ending, |s: &str| s.to_owned())(input) +} + +#[derive(Debug, PartialEq, Eq, Clone)] +struct DirTree { + name: String, + files: Vec<DirTreeFile>, + dirs: Vec<DirTree>, +} + +#[derive(Debug, PartialEq, Eq, Clone)] +struct DirTreeFile { + name: String, + size: u32, +} + +impl DirTree { + fn root() -> DirTree { + DirTree { + name: "/".into(), + files: Vec::new(), + dirs: Vec::new(), + } + } + + fn new(name: String) -> DirTree { + DirTree { + name, + files: Vec::new(), + dirs: Vec::new(), + } + } + + fn push_dir(&mut self, path: &[String], dir: DirTree) { + if path.is_empty() { + self.dirs.push(dir); + } else { + let subdir = self + .dirs + .iter_mut() + .find(|d| d.name == path[0]) + .expect("Subdir doesn't exist"); + subdir.push_dir(&path[1..], dir); + } + } + + fn push_file(&mut self, path: &[String], dir: DirTreeFile) { + if path.is_empty() { + self.files.push(dir); + } else { + let subdir = self + .dirs + .iter_mut() + .find(|d| d.name == path[0]) + .expect("Subdir doesn't exist"); + subdir.push_file(&path[1..], dir); + } + } + + fn size(&self) -> u32 { + self.files.iter().map(|f| f.size).sum::<u32>() + + self.dirs.iter().map(|f| f.size()).sum::<u32>() + } + + fn sum_sizes_below_threshhold(&self, threshhold: u32) -> u32 { + let self_size = self.size(); + let self_size_below_threshold = if self_size < threshhold { self_size } else { 0 }; + self_size_below_threshold + + self + .dirs + .iter() + .map(|f| f.sum_sizes_below_threshhold(threshhold)) + .sum::<u32>() + } + + fn find_min_size_greater_than(&self, threshhold: u32) -> Option<u32> { + let min_subdir = self + .dirs + .iter() + .filter_map(|d| d.find_min_size_greater_than(threshhold)) + .min(); + + match min_subdir { + Some(min) => Some(min), + None => { + let self_size = self.size(); + if self_size > threshhold { + Some(self_size) + } else { + None + } + } + } + } +} |