26

La distancia de Manhattan en una cuadrícula regular es la cantidad de pasos ortogonales que uno debe tomar para llegar a una celda desde otra. Los pasos ortogonales son aquellos que pasan por los bordes de las celdas de la cuadrícula (a diferencia de las esquinas, lo que nos daría la distancia de Chebyshev ).

Podemos definir una distancia similar en otras cuadrículas, por ejemplo, la cuadrícula triangular. Podemos abordar las celdas individuales en la cuadrícula con el siguiente esquema de indexación, donde cada celda contiene un x,ypar:

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

Ahora, la distancia de Manhattan en esta cuadrícula es nuevamente el número mínimo de pasos a través de los bordes para llegar de una celda a otra. Por lo que puede pasar de 3,1a 2,1, 4,1o 3,2, pero no a cualquier otro triángulo, ya que los cruzaría puntos en lugar de los bordes.

Por ejemplo, la distancia de 2,1a 5,2es 4. El camino más corto generalmente no es único, pero una forma de hacer la distancia en 4 pasos es:

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

El reto

Dados dos pares de coordenadas y del esquema de direccionamiento anterior, devuelva la distancia de Manhattan entre ellos.x₁,y₁x₂,y₂

Puede suponer que las cuatro entradas son enteros no negativos, cada uno menor que 128. Puede tomarlos en cualquier orden y agruparlos arbitrariamente (cuatro argumentos separados, una lista de cuatro enteros, dos pares de enteros, una matriz de 2x2, .. .).

Puede escribir un programa o una función y utilizar cualquiera de los métodos estándar para recibir entradas y proporcionar salidas.

Puede usar cualquier lenguaje de programación , pero tenga en cuenta que estas lagunas están prohibidas por defecto.

Este es el código de golf , por lo que gana la respuesta válida más corta, medida en bytes .

Casos de prueba

Cada caso de prueba se da como .x₁,y₁ x₂,y₂ => 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

code-golf geometry path-finding hexagonal-grid Martin Ender
fuente

¿Se incluirán las lagunas que recibieron calificaciones negativas netas entre las lagunas oficiales?

DavidC

@DavidC No. De la pregunta del vacío legal: "el [...] vacío legal descrito en cualquier respuesta que esté en +5 o más y tenga al menos el doble de votos positivos que los votos negativos se puede considerar inaceptable para la comunidad "

Martin Ender

¿Se nos permite tomar una quinta entrada, que comienza en 0 por defecto (el resultado)? Entonces no necesitaré agregar (a,b,x,y)->c(a,b,x,y,0)(llamando al método separado ccon los cuatro argumentos y 0como quinto argumento) a mi respuesta.

Kevin Cruijssen

3

@KevinCruijssen No lo siento. Los argumentos fijos adicionales son demasiado fáciles de abusar (y solo permitir 0 como caso especial parece extraño).

Martin Ender

@MartinEnder Ok, eso creo, pero nunca puede hacer daño preguntar. En ese caso, mi respuesta de 190 bytes permanece. Aunque respondí a la mitad hace un año, un caso de prueba estaba fallando. Encontré la pregunta nuevamente en este momento y pude corregir el error en mi respuesta.

Kevin Cruijssen

7

JavaScript (ES6), 84 78 bytes

Guardado 6 bytes gracias a 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)

Casos de prueba

Mostrar fragmento de código

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

Expand snippet

Solución recursiva inicial, 100 88 81

Guardado 12 bytes gracias a ETHproductions
Guardado 7 bytes gracias a 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

Cómo funciona

Aunque todavía se aplica esencialmente a la versión actual, la siguiente explicación se refiere más específicamente a la versión inicial:

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)

Pasar de (x0, y) a (x1, y) es trivial porque podemos atravesar los bordes laterales desde el triángulo de origen hasta el objetivo. La distancia de Manhattan en este caso es | x0 - x1 | .

La parte difícil son los pasos verticales. Para pasar de la fila y0 a la fila y1 , tenemos que tener en cuenta estos dos parámetros:

La orientación del triángulo actual.
Si y0 es menor o mayor que y1

La orientación de un triángulo viene dada por la paridad de x + y :

si es par, el triángulo está apuntando hacia arriba
si es extraño, el triángulo está apuntando hacia abajo

Podemos ir hacia abajo desde un triángulo apuntando hacia arriba (útil cuando y0 <y1 ) y hacia arriba desde un triángulo apuntando hacia abajo (útil cuando y0> y1 ).

Al combinar la orientación del triángulo con la comparación entre y0 e y1 , obtenemos la fórmula x + y0 + (y0> y1? 1: 0) cuyo resultado es incluso si podemos ir en la dirección deseada e impar si no.

Si no podemos llegar directamente a la siguiente fila, primero debemos obtener una alineación correcta actualizando x :

si x aún no es igual a x1 , definitivamente queremos movernos en la dirección correcta, por lo que lo incrementamos si x es menor que x1 y lo disminuimos si x es mayor que x1
si x ya es igual a x1 , podemos aumentarlo o disminuirlo

