Triangular Manhattan Distance

26

La distance de Manhattan sur une grille régulière est le nombre de pas orthogonaux qu'il faut prendre pour atteindre une cellule à partir d'une autre. Les étapes orthogonales sont celles qui traversent les bords des cellules de la grille (par opposition aux coins, ce qui nous donnerait la distance de Chebyshev ).

On peut définir une distance similaire sur d'autres grilles, par exemple la grille triangulaire. Nous pouvons traiter les cellules individuelles de la grille avec le schéma d'indexation suivant, où chaque cellule contient une x,ypaire:

    ____________________________________...
   /\      /\      /\      /\      /\
  /  \ 1,0/  \ 3,0/  \ 5,0/  \ 7,0/  \
 / 0,0\  / 2,0\  / 4,0\  / 6,0\  / 8,0\
/______\/______\/______\/______\/______\...
\      /\      /\      /\      /\      /
 \ 0,1/  \ 2,1/  \ 4,1/  \ 6,1/  \ 8,1/
  \  / 1,1\  / 3,1\  / 5,1\  / 7,1\  /
   \/______\/______\/______\/______\/___...
   /\      /\      /\      /\      /\
  /  \ 1,2/  \ 3,2/  \ 5,2/  \ 7,2/  \
 / 0,2\  / 2,2\  / 4,2\  / 6,2\  / 8,2\  
/______\/______\/______\/______\/______\...
\      /\      /\      /\      /\      /
 \ 0,3/  \ 2,3/  \ 4,3/  \ 6,3/  \ 8,3/
  \  / 1,3\  / 3,3\  / 5,3\  / 7,3\  /
   \/______\/______\/______\/______\/___...
   /\      /\      /\      /\      /\
  .  .    .  .    .  .    .  .    .  .
 .    .  .    .  .    .  .    .  .    .

Maintenant, la distance de Manhattan sur cette grille est à nouveau le nombre minimal d'étapes à travers les bords pour passer d'une cellule à l'autre. Vous pouvez donc passer de 3,1à 2,1, 4,1ou 3,2, mais pas à n'importe quel autre triangle, car ce sont des points de croisement plutôt que des bords.

Par exemple, la distance de 2,1à 5,2est 4. Le chemin le plus court n'est généralement pas unique, mais une façon de faire la distance en 4 étapes est:

2,1 --> 3,1 --> 3,2 --> 4,2 --> 5,2

Le défi

Étant donné deux paires de coordonnées et à partir du schéma d'adressage ci-dessus, renvoyez la distance Manhattan entre elles.x1,y1x2,y2

Vous pouvez supposer que les quatre entrées sont des entiers non négatifs, chacun inférieur à 128. Vous pouvez les prendre dans n'importe quel ordre et regroupés arbitrairement (quatre arguments distincts, une liste de quatre entiers, deux paires d'entiers, une matrice 2x2, .. .).

Vous pouvez écrire un programme ou une fonction et utiliser l'une des méthodes standard de réception d'entrée et de sortie.

Vous pouvez utiliser n'importe quel langage de programmation , mais notez que ces failles sont interdites par défaut.

Il s'agit de , donc la réponse valide la plus courte - mesurée en octets - l'emporte.

Cas de test

Chaque cas de test est donné sous la forme .x1,y1 x2,y2 => result

