Wie viele Züge?

16

Geben Sie bei zwei verschiedenen Positionen auf einem Schachbrett und der Art der Figur die minimale Anzahl von Zügen aus, die diese Figur benötigt, um von einer Position zur nächsten zu gelangen.

Regeln

Das gegebene Stück kann König, Königin, Turm, Ritter und Bischof sein. (Diese Eingabe kann als 5 beliebige eindeutige Zeichen verwendet werden.)

Die 2 Positionen können in jedem beliebigen Format eingenommen werden.

Example:
a8 b8 c8 d8 ... h8
a7 b7 c7 d7 ... h7
...
...
a1 b1 c1 d1 ... h1

Falls das Stück nicht dorthin gelangen kann, geben Sie etwas anderes als eine positive ganze Zahl aus.

Beispiele

i/p ---- o/p
King
a1,a4    3
a1,h6    7
b3,h5    6

Queen
a1,a4    1
a1,h6    2
b3,f7    1

Rook
a1,a4    1
a1,h6    2
h2,c7    2

Knight
a1,a4    3
a1,h6    4
b2,d3    1
b2,c3    2
b3,c3    3
a1,b2    4

Bishop
a1,a4    -1
a1,h6    2
b2,d3    -1
e1,h4    1
Vedant Kandoi
quelle
1
Warum braucht King 12 zu a1-h6? Kann König nicht Diag gehen?
14 m²,
@ 14m2, korrigiert
Vedant Kandoi
1
@ngn, Sie können 0 verwenden, um die Nichterreichbarkeit anzuzeigen. Die beiden Positionen sind immer unterschiedlich.
Vedant Kandoi
1
Einige Definitionen (z. B. ISO-80000-2) für natürliche Zahlen enthalten 0. Es wird empfohlen, durch "positive ganze Zahl" zu ersetzen.

Antworten:

9

JavaScript (Node.js) , 183 180 179 Byte

with(Math)(a,b,c,d,t,x=abs(a-c),y=abs(b-d),v=x<y?y:x,q=0|.9+max(/[18][18]/.test(a+b+9+c+d)-v?x/2:3,y/2,x*y?x*y-4?(x+y)/3:3:2))=>t?t==2&x+y?0:t&1>x*y|t/2&x==y?1:t<4?2:v:q+(q+x+y&1)

Probieren Sie es online!

Vielen Dank an Arnauld für die Prüfung. Ritterprüfung

l4m2
quelle
@ Arnauld Nun Ecke wirklich kosten
l4m2
Ich denke, Sie könnten ein Byte retten, indem Sie das letzte maxdurch ein ternäres ersetzen .
Shaggy
170 Bytes (Ich denke, ich bin auf meinem Handy.)
Shaggy
@ Shaggy war das, was Arnauld darauf hinwies, dass es falsch war
l4m2
6

APL (Dyalog Classic) , 117 107 105 103 98 97 95 92 89 87 Byte

{(⍎⍺⊃'⌈/' '≢∘∪~∘0' '+/×' '{⍺∊⍵:0⋄1+⍺∇i/⍨∨⌿2=|×/↑⍵∘.-i←,⍳8 8}/,¨⊂¨↓⍵' '≢∘∪×2=.|⊢')⊣|-⌿⍵}

Probieren Sie es online!

linkes Argument ist Stückart: 0 = König, 1 = Königin, 2 = Turm, 3 = Ritter, 4 = Bischof; Das rechte Argument ist eine 2x2-Matrix von Koordinaten, wobei jede Zeile eine Position darstellt. gibt 0 für nicht erreichbar zurück

|-⌿⍵ berechnet das Paar [abs (∆x), abs (∆y)]

(⍎⍺⊃... )⊣wählt einen Ausdruck aus der Liste "..."; Wenn es eine Funktion ist, wird sie angewendet |-⌿⍵; Wenn es sich um einen Wert handelt (dies gilt nur für einen Ritter), geben Sie diesen stattdessen zurück|-⌿⍵

  • König: max ( ⌈/) der abs ∆-s

  • Königin: Entferne Nullen ( ~∘0) und zähle ( ) einzigartig ( )

  • Turm: Summe ( +/) von Signa (monadisch ×; 0 für 0, 1 für positiv)

  • Ritter: {⍺∊⍵:0⋄1+⍺∇i/⍨∨⌿2=|×/↑⍵∘.-i←,⍳8 8}/,¨⊂¨↓⍵- Beginne mit der Anfangsposition und berechne rekursiv Generationen von Ritterzügen, bis die Endposition im Satz ist; Rekursionstiefe zurückgeben

  • bischof: sind die paritäten der beiden gleich? ( 2=.|⊢, äquivalent zu =/2|⊢) multipliziere das boolesche Ergebnis (0 oder 1) mit dem count-unique ( ≢∘∪)