Casos de prueba

Mostrar fragmento de código

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

Expand snippet

Arnauld
fuente

Eso es ... muchas operaciones matemáticas muy pequeñas ... ¿Pero no podría omitir la nvariable por completo y simplemente agregar 1 al resultado de cada iteración? ( 90 caracteres , creo)

ETHproductions

@ETHproductions Para ser honesto, lo publiqué sin ningún tipo de golf serio. Pero eso es definitivamente lo primero que hay que hacer. ¡Gracias!

Arnauld

1

Además, creo que la precedencia del operador &significa que puede hacer a+b+(b>d)&1para guardar 2 bytes

ETHproductions

Lo bajé a 81, creo: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

Creo que podría ser posible guardar otro byte usando un curry inteligente.

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
fuente

1

¿Puede, por favor, explicar esta parte **(x^y^(Y>=y))?

Dead Possum el

1

@DeadPossum Moverse por una distancia 1 verticalmente puede tomar 1 o 3 movimientos; no hay forma de saberlo simplemente mirando paridades, por lo que debe comparar los valores de y.

feersum

2

Lote, 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

Explicación: Un movimiento de solo horizontes simplemente toma la diferencia absoluta de coordenadas x. Para x lo suficientemente grande, el movimiento vertical solo toma un paso adicional por diferencia absoluta de coordenadas y, pero para x pequeño, toma cuatro pasos adicionales por dos diferencias de coordenadas y, más uno o tres pasos para una diferencia impar. Esto se calcula como dos pasos por diferencia más un factor de corrección. El resultado es el mayor de los dos pasos corregidos y la suma de las diferencias absolutas, aunque esto se calcula como el mayor de la diferencia de coordenadas y absoluta absoluta corregida y la distancia absoluta de coordenadas x añadida a la diferencia de coordenadas y absoluta absoluta sin corregir .

@cmd/cset/a" - Evalúa expresiones separadas por comas e imprime la última.
x=%3-%1,x*=x>>31|1 $x=|x_2-x_1|$
y=%4-%2,w=y>>31,y*=w|1 $w=y_1>y_2$ $y=|y_2-y_1|$
z=x+(y+x&1)*(-(%1+%2+w&1)|1)-y $c=(y+(x\bmod2))(1-2((x_1+y_1+w)\bmod2)), z=x+c-y$
z*=z>>31,x+y+z $max(x,y-c)+y = x+y-min(0,x+c-y)$

Neil
fuente

2

Jalea , 24 bytes

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

Pruébalo en línea!

$(x,y),(X,Y)$

\begin{aligned} d & = | y - Y | + max (| x - X |, | y - Y | + ((x + y + X + Y) mod - 2)^{x \oplus y \oplus (Y \geq y)}) \\ = | y - Y | + max (| x - X |, | y - Y | + [- (| x - X | + | y - Y | mod 2)]^{x + y + (Y ≮ y)}) \\ = max (| x - X | + | y - Y |, 2 | y - Y | + [- (| x - X | + | y - Y | mod 2)]^{(Y ≮ y) + x + y}) . \end{aligned}

$\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*}$

$¢ = (Y \not< y)+x+y$

$L=[|x-X|, |y-Y|]$ $\text{sum}(L)$ $f(L)$ $f$

$L=[a, b]$ $-((a+b)\bmod 2)$ $¢$ $2b$

Lynn
fuente

2

raqueta / esquema, 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
fuente

2

05AB1E , 24 bytes

$(x_1, x_2), (y_1, y_2)$

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

Pruébalo en línea!

Descompostura

