Im Schach darf sich ein Ritter auf Gitter (x, y) nach (x-2, y-1), (x-2, y + 1), (x-1, y-2), (x-1, y + 2), (x + 1, y-2), (x + 1, y + 2), (x + 2, y-1), (x + 2, y + 1) in einem Schritt. Stellen Sie sich ein unendliches Schachbrett mit nur einem Ritter vor (0, 0):

Wie viele Schritte sind erforderlich, um einen Ritter von (0, 0) nach (t _x , t _y ) zu bewegen ?

Eingänge

Zwei ganze Zahlen: t _x , t _y ;

-100 <t _x <100, -100 <t _y <100

Ausgabe

Minimale Schritte, um einen Ritter von (0, 0) nach (t _x , t _y ) zu bewegen .

Regeln

• Code Golf

Testfälle

  x    y -> out
  0,   0 ->  0
  0,   1 ->  3
  0,   2 ->  2
  1,   1 ->  2
  1,   2 ->  1
  3,   3 ->  2
  4,   0 ->  2
 42,  22 -> 22
 84,  73 -> 53
 45,  66 -> 37
 99,  99 -> 66
-45, -91 -> 46
-81,   1 -> 42
 11,  -2 ->  7

document.write('<div>');[..."EFEDEDCDCBCBCBCBCBCBCBCBCBCBCBCBCBCDCDEDEFE;FEDEDCDCBCBABABABABABABABABABABABCBCDCDEDEF;EDEDCDCBCBABABABABABABABABABABABABCBCDCDEDE;DEDCDCBCBABA9A9A9A9A9A9A9A9A9A9ABABCBCDCDED;EDCDCBCBABA9A9A9A9A9A9A9A9A9A9A9ABABCBCDCDE;DCDCBCBABA9A9898989898989898989A9ABABCBCDCD;CDCBCBABA9A989898989898989898989A9ABABCBCDC;DCBCBABA9A98987878787878787878989A9ABABCBCD;CBCBABA9A9898787878787878787878989A9ABABCBC;BCBABA9A989878767676767676767878989A9ABABCB;CBABA9A98987876767676767676767878989A9ABABC;BABA9A9898787676565656565656767878989A9ABAB;CBA9A989878767656565656565656767878989A9ABC;BABA98987876765654545454545656767878989ABAB;CBA9A987876765654545454545456567678789A9ABC;BABA98987676565454343434345456567678989ABAB;CBA9A987876565454343434343454565678789A9ABC;BABA98987676545434323232343454567678989ABAB;CBA9A987876565434323232323434565678789A9ABC;BABA98987676545432341214323454567678989ABAB;CBA9A987876565434321232123434565678789A9ABC;BABA98987676545432323032323454567678989ABAB;CBA9A987876565434321232123434565678789A9ABC;BABA98987676545432341214323454567678989ABAB;CBA9A987876565434323232323434565678789A9ABC;BABA98987676545434323232343454567678989ABAB;CBA9A987876565454343434343454565678789A9ABC;BABA98987676565454343434345456567678989ABAB;CBA9A987876765654545454545456567678789A9ABC;BABA98987876765654545454545656767878989ABAB;CBA9A989878767656565656565656767878989A9ABC;BABA9A9898787676565656565656767878989A9ABAB;CBABA9A98987876767676767676767878989A9ABABC;BCBABA9A989878767676767676767878989A9ABABCB;CBCBABA9A9898787878787878787878989A9ABABCBC;DCBCBABA9A98987878787878787878989A9ABABCBCD;CDCBCBABA9A989898989898989898989A9ABABCBCDC;DCDCBCBABA9A9898989898989898989A9ABABCBCDCD;EDCDCBCBABA9A9A9A9A9A9A9A9A9A9A9ABABCBCDCDE;DEDCDCBCBABA9A9A9A9A9A9A9A9A9A9ABABCBCDCDED;EDEDCDCBCBABABABABABABABABABABABABCBCDCDEDE;FEDEDCDCBCBABABABABABABABABABABABCBCDCDEDEF;EFEDEDCDCBCBCBCBCBCBCBCBCBCBCBCBCBCDCDEDEFE"].forEach(c=>document.write(c==';'?'<br>':`<span class="d-${c}">${c}</span>`));
document.write('<style>body{line-height:16px;color:rgba(255,255,255,0.2);}span{display:inline-block;width:16px;font-size:16px;text-align:center;}div{white-space:pre;}');[...'0123456789ABCDEF'].map((c,i)=>document.write(`.d-${c}{background:hsl(${60-4*i},80%,${65-2*i}%)}`));

Verwandte OEIS

Hier sind einige OEIS zur weiteren Lektüre

• A018837 : Anzahl der Schritte, die der Springer auf dem unendlichen Schachbrett erreichen muss (n, 0).
• A018838 : Anzahl der Schritte, die der Springer auf dem unendlichen Schachbrett erreichen muss (n, n).
• A065775 : Von Diagonalen gelesenes Array T: T (i, j) = Mindestanzahl der Springerzüge auf einem Schachbrett (unendlich in alle Richtungen), die erforderlich sind, um von (0,0) nach (i, j) zu gelangen.
• A183041 : Die geringste Anzahl von Springerzügen von (0,0) nach (n, 1) auf einem unendlichen Schachbrett.

