In Chinese Checkers kann sich eine Figur bewegen, indem sie über eine beliebige andere Figur springt oder eine Folge solcher Sprünge macht. Ihre Aufgabe ist es, eine möglichst lange Abfolge von Hopfen zu finden.

Eingang

Eine Folge von 121 Nullen oder Einsen, die jeweils einen Platz auf einer Tafel darstellen. Eine Null bedeutet, dass der Ort leer ist. Eine Eins bedeutet, dass der Platz besetzt ist. Die Positionen sind von links nach rechts aufgelistet. oben nach unten. Zum Beispiel kann die Eingabe dieser Einstellung wäre

1011110011000001000000000000000000000000100000000001000000000000000000000000000001000000000000000000000001000001100111111

Erläuterung:

Der oberste Platz wird von einem grünen Stück belegt, die erste Ziffer in der Eingabe ist also 1. Die zweite Reihe hat eine leere Position und dann eine besetzte Position, also 01kommt als nächstes. Die dritte Reihe ist alle besetzt, also 111. Die vierte Reihe hat zwei leere und zwei belegte Felder (von links nach rechts), also 0011. Dann kommen fünf 0, a 1und sieben 0für die nächste Reihe und so weiter.

Wie in dieser Konfiguration gibt es eine Ecke, die gerade nach oben zeigt. Es können beliebig viele Teile auf dem Brett liegen (von 1 bis 121). Beachten Sie, dass Stücke unterschiedlicher Farben nicht unterschiedlich dargestellt werden.

Ausgabe

Die maximale Länge eines legalen Hops, bei dem ein beliebiges Stück auf dem Brett verwendet wird. Sie dürfen denselben Ort nicht mehr als einmal besuchen (einschließlich der Start- und Endpositionen). Sie können jedoch mehr als einmal über dasselbe Stück springen. Wenn es keinen legalen Hop gibt, wird ausgegeben 0. Überlegen Sie nicht, ob es einen legalen Non-Hop-Move gibt.

Die Ausgabe an das oben beschriebene Setup lautet beispielsweise 3.

Die Ein- und Ausgabe kann über stdin und stdout, über Befehlszeilenargumente, über Funktionsaufrufe oder eine ähnliche Methode erfolgen.

Testfälle

Eingang:

0100000010000000000000000100000000000000000000000000000001010010000000000000000000000101000000000000000000100000000100001

Ausgabe: 0(keine zwei Stücke liegen nebeneinander)

Eingang:

0000000000111100000000011100000000011000000000100000000000000000000000000000000000000000000000000000000000000000000000000

Ausgabe: 1(Ersteinrichtung für einen Spieler in der oberen linken Ecke)

Perl, 345 322

Edit: Golf, leicht.

Weitere Testfälle wären nett, aber im Moment sieht es so aus, als ob es funktioniert. Ich werde später gegebenenfalls Kommentare hinzufügen. Mit Zeilenumbrüchen und Einrückung zur besseren Lesbarkeit:

$_=<>;
$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

Golfed Code (Debugging-Code und unnötige Leerzeichen entfernt. Von der Eingabe über stdin zur Eingabe über die Befehlszeile geändert und die Möglichkeit genutzt, die Variable i dort zu deklarieren. Letzte Änderung: Code in Klammern von forSchleifen verschoben , um zwei Semikolons zu speichern.)

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);}

Erläuterung

Dies basiert auf einer 20x21-Karte, die wie folgt aussieht und beim Start des Programms anfänglich mit Nullen gefüllt ist (diese ASCII-Grafik wurde von einer modifizierten Version des Programms generiert, und wenn die iSchleife abwärts zählt, befindet sich Null in der unteren rechten Ecke):

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

Die Schleife idurchläuft diese Tafel zweimal und verwendet x und y, um zu berechnen, ob ein Quadrat tatsächlich zum Schachbrett gehört oder nicht (dies erfordert 6 separate Ungleichungen in x und y).

Wenn dies der Fall ist, füllt es beim ersten Mal die Felder und setzt ein 0(falsch) für ein 1(besetzt) ​​und ein 1(wahr) für ein 0(unbesetzt). Diese Umkehrung ist wichtig, da alle Felder außerhalb der Grenzen bereits eine 0 enthalten, was bedeutet, dass sie belegten Feldern ähneln und ohne eine spezielle Prüfung nicht angesprungen werden können.

Wenn das Quadrat beim zweiten Mal besetzt ist (0 enthält), ruft es die Funktion auf f, die nach den Zügen sucht.

fSucht rekursiv in den 6 möglichen Richtungen, die durch +/- 1 (horizontal), +/- 20 (vertikal) und +/- 19 (diagonal) codiert sind "AST?-,"[k]-64. Wenn es einen Treffer findet, setzt es diese Zelle auf 0 (belegt), bevor es sich rekursiv selbst aufruft, und setzt sie dann auf 1 (leer) zurück, wenn die Funktion zurückgegeben wird. Der Zellenwert muss vor dem rekursiven Aufruf geändert werden, um zu verhindern, dass mehrmals in diese Zelle gesprungen wird.

Ungolfed Code

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
}