Wo kann der Ritter in N Zügen sein?

21

Dies ist Hole-3 von The Autumn Turnier von APL CodeGolf . Ich bin der ursprüngliche Autor des Problems dort und darf es daher hier erneut posten.


Gegeben:

  1. eine Anzahl von Umdrehungen (bitte geben Sie an, wenn keine Bewegung 0 ist, ansonsten nehmen wir an, dass es 1 heißt) und

  2. eine Liste von einer oder mehreren Startpositionen (in beliebiger Form, z. B. 0 oder 1 indexierte Koordinaten oder 64 fortlaufende Zahlen / Zeichen oder A1 – H8 - geben Sie an, welche) auf einem 8-mal-8-Schachbrett,

Gibt (in beliebiger Reihenfolge) die Liste der eindeutigen Positionen zurück (im selben Format wie die Eingabe), an denen sich der Ritter nach der angegebenen Anzahl von Runden befinden kann.

  • Jeder Ritter muss sich mit jedem Zug bewegen, aber Sie müssen sich keine Sorgen machen, dass mehrere Ritter dasselbe Feld besetzen.

  • Ein Ritter kann sich nur zu den mit X markierten Positionen relativ zu seiner aktuellen Position bewegen, die mit ♞ markiert ist:
    Wo sich ein Ritter bewegen kann

Beispiele (1-indizierte Koordinaten)

1umziehen von [[1,1]]: [[2,3],[3,2]]

2bewegt sich von [[1,1]]: [[1,1],[1,3],[1,5],[2,4],[3,1],[3,5],[4,2],[4,4],[5,1],[5,3]]

1umziehen von [[1,1],[5,7]]: [[2,3],[3,2],[3,6],[3,8],[4,5],[6,5],[7,6],[7,8]]

2bewegt sich von [[1,1],[5,7]]: [[1,1],[1,3],[1,5],[1,7],[2,4],[2,6],[2,8],[3,1],[3,3],[3,5],[3,7],[4,2],[4,4],[4,6],[4,8],[5,1],[5,3],[5,5],[5,7],[6,4],[6,6],[6,8],[7,3],[7,7],[8,4],[8,6],[8,8]]

0bewegt sich von [[3,4]]: [[3,4]]

Adam
quelle
Können Schachfelder durch Nummerierung von 0-63 anstelle von [Rang, Datei] eingegeben und ausgegeben werden?
Dave
@ Dave Klar, warum nicht? Seien Sie einfach konsistent mit I / O.
Adám
8
Ich schwöre, ich habe dieses HNQ als "Wo der Ritter in Ni ist" gelesen
Sidney
3
Wortspielalarm: Die Bezeichnung für Ritter lautet N.
Joshua
Können wir die 1-basierte Indizierung für die Anzahl der Schritte verwenden? ZB[[1,1]], 2 -> [[2,3],[3,2]]
Zgarb

Antworten:

11

Wolfram-Sprache (Mathematica) , 45 Bytes

Da die andere Lösung falsch ist (siehe Martins Kommentar unten), entscheide ich mich, meine Lösung zu posten:

8~KnightTourGraph~8~AdjacencyList~#&~Nest~##&

Probieren Sie es online!

Ultimative Infixnotation ...

Nimmt 2 Eingabe, die erste ist eine Liste von Zahlen in Reichweite, [1,64]beschreiben Sie die Startpositionen des Ritters, die zweite ist die Anzahl der Schritte.

Diese Lösung basiert auf dem extremen Komfort der in Mathematica integrierten Funktionen:

  • AdjacencyListmay nimmt eine Liste von Scheitelpunkten auf der rechten Seite und gibt eine Liste von Scheitelpunkten zurück, die an die bereits entfernten und sortierten Scheitelpunkte angrenzen .
  • KnightTourGraphist ein Builtin. Kein Wunder.
  • NestNest[f, expr, n]Nimmt Argumente in die ##richtige Reihenfolge , die wir über ihre rechte Seite als splat Nest[f, ##].
  • Und schließlich parst Mathematica a~b~c~d~eas (a~b~c)~d~e, sodass keine eckige Klammer erforderlich ist. Ohne Infixnotation und Abflachung ##wäre es Nest[AdjacencyList[KnightTourGraph[8, 8], #] &, #, #2]&.
