Distance du chevalier

24

Aux échecs, un chevalier sur la grille (x, y) peut se déplacer vers (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) en une seule étape. Imaginez un échiquier infini avec seulement un chevalier (0, 0):

Combien d'étapes faut-il pour déplacer un chevalier de (0, 0) à (t x , t y )?

Contributions

Deux entiers: t x , t y ;

-100 <t x <100, -100 <t y <100

Sortie

Pas minimum pour déplacer un chevalier de (0, 0) à (t x , t y ).

Règles

  • golf de code

Cas de test

  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}%)}`));

OEIS apparenté

Voici quelques OEIS pour plus de lecture

  • A018837 : Nombre d'étapes que le chevalier peut atteindre (n, 0) sur l'échiquier infini.
  • A018838 : Nombre de marches à atteindre par le chevalier (n, n) sur l'échiquier infini.
  • A065775 : Tableau T lu par des diagonales: T (i, j) = nombre minimum de mouvements de chevalier sur un échiquier (infini dans toutes les directions) nécessaires pour passer de (0,0) à (i, j).
  • A183041 : Le plus petit nombre de mouvements de chevalier de (0,0) à (n, 1) sur l'échiquier infini.
tsh
la source
Vous pouvez prendre une référence de la formule donnée dans oeis.org/A065775
tsh
2
Puis-je prendre l'entrée comme un nombre complexe x+yi?
Lynn
1
@lynn je pense que c'est acceptable.
tsh
@ user202729 a mis à jour l'extrait de code pour afficher le résultat.
tsh
Une carte très fine.
Willtech

Réponses:

11

Wolfram Language (Mathematica) , 64 octets

Utilisation du intégré KnightTourGraph.

Enregistré 2 octets grâce à Mathe172 .

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

Essayez-le en ligne!

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

alephalpha
la source
14
Les buildins de Mathematica frappent à nouveau
qwr
1
Légèrement plus court:GraphDistance[KnightTourGraph@@({x,y}=Abs@{##}+5),2y+3,(x-2)y-2]&
Lukas Lang
Quelle est cette langue? Comment se fait-il que tous ces éléments intégrés soient préchargés? Est-ce que tenter de compléter une phrase avec tabulation prend du temps?
OganM
@OganM Mathematica ne prend pas en charge la complétion automatique dans son interface de ligne de commande. La complétion automatique dans l'interface du notebook ressemble à ceci .
alephalpha
1
@OganM Peut-être que les développeurs utilisent un Trie (structure de données), ou simplement une recherche binaire sur la liste des éléments intégrés triés. Oui, pourquoi la recherche linéaire? | Notez que Mathematica est un langage de source fermée non libre, donc personne ne sait comment le prédicteur fonctionne réellement. | Les vrais programmeurs n'ont pas besoin de saisie semi-automatique. : P
user202729
7

JavaScript (ES6), 90 75 72 octets

Inspiré par la formule donnée pour A065775 . Lent comme l'enfer pour (pas si) de longues distances.

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

Essayez-le en ligne!

Comment?

Nous définissons z comme OR au niveau du bit entre x et y .

Étape 1

Nous nous assurons d'abord que nous sommes situés dans un quadrant spécifique en forçant x et y à être non négatifs. Tant que z <0 (ce qui signifie que x ou y est négatif), nous traitons l'appel récursif f (-y, x) :

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

Étape 2

Alors que nous avons z> 1 (ce qui signifie que x ou y est supérieur à 1 ), nous essayons récursivement les deux mouvements qui nous rapprochent de (0, 0) : f (x-1, y-2) et f ( x-2, y-1) . Nous gardons finalement le chemin le plus court.

Étape 3

Lorsque z est inférieur ou égal à 1 , il nous reste 3 possibilités qui sont traitées avecz*3^x&y (nous pourrions utiliser à la z*3-x*yplace):

  • x & y == 1 implique x | y == 1 et signifie que x = y = 1 . Nous avons besoin de deux mouvements supplémentaires pour atteindre (0, 0) :

    2 coups

  • x & y == 0 et x | y == 1 signifie que nous avons soit x = 1 / y = 0 ou x = 0 / y = 1 . Nous avons besoin de trois mouvements supplémentaires pour atteindre (0, 0) :

    3 coups

  • x & y == 0 et x | y == 0 signifie que nous avons déjà x = y = 0 .

Graphiques empruntés à chess.com

Arnauld
la source
5

Python 3 , 90 octets

Merci tsh pour -11 octets!

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

Essayez-le en ligne!

(formatage de code en ligne pour éviter aux lecteurs d'avoir à faire défiler. Désolé, mais je dois jouer à mon programme)

Très très efficace.


Comment pourrais-je trouver ça!?

1. Parité

Suppose que toute la planche est colorée dans le motif en damier (c'est-à-dire que les cellules x+yimpaires et x+ypaires sont colorées avec des couleurs différentes).

Notez que chaque étape doit sauter entre deux cellules de couleurs différentes. Par conséquent:

  • La parité du nombre de pas doit être égale à la parité de x+y.

2. Approximation

Suppose que le chevalier commence à partir des coordonnées (0,0), a déplacé des npas et se trouve actuellement à (x,y).
Par souci de simplicité, suppose x ≥ 0, y ≥ 0.
On peut conclure:

  • Étant donné que chaque étape xaugmente d'au plus 2, x ≤ 2×n. De même,y ≤ 2×n .
  • Étant donné que chaque étape x+yaugmente d'au plus 3, x+y ≤ 3×n.

Par conséquent, n ≥ l(x,y)l(x,y) = max(max(x,y)/2, (x+y)/3. (notez que nous n'avons pas besoin d'inclure -xou x-ydans la formule parce que par hypothèse,, x ≥ 0 and y ≥ 0ainsi x+y ≥ max(x-y,y-x,-x-y)et x ≥ -x,y ≥ -y )

Il s'avère que a(x,y) = round(0.4 + l(x,y))c'est une bonne approximation de n.

  • Supposons qu'il a(x,y)s'agit d'une approximation avec une erreur inférieure à 1, la valeur correcte est donnée par

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

    (arrondir sous soustraire x+yet diviser par 2)

3. Cas particuliers qui ne respectent pas la formule

Supposons x ≥ 0et y ≥ 0. Il y a 2 cas particuliers où l'algorithme échoue:

  • x == 1 and y == 0ou x == 0 and y == 1: l'algorithme renvoie incorrectement 1alors que la bonne réponse est 3.
  • x == y == 2: L'algorithme renvoie incorrectement 2alors que la bonne réponse est 4.

Donc, juste cas particulier ceux-là. Ajoutez le résultat par 2si la valeur de xet en yfait partie.

user202729
la source
1
@tsh Mais c'est vrai x==y==0aussi.
user202729
Pourquoi max(x+y,x-y,y-x)?
tsh
@tsh: Non, voir: x = -5, y = 5. x + y = 0, abs (xy) = 10 et donc x + y <abs (xy)
Nova
@Nova "Supposons x ≥ 0et y ≥ 0".
user202729
4

Python 2 , 87 octets

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

Essayez-le en ligne!

Prend l'entrée comme un nombre complexe z = complex(tx, ty).

Lynn
la source
4

TI-Basic, 86 54 octets

Basé sur l'ancienne solution de @ 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
la source
2

MATL , 29 octets

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

L'entrée est un nombre complexe avec des parties réelles et imaginaires entières.

Le code est très inefficace. Ses besoins en mémoire augmentent de façon exponentielle avec la sortie. Il expire dans TIO pour les cas de test avec une sortie supérieure à 7.

Essayez-le en ligne!

Luis Mendo
la source
2

Haskell, 79 72 octets

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]

Essayez-le en ligne!

Prend l'entrée comme une liste singleton de paires de nombres.

Une force brute simple. Nécessite beaucoup de temps et de mémoire pour les résultats> 8. En commençant par une seule liste d'éléments de coordonnées (l'entrée), ajoutez à plusieurs reprises toutes les positions qui peuvent être atteintes pour chaque élément jusqu'à(0,0) soit dans cette liste. Gardez une trace du niveau de récursivité et renvoyez-le comme résultat.

Edit: -7 octets grâce à @Lynn.

nimi
la source
72 octets
Lynn
1

JavaScript (ES6), 90 78 octets

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

Edit: 12 octets enregistrés grâce à @supercat qui x<0indique que cela implique soit y<0ou x<y. Explication: Il s'agit d'une solution récursive. Les deux premières conditions assurent simplement le bon quadrant pour les autres conditions. La troisième condition génère la réponse pour les coordonnées proches de l'origine, tandis que les deux dernières conditions traitent des deux autres cas spéciaux (1 octet de moins que le test des deux mouvements):

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

Tous les carrés marqués +peuvent être déterminés en se déplaçant directement vers l'origine, puis en revenant.

Neil
la source
Avez-vous besoin du x<0test? Étant donné, par exemple, -3,6, le x<ytest transformerait cela en 6, -3, que le y<0test transformerait en 6,3, que le x<ytest transformerait en 3,6.
supercat
@supercat En effet, comme dirait Python, x>=y>=0...
Neil
1

Kotlin , 148 146 140 octets

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

Essayez-le en ligne!

JohnWells
la source
Je suis sûr que vous n'avez pas besoin :Intde spécifier le type de retour.
therealfarfetchd du
Les fonctions récursives nécessitent un type de retour car le compilateur n'est pas assez intelligent pour comprendre le type.
JohnWells
1
Oh, j'ai raté les appels récursifs. Oups
therealfarfetchd
1

Gelée , 27 26 25 23 octets

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

Essayez-le en ligne!

Très lent; expire sur TIO pour les sorties supérieures à 6. Prend un nombre complexe en entrée.

Explication

Le code utilise des nombres complexes car il était plus court dans une étape intermédiaire et il semble également beaucoup plus rapide; vous pouvez également utiliser des paires en supprimant Æiet en remplaçant0 par 0,0sur la deuxième ligne.

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
la source