1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
|
use std::collections::HashMap;
fn main() {
let input = lib::read_input(7);
part1(&input);
part2(&input);
}
fn part1(input: &str) {
let fs = parse(input);
let ans: u32 = fs
.iter()
.enumerate()
.filter(|(_, f)| matches!(f, Node::Dir { .. }))
.map(|(i, _)| get_size(&fs, i))
.filter(|&s| s <= 100_000)
.sum();
println!("{}", ans);
}
fn part2(input: &str) {
let fs = parse(input);
let used = get_size(&fs, 0);
let free = 70_000_000 - used;
let to_free = 30_000_000 - free;
let ans = fs
.iter()
.enumerate()
.flat_map(|(i, f)| match f {
Node::Dir { .. } => Some(get_size(&fs, i)),
_ => None,
})
.filter(|&s| s >= to_free)
.min_by_key(|&s| s)
.unwrap();
println!("{:?}", ans);
}
fn get_size<'a>(fs: &Vec<Node<'a>>, index: usize) -> u32 {
match &fs[index] {
Node::Dir { contents, .. } => contents.values().map(|&i| get_size(fs, i)).sum::<u32>(),
&Node::File { size, .. } => size,
}
}
#[derive(Debug)]
enum Node<'a> {
Dir {
parent: usize,
contents: HashMap<&'a str, usize>,
name: &'a str,
},
File {
size: u32,
name: &'a str,
},
}
impl<'a> Node<'a> {
fn parent(&self) -> usize {
match self {
Node::Dir { parent, .. } => *parent,
Node::File { .. } => panic!("File has no parent"),
}
}
fn contents(&mut self) -> &mut HashMap<&'a str, usize> {
match self {
Node::Dir { contents, .. } => contents,
Node::File { .. } => panic!("File has no contents"),
}
}
}
fn parse<'a>(input: &'a str) -> Vec<Node<'a>> {
let mut dirs = vec![Node::Dir {
parent: 0,
contents: HashMap::new(),
name: "/",
}];
let mut curr = 0;
for line in input.lines() {
let s = line.split_whitespace().collect::<Vec<_>>();
if s[0] == "$" {
match s[1] {
"cd" => {
if s[2] == "/" {
curr = 0;
} else if s[2] == ".." {
curr = dirs[curr].parent();
} else {
curr = dirs[curr].contents()[s[2]];
}
}
_ => {}
}
} else if s[0] == "dir" {
let name = s[1];
let node = Node::Dir {
parent: curr,
contents: HashMap::new(),
name,
};
let idx = dirs.len();
dirs.push(node);
dirs[curr].contents().insert(name, idx);
} else {
let size = s[0].parse().unwrap();
let name = s[1];
let node = Node::File { size, name };
let idx = dirs.len();
dirs.push(node);
dirs[curr].contents().insert(name, idx);
}
}
dirs
}
|
