Knight Entfernung

24

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.
tsh
quelle
Sie können eine Referenz der in oeis.org/A065775
tsh,
2
Kann ich eine komplexe Zahl x+yieingeben?
Lynn
1
@lynn Ich denke, es ist akzeptabel.
TSH
@ user202729 hat das Code-Snippet aktualisiert, um das Ergebnis anzuzeigen.
tsh
Eine sehr schöne Karte.
Willtech

Antworten:

11

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!

ArrayPlot @ Array [GraphDistance [KnightTourGraph @@ ({x, y} = Abs @ {##} + 5), 2y + 3, (x-2) y-2] & {65,65}, - 32]

Alephalpha
quelle
14
Mathematica builtins streiken erneut
qwr
1
Etwas kürzer:GraphDistance[KnightTourGraph@@({x,y}=Abs@{##}+5),2y+3,(x-2)y-2]&
Lukas Lang
Was ist mit dieser Sprache? Wie kommt es, dass all diese integrierten Komponenten vorinstalliert sind? Braucht der Versuch, eine Phrase mit tab zu vervollständigen, Ewigkeiten?
OganM
@OganM Mathematica unterstützt die automatische Vervollständigung in seiner Befehlszeilenschnittstelle nicht. Die automatische Vervollständigung in der Notebook - Schnittstelle sieht aus wie diese .
Alephalpha
1
@OganM Vielleicht verwenden die Entwickler eine Trie (Datenstruktur) oder nur eine binäre Suche in der Liste der sortierten eingebauten Elemente. Ja, warum lineare Suche? | Beachten Sie, dass Mathematica eine nicht freie Closed-Source-Sprache ist, sodass niemand weiß, wie der Prädiktor tatsächlich funktioniert. | Echte Programmierer brauchen keine automatische Vervollständigung. : P
user202729
7

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 :

    2 Züge

  • 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 :

    3 Züge

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

Grafik von chess.com ausgeliehen

Arnauld
quelle
5

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.

user202729
quelle
1
@tsh Das gilt aber auch für x==y==0.
user202729
Warum max(x+y,x-y,y-x)?
tsh
@tsh: Nein, siehe: x = -5, y = 5. x + y = 0, abs (xy) = 10 und daher x + y <abs (xy)
Nova
@Nova "Angenommen, x ≥ 0und y ≥ 0".
user202729
4

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).

Lynn
quelle
4

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
Timtech
quelle
2

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!

Luis Mendo
quelle
2

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.

nimi
quelle
72 Bytes
Lynn
1

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.

Neil
quelle
Benötigen Sie den x<0Test? Wenn man zB -3,6 annimmt, würde der x<yTest 6, -3 ergeben, der y<0Test würde 6,3 ergeben, und der x<yTest würde 3,6 ergeben.
Supercat
@supercat In der Tat, wie Python sagen würde, x>=y>=0...
Neil
1

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!

JohnWells
quelle
Ziemlich sicher, dass Sie den :IntRückgabetyp nicht angeben müssen.
am
Rekursive Funktionen erfordern einen Rückgabetyp, da der Compiler nicht schlau genug ist, um den Typ herauszufinden.
JohnWells
1
Oh, ich habe die rekursiven Aufrufe verpasst. Whoops
therealfarfetchd
1

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.
PurkkaKoodari
quelle