26

A distância de Manhattan em uma grade regular é o número de etapas ortogonais necessárias para alcançar uma célula da outra. Etapas ortogonais são aquelas que atravessam as bordas das células da grade (em oposição aos cantos, o que nos daria a distância de Chebyshev ).

Podemos definir uma distância semelhante em outras grades, por exemplo, a grade triangular. Podemos endereçar as células individuais na grade com o seguinte esquema de indexação, em que cada célula contém um 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\  /
   \/______\/______\/______\/______\/___...
   /\      /\      /\      /\      /\
  .  .    .  .    .  .    .  .    .  .
 .    .  .    .  .    .  .    .  .    .

Agora, a distância de Manhattan nessa grade é novamente o número mínimo de etapas nas bordas para passar de uma célula para outra. Portanto, você pode passar de 3,1para 2,1, 4,1ou 3,2, mas não para qualquer outro triângulo, pois esses seriam pontos de cruzamento e não arestas.

Por exemplo, a distância de 2,1a 5,2é 4. O caminho mais curto geralmente não é único, mas uma maneira de fazer a distância em 4 etapas é:

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

O desafio

Dados dois pares de coordenadas e do esquema de endereçamento acima, retorne a distância de Manhattan entre eles.x₁,y₁x₂,y₂

Você pode assumir que todas as quatro entradas são números inteiros não negativos, cada uma com menos de 128. Você pode levá-las em qualquer ordem e agrupadas arbitrariamente (quatro argumentos separados, uma lista de quatro números inteiros, dois pares de números inteiros, uma matriz 2x2, .. .).

Você pode escrever um programa ou uma função e usar qualquer um dos métodos padrão de recebimento de entrada e saída.

Você pode usar qualquer linguagem de programação , mas observe que essas brechas são proibidas por padrão.

Isso é código-golfe , então a resposta mais curta e válida - medida em bytes - vence.

Casos de teste

Cada caso de teste é fornecido 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
fonte

As brechas que receberam classificações negativas líquidas devem ser incluídas entre as brechas oficiais?

DavidC

@DavidC No. Da questão da brecha: "[...] a brecha descrita em qualquer resposta que seja igual a +5 ou superior e tenha pelo menos o dobro de votos positivos e negativos que pode ser considerada inaceitável para a comunidade "

Martin Ender

É permitido fazer uma quinta entrada, que começa em 0 por padrão (o resultado)? Então não precisarei adicionar (a,b,x,y)->c(a,b,x,y,0)(chamando método separado ccom os quatro argumentos e 0como quinto argumento) à minha resposta.

Kevin Cruijssen

3

@KevinCruijssen Desculpe. Os argumentos fixos adicionais são um pouco facilmente abusáveis (e apenas permitir 0 como um caso especial parece estranho).

Martin Ender

@MartinEnder Ok, pensei que sim, mas nunca pode machucar perguntar. Nesse caso, minha resposta de 190 bytes permanece. Embora eu tenha respondido pela metade há um ano, um caso de teste estava falhando. Me deparei com a pergunta novamente agora e foi capaz de corrigir o erro na minha resposta.

Kevin Cruijssen 16/10

7

JavaScript (ES6), 84 78 bytes

Guardado 6 bytes graças 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 teste

Mostrar snippet 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

Expandir snippet

Solução recursiva inicial, 100 88 81

Economizou 12 bytes graças ao ETHproductions
Economizado 7 bytes graças ao 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

Como funciona

Embora ainda se aplique essencialmente à versão atual, a explicação a seguir se refere mais especificamente à versão 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)

Ir de (x0, y) a (x1, y) é trivial, pois podemos atravessar as arestas laterais desde o triângulo de origem até o alvo. A distância de Manhattan neste caso é | x0 - x1 | .

A parte complicada são as etapas verticais. Para ir da linha y0 para a linha y1 , precisamos levar em consideração esses dois parâmetros:

A orientação do triângulo atual
Se y0 é menor ou maior que y1

A orientação de um triângulo é dada pela paridade de x + y :

se for par, o triângulo está apontando para cima
se for estranho, o triângulo está apontando para baixo

Podemos descer de um triângulo apontando para cima (útil quando y0 <y1 ) e para cima de um triângulo apontando para baixo (útil quando y0> y1 ).

Ao combinar a orientação do triângulo com a comparação entre y0 e y1 , obtemos a fórmula x + y0 + (y0> y1? 1: 0) cujo resultado é uniforme se pudermos ir na direção desejada e, se não, ímpares.

