diff options
Diffstat (limited to '2022/rust/day07/src')
| -rw-r--r-- | 2022/rust/day07/src/main.rs | 216 |
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(()) +} |