/*
 * Vous disposez d'une grille de 4x4 pions. Les pions présentent une face
 * blanche et une face noire. Vous disposez de 5 opérations sur cette grille :
 *
 * (1) Vous pouvez retourner tous les pions d'une même ligne ;
 * (2) Vous pouvez retourner tous les pions d'une même colonne ;
 * (3) Vous pouvez décaler d'une case à gauche tous les pions d'une ligne
 *     (le pion à l'extrême gauche se retrouvant à l'extrême droite) ;
 * (4) Vous pouvez décaler d'une case vers le haut tous les pions d'une colonne
 *     (le pion tout en haut se retrouvant tout en bas) ;
 * (5) Vous pouvez retourner chaque pion individuellement.
 *
 * Le but est de fournir un algorithme qui fournisse en temps raisonnable
 * (quelques secondes) le nombre d'opérations minimales nécessaires pour que
 * tous les pions présentent leur face blanche.
 */

#include <stdint.h>

/* Encodage simple d'une position */
#define makepos(a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p) \
  (uint16_t)((a?1:0)|(b?2:0)|(c?4:0)|(d?8:0) \
           |(e?16:0)|(f?32:0)|(g?64:0)|(h?128:0) \
           |(i?256:0)|(j?512:0)|(k?1024:0)|(l?2048:0) \
           |(m?4096:0)|(n?8192:0)|(o?16384:0)|(p?32768:0))

/* Affichage d'une position encodée */
#define printpos(p) \
  printf("%i %i %i %i\n%i %i %i %i\n%i %i %i %i\n%i %i %i %i\n", \
         (p&1)?1:0,(p&2)?1:0,(p&4)?1:0,(p&8)?1:0, \
         (p&16)?1:0,(p&32)?1:0,(p&64)?1:0,(p&128)?1:0, \
         (p&256)?1:0,(p&512)?1:0,(p&1024)?1:0,(p&2048)?1:0, \
         (p&4096)?1:0,(p&8192)?1:0,(p&16384)?1:0,(p&32768)?1:0);

/* Affichage d'un coup entre 0 et 31 */
#define printmove(m) \
    if(m < 16) \
        printf("on retourne le pion %i,%i\n", m % 4, m / 4); \
    else if(m < 20) \
        printf("on inverse la ligne %i\n", m - 16); \
    else if(m < 24) \
        printf("on inverse la colonne %i\n", m - 20); \
    else if(m < 28) \
        printf("on décale à gauche la ligne %i\n", m - 24); \
    else if(m < 32) \
        printf("on décale en haut la colonne %i\n", m - 28); \
    else \
        printf("coup invalide\n");

/* Retrouve la position précédente */
uint16_t previous(uint16_t pos, unsigned int move)
{
    /* coups 0 à 15: on inverse le pion 0 à 15 */
    if(move < 16)
        return pos ^ (uint16_t)(0x1 << move);

    /* coups 16 à 19: on inverse la ligne 0 à 3 */
    if(move < 20)
        return pos ^ (uint16_t)(0xf << (4*(move-16)));

    /* coups 20 à 23: on inverse la colonne 0 à 3 */
    if(move < 24)
        return pos ^ (uint16_t)(0x1111 << (move-20));

    /* coups 24 à 27: on décale à gauche la ligne 0 à 3,
     * donc la position précédente s'obtient par décalage à droite */
    if(move < 28)
    {
        uint16_t mask = 0xf << (4*(move-24));
        uint16_t line = pos & mask;
        return (pos & ~mask) | ((line >> 3 | line << 1) & mask);
    }

    /* coups 28 à 31: on décale en haut la colonne 0 à 3,
     * donc la position précédente s'obtient par décalage vers le bas */
    if(move < 32)
    {
        uint16_t mask = 0x1111 << (move-28);
        uint16_t line = pos & mask;
        return (pos & ~mask) | ((line >> 12 | line << 4) & mask);
    }
}

typedef struct node
{
    int depth; /* profondeur du noeud dans le graphe */
    unsigned int move; /* le coup menant au père */
    uint16_t father; /* le père */
} node_t;

void solve(uint16_t problem)
{
    node_t node[65536];
    unsigned int depth, pos, move;

    for(pos = 0; pos < 65536; pos++)
    {
        node[pos].depth = 0;
    }

    /* On crée la position 0 (tout blanc) */
    node[0].depth = 1;

    /* Valeurs à la con */
    node[0].father = 0;
    node[0].move = 31337;

    /* Il faut au maximum 8 itérations pour remplir notre tableau car la
     * solution a maximum 8 coups (on vide chaque ligne par exemple ; si la
     * ligne fait 0, 1 ou 2 pièces noires, on les inverse, si elle en fait 3
     * ou 4 on inverse les blanches puis on inverse la ligne, et donc on
     * a maxi 2 opérations par ligne). */
    for(depth = 1; depth <= 8; depth++)
    {
        for(pos = 0; pos < 65536; pos++)
        {
            /* Si ce n'est pas un noeud de notre profondeur, on passe */
            if(node[pos].depth != depth)
                continue;

            /* On visite chacun des noeuds susceptibles d'avoir mené
             * à cette position, en testant tous les coups possibles. */
            for(move = 0; move < 32; move++)
            {
                uint16_t prev = previous(pos, move);

                /* Si le noeud existait déjà, on ne lui fait rien */
                if(node[prev].depth)
                    continue;

                node[prev].depth = depth + 1;

                node[prev].father = pos;
                node[prev].move = move;

                /* Si c'est la position de notre problème, on affiche
                 * la façon dont on est arrivé là et on quitte. */
                if(prev == problem)
                {
                    do
                    {
                        printmove(node[prev].move);
                        prev = node[prev].father;
                        printpos(prev);
                    } while (prev != 0);

                    return;
                }
            }
        }
    }
}

/* The starting position */
uint16_t tofind = makepos(
1,1,1,0,
0,0,1,1,
1,1,0,1,
0,0,0,0
);

int main(void)
{
  printf("à résoudre:\n");
  printpos(tofind);

  solve(tofind);
}