Triangular Manhattan Distance

Question

The Manhattan distance on a regular grid is the number of orthogonal steps one needs to take to reach one cell from another. Orthogonal steps are those that go through the edges of the grid cells (as opposed to the corners, which would give us the Chebyshev distance).

We can define a similar distance on other grids, for example the triangular grid. We can address the individual cells in the grid with the following indexing scheme, where each cell contains an x,y pair:

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

Now the Manhattan distance on this grid is again the minimal number of steps across edges to get from one cell to another. So you can move from 3,1 to 2,1, 4,1 or 3,2, but not to any other triangle, since those would be crossing points rather than edges.

For instance, the distance from 2,1 to 5,2 is 4. The shortest path is generally not unique, but one way to make the distance in 4 steps is:

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

The Challenge

Given two coordinate pairs x1,y1 and x2,y2 from the above addressing scheme, return the Manhattan distance between them.

You may assume that all four inputs are non-negative integers, each less than 128. You may take them in any order and arbitrarily grouped (four separate arguments, a list of four integers, two pairs of integers, a 2x2 matrix, ...).

You may write a program or a function and use any of the standard methods of receiving input and providing output.

You may use any programming language, but note that these loopholes are forbidden by default.

This is code-golf, so the shortest valid answer – measured in bytes – wins.

Test Cases

Each test case is given as 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

Answer 1

JavaScript (ES6), 84 78 bytes

Saved 6 bytes thanks to 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)

Test cases

let f =

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

console.log(f(  1,  2,  1,  2)); // => 0
console.log(f(  0,  1,  1,  1)); // => 1
console.log(f(  1,  0,  1,  1)); // => 3
console.log(f(  2,  1,  5,  2)); // => 4
console.log(f(  0,  0,  0,127)); // => 253
console.log(f(  0,  0,127,  0)); // => 127
console.log(f(  0,  0,127,127)); // => 254
console.log(f(  0,127,127,  0)); // => 254
console.log(f(  0,127,127,127)); // => 127
console.log(f(127,  0,127,127)); // => 255
console.log(f( 75,  7, 69,  2)); // => 11
console.log(f( 47, 58, 36, 79)); // => 42
console.log(f( 77,  9,111, 23)); // => 48
console.log(f(123,100,111, 60)); // => 80
console.log(f(120, 23, 55, 41)); // => 83
console.log(f( 28, 20, 91, 68)); // => 111
console.log(f( 85,107, 69, 46)); // => 123
console.log(f( 16, 25,100,100)); // => 159
console.log(f( 62, 85, 22,  5)); // => 160
console.log(f( 92, 26, 59,113)); // => 174
console.log(f( 62, 22, 35,125)); // => 206

Initial recursive solution, 100 88 81

Saved 12 bytes thanks to ETHproductions
Saved 7 bytes thanks to 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

How it works

Although it still essentially applies to the current version, the following explanation more specifically refers to the initial 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)

Going from (x0, y) to (x1, y) is trivial because we can go across lateral edges all the way from the source triangle to the target one. The Manhattan distance in this case is | x0 - x1 |.

The tricky part is the vertical steps. To go from row y0 to row y1, we have to take these two parameters into account:

• The orientation of the current triangle
• Whether y0 is less or greater than y1

The orientation of a triangle is given by the parity of x + y:

• if it's even, the triangle is up-pointing
• if it's odd, the triangle is down-pointing

We can go downwards from an up-pointing triangle (useful when y0 < y1) and upwards from a down-pointing triangle (useful when y0 > y1).

By combining the orientation of the triangle with the comparison between y0 and y1, we get the formula x + y0 + (y0 > y1 ? 1 : 0) whose result is even if we can go in the desired direction and odd if not.

If we can't reach the next row directly, we first need to get a correct alignment by updating x:

• if x is not yet equal to x1, we definitely want to move in the correct direction, so we increment it if x is less than x1 and we decrement it if x is greater than x1
• if x already equals x1, we can either increment or decrement it

Test cases

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)

console.log(f(  1,  2,  1,  2)); // => 0
console.log(f(  0,  1,  1,  1)); // => 1
console.log(f(  1,  0,  1,  1)); // => 3
console.log(f(  2,  1,  5,  2)); // => 4
console.log(f(  0,  0,  0,127)); // => 253
console.log(f(  0,  0,127,  0)); // => 127
console.log(f(  0,  0,127,127)); // => 254
console.log(f(  0,127,127,  0)); // => 254
console.log(f(  0,127,127,127)); // => 127
console.log(f(127,  0,127,127)); // => 255
console.log(f( 75,  7, 69,  2)); // => 11
console.log(f( 47, 58, 36, 79)); // => 42
console.log(f( 77,  9,111, 23)); // => 48
console.log(f(123,100,111, 60)); // => 80
console.log(f(120, 23, 55, 41)); // => 83
console.log(f( 28, 20, 91, 68)); // => 111
console.log(f( 85,107, 69, 46)); // => 123
console.log(f( 16, 25,100,100)); // => 159
console.log(f( 62, 85, 22,  5)); // => 160
console.log(f( 92, 26, 59,113)); // => 174
console.log(f( 62, 22, 35,125)); // => 206

