/*
 * Code pour le problème de syph
 *   énumération des polyamants non-réguliers libres d'ordre N
 *   peut être modifié pour énumérer les polyamants fixes
 *
 *  © 2004 Sam Hocevar <sam@zoy.org>
 *  Use, copy, modify at your will.
 */

#define N 10
//#define REGULAR_LATTICE
//#define LATTICE_ANIMALS
//#define VERBOSE

#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>

/*
 * Our cool data tructures
 */
typedef struct _i
{
    int n;
    uint16_t tri[N];
    uint16_t crc;
}
iamond;
    
typedef struct _l
{
    int n;
    iamond* list;
    int count;
}
list;

/*
 * CRC macros
 */
#define INITCRC 0xffff
#define MAKECRC(x) (((x) + 1) * 0xe73a)

/*
 * Prototypes
 */
static list* list_next_generation(list *gen);

static list* list_new(void);
static int list_has_iamond(list* l, iamond* iam);
static void list_add(list* l, iamond* iam);

static int iamond_has_triangle(iamond* iam, uint16_t tri);
static void iamond_normalise(iamond* iam);
static void iamond_push(iamond* iam);
static int iamond_eq(iamond* i1, iamond* i2);

static void iamond_print(iamond* iam);
static void list_print(list* l);

/*
 * C'est parti mon gros jean-jacques
 */
int main(void)
{
    list *g[N];
    iamond orig;
    int i;

    /* Initialisation: there is one free-1-iamond */
    g[0] = list_new();

    orig.n = 1;
    orig.crc = INITCRC;
    orig.tri[0] = (0 << 8) | 0;
    orig.crc ^= MAKECRC(orig.tri[0]);
    list_add(g[0], &orig);

#ifdef LATTICE_ANIMALS
    orig.n = 1;
    orig.crc = INITCRC;
    orig.tri[0] = (0 << 8) | 1;
    orig.crc ^= MAKECRC(orig.tri[0]);
    list_add(g[0], &orig);
#endif

    list_print(g[0]);

    for(i = 1; i < N; i++)
    {
        g[i] = list_next_generation(g[i-1]);
        list_print(g[i]);
    }

    return 0;
}

/*
 * Iamond lists handling
 */
static list* list_new(void)
{
    list* l = malloc(sizeof(list));
    l->n = 0;
    l->list = malloc(sizeof(iamond));
    l->count = 1;
    return l;
}

static int list_has_iamond(list* l, iamond* iam)
{
    int i;
    iamond tmp;

    for(i = l->n; i--;)
        if(iamond_eq(iam, &l->list[i]))
            return 1;

#ifndef LATTICE_ANIMALS
    tmp.n = iam->n;
    tmp.crc = INITCRC;
    for(i = iam->n; i--;)
    {
        tmp.tri[i] = 0xffff - iam->tri[i];
        /* Optimisation: we are sure the normalisation will do the checksum */
        //tmp.crc ^= MAKECRC(tmp.tri[j]);
    }
    iamond_normalise(&tmp);

    for(i = l->n; i--;)
        if(iamond_eq(&tmp, &l->list[i]))
            return 1;
#endif

    return 0;
}

static void list_add(list* l, iamond* iam)
{
    if(l->n == l->count)
    {
        l->count *= 2;
        l->list = realloc(l->list, (l->count) * sizeof(iamond));
    }
    memcpy(l->list + l->n, iam, sizeof(iamond));
    l->n++;
}

static list* list_next_generation(list *prev)
{
    list* next = list_new();
    int i, j, k;
    uint16_t offset[3];

    offset[0] = 0x0001;
    offset[1] = 0xffff;

    for(i = 0; i < prev->n; i++)
    {
        iamond cur, tmp = prev->list[i];
        iamond_push(&tmp);

        for(j = tmp.n; j--;)
        {
            offset[2] = 0x0101 - 0x0202 * (tmp.tri[j] % 2);

            for(k = 0; k < 3; k++)
            {
                if(!iamond_has_triangle(&tmp, tmp.tri[j] + offset[k]))
                {
                    cur = tmp;
                    cur.tri[cur.n] = tmp.tri[j] + offset[k];
                    cur.crc ^= MAKECRC(tmp.tri[j] + offset[k]);
                    cur.n++;
                    iamond_normalise(&cur);
                    if(!list_has_iamond(next, &cur))
                        list_add(next, &cur);
                }
            }
        }
    }

    return next;
}

/*
 * Iamond handling
 */
static int iamond_has_triangle(iamond* iam, uint16_t tri)
{
    int i;

    for(i = iam->n; i--;)
        if(iam->tri[i] == tri)
            return 1;

    return 0;
}

