/* Generated animated GIFs? */
#define USE_GD 1

/* Only check for perfect games? */
#define PERFECT 0

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

#ifdef USE_GD
#include <gd.h>
#endif

/*         0
 *        1  2
 *      3  4  5
 *     6  7  8  9
 *   10 11 12 13 14    */

/* We define a move by its start, intermediary and end positions */
struct m {
    uint8_t from, jump, to;
};

/* List of valid moves. We only define half of them because the 18 other
 * are just mirrors of the first ones. */
struct m moves[36] = {
    { 3, 1, 0 }, { 6, 3, 1 }, { 7, 4, 2 }, { 10, 6, 3 }, { 11, 7, 4 }, { 12, 8, 5 },
    { 3, 4, 5 }, { 6, 7, 8 }, { 7, 8, 9 }, { 10, 11, 12 }, { 11, 12, 13 }, { 12, 13, 14 },
    { 0, 2, 5 }, { 1, 4, 8 }, { 3, 7, 12 }, { 2, 5, 9 }, { 4, 8, 13 }, { 5, 9, 14 }
};

#ifdef USE_GD
/* Cell coordinates in a [200, 160] picture */
int coords[15][2] = {
    { 100, 20 },
    { 80, 50 },  { 120, 50 },
    { 60, 80 },  { 100, 80 }, { 140, 80 },
    { 40, 110 }, { 80, 110 }, { 120, 110 }, { 160, 110 },
    { 20, 140 }, { 60, 140 }, { 100, 140 }, { 140, 140 }, { 180, 140 }
};
#endif

/* The removed cell */
int removed = 0;

/* Initialise position and remove one cell */
static int16_t newpos(void)
{
    int i;
    int16_t pos;

    /* Fill the starting position */
    for(i = 0; i < 15; i++) {
        pos |= (1 << i);
    }

    /* Empty one cell */
    pos &= ~(1 << removed);

    return pos;
}

/* Check whether a move is valid */
static int validmove(int16_t pos, int i)
{
    return (pos & (1 << moves[i].from))
          && (pos & (1 << moves[i].jump))
          && !(pos & (1 << moves[i].to));
}

/* Play a move and return the new position */
static int16_t playmove(int16_t pos, int i)
{
   uint16_t newpos = pos;
   newpos ^= 1 << moves[i].from;
   newpos ^= 1 << moves[i].jump;
   newpos |= 1 << moves[i].to;
   return newpos;
}

/* Print a winning game. Optionally, write an animated GIF. */
static void printgame(char *game)
{
    int c;
    int16_t pos = newpos();

#ifdef USE_GD
    gdImagePtr im, oldim = NULL;
    int black, white, trans;
    FILE *fp;

    fp = fopen("/tmp/test.gif", "wb");
#endif

    for(c = 0; c < 14; c++) { /* XXX: we play a fake 14th move */
        int i;
        int m = game[c] - 'A';
#ifdef USE_GD
        /* Create frame */
        im = gdImageCreate(200, 160);
        white = gdImageColorAllocate(im, 255, 255, 255);
        black = gdImageColorAllocate(im, 0, 0, 0);
        trans = gdImageColorAllocate(im, 1, 1, 1);

        /* Draw shit */
        gdImageRectangle(im, 0, 0, 199, 159, black);

        for(i = 0; i < 15; i++) {
            int x = coords[i][0];
            int y = coords[i][1];
            if(pos & (1 << i))
                gdImageFilledArc(im, x, y, 30, 30, 0, 360, black, gdArc);
            else
                gdImageArc(im, x, y, 30, 30, 0, 360, black);
        }
        gdImageColorTransparent(im, trans);

        /* Append image to anim */
        if(oldim == NULL) {
            gdImageGifAnimBegin(im, fp, 1, 0);
        }
        gdImageGifAnimAdd(im, fp, 0, 0, 0, 100, 1, NULL);

        /* Update state */
        if(game[c]) {
            oldim = im;
            pos = playmove(pos, m);
        } else {
            gdImageGifAnimEnd(fp);
            fclose(fp);
        }
#endif
        if(game[c])
            printf("%i-%i ", moves[m].from, moves[m].to);
    }
    printf("\n");
}

/* Solve a position and record moves.
 * If depth == 13 it means we already won. */
static void solve(uint16_t pos, char *game, int depth)
{
    int i;

    if(depth == 13
#if PERFECT
       && (pos & (1 << removed))
#endif
      ) {
        printf("gagné\n");
        printgame(game);
        exit(0); /* XXX */
        return;
    }

    for(i = 0; i < 36; i++) {
        if(!validmove(pos, i))
            continue;

        game[depth] = 'A' + i;
        solve(playmove(pos, i), game, depth + 1);
    }
}

int main(int argc, char *argv[]) {
    int i;
    char game[16];

    if(argc > 1)
        removed = atoi(argv[1]);

    memset(game, 0, 16);

    /* Complete move list */
    for(i = 0; i < 18; i++) {
        moves[i + 18].from = moves[i].to;
        moves[i + 18].jump = moves[i].jump;
        moves[i + 18].to = moves[i].from;
    }

    /* Solve */
    solve(newpos(), game, 0);

    return 0;
}