aoc

advent of code
git clone git://source.orangerot.dev:/aoc.git
Log | Files | Refs

main2.c (2682B)

      1 #include <stdlib.h>
      2 #include <stdio.h>
      3 #include <string.h>
      4 
      5 typedef struct Dir_ Dir;
      6 
      7 typedef struct Dir_ {
      8     char name[32];
      9     int size, dir;
     10     int children;
     11     Dir *parent;
     12     Dir *files[32];
     13 } Dir;
     14 
     15 Dir* changeDir(Dir *dir, Dir *root, char *name)
     16 {
     17     printf("cd %s\n", name);
     18     if ( name[0] == '/' ) return root;
     19     if ( name[0] == '.' ) return dir->parent;
     20 
     21     for ( int i = 0; i < dir->children; i++ )
     22     {
     23         if(strcmp( dir->files[i]->name, name ) == 0)
     24         {
     25             return dir->files[i];
     26         }
     27     }
     28 }
     29 
     30 void list(Dir *dir, int d)
     31 {
     32     for (int i = 0; i < d; i++) printf("'-");
     33     printf("%s", dir->name);
     34     if (dir->dir) printf(" (d)");
     35     else printf(" %d", dir->size);
     36     printf("\n");
     37     for (int i = 0; i < dir->children; i++)
     38     {
     39         list(dir->files[i], d+1);
     40     }
     41 }
     42 
     43 int findlarge(Dir *dir, int *globalmin, int *localmin) {
     44     
     45     if (!dir->dir) {
     46         return dir->size;
     47     }
     48 
     49     int sum = 0;
     50     for (int i = 0; i < dir->children; i++)
     51     {
     52         sum += findlarge(dir->files[i], globalmin, localmin);
     53     }
     54     if (sum >= *globalmin && sum < *localmin) {
     55         *localmin = sum;
     56     }
     57 
     58     return sum;
     59 }
     60 
     61 int main()
     62 {
     63 
     64     char *line = 0;
     65     size_t len;
     66     ssize_t nlen;
     67 
     68     Dir *root = malloc(sizeof(Dir));
     69     root->children = 0;
     70     root->dir = 1;
     71     strcpy(root->name, "/");
     72     Dir *head = root;
     73     
     74     int globalmin = 0;
     75     int localmin = 70000000;
     76     
     77     int rootsize = 0;
     78 
     79     while( (nlen = getline(&line, &len, stdin)) != -1 )
     80     {
     81         line[nlen-1] = '\0';
     82         if ( line[0] == '$' )
     83         {
     84             if ( line[2] == 'c' ) head = changeDir(head, root, line+5);
     85         }
     86         else if ( line[0] == 'd' ) 
     87         {
     88             Dir *newdir = malloc(sizeof(Dir));
     89             strcpy(newdir->name, line+4);
     90             newdir->dir = 1;
     91             newdir->children = 0;
     92             newdir->parent = head;
     93             head->files[head->children] = newdir;
     94             head->children++;
     95         }
     96         else {
     97             Dir *newdir = malloc(sizeof(Dir));
     98             newdir->size = atoi( strsep(&line, " ") );    
     99             strcpy(newdir->name, strsep(&line, " "));
    100             head->files[head->children] = newdir;
    101             head->children++;
    102 
    103             rootsize += newdir->size;
    104             
    105             // printf("file %d %s\n", newdir->size, newdir->name);
    106             // printf("name %s\n", root->files[0]->name);
    107         }
    108         printf("cmd '%s' head: %s\n", line, head->name);
    109         list(root, 0);
    110     }
    111     
    112     list(root, 0);
    113 
    114     globalmin = 30000000 - (70000000 - rootsize);
    115 
    116     findlarge(root, &globalmin, &localmin);
    117     printf("sum: %d\n", localmin);
    118 }