static void iamond_normalise(iamond* iam)
{
    int i;
    int min_x = 0xff00, min_y = 0xff;

    for(i = iam->n; i--;)
    {
        int x = iam->tri[i] & 0xff00;
        int y = iam->tri[i] & 0xff;
        if(x < min_x) min_x = x;
        if(y < min_y) min_y = y;
    }

    min_y = min_y / 2 * 2;

    if((min_x | min_y) == 0)
        return;

    iam->crc = INITCRC;
    for(i = iam->n; i--;)
    {
        iam->tri[i] -= min_x | min_y;
        iam->crc ^= MAKECRC(iam->tri[i]);
    }
}

static void iamond_push(iamond* iam)
{
    int i;

    iam->crc = INITCRC;
    for(i = iam->n; i--;)
    {
        iam->tri[i] += 0x0102;
        iam->crc ^= (iam->tri[i] + 1) * 0x1e7a;
    }
}

static int iamond_eq(iamond* i1, iamond* i2)
{
    int i, j;

    if(i1->n != i2->n)
        return 0;

    if(i1->crc != i2->crc)
        return 0;

    for(i = i1->n; i--;)
        if(!iamond_has_triangle(i2, i1->tri[i]))
            return 0;

    return 1;
}

/*
 * Print stuff
 */
static void iamond_print(iamond* iam)
{
    int i, j;
    int ymax = 0, xmax = 0, oldr, l, r, d;

    //printf("Checksum %x\n", iam->crc);
    for(i = iam->n; i--;)
    {
        int x = (iam->tri[i] & 0xff00) >> 8;
        int y = iam->tri[i] & 0xff;
        //printf(" (%i,%i)", x, y);
        if(x > xmax) xmax = x;
        if(y > ymax) ymax = y;
    }
    //printf("\n");

    xmax++;
    ymax = ymax / 2 + 1;

    /* First line */
    printf(" ");
    for(i = 0; i < xmax; i++)
    {
        if(iamond_has_triangle(iam, i << 8))
            printf(" __ ");
        else
            printf("    ");
    }
    printf("\n");

    /* Remaining lines, 3 by 3 */
    for(j = 0; j < ymax; j++)
    {
        for(oldr = 0, i = 0; i < xmax; i++, oldr = r)
        {
            l = iamond_has_triangle(iam, (i << 8) | (j * 2 + 1));
            r = iamond_has_triangle(iam, (i << 8) | (j * 2));
            printf((oldr || l) ? "|" : " ");
            printf((l || r) ? "\\  " : "   ");
        }
        printf(oldr ? "|\n" : "\n");

        for(oldr = 0, i = 0; i < xmax; i++, oldr = r)
        {
            int u = iamond_has_triangle(iam, (i << 8) | (j * 2 - 1));
            int nextl = iamond_has_triangle(iam, ((i + 1) << 8) | (j * 2 + 1));
            d = iamond_has_triangle(iam, (i << 8) | (j * 2 + 2));
            l = iamond_has_triangle(iam, (i << 8) | (j * 2 + 1));
            r = iamond_has_triangle(iam, (i << 8) | (j * 2));
            printf((oldr || l) ? "|" : " ");
            printf((oldr && d && r && !l) ? "o" : " ");
            printf((l || r) ? "\\" : " ");
            printf((l && u && nextl && !r) ? "o" : " ");
        }
        printf(oldr ? "|\n" : "\n");

        for(oldr = 0, i = 0; i < xmax; i++, oldr = r)
        {
            l = iamond_has_triangle(iam, (i << 8) | (j * 2 + 1));
            r = iamond_has_triangle(iam, (i << 8) | (j * 2));
            d = iamond_has_triangle(iam, (i << 8) | (j * 2 + 2));
            printf((oldr || l) ? "|" : " ");
            printf(l ? "__" : d ? " _" : "  ");
            printf((l || r) ? "\\" : d ? "_" : " ");
        }
        printf(oldr ? "|\n" : "\n");
    }
}

static void list_print(list* l)
{
    int i;
#ifdef REGULAR_LATTICE
#   define LATTICE ""
#else
#   define LATTICE "irregular-"
#endif

#ifdef LATTICE_ANIMALS
#   define ANIMALS "fixed"
#else
#   define ANIMALS "free"
#endif

    printf("There are %i " ANIMALS " %i-" LATTICE "iamonds.\n",
           l->n, l->n ? l->list[0].n : 0);
#ifdef VERBOSE
    for(i = 0; i < l->n; i++)
    {
        iamond_print(&l->list[i]);
    }
    printf("\n");
#endif
}