Dame: König ich?

14

Herausforderung:

Geben Sie bei einem Schachbrett die kleinste Anzahl von Zügen aus, die erforderlich sind (vorausgesetzt, Schwarz bewegt sich überhaupt nicht), um nach Möglichkeit ein rotes Stück zu erhalten.

Regeln :

Die rote Seite wird immer unten sein, ihre Figuren können jedoch in einer beliebigen Reihe beginnen (sogar in der Königsreihe, zu der sie gelangen müssen). Schwarze Steine ​​sind stationär , das heißt, sie bewegen sich nicht zwischen den Bewegungen von Rot, sondern werden vom Spielfeld entfernt, wenn sie gefangen werden. Beachte, dass die Steine ​​auf jedem Feld des Spielfelds beginnen können, auch direkt nebeneinander. Dies ist nicht die Art und Weise, wie normale Checker gespielt werden, aber Ihr Programm muss in der Lage sein, diese zu lösen. (Siehe Eingabe 5) Steine ​​dürfen sich jedoch nur diagonal bewegen (siehe Eingabe 3). Rückwärtserfassung ist zulässig, wenn sich die erste Erfassung in der Kette vorwärts befindet (siehe Eingabe 7).

Eingang:

Ein 8x8-Schachbrett, bei dem die Platinenabstände wie folgt definiert sind (Sie können auch Alternativen verwenden, sofern diese übereinstimmen):

. - Leer

R - Rotes Stück

B - Schwarzes Stück

Ausgabe:

Die kleinste Anzahl von Zügen, für die ein rotes Steinchen benötigt wird, um durch Betreten der Königsreihe in der obersten Reihe des Bretts (schwarze Seite) "König" zu werden, 0, wenn keine Züge erforderlich sind (ein rotes Steinchen beginnt in der Königsreihe), oder eine negative Zahl, wenn es nicht möglich ist, ein rotes Stück zu bestimmen (dh Schwarz belegt die gesamte erste Reihe).

Eingang 1:

. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
R . . . . . . .

Ausgang 1:

7

Eingang 2:

. . . . . . . .
. . . . . . . .
. . . . . B . .
. . . . . . . .
. . . B . . . .
. . . . . . . .
. B . . . . . .
R . . . . . . .

Ausgang 2:

2

Eingang 3:

. B . B . B . B
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
R . . . . . . .

Ausgang 3:

-1

Eingang 4:

. . . . . . . R
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
R . . . . . . .

Ausgang 4:

0

Eingang 5:

. . . . . . . .
. . . . . . . .
. . . . . . . .
. B . . B . . .
B . . . . B . .
. B . B . . . .
. . B . . B . .
. . . R R . . .

Ausgang 5:

4

Eingang 6:

. . . . . . . .
. . . . . . . .
. B . . . . . .
. . B . . . . .
. B . B . . . .
. . . . R . . .
. . . B . . . .
. . . . R . . .

Ausgang 6:

2

Eingang 7:

. . . . . . . .
. . . . . . . .
. . B . . . . .
. . . . . . . .
. . B . . . . .
. B . B . B . .
. . . . B . . .
. . . . . R . R

Ausgang 7:

4

Wertung:

Das ist , also gewinnt der kürzeste Code in Bytes.

Jodler
quelle
1
Sollte der zweite Testfall nicht 2 sein, da Sie doppelt oder dreifach springen können?
DJMcMayhem
Ist ein Zustandsarray von Arrays von ganzen Zahlen als Eingabe OK?
Jonathan Allan
1
Ich habe einen weiteren Testfall hinzugefügt, der sich als schwierig erweisen sollte. Es geht um mehrere Sprünge, mehrere Teile und einen Rücksprung, um die bestmögliche Lösung zu erzielen.
Orlp
1
@orlp Hm, ich wollte sagen, dass sich keine der roten Figuren rückwärts bewegen darf, da keine von ihnen Könige sind (daher der Punkt der Herausforderung), aber es scheint, dass einige Leute mit Regeln spielen, bei denen das Erfassen rückwärts durch Nicht-Könige erlaubt ist. Königsstücke, wenn die erste Gefangennahme vorwärts war. Ich werde das zu den Regeln hinzufügen, da mir das vorher nicht bewusst war.
Yodle
1
ooooooooh, du musst nicht nur ein rotes Teil auswählen, sie können sich zusammenschließen! Ich verstehe
Greg Martin

Antworten:

4

JavaScript (ES6), 354 322 Byte

Nimmt ein Array als Eingabe mit:

  • 0 = leeres Quadrat
  • 1 = rotes Stück
  • 2 = schwarzes Stück

Gibt die optimale Anzahl von Zügen zurück oder 99, wenn es keine Lösung gibt.

Es ist sehr schnell, aber man könnte viel mehr Golf spielen.

F=(b,n=0,C=-1,i)=>b.map((v,f,X,T,x=f&7,y=f>>3)=>v-1||(y&&n<m?[-9,-7,7,9].map(d=>(N=c=X=-1,r=(d&7)<2,T=(t=f+d)>=0&t<64&&(x||r)&&(x<7||!r)?(!b[t]&d<0)?t:b[t]&1?N:b[t]&2&&(d<0&y>1|d>0&C==f)?(X=t,x>1||r)&&(x<6|!r)&&!b[t+=d]?c=t:N:N:N)+1&&(b[f]=b[X]=0,b[T]=1,F(b,n+!(C==f&c>N),c,1),b[f]=1,b[X]=2,b[T]=0)):m=n<m?n:m),m=i?m:99)|m

var test = [
  [ 0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    1,0,0,0,0,0,0,0
  ],
  [ 0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,2,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,2,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,2,0,0,0,0,0,0,
    1,0,0,0,0,0,0,0
  ],
  [ 0,2,0,2,0,2,0,2,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    1,0,0,0,0,0,0,0
  ],
  [ 0,0,0,0,0,0,0,1,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    1,0,0,0,0,0,0,0
  ],
  [ 0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,2,0,0,2,0,0,0,
    2,0,0,0,0,2,0,0,
    0,2,0,2,0,0,0,0,
    0,0,2,0,0,2,0,0,
    0,0,0,1,1,0,0,0
  ],
  [ 0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,2,0,0,0,0,0,0,
    0,0,2,0,0,0,0,0,
    0,2,0,2,0,0,0,0,
    0,0,0,0,1,0,0,0,
    0,0,0,2,0,0,0,0,
    0,0,0,0,1,0,0,0
  ],
  [ 0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,2,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,2,0,0,0,0,0,
    0,2,0,2,0,2,0,0,
    0,0,0,0,2,0,0,0,
    0,0,0,0,0,1,0,1
  ]
];

test.forEach((b, n) => {
  console.log("Test #" + (n + 1) + " : " + F(b));
});

Arnauld
quelle
99 ist wahrscheinlich in Ordnung, ich kann mir keine echte Lösung vorstellen, die 99 Züge auf einem 8x8-Brett macht. Gut gemacht!
Yodle