main.rs (2613B)
1 use regex::Regex;
2 use std::collections::HashMap;
3 use std::path::PathBuf;
4
5 #[derive(Debug)]
6 enum Node {
7 Dir,
8 File { size: usize },
9 }
10
11 fn main() {
12 let input = {
13 let mut tmp = HashMap::new();
14 let mut root = PathBuf::new();
15 for l in std::fs::read_to_string("input.txt")
16 .unwrap()
17 .trim()
18 .split('\n')
19 {
20 if Regex::new(r"^\$ cd ..$").unwrap().is_match(l) {
21 root.pop();
22 } else if let Some(cap) = Regex::new(r"^\$ cd (?P<dir_name>.*)$").unwrap().captures(l) {
23 root.push(cap.name("dir_name").unwrap().as_str());
24 tmp.insert(root.clone(), Node::Dir);
25 } else if let Some(cap) = Regex::new(r"^(?P<size>[0-9]+) (?P<file_name>.*)$")
26 .unwrap()
27 .captures(l)
28 {
29 root.push(cap.name("file_name").unwrap().as_str());
30 tmp.insert(
31 root.clone(),
32 Node::File {
33 size: cap.name("size").unwrap().as_str().parse().unwrap(),
34 },
35 );
36 root.pop();
37 } else if let Some(cap) = Regex::new(r"^dir (?P<dir_name>.*)$").unwrap().captures(l) {
38 root.push(cap.name("dir_name").unwrap().as_str());
39 tmp.insert(root.clone(), Node::Dir);
40 root.pop();
41 } else if Regex::new(r"^\$ ls$").unwrap().is_match(l) {
42 } else {
43 unreachable!();
44 }
45 }
46 tmp
47 };
48 let dir_sizes = {
49 let mut tmp = HashMap::new();
50 for (path, node) in input.iter() {
51 let mut path = path.clone();
52 if let Node::File { size } = node {
53 while path.pop() {
54 tmp.insert(path.clone(), *tmp.get(&path).unwrap_or(&0) + size);
55 }
56 }
57 }
58 tmp
59 };
60 // 1307902
61 println!("Part 1: {}", part_1(&dir_sizes, 100000));
62 // 7068748
63 println!("Part 2: {}", part_2(&dir_sizes, 70000000, 30000000));
64 }
65
66 fn part_1(dir_sizes: &HashMap<PathBuf, usize>, size_thresh: usize) -> usize {
67 dir_sizes
68 .values()
69 .filter(|&size| *size <= size_thresh)
70 .sum()
71 }
72
73 fn part_2(
74 dir_sizes: &HashMap<PathBuf, usize>,
75 tot_space: usize,
76 required_free_space: usize,
77 ) -> usize {
78 let used_space = dir_sizes.get(&PathBuf::from("/")).unwrap();
79 *dir_sizes
80 .values()
81 .filter(|&size| tot_space - used_space + *size >= required_free_space)
82 .min()
83 .unwrap()
84 }