#include<stdio.h>
#include<stdlib.h>
typedef long long unsigned llu; // Un mot de 64 bits est en fait un tableau de 16 nombres de 4 bits.
#define lh 22
#define nh (1<<lh)    // taille de la table de hachage
llu val2(llu a) { asm("bsf %0,%0" : "+r"(a) ); return a; }
struct { llu pos; int suite, pere; } hash[nh];
int hlibre;     // nombre de cases libres
int nouveau(llu pos,int pere)
{ llu x=(pos>>lh)*3+(pos>>2*lh)*5, p;  // fonction de hachage
  for(;p=hash[x=(2*pos+1+x)&(nh-1)].pos,p;) if(p==pos) return 0;  // pos est déjà dans la table
  if(--hlibre<10000) printf("hash saturé\n"), exit(1);    // pos n'est pas encore dans la table. Il faut l'y insérer.
  return hash[x]=(typeof(*hash)){pos,0,pere}, x;
}
int parite(llu a)
{ int t[16], u[16], i, j, p;
  for(i=16;i--;) u[t[i]=a>>4*i&15]=i;
  for(i=16;i--;) if(u[t[i]]!=i) printf("%16llX n'est pas une permutation\n",a), exit(1);
  for(p=*u,i=16;i--;) for(;j=t[i],j!=i;p++) t[i]=t[j], t[j]=j; // calcule la signature de la permutation + parité de la position du trou
  return p&1;
} 
int dist(llu dep,llu arr,int l)  // un taquin 3x5 n'a que 15 cases. On force donc t[15]=15.
{ if(parite(dep|=15llu<<60)^parite(arr|=15llu<<60)) return printf("%16llX ne peut pas être atteint à partir de %16llX",dep,arr), 0;
  int i, j, l0, l1, x[16], y[16], p, q, h=1;
  for(i=hlibre=nh;i--;) hash[i].pos=0;// On vide la table de hachage.
  *hash=(typeof(*hash)){1,0,0};       // La case 0 sert de fin de liste.
  for(i=16;i--;) x[j=arr>>4*i&15]=i/3, y[j]=i%3; // Coordonnées du jeton j=t[i] dans la position d'arrivée
  for(l0=nouveau(dep,0);;l0=l1,h=!h)  // Au début l0=(dep). Quand la liste l0 est épuisée on vide l1 dans l0.
  for(l1=0;l0;)                // Tant que l0 est non vide
  { l0=hash[p=l0].suite;       // on dépile son premier élément (d'adresse p)
    llu a=hash[p].pos, b=~a&~a>>1, pere=hash[hash[p].pere].pos, k; // dans a.
    if(h) if(hash[p].suite=l1, l1=p, // Si h=1 on ne garde que les mouvements qui rapprochent d'arr, mais on met
                        // les positions traitées dans l1 pour y chercher plus tard (h=0) les autres mouvements.
             a==arr) return p; // On a atteint la position d'arrivée.
#if __x86_64
    i=val2(b&b>>2&0x1111111111111111llu)>>2;   //  position du trou dans a. t[i]=0
#else
    for(i=0;a>>i*4&15;i++) ;
#endif
    int xi=i/3, yi=i%3;        //  Coordonnées du trou.
    for(j=-3;j<5;j+=2)         //  Les 4 déplacements possibles du trou sont -3 -1 +1 et +3
    if(k=i+j,k<15)             //  Si le trou ne sort pas en haut ni en bas. (k est non signé)
    if(-~j&4||k/3==xi)         //  Si le trou ne sort pas à gauche ni à droite.
    if(b=a>>4*k&15,b<l)        //  Si le trou n'est pas échangé avec un jeton gelé.
    if((j*(-~j&4?x[b]-xi:y[b]-yi)>0)^h) // Si la distance de Manhattan à la position d'arrivée varie de 1-2h
    if(b=a^b<<4*i^b<<4*k,b!=pere) //  Si l'échange du trou 0=t[i] avec le jeton b=t[k], ne retourne pas vers le père.
    if(q=nouveau(b,p),q)       //  Si c'est une nouvelle position, elle est empilée
    { if(h) hash[q].suite=l0, l0=q;  //    dans la liste courante ( h=1 dist-- ) pour un traitement immédiat
      else  hash[q].suite=l1, l1=q;  // ou dans la liste suivante ( h=0 dist++ ) pour un traitement différé.
    }
  }
}
void aff(llu a) { int i; for(i=0;printf(i%3?" ":"\n"),i<15;i++,a>>=4) if(a&15) printf("%0llX",a&15); else printf("."); }
void afff(int l) { int i=0; for(;l;l=hash[l].pere) printf("%d",i++), aff(hash[l].pos); }
void affl(int p,int n)
{ int i,j,q,m,l=0,c;
  for(;p;p=q)
  for(i=-3;i<15;i+=3,printf("\n"))
  for(q=p,m=n;q && m--;q=hash[q].pere,printf("  "))
  if(i<0) printf("%6d",l++); else
  for(j=i;j<i+3;j++) if(c=hash[q].pos>>4*j&15,c) printf(" %0X",c); else printf(" .");
}
#define afff(a) affl(a,10)
int main()
{ afff(dist(0xF0123456789ABCDEllu, 0xF1203456789ABCDEllu,15));  //  2
  afff(dist(0xF0123456789ABCDEllu, 0xF123456789ABCDE0llu,15));  // 38
  afff(dist(0xF0123456789ABCDEllu, 0xF123456789ABCD0Ellu,15));  // 37
  afff(dist(0xF0123456789ABCDEllu, 0xF3210764589ABCDEllu,15));  // 21
  afff(dist(0xF0123456789ABCDEllu, 0xFBA9867543210CDEllu,15));  // 49
  afff(dist(0xF0123456789ABCDEllu, 0xFD123456789ABCE0llu,15));  // 28
  afff(dist(0xFEDCBA9876543210llu, 0xFEDCBA9874523610llu, 9));  // 20
  afff(dist(0xFEDCBA9876543210llu, 0xFEDCBA9874523610llu, 8));  // 24
  afff(dist(0xFEDCBA9876504321llu, 0xFEDCBA9123405678llu, 9));  // 30
  afff(dist(0xFCBA9E87065D4321llu, 0xF1234E56078D9ABCllu,13));  // 68
  return 0;
}