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
123
124
125
126
127
128
129
130
131
132
|
use std::{collections::HashMap};
// Making a recursive data structure in Rust is a pain in the ass.
// So don't bother, just link one way (nodes own their children)
// And we'll separately track our 'current working directory' with a
// vector of keys into the tree
#[derive(Debug)]
struct Node {
children: HashMap<String, Node>,
// Intrinsic size of the file at this location.
size: Option<u32>,
// Is the location a directory. Technically should be able to tell by presence/absence of children, but
// empty directories are a thing.
isdir: bool,
}
impl Node {
fn new(isdir: bool) -> Node {
Node {
children: HashMap::new(),
size: None,
isdir: isdir,
}
}
fn set(&mut self, path: &Vec<&str>, size: Option<u32>, isdir: bool) {
let mut cn = self;
for ch in path {
cn = cn.children.entry((*ch).to_owned()).or_insert(Node::new(true));
}
cn.size = size;
cn.isdir = isdir;
}
/**
* Returns a map of total, recursive directory sizes,by relative path from the current directory
* Empty string key is the current directory size
*/
fn dir_sizes(self) -> HashMap<String, u32> {
let mut res: HashMap<String, u32> = HashMap::new();
let mut mysize: u32 = 0;
for (name, nn) in self.children {
if let Some(fz) = nn.size {
// It's a file, just add the size
mysize += fz;
} else {
// It's a directory, add the size _and_ all the entries with subdir prefixed
let child_ds = nn.dir_sizes();
let child_sz = child_ds[""];
mysize += child_sz;
for (cn, sz) in child_ds {
res.insert(format!("{}/{}", name, cn), sz);
}
}
}
res.insert("".to_owned(), mysize);
res
}
}
pub fn run(input: String) {
let mut root = Node::new(true);
let mut cwd: Vec<&str>= vec![];
let lines: Vec<&str> = input.lines().collect();
let mut i = 0;
loop {
if i >= lines.len() {
break;
}
let line = lines[i];
let toks: Vec<&str> = line.split_whitespace().collect();
if toks[0] != "$" {
panic!("expected a command, got {}",line);
}
match toks[1] {
"cd" => {
i += 1;
let dirname = toks[2];
if dirname == "/" {
cwd.clear();
} else if dirname == ".." {
cwd.pop();
} else {
cwd.push(dirname);
}
root.set(&cwd, None, true);
}
"ls" => {
i += 1;
loop {
if i >= lines.len() {
break;
}
let lsline = lines[i];
let lstoks: Vec<&str> = lsline.split_whitespace().collect();
if lstoks[0] == "$" {
// This is the next command, loop back to the top without incrementing!
break;
}
let (fsize, isdir) = if lstoks[0] == "dir" {
(None, true)
} else {
(Some(lstoks[0].parse().expect("filesize wasn't a u32!")), false)
};
let fname = lstoks[1];
cwd.push(fname);
root.set(&cwd, fsize, isdir);
cwd.pop();
i += 1;
}
}
cmd => {
panic!("unknown command {}", cmd)
}
}
}
let ds = root.dir_sizes();
// let mut tot: u32 = 0;
// for (_, sz) in ds {
// if sz <= 100000 {
// tot += sz;
// }
// }
// println!("Day 7: {}", tot);
let fs_size:u32 = 70000000;
let total_used = ds.get("").unwrap();
let total_free = fs_size - total_used;
let update_size:u32 = 30000000;
let need_to_free = update_size - total_free;
let ddsz = ds.values()
.filter(|sz| { **sz >= need_to_free })
.fold(fs_size, |acc, e| { acc.min(*e) });
println!("Day 7: {}", ddsz);
}
|