ngn
quelle
Ich liebe das ⍎⍺⊃. Sehr schlau.
J. Sallé
@ J.Sallé Danke
ngn
2

Java (JDK) , 229 Byte

(p,a,b,c,d)->{c^=a/4*7;a^=a/4*7;d^=b/4*7;b^=b/4*7;int x=c<a?a-c:c-a,y=d<b?b-d:d-b,z=(x^=y^(y=y<x?y:x))-y;return p<1?x:p<2?z*y<1?1:2:p<3?2-z%2:p<4?x+y<2?3:(a<c?a+b:c+d)+x<2|x==2&z<1?4:z+2*Math.ceil((y-z)/(y>z?3:4.)):z<1?1:~z*2&2;}

Probieren Sie es online!

Erklärungen

  • Das Board ist ein 0-basiertes Board.
  • Der zurückgegebene Wert ist eine Ganzzahl, die als Double dargestellt wird. Es wird niemals einen Dezimalteil geben.

Code:

(p,a,b,c,d)->{                          // double-returning lambda.
                                        // p is the piece-type (0: king, 1: queen, 2: rook, 3: knight, 4: bishop)
                                        // a is the origin-X
                                        // b is the origin-Y
                                        // c is the destination-X
                                        // d is the destination-Y
 c^=a/4*7;a^=a/4*7;                     // Mirror board if origin is in the top part of the board
 d^=b/4*7;b^=b/4*7;                     // Mirror board if origin is in the left part of the board
 int x=c<a?a-c:c-a,                     // x is the X-distance between a and c
     y=d<b?b-d:d-b,                     // y is the Y-distance between b and d
     z=(x^=y^(y=y<x?y:x))-y;            // z is the delta between x and y
                                        // also, swap x and y if necessary so that x is the greater value.
               //    At this point,
               //     x      cannot be 0 (because the two positions are different)
               //     z<1    means the origin and destination are on the same diagonal
               //     y<1    means the origin and destination are on the same horizontal/vertical line
 return
  p<1?x:                                //  For a king, just take the max distance.
  p<2?z*y<1?1:2:                        //  For a queen, just move once if in direct line, or twice.
  p<3?2-z%2:                            //  For a rook, just move once if on the same horizontal or vertical line, or twice
  p<4?                                  //  For a knight, 
   x+y<2?3:                             //   Hardcode 3 if moving to the next horizontal/vertical square
   (a<c?a+b:c+d)+x<2|x==2&z<1?4:        //   Hardcode 4 if moving 2 cases in diagonal or one case in diagonal in a corner.
   z+2*Math.ceil((y-z)/(y>z?3:4.)):     //   Compute the number of moves necessary for the usual cases
  z<1?1:                                //  For a bishop, hardcode 1 if they are on the same diagonal
   ~z*2&2;                              //   Return 2 if they have the same parity else 0.
}

Credits

  • -2 Bytes danke an Arnauld und auch dafür, dass ich gemerkt habe, dass ich ein Problem mit all meinen Eckfällen hatte.
Olivier Grégoire
quelle
1

Kohle , 108 Bytes

F…β⁸F⁸⊞υ⁺ι⊕κ≔⟦⟦η⟧⟧δW¬№§δ±¹ζ⊞δΦυΦ§δ±¹⁼⁵ΣEμX⁻℅ξ℅§κπ²≔Eη↔⁻℅ι℅§ζκε≡θKI⌈εQI∨∨¬⌊ε⁼⊟ε⊟ε²RI∨¬⌊ε²BI∧¬﹪Σε²∨⁼⊟ε⊟ε²NI⊖Lδ

Probieren Sie es online! Link ist eine ausführliche Version des Codes. Erläuterung:

F…β⁸F⁸⊞υ⁺ι⊕κ

Listen Sie alle 64 Felder der Tafel in der vordefinierten leeren Listenvariablen auf.

≔⟦⟦η⟧⟧δ

Erstellen Sie eine Liste von Listen, deren erster Eintrag eine Liste mit der Startposition ist.

W¬№§δ±¹ζ

Wiederholen, bis der letzte Eintrag der Liste die Endposition enthält.

⊞δΦυΦ§δ±¹⁼⁵ΣEμX⁻℅ξ℅§κπ²

