Dreieckige Manhattan Entfernung

26

Die Manhattan-Entfernung in einem regelmäßigen Raster ist die Anzahl der orthogonalen Schritte, die erforderlich sind, um eine Zelle von einer anderen zu erreichen. Orthogonale Schritte sind diejenigen, die durch die Kanten der Gitterzellen verlaufen (im Gegensatz zu den Ecken, die uns den Chebyshev-Abstand geben würden ).

Wir können einen ähnlichen Abstand für andere Gitter definieren, zum Beispiel für das Dreiecksgitter. Wir können die einzelnen Zellen im Raster mit dem folgenden Indizierungsschema ansprechen, wobei jede Zelle ein x,yPaar enthält :

    ____________________________________...
   /\      /\      /\      /\      /\
  /  \ 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\  /
   \/______\/______\/______\/______\/___...
   /\      /\      /\      /\      /\
  .  .    .  .    .  .    .  .    .  .
 .    .  .    .  .    .  .    .  .    .

Nun ist die Manhattan-Distanz in diesem Raster wieder die minimale Anzahl von Schritten über Kanten, um von einer Zelle zur anderen zu gelangen. So können Sie aus bewegen 3,1zu 2,1, 4,1oder 3,2, aber nicht auf anderes Dreieck, da diese Punkte überqueren würde , statt Kanten.

Zum Beispiel ist die Entfernung von 2,1zu 5,2ist 4. Der kürzeste Weg ist im Allgemeinen nicht eindeutig, aber eine Möglichkeit, die Entfernung in 4 Schritten zu ermitteln, ist:

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

Die Herausforderung

Geben Sie bei zwei Koordinatenpaaren und nach dem obigen Adressierungsschema den Manhattan-Abstand zwischen ihnen zurück.x1,y1x2,y2

Sie können davon ausgehen, dass alle vier Eingaben nicht negative Ganzzahlen mit jeweils weniger als 128 sind. Sie können diese in beliebiger Reihenfolge und willkürlich gruppieren (vier separate Argumente, eine Liste mit vier Ganzzahlen, zwei Paare von Ganzzahlen, eine 2x2-Matrix, ...). .).

Sie können ein Programm oder eine Funktion schreiben und eine der Standardmethoden zum Empfangen von Eingaben und zum Bereitstellen von Ausgaben verwenden.

Sie können jede Programmiersprache verwenden , beachten Sie jedoch, dass diese Lücken standardmäßig verboten sind.

Das ist , also gewinnt die kürzeste gültige Antwort - gemessen in Bytes .

Testfälle

Jeder Testfall wird als gegeben .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
quelle
Sollen Schlupflöcher, die negative Nettoratings erhalten haben, in die offiziellen Schlupflöcher aufgenommen werden?
DavidC
@DavidC Nein. Aus der Lückenfrage: "[...] Die in jeder Antwort beschriebene Lücke, die bei +5 oder höher liegt und mindestens doppelt so viele positive wie negative Stimmen hat, kann als für die Community inakzeptabel angesehen werden "
Martin Ender
Dürfen wir eine fünfte Eingabe machen, die standardmäßig bei 0 beginnt (das Ergebnis)? Dann muss ich meiner Antwort nicht hinzufügen (a,b,x,y)->c(a,b,x,y,0)(getrennte Methode cmit den vier Argumenten und 0als fünftes Argument aufrufen ).
Kevin Cruijssen
3
@ KevinCruijssen Nein, tut mir leid. Zusätzliche, feste Argumente sind etwas zu leicht zu missbrauchen (und nur 0 als Sonderfall zuzulassen, scheint seltsam).
Martin Ender
@MartinEnder Ok, dachte schon, kann aber nie weh tun zu fragen. In diesem Fall bleibt meine 190-Byte-Antwort bestehen. Obwohl ich vor einem Jahr halbiert geantwortet habe, ist ein Testfall fehlgeschlagen. Kam gerade wieder über die Frage und konnte den Fehler in meiner Antwort beheben.
Kevin Cruijssen

Antworten:

7

JavaScript (ES6), 84 bis 78 Byte

6 Bytes gespart dank 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)

Testfälle

Anfängliche rekursive Lösung, 100 88 81

Dank ETHproductions 12 Bytes gespart Dank Neil 7 Bytes gespart

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

Wie es funktioniert

Obwohl dies im Wesentlichen immer noch für die aktuelle Version gilt, bezieht sich die folgende Erläuterung genauer auf die ursprüngliche Version:

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)

Es ist trivial, von (x0, y) nach (x1, y) zu gehen, da wir die Seitenkanten vom Quellendreieck bis zum Zieldreieck überqueren können. Die Manhattan-Entfernung beträgt in diesem Fall | x0 - x1 | .

Der schwierige Teil sind die vertikalen Stufen. Um von Zeile y0 zu Zeile y1 zu gelangen , müssen diese beiden Parameter berücksichtigt werden:

  • Die Ausrichtung des aktuellen Dreiecks
  • Ob y0 kleiner oder größer als y1 ist