1,2 1,2 => 0
0,1 1,1 => 1
1,0 1,1 => 3
2,1 5,2 => 4
0,0 0,127 => 253
0,0 127,0 => 127
0,0 127,127 => 254
0,127 127,0 => 254
0,127 127,127 => 127
127,0 127,127 => 255
75,7 69,2 => 11
47,58 36,79 => 42
77,9 111,23 => 48
123,100 111,60 => 80
120,23 55,41 => 83
28,20 91,68 => 111
85,107 69,46 => 123
16,25 100,100 => 159
62,85 22,5 => 160
92,26 59,113 => 174
62,22 35,125 => 206
Martin Ender
la source
Les failles qui ont reçu des notes négatives nettes doivent-elles être incluses parmi les failles officielles?
DavidC
@DavidC No. D'après la question de l'échappatoire: "[...] l'échappatoire décrite dans toute réponse qui est à +5 ou au-dessus et qui a au moins deux fois plus de votes positifs que de votes négatifs peut être considérée comme inacceptable pour la communauté "
Martin Ender
Sommes-nous autorisés à prendre une cinquième entrée, qui commence à 0 par défaut (le résultat)? Ensuite, je n'aurai pas besoin d'ajouter (a,b,x,y)->c(a,b,x,y,0)(appel de la méthode séparée cavec les quatre arguments et 0comme cinquième argument) à ma réponse.
Kevin Cruijssen
3
@KevinCruijssen Non désolé. Les arguments supplémentaires et fixes sont un peu trop facilement exploitables (et autoriser simplement 0 comme cas spécial semble étrange).
Martin Ender
@MartinEnder Ok, c'est ce que je pensais, mais je n'ai jamais de mal à demander. Dans ce cas, ma réponse de 190 octets reste. Même si j'ai répondu de moitié il y a un an, un cas de test échouait. Je suis revenu sur la question tout à l'heure et j'ai pu corriger le bogue dans ma réponse.
Kevin Cruijssen

Réponses:

7

JavaScript (ES6), 84 78 octets

6 octets enregistrés grâce à Neil

(a,b,c,d,x=a>c?a-c:c-a,y=b>d?b-d:d-b,z=x>y?x:y)=>y+z+(x+z&1?a+b+(b>d)&1||-1:0)

Cas de test

Solution récursive initiale, 100 88 81

12 octets enregistrés grâce à ETHproductions
7 octets enregistrés grâce à Neil

f=(a,b,c,d,e=b==d|a+b+(b>d)&1)=>a-c|b-d&&f(e?a+1-2*(a>c):a,e?b:b+1-2*(b>d),c,d)+1

Comment ça marche

Bien qu'elle s'applique toujours essentiellement à la version actuelle, l'explication suivante se réfère plus spécifiquement à la version initiale:

f=(a,b,c,d)=>b-d?a+b+(b>d)&1?f(a+1-2*(a>c),b,c,d)+1:f(a,b+1-2*(b>d),c,d)+1:Math.abs(a-c)

Passer de (x0, y) à (x1, y) est trivial car nous pouvons traverser les bords latéraux tout le long du triangle source jusqu'au triangle cible. La distance de Manhattan dans ce cas est | x0 - x1 | .

La partie délicate est les étapes verticales. Pour passer de la ligne y0 à la ligne y1 , nous devons prendre en compte ces deux paramètres:

  • L'orientation du triangle actuel
  • Si y0 est inférieur ou supérieur à y1

L'orientation d'un triangle est donnée par la parité de x + y :

  • s'il est pair, le triangle pointe vers le haut
  • si c'est étrange, le triangle pointe vers le bas

On peut descendre d'un triangle pointant vers le haut (utile quand y0 <y1 ) et monter d'un triangle pointant vers le bas (utile quand y0> y1 ).

En combinant l'orientation du triangle avec la comparaison entre y0 et y1 , nous obtenons la formule x + y0 + (y0> y1? 1: 0) dont le résultat est même si nous pouvons aller dans la direction souhaitée et impair sinon.

Si nous ne pouvons pas atteindre directement la ligne suivante, nous devons d'abord obtenir un alignement correct en mettant à jour x :

  • si x n'est pas encore égal à x1 , nous voulons vraiment nous déplacer dans la bonne direction, donc nous l'incrémentons si x est inférieur à x1 et nous le décrémentons si x est supérieur à x1
  • si x est déjà égal à x1 , nous pouvons l'incrémenter ou le décrémenter

Cas de test

