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
|
#include "aoc.h"
#include <iostream>
#include <algorithm>
namespace aoc2022 {
static dir root{"/"};
// ls
void load(dir* d, line_view lv) {
per_line(lv, [&d](line_view l) {
dir* n = new dir(l);
n->parent = d;
d->dirs.push_back(n);
return true;
});
}
// cd /
void get_root(dir** current) {
*current = &root;
}
// cd ..
void get_parent(dir** current) {
dir* parent = (*current)->parent;
*current = parent;
}
// cd xxxx
void get_dir(dir** current, line_view n) {
dir* d = *current;
for(auto& s : d->dirs) {
if (s->name == n) {
*current = s;
break;
}
}
}
struct dst {
dir* d;
int s;
};
void get_size(dir* d, std::vector<dir*> & dirs, std::vector<dst>& ds, int target) {
int s = d->get_size();
if (d->size == 0) {
ds.push_back({d, s});
}
if (s <= target && d->size == 0) {
// std::cout << d->name << " size is " << s << std::endl;
dirs.push_back(d);
}
for (auto& x: d->dirs) {
get_size(x, dirs, ds, target);
}
}
std::pair<int,int> day7(line_view file) {
dir* current = nullptr;
const char* p = file.line;
while(p < file.line + file.length) {
if (p[0] == '$') {
if (p[2] == 'c' && p[3] == 'd') {
if (p[5] == '/') get_root(¤t);
else if (p[5] == '.') get_parent(¤t);
else {
const char *p0 = p + 5;
while(*p0 != '\n') p0++;
get_dir(¤t, line_view{p + 5, p0});
}
while(*p != '\n') p++;
}
if (p[2] == 'l' && p[3] == 's') {
const char* p0 = p + 5;
while (*p0 != '$') p0++;
load(current, line_view{p + 5, p0});
p = p0 - 1;
}
}
p++;
}
int rootsize = root.get_size();
// printf("root size is %d\n", rootsize);
std::vector<dir*> dirs;
std::vector<dst> ds;
get_size(&root, dirs, ds, 100000);
int total{0};
for(auto& d : dirs) {
total += d->get_size();
}
std::sort(ds.begin(), ds.end(), [](const dst&d1, const dst&d2) {
return d1.s < d2.s;
});
int smallest{0};
for (auto& d: ds) {
int x = 70000000 - rootsize + d.s;
// std::cout << d.d->name << ": " << d.s << " avail: " << x << std::endl;
if ( x >= 30000000) {
smallest = d.s;
break;
}
}
return {total, smallest};
}
}
|
