Dans les Dames chinoises , une pièce peut se déplacer en sautant sur n'importe quelle autre pièce ou en faisant une séquence de tels sauts. Votre tâche consiste à trouver la séquence de sauts la plus longue possible.

Contribution

Une séquence de 121 zéros ou uns, chacun représentant une place sur une planche. Un zéro signifie que l'endroit est vide; un signifie que la place est occupée. Les postes sont répertoriés de gauche à droite; de haut en bas. Par exemple, l'entrée de cette configuration serait

1011110011000001000000000000000000000000100000000001000000000000000000000000000001000000000000000000000001000001100111111

Explication:

L'endroit le plus haut est occupé par une pièce verte, donc le premier chiffre de l'entrée est 1. La deuxième ligne a une position vide puis une position occupée, 01vient ensuite. La troisième rangée est donc entièrement occupée 111. La quatrième rangée a deux espaces vides et deux espaces occupés (de gauche à droite) 0011. Viennent ensuite cinq 0, a 1et sept 0pour la ligne suivante, et ainsi de suite.

Comme dans cette configuration, il y a un coin pointé vers le haut. Il peut y avoir n'importe quel nombre de pièces sur le plateau (de 1 à 121). Notez que les pièces de couleurs différentes ne sont pas représentées différemment.

Production

La longueur maximale d'un saut légal, en utilisant n'importe quelle pièce du plateau. Vous ne pouvez pas visiter le même endroit plus d'une fois (y compris les positions de départ et de fin). Cependant, vous pouvez sauter plusieurs fois sur la même pièce. S'il n'y a pas de saut légal, sortez 0. Ne considérez pas s'il existe un mouvement légal de non-saut.

Par exemple, la sortie de la configuration décrite ci-dessus est 3.

L'entrée et la sortie peuvent être effectuées via stdin et stdout, via des arguments de ligne de commande, via des appels de fonction ou toute autre méthode similaire.

Cas de test

Contribution:

0100000010000000000000000100000000000000000000000000000001010010000000000000000000000101000000000000000000100000000100001

Sortie: 0(pas deux pièces côte à côte)

Contribution:

0000000000111100000000011100000000011000000000100000000000000000000000000000000000000000000000000000000000000000000000000

Sortie: 1(configuration initiale pour un joueur dans le coin supérieur gauche)

Perl, 345 322

Edit: golfé, légèrement.

Plus de cas de test seraient bien, mais pour l'instant, il semble que cela fonctionne. J'ajouterai des commentaires plus tard si nécessaire. Avec des nouvelles lignes et un retrait pour la lisibilité:

$_=<>;
$s=2x185;
substr$s,(4,22,unpack'C5(A3)*','(:H[n129148166184202220243262281300')[$i++],0,$_ 
    for unpack A.join A,1..4,13,12,11,10,9..13,4,3,2,1;
$_=$s;
sub f{
    my(@a,%h)=@_;
    $h{$_}++&&return for@a;
    $-+=$#a>$-;
    $s=~/^.{$a[0]}$_/&&f($+[1],@a)
        for map{("(?=.{$_}1.{$_}(0))","(?<=(0).{$_}1.{$_}.)")}0,17,18
}
f$+[0]while/1/g;
print$-

C, 262 260

Code golfé ( code de débogage et espaces inutiles supprimés. Changé de l'entrée via stdin en entrée via la ligne de commande, et a profité de l'occasion pour y déclarer la variable i. Dernière modification: le code a été placé entre crochets de forboucles pour enregistrer deux points-virgules.)

t[420],j,l,x,y;f(p,d){int z,q,k;for(k=6;k--;t[q]&!t[p+z]?t[q]=0,f(q,d+1),t[q]=1:0)z="AST?-,"[k]-64,q=p+z*2;l=d>l?d:l;}main(int i,char**s){for(i=840;i--;x>3&y>5&x+y<23|x<13&y<15&x+y>13?i>420?t[i-420]=49-s[1][j++]:t[i]||f(i,0):0)x=i%20,y=i/20%21;printf("%d",l);}

Explication

Cela repose sur une carte 20x21 qui ressemble à ceci, initialement remplie de zéros au démarrage du programme (cet art ASCII a été généré par une version modifiée du programme, et comme la iboucle compte vers le bas, zéro est dans le coin inférieur droit):

....................
....................
...............#....
..............##....
.............###....
............####....
.......#############
.......############.
.......###########..
.......##########...
.......#########....
......##########....
.....###########....
....############....
...#############....
.......####.........
.......###..........
.......##...........
.......#............
....................
....................

La boucle iparcourt ce tableau deux fois, en utilisant x et y pour calculer si un carré appartient réellement au damier ou non (cela nécessite 6 inégalités distinctes en x et y.)

Si c'est le cas, la première fois, il remplit les cases, mettant un 0(faux) pour un 1(occupé) et un 1(véridique) pour un 0(inoccupé). Cette inversion est importante, car tous les carrés hors limites contiennent déjà un 0, ce qui signifie qu'ils ressemblent à des carrés occupés et il est clair qu'ils ne peuvent pas être sautés sans avoir besoin d'une vérification spécifique.

La deuxième fois, si le carré est occupé (contient 0), il appelle la fonction fqui recherche les mouvements.

frecherche récursivement dans les 6 directions possibles encodées par +/- 1 (horizontal), +/- 20 (vertical) et +/- 19 (diagonal) encodées dans l'expression "AST?-,"[k]-64. Lorsqu'il trouve un hit, il met cette cellule à 0 (occupé) avant de s'appeler récursivement, puis la remet à 1 (vide) lorsque la fonction est retournée. La valeur de la cellule doit être modifiée avant l'appel récursif pour éviter de sauter plusieurs fois dans cette cellule.

Code non golfé

char s[999];                           //input string.
t[420],i,j,l,x,y;                      //t=board. i=board counter, j=input counter. l=length of longest hop found so far.

f(p,d){                                //p=position, d= recursion depth.
  //printf("%d,%d ",p,d);              //debug code: uncomment to show the nodes visited.
  int k,z,q;                           //k=counter,z=displacement,q=destination
  for(k=6;k--;)                        //for each direction
    z="AST?-,"[k]-64,                  //z=direction
    q=p+z*2,                           //q=destination cell
    t[q]&!t[p+z]?                      //if destination cell is empty (and not out of bounds) and intervening cell is full
      t[q]=0,f(q,d+1),t[q]=1           //mark destination cell as full, recurse, then mark it as empty again.
      :0;
  l=d>l?d:l;                           //if d exceeds the max recorded recursion depth, update l
}

main(){
  gets(s);                             //get input
  for(i=840;i--;)                      //cycle twice through t
    x=i%20,                            //get x
    y=i/20%21,                         //and y coordinates
    x>3&y>5&x+y<23|x<13&y<15&x+y>13?   //if they are in the bounds of the board
      i>420?
        t[i-420]=49-s[j++]             //first time through the array put 0 for a 1 and a 1 for a 0 ('1'=ASCII49)
        :t[i]||f(i,0)                  //second time, if t[i]=0,call f(). 
       //,puts("")                     //puts() formats debug output to 1 line per in-bounds cell of the board
      :0;
  printf("%d",l);                      //print output
}