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
|
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
typedef struct Dir_ Dir;
typedef struct Dir_ {
char name[32];
int size, dir;
int children;
Dir *parent;
Dir *files[32];
} Dir;
Dir* changeDir(Dir *dir, Dir *root, char *name)
{
printf("cd %s\n", name);
if ( name[0] == '/' ) return root;
if ( name[0] == '.' ) return dir->parent;
for ( int i = 0; i < dir->children; i++ )
{
if(strcmp( dir->files[i]->name, name ) == 0)
{
return dir->files[i];
}
}
}
void list(Dir *dir, int d)
{
for (int i = 0; i < d; i++) printf("'-");
printf("%s", dir->name);
if (dir->dir) printf(" (d)");
else printf(" %d", dir->size);
printf("\n");
for (int i = 0; i < dir->children; i++)
{
list(dir->files[i], d+1);
}
}
int findlarge(Dir *dir, int *globalmin, int *localmin) {
if (!dir->dir) {
return dir->size;
}
int sum = 0;
for (int i = 0; i < dir->children; i++)
{
sum += findlarge(dir->files[i], globalmin, localmin);
}
if (sum >= *globalmin && sum < *localmin) {
*localmin = sum;
}
return sum;
}
int main()
{
char *line = 0;
size_t len;
ssize_t nlen;
Dir *root = malloc(sizeof(Dir));
root->children = 0;
root->dir = 1;
strcpy(root->name, "/");
Dir *head = root;
int globalmin = 0;
int localmin = 70000000;
int rootsize = 0;
while( (nlen = getline(&line, &len, stdin)) != -1 )
{
line[nlen-1] = '\0';
if ( line[0] == '$' )
{
if ( line[2] == 'c' ) head = changeDir(head, root, line+5);
}
else if ( line[0] == 'd' )
{
Dir *newdir = malloc(sizeof(Dir));
strcpy(newdir->name, line+4);
newdir->dir = 1;
newdir->children = 0;
newdir->parent = head;
head->files[head->children] = newdir;
head->children++;
}
else {
Dir *newdir = malloc(sizeof(Dir));
newdir->size = atoi( strsep(&line, " ") );
strcpy(newdir->name, strsep(&line, " "));
head->files[head->children] = newdir;
head->children++;
rootsize += newdir->size;
// printf("file %d %s\n", newdir->size, newdir->name);
// printf("name %s\n", root->files[0]->name);
}
printf("cmd '%s' head: %s\n", line, head->name);
list(root, 0);
}
list(root, 0);
globalmin = 30000000 - (70000000 - rootsize);
findlarge(root, &globalmin, &localmin);
printf("sum: %d\n", localmin);
}
|