Answer 2

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

Answer 3

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

Explanation: A horizonal-only motion simply takes the absolute x-coordinate difference. For large enough x, the vertical motion only takes one extra step per absolute y-coordinate difference, but for small x, it takes four extra steps per two y-coordinate difference, plus one or three steps for an odd difference. This is calcluated as two steps per difference plus a correction factor. The larger of the corrected two steps and the sum of absolute differences is then the result, although this is itself calculated as the larger of the corrected absolute y-coordinate difference and the absolute x-coordinate distance added to the uncorrected absolute y-coordinate difference.

• @cmd/cset/a" - Evaluates comma-separated expressions and prints the last one
• x=%3-%1,x*=x>>31|1 Calculates \$x=|x_2-x_1|\$
• y=%4-%2,w=y>>31,y*=w|1 Calculates \$w=y_1>y_2\$ and \$y=|y_2-y_1|\$
• z=x+(y+x&1)*(-(%1+%2+w&1)|1)-y Correction factor \$c=(y+(x\bmod2))(1-2((x_1+y_1+w)\bmod2)), z=x+c-y\$
• z*=z>>31,x+y+z Calculates \$max(x,y-c)+y = x+y-min(0,x+c-y)\$

Answer 4

05AB1E, 24 bytes

Port of my Pyth answer, which in turn uses roughly the same approach as feersum's Python answer. Takes input as a list of pairs of coordinates, \$(x_1, x_2), (y_1, y_2)\$. Fixed a bug for +1 byte, then fixed another mistake for +1, but which yielded the correct result for all test cases...

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

Try it online!

Breakdown

ÆÄ`©I˜OÉ(IøнOIθD{Q+m+M®+    Full program. I represents the evaluated input.
ÆÄ                          Reduce the pairs by subtraction, take the absolute values.
  `©                        Dump them separately onto the stack and store the second
                            one, |y1-y2| in the register C.
    I˜O                     Push the sum of flattened input onto the stack.
       É(                   Take its parity and negate it.
         Iøн                Push [x1, y1].
            O               Take x1+y1 (sum them).
             IθD{Q          Then check if the second pair is sorted (y1 ≤ y2).
                  +         And sum that with x1+y1.
                   m        Exponentiate. Push the parity above ** the result.
                    +       And add the second absolute difference to that.
                     M®+    As a result, push the largest number on the stack
                            plus the value stored in register C.

Answer 5

Jelly, 24 bytes

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

Try it online!

Let’s call the input \$(x,y),(X,Y)\$. I worked from feersum's formula:

\begin{align*} d &= |y-Y|+\max(|x-X|,|y-Y|+((x+y+X+Y)\bmod -2)^{x \oplus y \oplus (Y \geq y)}) \\ &= |y-Y|+\max(|x-X|,|y-Y|+[-(|x-X|+|y-Y| \bmod 2)]^{x + y + (Y \not< y)}) \\ &= \max(|x-X|+|y-Y|,2|y-Y|+[-(|x-X|+|y-Y| \bmod 2)]^{(Y \not< y) + x + y}). \end{align*}

The first line computes \$¢ = (Y \not< y)+x+y\$, the exponent in the formula.

The last line first computes \$L=[|x-X|, |y-Y|]\$ and then computes the maximum of \$\text{sum}(L)\$ and \$f(L)\$, where \$f\$ is the function on the middle line.

The middle line, given \$L=[a, b]\$, computes \$-((a+b)\bmod 2)\$, takes that to the \$¢\$'th power, then adds \$2b\$.

Answer 6

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)

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:

$$ \left|a_i-b_i\right|\;+\;\left|\left(a_i-\left\lfloor\frac{a_j}2\right\rfloor\right)-\left(b_i-\left\lfloor\frac{b_j}2\right\rfloor\right)\right|\;+\;\left|\left\lfloor\frac{a_j+1}2\right\rfloor-\left\lfloor\frac{b_j+1}2\right\rfloor\right| $$

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^\circ\$ rather than \$90^\circ\$ (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:

$$ \left|a_i-b_i\right|\;+\;\left|\left(a_i-\left\lfloor\frac{a_j+1}2\right\rfloor\right)-\left(b_i-\left\lfloor\frac{b_j+1}2\right\rfloor\right)\right|\;+\;\left|\left\lfloor\frac{a_j}2\right\rfloor-\left\lfloor\frac{b_j}2\right\rfloor\right| $$

This can then be golfed by noting that \$ -\lfloor\frac{a_j+1}2\rfloor = \lfloor\frac{-a_j}2\rfloor \$.

Answer 7

racket/scheme, 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))))))

Answer 8

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

Answer 9

Pyth, 31 28 bytes

Uses roughly the same approach as in feersum's Python answer. Takes input as a list of pairs of coordinates, \$(x_1, x_2), (y_1, y_2)\$. 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).

Answer 10

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.

Answer 11

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, \$(x_1, x_2), (y_1, y_2)\$, 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)}}