hydra.c (Kirby-Paris Hydras)

#include "ggy.h"

struct hydra {
        int children_count;
        struct hydra **children;
        struct hydra *parent;
};

struct hydra *duplicate_hydra(struct hydra *hydra)
{
        int i;
        struct hydra dup;

        dup.children_count = hydra->children_count;
        dup.parent = hydra->parent;

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

        return &dup;
}

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

        if (parent->children_count == 1) {
                parent->children_cound = 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;
        }

}

int solve_hydra(struct hydra *hydra, int n)
{
        struct hydra *parent = hydra->parent;
        struct hydra *pparent = parent->parent;

        if (hydra->children) {
                unlink_hydra(hydra);

                if (pparent == NULL) {
                        return n + 1;
                }

                int i;
                for (i = n ; i ; i--) {
                        pparent->children_count++;
                        pparent->children[pparent->children_count - 1] = duplicate_hydra(parent);
                }
        }
        else {
                return solve_hydra(hydra->children[hydra->children_count - 1], n + 1);
        }
}

int Hydra(int x)
{
        int i;
        struct hydra *tmp[x];

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

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

                tmp[i] = &hydra;

                if (i > 0) {
                        tmp[i - 1]->children = &hydra;
                }

        }

        return solve_hydra(tmp[0], 1);
}