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 , 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
  • Are loopholes that received net negative ratings to be included among the official loopholes? – DavidC Apr 5 '17 at 12:46
  • @DavidC No. From the loophole question: "[...] the loophole described in any answer which is at +5 or above and has at least twice as many upvotes as downvotes may be taken to be deemed to be unacceptable to the community" – Martin Ender Apr 5 '17 at 12:48
  • Are we allowed to take a fifth input, which starts at 0 by default (the result)? Then I won't need to add (a,b,x,y)->c(a,b,x,y,0) (calling separated method c with the four arguments and 0 as fifth argument) to my answer. – Kevin Cruijssen Oct 16 '17 at 10:43
  • 3
    @KevinCruijssen No sorry. Additional, fixed arguments are a bit too easily abusable (and just allowing 0 as a special case seems weird). – Martin Ender Oct 16 '17 at 11:03
  • @MartinEnder Ok, thought so, but can never hurt asking. In that case my 190-byte answer remains. Even though I answered halve a year ago, one test case was failing. Came across the question again just now, and was able to fix the bug in my answer. – Kevin Cruijssen Oct 16 '17 at 11:39

11 Answers 11

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

  • That's... a lot of very small math operations... But couldn't you skip the n variable altogether and just add 1 to the result of each iteration? (90 chars I think) – ETHproductions Apr 4 '17 at 14:31
  • @ETHproductions To be honest, I posted it without any serious golfing. But that's definitely the first thing to do. Thanks! – Arnauld Apr 4 '17 at 14:36
  • 1
    Also, I think the operator precedence of & means you can do a+b+(b>d)&1 to save 2 bytes – ETHproductions Apr 4 '17 at 14:36
  • Got it down to 81, I think: 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 Apr 4 '17 at 14:50
  • I think it might be possible to save another byte using some clever currying. – Neil Apr 4 '17 at 14:52

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)))
  • 1
    Can you, please, explain this part: **(x^y^(Y>=y)) ? – Dead Possum Apr 5 '17 at 11:56
  • 1
    @DeadPossum Moving by a distance 1 vertically can take either 1 or 3 moves; there's no way to tell by just looking at parities so you have to compare the y values. – feersum Apr 6 '17 at 1:52

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

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\$.

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

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.
  • I'm not 100% sure, but can't you change the © to D and remove the ®? It seems to work for the case currently in your TIO, but I'm not sure if it follows the same path for every case. – Kevin Cruijssen Jun 25 at 11:49
  • 1
    @KevinCruijssen EDIT: No, because M's behaviour would be affected by this. Fails for [[0, 127], [0, 0]]. – Mr. Xcoder Jun 25 at 11:56

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 \$.

  • You can make it a one-liner by removing the newline – Jo King Jun 27 at 1:06
  • 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 Jun 27 at 6:19

Java 8, 157 190 188 144 142 141 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.

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<0?-z:z)     //   If the absolute difference between y2 and y1
       <(c<0?-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

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

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)

  • 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 Jun 27 at 7:46
  • @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 Jun 27 at 7:47
  • 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 Jun 27 at 13:59

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.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.