user202729
quelle
1
Ich glaube nicht, dass es falsch ist, eine bestehende Lösung zu übertreiben.
Adám
1
Funktioniert das mit mehreren Startpositionen?
Adám
Tolle! Jetzt muss ich herausfinden, wie ich das gelesen habe ...
Dave
Dies wären wahrscheinlich 17 Bytes in der hypothetischen Mthmca-Golfsprache.
Michael Stern
7

JavaScript (ES7), 99 Byte

Eingabe- / Ausgabeformat: Quadrate Indizes in [0 ... 63] .

f=(a,n)=>n--?f([...Array(64).keys()].filter(p=>!a.every(P=>(p%8-P%8)**2^((p>>3)-(P>>3))**2^5)),n):a

Testfälle

Dieses Snippet enthält zwei Hilfsfunktionen zum Übersetzen von und in das vom OP bereitgestellte Format.

Wie?

Ein Zug von (x, y) nach (X, Y) ist ein gültiger Ritterzug, wenn wir entweder:

  • | xX | = 1 und | yY | = 2 oder
  • | xX | = 2 und | yY | = 1

Durch Quadrieren anstelle von Absolutwerten kann dies ausgedrückt werden als:

  • (xX) ² = 1 und (yY) ² = 4 oder
  • (xX) ² = 4 und (yY) ² = 1

Da 1 und 4 die einzigen perfekten Quadrate sind, die zusammen mit XOR 5 ergeben, haben wir einen gültigen Springerzug, wenn:

(xX) ²XOR (yY) ²XOR 5 = 0

Wir wenden diese Formel auf jedes Quadrat p = 8y + x auf dem Brett und jedes Ritterquadrat P = 8Y + X an, um die neuen möglichen Ritterzielquadrate abzuleiten, und wiederholen diesen Vorgang n- mal rekursiv .

Arnauld
quelle
5

Oktave, 69 Bytes

function a=f(a,n,b=~a)for k=1:n;a=b&imdilate(a,de2bi(")0#0)"-31));end

Online Demo!

Der Ein- / Ausgang ist die Konfiguration der Karte am Anfang / Ende als binäre 8 * 8-Matrix.

Erläuterung:

nWiederholen Sie für Schritte die morphologische Erweiterung der Platte mit der folgenden Maske:

01010
10001
00100
10001
01010
rahnema1
quelle
5

Retina , 147 102 Bytes