Wolfram Language (Mathematica) , 64 Byte

Verwendung des eingebauten KnightTourGraph.

2 Bytes dank Mathe172 gespart .

GraphDistance[KnightTourGraph@@({x,y}=Abs@{##}+4),y+2,(x-2)y-2]&

Probieren Sie es online!

JavaScript (ES6), 90 75 72 Byte

Inspiriert von der Formel für A065775 . Langsam für (nicht so) lange Strecken.

f=(x,y,z=x|y)=>z<0?f(-y,x):z>1?1+Math.min(f(x-1,y-2),f(x-2,y-1)):z*3^x&y

Probieren Sie es online!

Wie?

Wir definieren z als bitweises ODER zwischen x und y .

Schritt 1

Wir stellen zunächst sicher, dass wir uns in einem bestimmten Quadranten befinden, indem wir x und y zwingen , nicht negativ zu sein. Solange z <0 ist (was bedeutet, dass entweder x oder y negativ ist), verarbeiten wir den rekursiven Aufruf f (-y, x) :

(+1, -2) --> (+2, +1)
(-1, +2) --> (-2, -1) --> (+1, -2) --> (+2, +1)
(-1, -2) --> (+2, -1) --> (+1, +2)

Schritt 2

Während wir z> 1 haben (was bedeutet, dass entweder x oder y größer als 1 ist ), versuchen wir rekursiv die beiden Züge, die uns näher an (0, 0) bringen : f (x-1, y-2) und f ( x-2, y-1) . Wir halten schließlich den kürzesten Weg.

Schritt 3

Wenn z kleiner oder gleich 1 ist , bleiben uns 3 Möglichkeiten, die verarbeitet werden z*3^x&y(wir könnten z*3-x*ystattdessen verwenden):

• x & y == 1 impliziert x | y == 1 und bedeutet, dass x = y = 1 ist . Wir brauchen noch zwei Züge, um (0, 0) zu erreichen :

  

• x & y == 0 und x | y == 1 bedeutet, dass wir entweder x = 1 / y = 0 oder x = 0 / y = 1 haben . Wir brauchen drei weitere Züge, um (0, 0) zu erreichen :

  

• x & y == 0 und x | y == 0 bedeutet, dass wir bereits x = y = 0 haben .

_{Grafik von chess.com ausgeliehen}

Python 3 , 90 Bytes

Danke tsh für -11 Bytes!

def f(x,y):x=abs(x);y=abs(y);s=x+y;return(.9+max(x/4,y/4,s/6)-s/2+(s==1or x==y==2))//1*2+s

Probieren Sie es online!

(Inline-Code-Formatierung, damit die Leser nicht scrollen müssen. Tut mir leid, aber ich muss mein Programm spielen.)

Sehr sehr effizient.

Wie könnte ich darauf kommen?

1. Parität

Es wird davon ausgegangen, dass die gesamte Tafel im Schachbrettmuster eingefärbt ist (dh Zellen mit x+yungeraden und x+ygeraden Farben werden mit unterschiedlichen Farben eingefärbt).

Beachten Sie, dass jeder Schritt zwischen zwei verschiedenfarbigen Zellen springen muss. Deshalb:

• Die Parität der Anzahl der Schritte muss gleich der Parität von sein x+y.

2. Annäherung

Angenommen, der Springer startet von der Koordinate (0,0)und hat nSchritte bewegt und befindet sich derzeit auf (x,y).
Der Einfachheit halber wird davon ausgegangen x ≥ 0, y ≥ 0.
Wir können folgern:

• Da jeder Schritt xerhöht um höchstens 2, x ≤ 2×n. Ebenso y ≤ 2×n.
• Da jeder Schritt x+yerhöht um höchstens 3, x+y ≤ 3×n.

Deshalb, n ≥ l(x,y)wo l(x,y) = max(max(x,y)/2, (x+y)/3. (Beachten Sie, dass wir nicht -xoder x-yin die Formel aufnehmen müssen, weil nach Annahme,, x ≥ 0 and y ≥ 0so x+y ≥ max(x-y,y-x,-x-y)und x ≥ -x, y ≥ -y)

Es stellt sich heraus, dass dies a(x,y) = round(0.4 + l(x,y))eine gute Annäherung an ist n.

• Es sei angenommen, dass a(x,y)eine Annäherung mit einem Fehler kleiner ist als 1der korrekte Wert durch

  f(x,y) = round((a(x,y) - (x+y)) / 2) * 2 + (x+y)

  (runde unter subtrahieren x+yund dividieren durch 2)

3. Sonderfälle, die die Formel nicht erfüllen

Angenommen, x ≥ 0und y ≥ 0. Es gibt zwei Sonderfälle, in denen der Algorithmus fehlschlägt:

• x == 1 and y == 0oder x == 0 and y == 1: Der Algorithmus gibt fälschlicherweise zurück, 1während die richtige Antwort lautet 3.
• x == y == 2: Der Algorithmus gibt fälschlicherweise zurück, 2während die richtige Antwort lautet 4.

Also nur Sonderfälle. Addieren Sie das Ergebnis, indem Sie 2den Wert von xund yangeben.

Python 2 , 87 Bytes

f=lambda z,a={0}:1-({z}<=a)and-~f(z,{k+1j**i*(2-i/4*4+1j)for k in a for i in range(8)})

Probieren Sie es online!

Nimmt die Eingabe als komplexe Zahl z = complex(tx, ty).

TI-Basic, 86 54 Bytes

Basiert auf der älteren Lösung von @ user202729

Input :abs(X->C:abs(Y->D:C+Ans
Ans+2int(.9+(S=1 or C=2 and D=2)-.5Ans+max({C/4,D/4,Ans/6

MATL , 29 Bytes

`JEQ2J-htZjht_h@Z^2&sG=~}@Gg*

Die Eingabe ist eine komplexe Zahl mit ganzzahligen Real- und Imaginärteilen.

Der Code ist sehr ineffizient. Der Speicherbedarf steigt exponentiell mit der Ausgabe. Bei Testfällen mit einer Ausgabe von mehr als 7 tritt in TIO eine Zeitüberschreitung auf.

Probieren Sie es online!

Haskell, 79 72 Bytes

p l|elem(0,0)l=0|r<-[-2..2]=1+p[(x+i,y+j)|(x,y)<-l,i<-r,j<-r,(i*j)^2==4]

Probieren Sie es online!

Nimmt die Eingabe als Singleton-Liste von Zahlenpaaren.

Eine einfache rohe Kraft. Benötigt viel Zeit und Speicher für Ergebnisse.> 8. Füge beginnend mit einer einzelnen Element-Koordinatenliste (der Eingabe) wiederholt alle Positionen hinzu, die für jedes Element erreicht werden können, bis (0,0)es in dieser Liste enthalten ist. Behalten Sie die Rekursionsstufe im Auge und geben Sie sie als Ergebnis zurück.

Edit: -7 Bytes dank @Lynn.

JavaScript (ES6), 90 bis 78 Byte

f=(x,y)=>y<0?f(x,-y):x<y?f(y,x):x+y<3?4-x-y&3:x-3|y-1?x-4|y-3?f(x-2,y-1)+1:3:2

Bearbeiten: 12 Bytes dank @supercat gespeichert darauf hingewiesen x<0 entweder y<0oder impliziert x<y. Erläuterung: Dies ist eine rekursive Lösung. Die ersten beiden Bedingungen stellen nur den richtigen Quadranten für die anderen Bedingungen sicher. Die dritte Bedingung generiert die Antwort für Koordinaten in der Nähe des Ursprungs, während die letzten beiden Bedingungen die beiden anderen Sonderfälle behandeln (1 Byte kürzer als das Testen beider Züge):

0
32
2++
+2++
+++3+
++++++
(etc.)

Alle markierten Quadrate +können bestimmt werden, indem Sie sich direkt zum Ursprung bewegen und dann rekursiv vorgehen.

Kotlin , 148 146 140 Bytes

fun s(x:Int,y:Int):Int=if(y<0)s(x,-y)else
if(x<y)s(y,x)else if(x+y<3)4-x-y and 3
else if(x!=3||y!=1)if(x!=4||y!=3)s(x-2,y-1)+1
else 3 else 2

Probieren Sie es online!

Jelly , 27 26 25 23 Bytes

1,-pḤµ;UÆị
¢ṗS€;0i
0ç1#

Probieren Sie es online!

Sehr langsam; Zeitüberschreitung bei TIO für Ausgänge über 6. Übernimmt eine komplexe Zahl als Eingabe.

Erläuterung

Der Code verwendet komplexe Zahlen, weil er in einem Zwischenschritt kürzer war und auch viel schneller zu sein scheint. Sie könnten auch Paare durch Entfernen verwenden Æiund ersetzt 0mit 0,0der zweiten Zeile.

1,-pḤµ;UÆị    Helper link. No arguments.
1,-             Get the pair [1,-1].
    Ḥ           Double each to get [2,-2].
   p            Cartesian product: get [[1,2],[1,-2],[-1,2],[-1,-2]].
     µ          Start a new chain with the list of pairs as argument.
       U        Reverse each pair.
      ;         Append the reversed pairs to the list.
        Æi      Convert each pair [real,imag] to a complex number.

¢ṗS€;0i    Helper link. Arguments: iterations, target
¢            Call the previous link to get knight moves as complex numbers.
 ṗ           Get the iterations-th Cartesian power of the list. This will
             yield 8^n tuples containing move sequences.
  S€         Sum each move sequence to get the resulting square.
    ;0       Add the starting square, since the zeroth iteration results
             in no move sequences.
      i      Find the target squares (1-based) index in the results, or 0.

0ç1#    Main link. Argument: target
0         Starting from 0,
   #      find the
  1       first number of iterations where
 ç        calling the previous link results in a nonzero result.