Arnauld
la source
C'est ... beaucoup de très petites opérations mathématiques ... Mais ne pourriez-vous pas ignorer la nvariable et ajouter simplement 1 au résultat de chaque itération? ( 90 caractères je pense)
ETHproductions
@ETHproductions Pour être honnête, je l'ai posté sans aucun golf sérieux. Mais c'est définitivement la première chose à faire. Merci!
Arnauld
1
En outre, je pense que la priorité de l'opérateur &signifie que vous pouvez faire a+b+(b>d)&1pour économiser 2 octets
ETHproductions
Je suis descendu à 81, je pense: f=(a,b,c,d,e=b==d|a+b+(b>d)&1)=>a-c|b-d&&f(e?a+1-2*(a>c):a,e?b:b+1-2*(b>d),c,d)+1
Neil
Je pense qu'il pourrait être possible d'enregistrer un autre octet en utilisant un curry intelligent.
Neil
5

Python 2, 74 octets

lambda x,y,X,Y:abs(y-Y)+max(x-X,X-x,abs(y-Y)+((x+y+X+Y)%-2)**(x^y^(Y>=y)))
feersum
la source
1
Pouvez-vous, s'il vous plaît, expliquer cette partie **(x^y^(Y>=y)):?
Dead Possum
1
@DeadPossum Un déplacement vertical de 1 peut prendre 1 ou 3 mouvements; il n'y a aucun moyen de le dire en regardant simplement les parités, vous devez donc comparer les valeurs y.
feersum
2

Lot, 99 octets

@cmd/cset/a"x=%3-%1,x*=x>>31|1,y=%4-%2,w=y>>31,y*=w|1,z=x+(y+x&1)*(-(%1+%2+w&1)|1)-y,z*=z>>31,x+y+z

Explication: Un mouvement uniquement horizontal ne prend que la différence absolue de coordonnées x. Pour un assez grand x, le mouvement vertical ne prend qu'un pas supplémentaire par différence absolue de coordonnées y, mais pour un petit x, il faut quatre pas supplémentaires pour deux différences de coordonnées y, plus un ou trois pas pour une différence impaire. Ceci est calculé en deux étapes par différence plus un facteur de correction. Le plus grand des deux pas corrigés et la somme des différences absolues est alors le résultat, bien que cela soit lui-même calculé comme le plus grand de la différence de coordonnée y absolue corrigée et de la distance de coordonnée x absolue ajoutée à la différence de coordonnée y absolue non corrigée .

  • @cmd/cset/a" - Évalue les expressions séparées par des virgules et imprime la dernière
  • x=%3-%1,x*=x>>31|1x=|x2x1|
  • y=%4-%2,w=y>>31,y*=w|1w=y1>y2y=|y2y1|
  • z=x+(y+x&1)*(-(%1+%2+w&1)|1)-yc=(y+(xmod2))(12((x1+y1+w)mod2)),z=x+cy
  • z*=z>>31,x+y+zmax(x,yc)+y=x+ymin(0,x+cy)
Neil
la source
2

Gelée , 24 octets

⁴<³¬Ḋ;³S
SḂN*¢+ḊḤ$
ạµS»Ç

Essayez-le en ligne!

(x,y),(X,Y)

d=|yY|+max(|xX|,|yY|+((x+y+X+Y)mod2)xy(Yy))=|yY|+max(|xX|,|yY|+[(|xX|+|yY|mod2)]x+y+(Yy))=max(|xX|+|yY|,2|yY|+[(|xX|+|yY|mod2)](Yy)+x+y).

¢=(Yy)+x+y

L=[|xX|,|yY|]sum(L)f(L)f est la fonction sur la ligne médiane.

L=[a,b]((a+b)mod2)¢2b .

Lynn
la source
2

raquette / schéma, 214 octets

(define(f x y X Y)(let m((p x)(q y)(c 0))
(let((k(+ c 1))(d(- Y q)))
(cond((= 0(- X p)d)c)
((and(> d 0)(even?(+ p q)))(m p(+ q 1)k))
((and(< d 0)(odd?(+ p q)))(m p(- q 1)k))
((< p X)(m(+ p 1)q k))
(else(m(- p 1)q k))))))
Kevin
la source
2