.$
$*	
¶
 ¶
{s`((?<=N(....|.{11}|.{13})?.{7})|(?=.{8}(....|.{11}|.{13})?N))\S(?=.*	)
n
Ts`	Nn`_:N`.*¶	

Probieren Sie es online! Nimmt die Eingabe als 8x8-Tafel :mit den mit markierten Rittern vorN s , mit einer Ziffer für die Anzahl der Runden in der nächsten Zeile (es macht keinen Sinn, mehr als 9 Runden zu haben, aber wenn Sie darauf bestehen, kann ich es für eine zusätzliche unterstützen Byte). Beachten Sie, dass die Ausgabe zusätzliche Leerzeichen enthält. Bearbeiten: 45 Bytes dank @MartinEnder gespeichert. Erläuterung: In der ersten Stufe wird die Anzahl der Umdrehungen in unäre Zeichen umgewandelt, wobei jedoch Tabulatorzeichen verwendet werden, damit sie später nicht versehentlich abgeglichen werden, während in der zweiten Stufe rechts auf der Tafel Leerzeichen eingefügt werden, um zu verhindern, dass sich die Regex-Zeichen überschneiden die Kante. Die dritte Stufe ersetzt alle Ns und :s, die ein Springer von einem Nmit einemn während die vierte Stufe alle verbleibenden Ns löscht , die ändertns zu Ns und subtrahiert 1 von der Bewegungszahl. Dies wiederholt sich, bis der Bewegungszähler Null ist.

Neil
quelle
Das ist sehr beeindruckend. Auf jeden Fall nicht das richtige Werkzeug für den Job!
Adám
4

Gelee , 29 Bytes

+þ1,2Œ!×þ1,-p`¤¤Ẏ¤Ẏ⁼%8$$ÐfQµ¡

Probieren Sie es online!

0-indizierte Koordinaten. Mit ziemlicher Sicherheit ist dies nicht optimal.

-1 Byte dank user202729

Erläuterung

+þ1,2Œ!×þ1,-p`¤¤Ẏ¤Ẏ⁼%8$$ÐfQµ¡  Main Link
+þ                             Addition Table (all pairs using + as combining function) with
  1,2Œ!×þ1,-p`¤¤Ẏ¤             All knight moves:
  1,2                          [1, 2]
     Œ!                        All permutations ([1, 2], [2, 1])
       ×þ                      Product Table (all pairs using × as combining function) with
         1,-p`¤                [1, 1], [1, -1], [-1, 1], [-1, -1]
         1,-                   [1, -1]
            p`                 Cartestian Product with itself
               ¤               All knight moves (in a nested array) as a nilad
                Ẏ¤             Tighten (flatten once); all knight moves in a (semi-)flat array
                        Ðf     Keep elements where
                   ⁼%8$$       The element equals itself modulo 8 (discard all elements out of the range)
                          Q    Remove Duplicates
                           µ   Start new monadic chain (essentially, terminates previous chain)
                            ¡  Repeat n times; n is implicitly the second input (right argument)
HyperNeutrino
quelle
1
0-indiziertes Gelee?
Adám
1
@ Adám Erleichtert das Filtern: P
HyperNeutrino
2
Ich erwarte, dass Jelly dies in weniger als 15 Bytes tun kann, da der aktuelle Rekordhalter in APL dies in 24 Zeichen tut.
Adám
Wenn Sie> = 3 $ haben, können Sie es wahrscheinlich zum vorherigen Link verschieben und mit zurückverweisen Ç.
user202729
@ user202729 Oh ja wahr, danke.
HyperNeutrino
3

05AB1E , 27 25 Bytes

Vielen Dank an Emigna für das Speichern von 2 Bytes!

Verwendet 1-indizierte Koordinaten.

Code:

F•eĆ•SÍü‚Dí«δ+€`Ùʒ{`9‹*0›

Verwendet die 05AB1E- Codierung.Probieren Sie es online!

Erläuterung:

F                          # Do the following <input_1> times..
 •eĆ•SÍ                    #   Push [-1, -2, 1, 2, -1]
       ü‚                  #   Pairwise pairing: [[-1, -2], [-2, 1], [1, 2], [2, -1]]
         D                 #   Duplicate the array
          í                #   Reverse each element
           «               #   Concatenate to the previous array

Dies gibt uns das folgende Array:

[[-1, -2], [-2, 1], [1, 2], [2, -1], [-2, -1], [1, -2], [2, 1], [-1, 2]]

Welches sind die Deltas der Bewegungen des Ritters.

            δ+             #   Addition vectorized on both sides
              €`           #   Flatten each element
                Ù          #   Uniquify
                 ʒ         #   Keep elements which..
                  {`9‹     #     Has a maximum element smaller than 9
                      *0›  #     And a minimum element larger than 0
Adnan
quelle
Sie können •eĆ•SÍü‚anstelle von Ƶ‡4в2ô<D(«2 Bytes speichern.
Emigna
@Emigna Ahh, das ist klug, danke!
Adnan
2

Python 3, 105 Bytes

p=lambda g,i:i and list(set(p([x+y for x in g for y in[6,10,15,17,-6,-10,-15,-17]if 0<=x+y<64],i-1)))or g

Für die Rekursion muss ein benanntes Lambda verwendet werden. Ich bin mir nicht sicher, ob das disqualifizierend ist. Übergeben Sie die Startpositionen als 0-indizierte Quadratzahlenliste. 0 zählt als keine Züge.

mypetlion
quelle
2

Java (OpenJDK 8) , 124 Byte

(m,p)->{for(;m-->0;)for(long a=p,i=p=0,j;i<64;i++)for(j=64;j-->0;)p|=(p=i%8-j%8)*p+(p=i/8-j/8)*p==5?(a>>i&1)<<j:0;return p;}

Probieren Sie es online!

Eingabe- / Ausgabeformat

Die Eingabe / Ausgabe wird als Bits in a long(64 Bits) dargestellt: gesetzte Bits bedeuten, dass ein Pferd vorhanden ist, nicht gesetzte Bits bedeuten, dass kein Pferd vorhanden ist. Beispiel:

// [[0, 0]]
0b00000000_00000000_00000000_00000000_00000000_00000000_00000000_00000001L

Erklärungen

(m, p) -> {                          // Lambda. No currying because m and p are modified
 for(;m-->0;)                        // For each move
  for(long a=p,i=p=0,j;i<64;i++)     // Declare variables, move p to a, create a new p and loop on bits of a.
   for(j=64;j-->0;)                  // Loop on bits of p.
    p |=                             // Assign to p a value.
     (p=i%8-j%8)*p+(p=i/8-j/8)*p==5  // If i -> j is a valid horse move, see Arnauld's JavaScript answer for full explanations
      ? (a>>i&1)<<j                  // Assign the presence of the horse (i-th bit of a) to the resulting board (j-th bit of p).
      : 0;                           // Else it's not a valid horse move
 return p;
}

Credits

  • Dank Nevay 19 Bytes gespart!
  • Der (X-x)²+(Y-y)²==5Trick aus Arnauld's JavaScript-Antwort wurde wiederverwendet
  • Dank Nevay im neuen Algorithmus 1 Byte mehr gespart!
  • Nochmal 7 Bytes gespart dank Nevay durch Umstellung von int[]auf 64-Bit long.
Olivier Grégoire
quelle
1
169 Bytes:(m,p)->{for(;m-->0;){int i=64,a[]=p,x,y,u[]={1,3,5,9,15,19,21,23};for(p=new int[i];i-->0;)for(int z:u)if((((x=i/8+z/5-2)|(y=i%8+z%5-2))&-8)==0)p[x*8+y]|=a[i];}return p;}
Nevay
1
-1 Byte:(m,p)->{for(int i,j,a[],x;m-->0;)for(a=p,p=new int[i=64];i-->0;)for(j=64;j-->0;)p[j]|=(x=i%8-j%8)*x+(x=i/8-j/8)*x==5?a[i]:0;return p;}
Nevay,
Vielen Dank @Nevay! Hinzufügen von Code zum Entfernen von Klammern / Blöcken ist immer schön! ;-)
Olivier Grégoire
1
-7 Bytes durch Ersetzen int[]durch long:(m,p)->{for(long i,j,a;m-->0;)for(a=p,p=i=0;i<64;i++)for(j=64;j-->0;)p|=(p=i%8-j%8)*p+(p=i/8-j/8)*p==5?(a>>i&1)<<j:0;return p;}
Nevay
Prost, ich habe nicht mal daran gedacht! Gute Arbeit, @Nevay ;-)
Olivier Grégoire
2

Jelly , 29 28 Bytes

8Rp`
“¦Ʋƈ2’D_2ṡ2+€µẎ
ÇƓ¡f1£Q

Probieren Sie es online!

Die Anzahl der Umdrehungen erfolgt durch STDIN, und die Quadrate sind ein Argument.

Dies verbindet die @ HyperNeutrino Jelly-Lösung mit einem anderen Ansatz.

Schlage jetzt @HyperNeutrino um 1 ganzes Byte!

Vorschläge, um ein paar Bytes abzuschlagen, sind erwünscht!

Link 1 (Das Schachbrett)

8Rp`
8R   = The list [1,2,3,4,5,6,7,8]
  p` = cartesian multiplied with itself (this results in the chessboard)

Link 2 (Generierung verschieben)

“¦Ʋƈ2’D_2ṡ2+€µẎ
“¦Ʋƈ2’          = the number 103414301
      D         = converted into a list of digits
       _2       = subtract two from each element
         ṡ2     = overlapping pairs
           +€   = add to the list of squares
             µ  = Make sure the next part isn't treated as a right argument
              Ẏ = Tighten the list (Reducing the depth by one)

Link 3 (Viereckprüfung)

ÇƓ¡f1£Q
ÇƓ¡     = Repeat link #2 the requested amount of times
   f1£  = Remove everything not a member of link #1 (not on the chess board)
      Q = Make sure squares don't appear more than once
Zacharý
quelle
1

Schale , 18 Bytes

u!¡ṁö`fΠR2ḣ8=5ṁ□z-

Verwendet die 1-basierte Indizierung von Quadraten und Schritten. Probieren Sie es online!

Erläuterung

u!¡ṁö`fΠR2ḣ8=5ṁ□z-  Implicit inputs, say P=[[1,1],[5,7]] and n=2
  ¡                 Iterate on P:
   ṁö               Map the following function, then concatenate:
                     Argument is a pair, say p=[5,7].
          ḣ8         The range [1,2,..,8]
       ΠR2           Repeat twice, take cartesian product: [[1,1],[1,2],..,[8,8]]
     `f              Filter with this predicate:
                      Argument is a pair, say q=[3,8].
                z-    Zip p and q with difference: [-2,1]
              ṁ□      Sum of squares: 5
            =5        Is it 5? Yes, so [3,8] is kept.
 !                  Take n'th step of the iteration.
u                   Remove duplicates, implicitly print.
Zgarb
quelle
1

R , 145 183 134 Bytes

Dies ist das Ergebnis von Giuseppes exzellentem Golfspiel mit meinem anfänglichen, nicht allzu golfenen Algo (siehe Kommentar unten).

function(x,n){x=x%/%8*24+x%%8
t=c(49,47,26,22)
t=c(t,-t)
for(i in 1:n)x=intersect(v<-outer(1:8,0:7*24,"+"),outer(x,t,"+"))
match(x,v)}

Probieren Sie es online!

Eingang und Ausgang sind 1 ... 64-basiert. Nimmt einen Positionsvektor mit der Notation 1 ... 64 auf. Ordnet es einer 1: 576-Notation zu, dh einem Super-Board aus neun Boards. In dieser Notation sollte jeder Ritter bei jeder Iteration in der Lage sein, sich um +/- 22,26,47,49 zu bewegen. Geben Sie zukünftige Positionen in der Notation 1 ... 64 zurück, mit Ausnahme derjenigen, die von der zentralen Tafel fallen. Das TIO-Beispiel zeigt das Ergebnis mit einer 8x8-Matrix an.

NofP
quelle
Dies scheint im ersten Testfall zu scheitern (es werden 4 anstatt 2 Koordinaten zurückgegeben).
Zgarb
Vielen Dank, dass Sie Zgarb darauf hingewiesen haben. Ich glaube, ich habe das Problem jetzt
behoben
154 Bytes
Giuseppe
oder 148 Bytes, wenn Sie es [0...63]stattdessen in Notation nehmen.
Giuseppe
1
134 Bytes , [1..64]für die Eingabe und Ausgabe. +1, aber das ist eine ausgezeichnete Antwort.
Giuseppe