From c5a8824311e7c814f58593f43b0528505756f46a Mon Sep 17 00:00:00 2001 From: kartofen Date: Wed, 7 Dec 2022 22:21:42 +0200 Subject: day 7 --- Advent-of-Code-2022/aoc-7/main.c | 294 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 294 insertions(+) create mode 100644 Advent-of-Code-2022/aoc-7/main.c (limited to 'Advent-of-Code-2022/aoc-7/main.c') diff --git a/Advent-of-Code-2022/aoc-7/main.c b/Advent-of-Code-2022/aoc-7/main.c new file mode 100644 index 0000000..870f9d1 --- /dev/null +++ b/Advent-of-Code-2022/aoc-7/main.c @@ -0,0 +1,294 @@ +#include +#include +#include +#include +#include + +#if 0 + #define PART() part1(root) + #define TARGET_SIZE 100000 +#else + #define PART() sz = INT_MAX; part2(root, total_size(root)) + #define FILESYSTEM_SIZE 70000000 + #define TARGET_SIZE 30000000 +#endif + +#if 0 + #define FILENAME "sample.txt" +#else + #define FILENAME "input.txt" +#endif + +#define MIN(x, y) (((x) < (y)) ? (x) : (y)) + +#define INDENT_INC 2 +#define ENTRIES_CAP 256 + +typedef enum { + DIR, + FIL, + LINK, +} type; + +typedef struct node node; + +node *create_node(type t, char *name, size_t sz); +void insert_node(node *parent, node* child); +node *get_dir(node *parent, char *name); +void free_tree(node *n); +void print_tree(node *n, int indent); +size_t total_size(node *n); + +size_t part1(node *n); +size_t part2(node *n, size_t total); + +node *root; +node *cur; + +size_t sz = 0; + +void parse() +{ + FILE *fp = fopen(FILENAME, "r"); + if(!fp) { + fprintf(stderr, "ERROR: Could not open file: %s\n", FILENAME); + exit(1); + } + + char line[256]; + while(fgets(line, sizeof(line), fp)) + { + size_t len = strlen(line); + if(line[len-1] == '\n') line[len-1] = '\0'; + + char *tok0 = strtok(line, " "); + char *tok1 = strtok(NULL, " "); + char *tok2 = strtok(NULL, " "); + + if(tok0[0] == '$') + { + if(strcmp(tok1, "cd") != 0) continue; + + if(tok2[0] == '/') cur = root; + else cur = get_dir(cur, tok2); + + continue; + } + + if(strcmp(tok0, "dir") == 0) + insert_node(cur, create_node(DIR, tok1, 0)); + else + insert_node(cur, create_node(FIL, tok1, atoi(tok0))); + } + + fclose(fp); +} + +int main(void) +{ + root = create_node(DIR, "/", 0); + parse(); + + PART(); + print_tree(root, 0); + printf("%ld\n", sz); + + free_tree(root); + return 0; +} + +/// ------- Definitions ------- /// + +struct _dir { + size_t entries_sz; + struct node *entries[ENTRIES_CAP]; +}; + +struct _file { + size_t sz; +}; + +struct _link { + struct node *to; +}; + +struct node { + type t; + char name[16]; + union { + struct _dir dir; + struct _file file; + struct _link link; + }; +}; + +node *_create_dot(node *n) +{ + node* dot = create_node(LINK, ".", 0); + dot->link.to = n; + return dot; +} + +node *_create_dotdot(node *p) +{ + node *dotdot = create_node(LINK, "..", 0); + dotdot->link.to = p; + return dotdot; +} + +node *create_node(type t, char *name, size_t sz) +{ + node *n = malloc(sizeof(node)); + n->t = t; + strncpy(n->name, name, 16); + + switch(t) { + case DIR: + n->dir.entries_sz = 0; + break; + case FIL: + n->file.sz = sz; + break; + case LINK: + n->link.to = NULL; + break; + } + + return n; +} + +void insert_node(node *parent, node* child) +{ + assert(parent->t == DIR); + assert(parent->dir.entries_sz < ENTRIES_CAP); + + if(child->t == DIR) { + insert_node(child, _create_dot(child)); + insert_node(child, _create_dotdot(parent)); + } + parent->dir.entries[parent->dir.entries_sz++] = child; +} + +node *get_dir(node *parent, char *name) +{ + assert(parent->t == DIR); + struct _dir dir = parent->dir; + + for(int i = 0; i < dir.entries_sz; i++) + { + node *e = dir.entries[i]; + + if(strcmp(e->name, name) == 0) { + if(e->t == DIR) + return e; + else if(e->t == LINK) + return e->link.to; + } + } + + assert("No entries found" && 0); +} + +void free_tree(node *n) +{ + assert(n->t == DIR); + struct _dir dir = n->dir; + + for(int i = 0; i < dir.entries_sz; i++) + { + node *e = dir.entries[i]; + + switch(e->t) { + case DIR: + free_tree(e); + break; + case FIL: + free(e); + break; + case LINK: + free(e); + break; + } + } + + free(n); +} + +void print_tree(node *n, int indent) +{ + for(int i = 0; i < indent; i++) + printf(" "); + printf("- "); + + switch(n->t) { + case DIR: + printf("%s (dir)\n", n->name); + for(int i = 0; i < n->dir.entries_sz; i++) + print_tree(n->dir.entries[i], indent + INDENT_INC); + break; + case FIL: + printf("%s (file, size=%ld)\n", n->name, n->file.sz); + break; + case LINK: + printf("%s (link)\n", n->name); + break; + } +} + +size_t total_size(node *n) +{ + size_t s = 0; + + switch(n->t) { + case DIR: + for(int i = 0; i < n->dir.entries_sz; i++) + s += part1(n->dir.entries[i]); + break; + case FIL: + return n->file.sz; + case LINK: + return 0; + } + + return s; +} + +size_t part1(node *n) +{ + size_t s = 0; + + switch(n->t) { + case DIR: + for(int i = 0; i < n->dir.entries_sz; i++) + s += part1(n->dir.entries[i]); + break; + case FIL: + return n->file.sz; + case LINK: + return 0; + } + + if(s <= TARGET_SIZE) sz += s; + return s; +} + +size_t part2(node *n, size_t total) +{ + size_t s = 0; + + switch(n->t) { + case DIR: + for(int i = 0; i < n->dir.entries_sz; i++) + s += part2(n->dir.entries[i], total); + break; + case FIL: + return n->file.sz; + case LINK: + return 0; + } + + if((FILESYSTEM_SIZE - total) + s >= TARGET_SIZE) + sz = MIN(sz, s); + + return s; +} -- cgit v1.2.3