#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;
}