Die Ausrichtung eines Dreiecks ergibt sich aus der Parität von x + y :

  • Wenn es gerade ist, zeigt das Dreieck nach oben
  • Wenn es ungerade ist, zeigt das Dreieck nach unten

Wir können von einem nach oben weisenden Dreieck (nützlich, wenn y0 <y1 ) nach unten und von einem nach unten weisenden Dreieck (nützlich, wenn y0> y1 ) nach oben gehen.

Durch Kombinieren der Ausrichtung des Dreiecks mit dem Vergleich zwischen y0 und y1 erhalten wir die Formel x + y0 + (y0> y1? 1: 0), deren Ergebnis gerade ist, wenn wir in die gewünschte Richtung gehen können, und ungerade, wenn nicht.

Wenn wir die nächste Zeile nicht direkt erreichen können, müssen wir zuerst eine korrekte Ausrichtung erhalten, indem wir x aktualisieren :

  • Wenn x noch nicht gleich x1 ist , möchten wir uns definitiv in die richtige Richtung bewegen, also erhöhen wir es, wenn x kleiner als x1 ist, und verringern es, wenn x größer als x1 ist
  • Wenn x bereits gleich x1 ist , können wir es entweder inkrementieren oder dekrementieren

Testfälle

Arnauld
quelle
Das ist ... eine Menge sehr kleiner mathematischer Operationen ... Aber konnten Sie die nVariable nicht komplett überspringen und nur 1 zum Ergebnis jeder Iteration hinzufügen? ( 90 Zeichen, denke ich)
ETHproductions
@ETHproductions Um ehrlich zu sein, habe ich es ohne ernsthaftes Golfen gepostet. Aber das ist definitiv das Erste, was zu tun ist. Vielen Dank!
Arnauld
1
Ich denke auch, dass die Operator-Rangfolge &bedeutet, dass Sie a+b+(b>d)&12 Bytes einsparen können
ETHproductions
Ich glaube, es war 81.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,
Ich denke, es könnte möglich sein, ein weiteres Byte mit cleverem Curry zu speichern.
Neil
5

Python 2, 74 Bytes

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
quelle
1
Können Sie bitte erklären, diesen Teil: **(x^y^(Y>=y))?
Dead Possum
1
@DeadPossum Eine vertikale Bewegung um eine Strecke kann entweder 1 oder 3 Züge dauern. Es gibt keine Möglichkeit, anhand von Paritäten zu erkennen, weshalb Sie die y-Werte vergleichen müssen.
Feersum
2

Batch, 99 Bytes

@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

Erläuterung: Bei einer Bewegung nur für den Horizont wird einfach die absolute Differenz der x-Koordinaten berechnet. Bei ausreichend großen x-Werten benötigt die vertikale Bewegung nur einen zusätzlichen Schritt pro absoluter y-Koordinatendifferenz, bei kleinen x-Werten jedoch vier zusätzliche Schritte pro zwei y-Koordinatendifferenzen sowie einen oder drei Schritte für eine ungerade Differenz. Dies wird in zwei Schritten pro Differenz plus einem Korrekturfaktor berechnet. Das Ergebnis ist dann der größere der beiden korrigierten Schritte und die Summe der absoluten Differenzen, obwohl dies selbst als der größere der korrigierten absoluten y-Koordinatendifferenz und des absoluten x-Koordinatendistanz berechnet wird, die zu der nicht korrigierten absoluten y-Koordinatendifferenz addiert werden .

  • @cmd/cset/a" - Wertet kommagetrennte Ausdrücke aus und druckt den letzten
  • x=%3-%1,x*=x>>31|1x=|x2-x1|
  • y=%4-%2,w=y>>31,y*=w|1w=y1>y2y=|y2-y1|
  • z=x+(y+x&1)*(-(%1+%2+w&1)|1)-yc=(y+(xmod2))(1-2((x1+y1+w)mod2)),z=x+c-y
  • z*=z>>31,x+y+zmeinx(x,y-c)+y=x+y-michn(0,x+c-y)
Neil
quelle
2

Gelee , 24 Bytes

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

Probieren Sie es online!

(x,y),(X,Y.)

d=|y-Y.|+max(|x-X|,|y-Y.|+((x+y+X+Y.)mod-2)xy(Y.y))=|y-Y.|+max(|x-X|,|y-Y.|+[-(|x-X|+|y-Y.|mod2)]x+y+(Y.y))=max(|x-X|+|y-Y.|,2|y-Y.|+[-(|x-X|+|y-Y.|mod2)](Y.y)+x+y).

¢=(Y.y)+x+y

L=[|x-X|,|y-Y.|]Summe(L)f(L)f

L=[ein,b]-((ein+b)mod2)¢2b

Lynn
quelle
2

Schläger / Schema, 214 Bytes

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

05AB1E , 24 Byte

(x1,x2),(y1,y2)

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

Probieren Sie es online!

Nervenzusammenbruch