ÆÄ` © I˜OÉ (IøнOIθD {Q + m + M® + Programa completo. I representa la entrada evaluada.
ÆÄ Reduzca los pares por sustracción, tome los valores absolutos.
  `© Volcarlos por separado en la pila y almacenar el segundo
                            uno, | y1-y2 | en el registro C.
    I˜O Empuje la suma de la entrada aplanada en la pila.
       É (toma su paridad y lo niega.
         Iøн Push [x1, y1].
            O Tomar x1 + y1 (sumarlos).
             IθD {Q Luego verifique si el segundo par está ordenado (y1 ≤ y2).
                  + Y suma eso con x1 + y1.
                   m Exponenciar. Empuje la paridad por encima ** del resultado.
                    + Y agregue la segunda diferencia absoluta a eso.
                     M® + Como resultado, empuja el número más grande en la pila
                            más el valor almacenado en el registro C.

Sr. Xcoder
fuente

No estoy 100% seguro, pero no se puede cambiar el ©a Dy retire el ®? Parece funcionar para el caso actualmente en su TIO, pero no estoy seguro si sigue el mismo camino para cada caso.

Kevin Cruijssen

1

@KevinCruijssen EDITAR : No, porque Mel comportamiento se vería afectado por esto. Falla por [[0, 127], [0, 0]].

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

Pruébalo en línea! El enlace incluye casos de prueba. Editar: Guardado 2 bytes gracias a @JoKing. Salvó un byte adicional gracias a @ Mr.Xcoder. Basado en la siguiente fórmula que encontré en esta pregunta :

| a_{i} - b_{i} | + | (a_{i} - ⌊ \frac{a_{j}}{2} ⌋) - (b_{i} - ⌊ \frac{b_{j}}{2} ⌋) | + | ⌊ \frac{a_{j} + 1}{2} ⌋ - ⌊ \frac{b_{j} + 1}{2} ⌋ |

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

$120^\circ$ $90^\circ$

| a_{i} - b_{i} | + | (a_{i} - ⌊ \frac{a_{j} + 1}{2} ⌋) - (b_{i} - ⌊ \frac{b_{j} + 1}{2} ⌋) | + | ⌊ \frac{a_{j}}{2} ⌋ - ⌊ \frac{b_{j}}{2} ⌋ |

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

$-\lfloor\frac{a_j+1}2\rfloor = \lfloor\frac{-a_j}2\rfloor$

Neil
fuente

Puede hacerlo de una sola línea eliminando la nueva línea

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)debería guardar 3 bytes.

Sr. Xcoder

1

Pyth , 31 28 bytes

$(x_1, x_2), (y_1, y_2)$

+eKaMQg#hK+eK^%ssQ_2+shCQSIe

Pruébalo aquí! o prueba la suite de prueba!

Descompostura

+ eKaMQg # hK + eK ^% ssQ_2xxFhCQSIe Programa completo. Q = eval (input ()).
  KaMQ Almacene las diferencias [| x1-x2 |, | y1-y2 |] en K.
 e Recupere el último (| y1-y2 |).
+ g # Y agrégalo al mayor valor entre:
        hK - La cabeza de K (| x1-x2 |)
          + - Y el resultado de agregar:
           eK El final de K (| y1-y2 |).
             ^ - con el resultado de exponencial:
              % ssQ_2 La suma de la Q aplanada, módulo -2.
                                        Produce -1 si x1 + x2 + y1 + y2 es impar, 0 en caso contrario.
                    xxFhCQSIe: por el resultado de esta expresión:
                       hCQ Transponer Q y obtener la cabeza (x1, y1).
                     xF Reducir en XOR bit a bit.
                          SI Y compruebe si la lista [y1, y2] está ordenada.
                    x Después de lo cual, xor el resultado por el bool (0/1).

Sr. Xcoder
fuente

1

05AB1E , 16 bytes

Utiliza una versión modificada de la respuesta de Neil , optimizada para lenguajes basados en pila como 05AB1E. Toma la entrada como dos pares de coordenadas, $(x_1, x_2), (y_1, y_2)$ , separados por una nueva línea de STDIN. Inicialmente fusioné eso con mi otra respuesta 05AB1E, pero luego decidí publicarlo por separado porque es muy, muy diferente.

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

Pruébalo en línea! o prueba la suite de prueba! _{^{(Utiliza una versión ligeramente modificada del código (en ®lugar de ²), cortesía de Kevin Cruijssen )}}

Sr. Xcoder
fuente

¡Buena respuesta! No es algo para el golf, pero cuando cambias ©+®a DŠ+él es más fácil configurar un conjunto de pruebas. ;) Aquí está ese conjunto de pruebas, y todos los casos de prueba están teniendo éxito (ignore el encabezado desordenado; p).

Kevin Cruijssen

@KevinCruijssen Tenía eso como una versión alternativa, pero no se me ocurrió que podría escribir un conjunto de pruebas ... Gracias, lo

agregaré

1

@KevinCruijssen Jugué dos bytes más (¡muy obvio ...!) Y logré romper aún más la compatibilidad de la suite de pruebas, así que lo mantuve como está: P Gracias por la edición, por cierto.

Sr. Xcoder

1

Jalea , 22 .. 16 15 bytes

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

Pruébalo en línea!

Pruebe todos los casos de prueba.

Utiliza el método de @ Neil en esta respuesta que utiliza una fórmula modificada de esta pregunta matemática.

Toma las coordenadas como argumentos y1, y2y x1, x2.

dylnan
fuente

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) debido a una corrección de errores.
-44 bytes (188 → 144) que convierten el método recursivo en un único método de bucle.
-14 bytes gracias a @ceilingcat .

Explicación:

Pruébalo aquí

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

1

Sugerir en z*z<c*clugar de(z<0?-z:z)<(c<0?-c:c)

ceilingcat

@ceilingcat Ah, uno bueno. ¡Gracias!

Kevin Cruijssen

Distancia triangular de Manhattan

El reto

Casos de prueba

Respuestas:

JavaScript (ES6), 84 78 bytes

Casos de prueba

Solución recursiva inicial, 100 88 81

Cómo funciona

Casos de prueba

Python 2, 74 bytes

Lote, 99 bytes

Jalea , 24 bytes

raqueta / esquema, 214 bytes

05AB1E , 24 bytes

Descompostura

Python 2 , 74 72 71 bytes

Pyth , 31 28 bytes

Descompostura

05AB1E , 16 bytes

Jalea , 22 .. 16 15 bytes

Java 8, 157 190 188 144 142 141 127 bytes