#include <stdio.h>

#include <glib.h>

struct action {
    int id;
    GPtrArray *depends;
    GPtrArray *required_by;
};

void free_action(gpointer data)
{
    struct action *action = (struct action *)data;
    g_ptr_array_free(action->depends, TRUE);
    g_ptr_array_free(action->required_by, TRUE);
    g_free(action);
}

struct action *get_action(GHashTable *table, int id)
{
    struct action *action = g_hash_table_lookup(table, GINT_TO_POINTER(id));
    if (action) return action;

    action = g_malloc(sizeof(struct action));
    action->depends = g_ptr_array_new();
    action->required_by = g_ptr_array_new();
    action->id = id;
    g_hash_table_insert(table, GINT_TO_POINTER(id), action);
    return action;
}

gint compare_action(gconstpointer _a, gconstpointer _b)
{
    struct action *a = *(struct action **)_a;
    struct action *b = *(struct action **)_b;
    return a->id - b->id;
}

GHashTable *parse_tree(const char *fname)
{
    FILE *f = fopen(fname, "r");
    if (!f) {
        perror(fname);
        return NULL;
    }

    GHashTable *table = g_hash_table_new_full(NULL, NULL, NULL, free_action);

    char *line = NULL;
    size_t line_len = 0;
    while (getline(&line, &line_len, f) != -1) {
        char depends = 0;
        char required_by = 0;
        sscanf(line, "Step %c must be finished before step %c can begin.",
                &depends, &required_by);

        struct action *dependent = get_action(table, depends);
        struct action *required = get_action(table, required_by);

        g_ptr_array_add(dependent->required_by, required);
        g_ptr_array_add(required->depends, dependent);
    }

    free(line);
    fclose(f);
    return table;
}

int main()

{
    GHashTable *table = parse_tree("input");
    if (!table) return 1;

    GPtrArray *queue = g_ptr_array_new();
    GString *result = g_string_new(NULL);

    // Find items without dependencies
    GHashTableIter iter;
    gpointer key, value;
    g_hash_table_iter_init(&iter, table);
    while (g_hash_table_iter_next(&iter, &key, &value)) {
        struct action *action = (struct action *)value;
        if (action->depends->len == 0) {
            g_ptr_array_add(queue, action);
        }
    }

    while (queue->len) {
        g_ptr_array_sort(queue, compare_action);

        struct action *action = g_ptr_array_remove_index_fast(queue, 0);
        g_string_append_c(result, action->id);
        for (unsigned i = 0; i < action->required_by->len; i++) {
            struct action *next = g_ptr_array_index(action->required_by, i);
            g_ptr_array_remove_fast(next->depends, action);
            if (next->depends->len == 0) g_ptr_array_add(queue, next);
        }
    }

    puts(result->str);

    g_string_free(result, TRUE);
    g_ptr_array_free(queue, TRUE);
    g_hash_table_destroy(table);
    return 0;
}