Hydra Games

#include "ggy.h"

#define LABEL_OMEGA (-1)

struct labelled_hydra {
    int children_count;
    struct labelled_hydra **children;
    struct labelled_hydra *parent;
    int label;
    struct labelled_hydra *aarex;
    int n;
};

struct labelled_hydra *duplicate_labelled_hydra(struct labelled_hydra *hydra)
{
    int i;
    struct labelled_hydra *dup = malloc(sizeof(struct labelled_hydra));

    dup->children_count = hydra->children_count;
    dup->parent = hydra->parent;
    dup->label = hydra->label;
    dup->aarex = hydra->aarex;

    for (i = 0 ; i < dup->children_count ; dup->children[i] = duplicate_labelled_hydra(hydra->children[i]));

    return dup;
}

void unlink_labelled_hydra(struct labelled_hydra *hydra)
{
    int i, j;
    struct labelled_hydra *parent = hydra->parent;

    if (parent->children_count == 1) {
        parent->children_count = 0;
        parent->children = NULL;
    }
    else {
        for (i = 0 ; i < parent->children_count && parent->children[i] != hydra ; i++);
        for (j = i + 1 ; j < parent->children_count ; parent->children[j - 1] = parent->children[i]);

        parent->children_count--;
        parent->children[parent->children_count] = NULL;
    }
}

struct labelled_hydra *solve_labelled_hydra(struct labelled_hydra *hydra, int n, int only_one_step)
{
    if (hydra->children) {
        return solve_labelled_hydra(hydra->children[hydra->children_count - 1], n + 1, only_one_step);
    }
    if (!hydra->parent) {
        hydra->n = n+1;
        return hydra;
    }
    if (hydra->label == 0) {
        if (hydra->aarex) {
            if (!hydra->aarex->children) {
                hydra->aarex = NULL;
                hydra->label = hydra->aarex->n;
            }
            else {
                hydra->label = LABEL_OMEGA;
                solve_labelled_hydra(hydra->aarex, n + 1, 1);
            }
        }
        struct labelled_hydra *parent = hydra->parent;
        struct labelled_hydra *pparent = parent->parent;

        unlink_labelled_hydra(hydra);

        if (pparent == NULL) {
            if (only_one_step) {
                return hydra->parent;
            }
            return solve_labelled_hydra(parent, n+1, 0);
        }

        int i;
        for (i = n ; i ; i--) {
            pparent->children_count++;
            pparent->children[pparent->children_count - 1] = duplicate_labelled_hydra(parent);
        }

        if (only_one_step) {
            return hydra->parent;
        }
        return solve_labelled_hydra(pparent, n+1, 0);
    }
    else {
        if (hydra->label == LABEL_OMEGA) {
            hydra->label = n+1;
        }

        hydra->label--;

        struct labelled_hydra *tmp = hydra->parent;

        while (tmp && tmp->label > hydra->label) {
            tmp = tmp->parent;
        }

        int tmplabel = tmp->label;

        tmp->label = hydra->label;
        hydra->label = 0;
        hydra->parent->children[hydra->parent->children_count - 1] = duplicate_labelled_hydra(tmp);
        tmp->label = tmplabel;

        if (only_one_step) {
            return hydra->parent;
        }

        return solve_labelled_hydra(hydra->parent, n+1, 0);
    }
}

int KirbyParisHydra(int x)
{
    int i;
    struct labelled_hydra *tmp[x];

    for (i = 0 ; i < x ; i++) {
        struct labelled_hydra hydra;

        hydra.children_count = 1;
        hydra.children = NULL;
        hydra.parent = (i > 0 ? tmp[i - 1] : NULL);

        hydra.label = 0;
        hydra.aarex = NULL;
        hydra.n = 0;

        tmp[i] = &hydra;

        if (i > 0) {
#ifdef NO_MAGIC
            tmp[i - 1]->children = malloc(sizeof(struct labelled_hydra *));
#else // NO_MAGIC
            tmp[i - 1]->children = magic_malloc_2();
#endif // NO_MAGIC
            tmp[i - 1]->children[0] = &hydra;
        }
    }

    return solve_labelled_hydra(tmp[0], 1, 0)->n;
}

int WeakBuchholzHydra(int x)
{
    int i;
    struct labelled_hydra *tmp[x];

    for (i = 0 ; i < x ; i++) {
        struct labelled_hydra hydra;

        hydra.children_count = 1;
        hydra.children = NULL;
        hydra.parent = (i > 0 ? tmp[i - 1] : NULL);

        if (i <= 1) {
            hydra.label = 0;
        }
        else {
            hydra.label = i;
        }
        hydra.aarex = NULL;
        hydra.n = 0;

        tmp[i] = &hydra;

        if (i > 0) {
#ifdef NO_MAGIC
            tmp[i - 1]->children = malloc(sizeof(struct labelled_hydra *));
#else // NO_MAGIC
            tmp[i - 1]->children = magic_malloc_2();
#endif // NO_MAGIC
            tmp[i - 1]->children[0] = &hydra;
        }
    }

    return solve_labelled_hydra(tmp[0], 1, 0)->n;
}

int BuchholzHydra(int x)
{
    int i;
    struct labelled_hydra *tmp[x];

    for (i = 0 ; i < x ; i++) {
        struct labelled_hydra hydra;

        hydra.children_count = 1;
        hydra.children = NULL;
        hydra.parent = (i > 0 ? tmp[i - 1] : NULL);

        if (i <= 1) {
            hydra.label = 0;
        }
        else {
            hydra.label = LABEL_OMEGA;
        }
        hydra.aarex = NULL;
        hydra.n = 0;

        tmp[i] = &hydra;

        if (i > 0) {
#ifdef NO_MAGIC
            tmp[i - 1]->children = malloc(sizeof(struct labelled_hydra *));
#else // NO_MAGIC
            tmp[i - 1]->children = magic_malloc_2();
#endif // NO_MAGIC
            tmp[i - 1]->children[0] = &hydra;
        }
    }

    return solve_labelled_hydra(tmp[0], 1, 0)->n;
}

int ModifiedAarexHydra(int x) {
    int i;
    struct labelled_hydra *tmp[x];

    for (i = 0 ; i < x ; i++) {
        struct labelled_hydra hydra;

        hydra.children_count = 1;
        hydra.children = NULL;
        hydra.parent = (i > 0 ? tmp[i - 1] : NULL);

        if (i <= 1) {
            hydra.label = 0;
        }
        else {
            hydra.label = LABEL_OMEGA;
            hydra.aarex = duplicate_labelled_hydra(tmp[0]);
        }

        hydra.n = 0;

        tmp[i] = &hydra;

        if (i > 0) {
#ifdef NO_MAGIC
            tmp[i - 1]->children = malloc(sizeof(struct labelled_hydra *));
#else // NO_MAGIC
            tmp[i - 1]->children = magic_malloc_2();
#endif // NO_MAGIC
            tmp[i - 1]->children[0] = &hydra;
        }
    }
    return solve_labelled_hydra(tmp[0], 1, 0)->n;
}