Filtern Sie alle Brettpositionen, die ein Ritter von einem Eintrag im letzten Eintrag der Listenliste entfernt hat, und verschieben Sie diese Liste in die Listenliste. Dies schließt Positionen ein, die zuvor besucht wurden, an denen wir uns jedoch ohnehin nicht interessiert haben, sodass wir am Ende eine umfassende erste Suche des Boards nach der Endposition durchführen.

≔Eη↔⁻℅ι℅§ζκε

Berechnen Sie die absoluten Koordinatendifferenzen zwischen Start- und Endposition.

≡θ

Wählen Sie basierend auf dem Eingabestück.

KI⌈ε

Wenn es ein König ist, dann drucken Sie die maximale absolute Koordinatendifferenz.

QI∨∨¬⌊ε⁼⊟ε⊟ε²

Wenn es sich um eine Dame handelt, drucken Sie 2, es sei denn, die beiden Unterschiede sind gleich oder einer ist Null.

RI∨¬⌊ε²

Wenn es sich um einen Turm handelt, drucken Sie 2, es sei denn, einer der Unterschiede ist Null.

BI∧¬﹪Σε²∨⁼⊟ε⊟ε²

Wenn es ein Läufer ist, dann drucke 0, wenn die Quadrate von entgegengesetzter Parität sind, andernfalls drucke 2, es sei denn, die beiden Unterschiede sind gleich.

NI⊖Lδ

Wenn es ein Ritter ist, drucken Sie die Anzahl der Schleifen, um die Endposition zu finden.

Neil
quelle
1

Japt , 67 Bytes

®ra
g[_rw}_â è}@=ã ü;@pUÌïVõ á ÈíaY})Ìde[TT]}a Ä}_è}_ra v *Zâ l}]gV

Probieren Sie es online!

Das war eine ziemliche Erfahrung. Ich habe mich sehr von der hervorragenden APL-Antwort inspirieren lassen . Ich vermute, dass gerade im Knight-Code noch viel Golf möglich ist.

Die Positionen sind die erste Eingabe im Formular [[x1,x2],[y1,y2]]. Es sollte auch gut funktionieren [[y1,y2],[x1,x2]]. Die Teileauswahl ist die zweite Eingabe, mit 0 = König, 1 = Dame, 2 = Ritter, 3 = Turm, 4 = Bischof. Beachten Sie, dass Ritter und Turm im Vergleich zur APL-Antwort vertauscht sind.

Erläuterung:

®ra         :Turn absolute positions into relative movement and store in U
®           : For each of X and Y
 ra         : Get the absolute difference between the start position and the end position

g[...]gV    :Apply the appropriate function
 [...]      : A list of functions
      gV    : Get the one indicated by the second input
g           : Apply it to U

_rw}        :King function
 rw         : Get the maximum of X and Y

_â è}       :Queen function
 â          : Get unique elements
   è        : Count non-zero elements

@=ã ü;@pUÌï2õ á ÈíaY})Ìde[TT]}a Ä}  :Knight function
 =ã ü;                              : Wrap U twice (U -> [[U]])
      @                      }a Ä   : Repeat until True; return number of tries:
        UÌ                          :  Get the previous positions
          ï                         :  Cartesian product with:
           2õ                       :   The range [1,2]
              á                     :   All permutations, i.e. [[1,2],[2,1]]
                ÈíaY})              :  Apply each move to each position
       p                            :  Store the new positions
                      Ìde[TT]       :  True if any are at the destination

_è}         :Rook function
 è          : Count non-zero elements

_ra v *Zâ l}    :Bishop function
 ra             : Absolute difference between X and Y
    v           : Is divisible by 2? (returns 1 or 0)
      *         : Times:
       Zâ       :  Get the unique elements
          l     :  Count them
Kamil Drakari
quelle
@ETHproductions Gute Vorschläge. Während ich sie einfügte, stellte ich fest, dass ásich das Ergebnis [[1,2][2,1]]erheblich verkürzte .
Kamil Drakari
Wow, hätte nie gedacht zu benutzen á, nette!
ETHproductions
Noch ein paar Vorschläge: UIst nach implizit @, so dass Sie zwei Bytes in der Ritterfunktion speichern können. Sie können es auch mit starten @=ã ü;, um ein anderes zu speichern. (Der ãTrick ist auch klug :-))
ETHproductions
@ETHproductions Gute Entdeckung, die Zeiten, in denen U impliziert ist, sind eines der Dinge, die ich noch nicht vollständig verstanden habe.
Kamil Drakari