ÆÄ` © I˜OÉ (IøнOIθD {Q + m + M® + Vollprogramm. I repräsentiert den ausgewerteten Eingang.
ÆÄ Reduzieren Sie die Paare durch Subtraktion und nehmen Sie die absoluten Werte.
  `© Separat auf den Stapel legen und den zweiten ablegen
                            eins, | y1-y2 | im Register C.
    I˜O Schieben Sie die Summe der abgeflachten Eingaben auf den Stapel.
       (Nehmen Sie die Parität und negieren Sie sie.
         Drücken Sie [x1, y1].
            O Nimm x1 + y1 (summiere sie).
             IθD {Q Überprüfe dann, ob das zweite Paar sortiert ist (y1 ≤ y2).
                  + Und summiere das mit x1 + y1.
                   m Potenzieren. Schieben Sie die Parität über ** das Ergebnis.
                    + Und addiere den zweiten absoluten Unterschied dazu.
                     M® + Drücken Sie daher die größte Zahl auf dem Stapel
                            zuzüglich des in Register C gespeicherten Wertes.
Mr. Xcoder
quelle
Ich bin nicht 100% sicher, aber Sie können nicht das ändern ©zu Dund entfernen Sie das ®? Es scheint für den Fall in Ihrem TIO zu funktionieren, aber ich bin nicht sicher, ob es in jedem Fall den gleichen Weg geht.
Kevin Cruijssen
1
@KevinCruijssen EDIT : Nein, da Mdas Verhalten hiervon betroffen wäre. Scheitert für [[0, 127], [0, 0]].
Mr. Xcoder
2

Python 2 , 74 72 71 Bytes

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

Probieren Sie es online! Link enthält Testfälle. Bearbeiten: 2 Bytes dank @JoKing gespeichert. Dank @ Mr.Xcoder wurde ein weiteres Byte gespeichert. Basierend auf der folgenden Formel habe ich in dieser Frage gefunden :

|einich-bich|+|(einich-einj2)-(bich-bj2)|+|einj+12-bj+12|

12090

|einich-bich|+|(einich-einj+12)-(bich-bj+12)|+|einj2-bj2|

-einj+12=-einj2

Neil
quelle
Sie können es zu einem Einzeiler machen, indem Sie den Zeilenumbruch entfernen
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)sollte 3 Bytes sparen.
Mr. Xcoder
1

Pyth , 31 28 Bytes

(x1,x2),(y1,y2)

+eKaMQg#hK+eK^%ssQ_2+shCQSIe

Probieren Sie es hier aus! oder Testen Sie die Testsuite!

Nervenzusammenbruch

+ eKaMQg # hK + eK ^% ssQ_2xxFhCQSIe Vollständiges Programm. Q = eval (Eingabe ()).
  KaMQ Speichere die Differenzen [| x1-x2 |, | y1-y2 |] in K.
 e Rufen Sie letzteres ab (| y1-y2 |).
+ g # und addiere es zum größten Wert zwischen:
        hK - Der Kopf von K (| x1-x2 |)
          + - Und das Ergebnis des Hinzufügens:
           eK Das Ende von K (| y1-y2 |).
             ^ - mit dem Ergebnis der Potenzierung:
              % ssQ_2 Die Summe des abgeflachten Q, Modulo -2.
                                        Ergibt -1, wenn x1 + x2 + y1 + y2 ungerade ist, sonst 0.
                    xxFhCQSIe - nach dem Ergebnis dieses Ausdrucks:
                       hCQ Transponiere Q und nimm den Kopf (x1, y1).
                     xF Reduziere um bitweises XOR.
                          SIe Und prüfen Sie, ob die Liste [y1, y2] sortiert ist.
                    x Danach xoder das Ergebnis durch den Bool (0/1).
Mr. Xcoder
quelle
1

05AB1E , 16 Bytes

(x1,x2),(y1,y2)

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

Probieren Sie es online! oder Testen Sie die Testsuite! (Verwendet eine leicht modifizierte Version des Codes ( ®anstelle von ²), mit freundlicher Genehmigung von Kevin Cruijssen )

Mr. Xcoder
quelle
Gute Antwort! Nicht etwas zum Golfen, aber wenn Sie wechseln ©+®, ist DŠ+es einfacher, eine Testsuite einzurichten. ;) Hier ist diese Testsuite, und alle Testfälle sind in der Tat erfolgreich (ignorieren Sie den unordentlichen Header; p).
Kevin Cruijssen
@ KevinCruijssen Ich hatte das als alternative Version, aber es fiel mir nicht ein, dass ich eine Testsuite schreiben könnte ... Danke, ich werde es hinzufügen
Mr. Xcoder
1
@KevinCruijssen Ich habe zwei weitere (sehr offensichtliche ...!) Bytes entfernt und es geschafft, die Kompatibilität der Testsuite noch weiter zu verbessern. Deshalb habe ich sie so belassen: P Übrigens, danke für die Bearbeitung.
Mr. Xcoder
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) aufgrund einer Fehlerbehebung.
-44 Bytes (188 → 144) Konvertieren der rekursiven Methode in eine Einzelschleifenmethode.
-14 Bytes dank @ceilingcat .

Erläuterung:

Probieren Sie es hier aus.

(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
quelle
1
Schlagen Sie z*z<c*cstattdessen vor(z<0?-z:z)<(c<0?-c:c)
ceilingcat
@ceilingcat Ah, schön. Vielen Dank!
Kevin Cruijssen