advent-of-code

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define CUTOFF_SIZE 100000

struct dir {
    char  *name;
    size_t total_size;   /* size of all files in or below dir */
    size_t n_files;      /* number of files */
    struct file *files;  /* array of files */
    size_t n_dirs;       /* number of dirs */
    struct dir **dirs;   /* pointers to dirs */
    struct dir *parent;  /* parent; NULL for "/" */
};

struct file {
    char *name;
    size_t size;
};

/* parent may be NULL, in which case we create the top level dir, and name should be "/". */
struct dir *
add_dir_to_dir(struct dir *parent, char *name) {
    /* first check for an existing dir called name in parent */
    if (parent != NULL) {
        for (size_t i = 0; i < parent->n_dirs; i++) {
            if (strcmp(parent->dirs[i]->name, name) == 0)
                return parent->dirs[i];
        }
    }
    struct dir *d = malloc(sizeof(struct dir));
    if (d == NULL) {
        perror("malloc");
        return NULL;
    }
    d->name = strdup(name);
    if (d->name == NULL) {
        perror("strdup");
        free(d);
        return NULL;
    }
    d->total_size = 0;
    d->n_files = 0;
    d->files = NULL;
    d->n_dirs = 0;
    d->dirs = NULL;
    d->parent = parent;

    if (parent != NULL) {
        struct dir **tmp = realloc(parent->dirs, sizeof(struct dir *) * (parent->n_dirs + 1));
        if (tmp == NULL) {
            perror("realloc");
            free(d->name);
            free(d);
            return NULL;
        }
        tmp[parent->n_dirs] = d;
        parent->n_dirs++;
        parent->dirs = tmp;
    }

    return d;
}

int
add_file_to_dir(struct dir *d, char *name, size_t size) {
    if (d == NULL) {
        fprintf(stderr, "the given directory entry does not exist, create first\n");
        return -1;
    }
    struct file *tmp = realloc(d->files, sizeof(struct file) * (d->n_files + 1));
    if (tmp == NULL) {
        perror("realloc");
        return -1;
    }

    size_t n_files = d->n_files;
    tmp[n_files].size = size;
    tmp[n_files].name = strdup(name);
    if (tmp[n_files].name == NULL) {
        perror("strdup");
        free(tmp);
        return -1;
    }
    d->files = tmp;
    d->n_files++;
    d->total_size += size;
    
    for (struct dir *p = d->parent; p != NULL; p = p->parent)
        p->total_size += size;
    return 0;
}

void
destroy_dir_recurse(struct dir *d) {
    if (d == NULL)
        return;
    free(d->name);
    for (size_t i = 0; i < d->n_files; i++)
        free(d->files[i].name);
    free(d->files);
    for (size_t i = 0; i < d->n_dirs; i++)
        destroy_dir_recurse(d->dirs[i]);
    free(d->dirs);
    free(d);
}

void
print_dir_sizes_recurse(struct dir *d) {
    if (d == NULL)
        return;
    printf("%lu %s\n", d->total_size, d->name);
    for (size_t i = 0; i < d->n_dirs; i++)
        print_dir_sizes_recurse(d->dirs[i]);
}

size_t
find_total_sizes_recurse(struct dir *d) {
    size_t total = 0;
    if (d == NULL)
        return 0;
    for (size_t i = 0; i < d->n_dirs; i++) {
        total += find_total_sizes_recurse(d->dirs[i]);
    }
    if (d->total_size <= CUTOFF_SIZE)
        total += d->total_size;
    return total;
}

size_t
find_smallest_at_least_recurse(struct dir *d, size_t s) {
    size_t min = 70000000;
    if (d == NULL)
        return min;
    for (size_t i = 0; i < d->n_dirs; i++) {
        size_t x = find_smallest_at_least_recurse(d->dirs[i], s);
        if (x < min)
            min = x;
    }
    if (d->total_size >= s && d->total_size < min)
        min = d->total_size;
    return min;
}

int
main(int argc, char **argv) {
    char *buf = NULL;
    size_t buflen = 0;
    ssize_t n;
    FILE *f;

    if (argc != 2) {
        fprintf(stderr, "usage: %s input\n", argv[0]);
        return 1;
    }

    f = fopen(argv[1], "r");
    if (f == NULL) {
        perror(argv[1]);
        return 1;
    }

    struct dir *top, *cwd, *tmp;
    top = cwd = tmp = NULL;
    int reading_ls = 0;

    while ((n = getline(&buf, &buflen, f)) != -1) {
        char *tmpname = NULL;
        if (buf[n - 1] == '\n') {
            buf[n - 1] = '\0';
            n--;
        }

        if (buf[0] == '$') {
            reading_ls = 0;
            /* command: cd DIR or ls */
            if (buf[2] == 'c') {
                /* $ cd DIR... */
                tmpname = &buf[5];
                if (strcmp(tmpname, "..") == 0) {
                    if (cwd->parent != NULL) /* don't go above top */
                        cwd = cwd->parent;
                    continue;
                }

                tmp = add_dir_to_dir(cwd, tmpname);
                if (tmp == NULL) {
                    destroy_dir_recurse(top);
                    free(buf);
                    fclose(f);
                    return 1;
                }
                if (cwd == NULL)
                    top = tmp;
                cwd = tmp;
            } else {
                /* ls */
                assert(buf[2] == 'l');
                reading_ls = 1;
            }
        } else {
            /* reading output of ls */
            assert(reading_ls == 1);
            size_t size = 0;
            char *x = strchr(buf, ' ');
            if (x == NULL) {
                fprintf(stderr, "no space found in line \"%s\"\n", buf);
                destroy_dir_recurse(top);
                free(buf);
                fclose(f);
                return 1;
            }
            tmpname = x + 1;
            if (buf[0] == 'd') {
                /* dir DIRNAME */
                add_dir_to_dir(cwd, tmpname);
            } else {
                sscanf(buf, "%lu ", &size);
                add_file_to_dir(cwd, tmpname, size);
            }
        }
    }

    printf("Part A: %lu\n", find_total_sizes_recurse(top));

    size_t need_to_free = top->total_size - 40000000;
    printf("Part B: %lu\n", find_smallest_at_least_recurse(top, need_to_free));

    destroy_dir_recurse(top);
    free(buf);
    fclose(f);

    return 0;
}