1 files changed, 294 insertions, 0 deletions
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 <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <assert.h>
+#include <limits.h>
+
+#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;
+}