Se não conseguirmos alcançar a próxima linha diretamente, primeiro precisamos obter um alinhamento correto atualizando x :

se x ainda não é igual a x1 , nós definitivamente queremos mover na direção correta, então aumentamos se x for menor que x1 e diminuímos se x for maior que x1
se x já é igual a x1 , podemos incrementá-lo ou diminuí-lo

Casos de teste

Mostrar snippet 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

Expandir snippet

Arnauld
fonte

Isso é ... muitas operações matemáticas muito pequenas ... Mas você não poderia pular a nvariável completamente e apenas adicionar 1 ao resultado de cada iteração? ( 90 caracteres, eu acho)

ETHproductions

@ETHproductions Para ser sincero, publiquei sem nenhum golfe sério. Mas essa é definitivamente a primeira coisa a fazer. Obrigado!

Arnauld #

1

Além disso, eu acho que a precedência de operadores de &meios que você pode fazer a+b+(b>d)&1para salvar 2 bytes

ETHproductions

O número chegou a 81, eu acho: #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

Eu acho que pode ser possível salvar outro byte usando um 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
fonte

1

Você pode, por favor, explicar esta parte **(x^y^(Y>=y)):?

Possum morto

1

@DeadPossum Mover uma distância 1 verticalmente pode fazer 1 ou 3 movimentos; não há como dizer apenas olhando para paridades, então você precisa comparar os valores de y.

precisa saber é

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

Explicação: Um movimento somente na horizontal simplesmente leva a diferença absoluta da coordenada x. Para x grande o suficiente, o movimento vertical leva apenas um passo extra por diferença absoluta de coordenadas y, mas para x pequeno, são necessários quatro etapas extras por diferença de coordenadas y duas, além de um ou três passos para uma diferença ímpar. Isso é calculado como duas etapas por diferença mais um fator de correção. O maior dos dois passos corrigidos e a soma das diferenças absolutas é o resultado, embora este seja calculado como o maior entre a diferença absoluta de coordenadas y corrigida e a distância absoluta de coordenadas x adicionada à diferença absoluta de coordenadas y não corrigida .

@cmd/cset/a" - Avalia expressões separadas por vírgula e imprime a ú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
fonte

2

Gelatina , 24 bytes

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

Experimente online!

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

A primeira linha calcula , o expoente na fórmula. $¢ = (Y \not< y)+x+y$

A última linha de primeiro calcula e, em seguida, calcula o máximo de e , onde é a função na linha média. $L=[|x-X|, |y-Y|]$ $\text{sum}(L)$ $f(L)$ $f$

A linha do meio, dado , calcula , leva a que o 'th poder, em seguida, adiciona . $L=[a, b]$ $-((a+b)\bmod 2)$ $¢$ $2b$

Lynn
fonte

2

raquete / 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
fonte

2

05AB1E , 24 bytes

Resposta do Port of my Pyth , que por sua vez usa aproximadamente a mesma abordagem que a resposta Python do feersum . Recebe a entrada como uma lista de pares de coordenadas, . Corrigido um bug para +1 byte e outro erro para +1, mas que produzia o resultado correto para todos os casos de teste ... $(x_1, x_2), (y_1, y_2)$

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

Experimente online!

Demolir