05AB1E , 24 octets

Port de ma réponse Pyth , qui à son tour utilise à peu près la même approche que la réponse Python de feersum . Prend l'entrée comme une liste de paires de coordonnées,(X1,X2),(y1,y2). Correction d'un bug pour +1 octet, puis correction d'une autre erreur pour +1, mais qui donnait le résultat correct pour tous les cas de test ...

ÆÄ`©I˜OÉ(IøнOIθD{Q+m+M®+

Essayez-le en ligne!

Panne

ÆÄ` © I˜OÉ (IøнOIθD {Q + m + M® + programme complet. I représente l'entrée évaluée.
ReduceÄ Réduisez les paires par soustraction, prenez les valeurs absolues.
  `© Videz-les séparément sur la pile et stockez le second
                            un, | y1-y2 | dans le registre C.
    I˜O Poussez la somme des entrées aplaties sur la pile.
       É (Prenez sa parité et niez-la.
         Appuyez sur [x1, y1].
            O Prenez x1 + y1 (additionnez-les).
             IθD {Q Vérifiez ensuite si la deuxième paire est triée (y1 ≤ y2).
                  + Et additionnez cela avec x1 + y1.
                   m Exponentiate. Poussez la parité au-dessus ** du résultat.
                    + Et ajoutez la deuxième différence absolue à cela.
                     M® + En conséquence, poussez le plus grand nombre sur la pile
                            plus la valeur stockée dans le registre C.
M. Xcoder
la source
Je ne suis pas sûr à 100%, mais ne peux pas vous changer ©pour Det supprimer la ®? Cela semble fonctionner pour le cas actuellement dans votre TIO, mais je ne sais pas s'il suit le même chemin pour chaque cas.
Kevin Cruijssen
1
@KevinCruijssen EDIT : Non, car Mle comportement de cela en serait affecté. Échoue pour [[0, 127], [0, 0]].
M. Xcoder
2

Python 2 , 74 72 71 octets

lambda c,a,d,b:abs(a-b)+abs(a+(-c-a)/2-b-(-d-b)/2)+abs((c+a)/2-(d+b)/2)

Try it online! Link includes test cases. Edit: Saved 2 bytes thanks to @JoKing. Saved a further byte thanks to @Mr.Xcoder. Based on the following formula I found in this question:

|aibi|+|(aiaj2)(bibj2)|+|aj+12bj+12|

The coordinate systems differ in three ways; the coordinates are exchanged (which explains my somewhat strange parameter name order), the coordinates are angled at 120 rather than 90 (which explains the two additions) and the coordinates in the linked question use inferior 1-indexing. Since we're taking differences this cancels out most of the time and we are left with:

|aibi|+|(aiaj+12)(bibj+12)|+|aj2bj2|

This can then be golfed by noting that aj+12=aj2.

Neil
la source
You can make it a one-liner by removing the newline
Jo King
1
lambda c,a,d,b:abs(a-b)+abs(a+-(c+a)/2-b--(d+b)/2)+abs((c+a)/2-(d+b)/2) should save 3 bytes.
Mr. Xcoder
1

Pyth, 31 28 bytes

Uses roughly the same approach as in feersum's Python answer. Takes input as a list of pairs of coordinates, (x1,x2),(y1,y2). Fixed a bug for -1 byte.

+eKaMQg#hK+eK^%ssQ_2+shCQSIe

Try it here! or Try the test suite!

Breakdown

+eKaMQg#hK+eK^%ssQ_2xxFhCQSIe     Full program. Q = eval(input()).
  KaMQ                            Store the differences [|x1-x2|, |y1-y2|] in K.
 e                                Retrieve the latter (|y1-y2|).
+     g#                          And add it to the greatest value between:
        hK                          - The head of K (|x1-x2|)
          +                         - And the result of adding:
           eK                           The end of K (|y1-y2|).
             ^                      - with the result of exponentiating:
              %ssQ_2                    The sum of the flattened Q, modulo -2.
                                        Yields -1 if x1+x2+y1+y2 is odd, 0 otherwise.
                    xxFhCQSIe       - by the result of this expression:
                       hCQ              Transpose Q and get the head (x1, y1).
                     xF                 Reduce by bitwise XOR.
                          SIe           And check if the list [y1, y2] is sorted.
                    x                   After which, xor the result by the bool (0/1).
Mr. Xcoder
la source
1

05AB1E, 16 bytes

Uses a modified version of Neil's answer, optimised for stack-based languages like 05AB1E. Takes input as two pairs of coordinates, (x1,x2),(y1,y2), separated by a newline from STDIN. Initially I merged that with my other 05AB1E answer but then decided to post it separately because it's very, very different.

+D(‚2÷Æ`²Æ©+®)ÄO

Try it online! or Try the test suite! (Uses a slightly modified version of the code (® instead of ²), courtesy of Kevin Cruijssen)

Mr. Xcoder
la source
Nice answer! Not something to golf, but when you change ©+® to DŠ+ it's easier to set up a test suite. ;) Here is that test suite, and all test cases are indeed succeeding (ignore the messy header ;p).
Kevin Cruijssen
@KevinCruijssen I had that as an alternate version, but it didn't occur to me that I could write a test suite... Thanks, I'll add it
Mr. Xcoder
1
@KevinCruijssen I golfed off two more (very obvious...!) bytes, and succeeded breaking the test suite compatibility even more, so I kept it as-is :P Thanks for the edit, by the way.
Mr. Xcoder
1

Jelly, 22 .. 16 15 bytes

ṭH,‘H_ɗɗ@+¥ḞIAS

Try it online!

Try all test cases.

Uses @Neil's method in this answer which uses a modified formula from this math.SE question.

Takes the coordinates as arguments y1, y2 and x1, x2.

dylnan
la source
1

Java 8, 157 190 188 144 142 141 127 bytes

(a,b,x,y)->{int r=0,c=1,z=1;for(;(c|z)!=0;r--){c=x-a;z=y-b;if((z<0?-z:z)<(c<0?-c:c)|a%2!=b%2?z<0:z>0)b+=z<0?-1:1;else a+=c<0?-1:1;}return~r;}

+33 bytes (157 → 190) due to a bug fix.
-44 bytes (188 → 144) converting the recursive method to a single looping method.
-14 bytes thanks to @ceilingcat.

Explanation:

Try it here.

(a,b,x,y)->{          // Method with four integers as parameter and integer return-type
                      // (a=x1; b=y1; x=x2; y=y2)
  int r=0,            //  Result-integer `r`, starting at 0
      c=1,z=1;        //  Temp integers for the differences, starting at 1 for now
  for(;(c|z)!=0;      //  Loop until both differences are 0
      r--){           //    After every iteration: decrease the result `r` by 1
    c=x-a;            //   Set `c` to x2 minus x1
    z=y-b;            //   Set `z` to y2 minus y1
    if(z*Z            //   If the absolute difference between y2 and y1
       <c*c)          //   is smaller than the absolute difference between x2 and x1
       |a%2!=b%2?     //   OR if the triangle at the current location is facing downwards
         z<0          //       and we have to go upwards,
        :z>0)         //      or it's facing upwards and we have to go downwards
      b+=z<0?-1:1;    //    In/decrease y1 by 1 depending on where we have to go
    else              //   Else:
     a+=c<0?-1:1;}    //    In/decrease x1 by 1 depending on where we have to go
  return~r;           //  Return `-r-1` as result
Kevin Cruijssen
la source
1
Suggest z*z<c*c instead of (z<0?-z:z)<(c<0?-c:c)
ceilingcat
@ceilingcat Ah, nice one. Thanks!
Kevin Cruijssen