ÆÄ` © I˜OÉ (IøнOIθD {Q + m + M® + Programa completo. I representa a entrada avaliada.
ÆÄ Reduza os pares por subtração, pegue os valores absolutos.
  `© Coloque-os separadamente na pilha e armazene o segundo
                            um | y1-y2 | no registro C.
    Empurre a soma da entrada achatada para a pilha.
       Pegue sua paridade e negue.
         Pressione [x1, y1].
            O Tome x1 + y1 (some-os).
             IθD {Q Em seguida, verifique se o segundo par está classificado (y1 ≤ y2).
                  + E some isso com x1 + y1.
                   m Exponencial. Empurre a paridade acima ** do resultado.
                    + E adicione a segunda diferença absoluta a isso.
                     M® + Como resultado, empurre o maior número na pilha
                            mais o valor armazenado no registro C.

Mr. Xcoder
fonte

Não estou 100% de certeza, mas você não pode mudar o ©que De remover o ®? Parece funcionar para o caso atualmente no seu TIO, mas não tenho certeza se ele segue o mesmo caminho para todos os casos.

Kevin Cruijssen

1

@KevinCruijssen EDIT : Não, porque Mo comportamento de seria afetado por isso. Falha em [[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)

Experimente online! O link inclui casos de teste. Editar: salvou 2 bytes graças a @JoKing. Economizou mais um byte graças a @ Mr.Xcoder. Com base na seguinte fórmula, encontrei nesta pergunta :

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

Os sistemas de coordenadas diferem de três maneiras; as coordenadas são trocadas (o que explica minha ordem de nome de parâmetro um tanto estranha), as coordenadas são anguladas em vez de (o que explica as duas adições) e as coordenadas na pergunta vinculada usam indexação 1 inferior. Como estamos enfrentando diferenças, isso cancela a maior parte do tempo e nos resta: $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|$

Isso pode ser praticado quando se observa que . $-\lfloor\frac{a_j+1}2\rfloor = \lfloor\frac{-a_j}2\rfloor$

Neil
fonte

Você pode criar uma linha removendo a nova linha

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)deve salvar 3 bytes.

Xcoder

1

Pitão , 31 28 bytes

Usa aproximadamente a mesma abordagem da resposta Python do feersum . Recebe a entrada como uma lista de pares de coordenadas, . Corrigido um bug para -1 byte. $(x_1, x_2), (y_1, y_2)$

+eKaMQg#hK+eK^%ssQ_2+shCQSIe

Experimente aqui! ou Experimente a suíte de testes!

Demolir

+ eKaMQg # hK + eK ^% ssQ_2xxFhCQSIe Programa completo. Q = eval (entrada ()).
  KaMQ Armazene as diferenças [| x1-x2 |, | y1-y2 |] em K.
 e Recupere o último (| y1-y2 |).
+ g # E adicione-o ao maior valor entre:
        hK - A cabeça de K (| x1-x2 |)
          + - E o resultado da adição:
           eK O fim de K (| y1-y2 |).
             ^ - com o resultado de exponenciação:
              % ssQ_2 A soma do Q nivelado, módulo -2.
                                        Rende -1 se x1 + x2 + y1 + y2 é ímpar, 0 caso contrário.
                    xxFhCQSIe - pelo resultado desta expressão:
                       hCQ Transponha Q e pegue a cabeça (x1, y1).
                     xF Reduza em XOR bit a bit.
                          SIe E verifique se a lista [y1, y2] está classificada.
                    x Depois disso, xou o resultado pelo bool (0/1).

Mr. Xcoder
fonte

1

05AB1E , 16 bytes

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

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

Experimente online! ou Experimente a suíte de testes! _{^{(Usa uma versão ligeiramente modificada do código (em ®vez de ²), cortesia de Kevin Cruijssen )}}

Mr. Xcoder
fonte

Boa resposta! Não é algo para jogar golfe, mas quando você muda ©+®para DŠ+é mais fácil configurar uma suíte de testes. ;) Aqui está o conjunto de testes e todos os casos de teste estão sendo bem-sucedidos (ignore o cabeçalho bagunçado; p).

Kevin Cruijssen

@KevinCruijssen eu tinha isso como uma versão alternativa, mas não me ocorreu que eu poderia escrever um conjunto de testes ... Obrigado, eu vou adicioná-lo

Mr. Xcoder

1

@KevinCruijssen Eu joguei mais dois bytes (muito óbvios ...!) E consegui quebrar ainda mais a compatibilidade da suíte de testes, então continuei como está: P A propósito, obrigado pela edição.

Mr. Xcoder

1

Geléia , 22 .. 16 15 bytes

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

Experimente online!

Experimente todos os casos de teste.

Usa o método de @ Neil nesta resposta, que usa uma fórmula modificada desta pergunta math.SE.

Toma as coordenadas como argumentos y1, y2e x1, x2.

dylnan
fonte

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) devido a uma correção de bug.
-44 bytes (188 → 144) convertendo o método recursivo em um único método de loop.
-14 bytes graças a @ceilingcat .

Explicação:

Experimente aqui.

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

1

Sugerir em z*z<c*cvez de(z<0?-z:z)<(c<0?-c:c)

ceilingcat 20/09

@ceilingcat Ah, bom. Obrigado!

Kevin Cruijssen 20/09

Distância Triangular Manhattan

O desafio

Casos de teste

Respostas:

JavaScript (ES6), 84 78 bytes

Casos de teste

Solução recursiva inicial, 100 88 81

Como funciona

Casos de teste

Python 2, 74 bytes

Lote, 99 bytes

Gelatina , 24 bytes

raquete / esquema, 214 bytes

05AB1E , 24 bytes

Demolir

Python 2 , 74 72 71 bytes

Pitão , 31 28 bytes

Demolir

05AB1E , 16 bytes

Geléia , 22 .. 16 15 bytes

Java 8, 157 190 188 144 142 141 127 bytes