Em um reino distante, uma rainha do xadrez faz uma caminhada diária por um caminho em espiral, numerado de 1 a n
, não se importando em seguir a própria espiral, mas simplesmente fazendo os movimentos da rainha como faria em um tabuleiro de xadrez. A rainha é amada por seus súditos, e eles anotam cada quadrado que ela visita em seu caminho. Dado que a rainha pode começar sua caminhada em qualquer praça e terminar em qualquer praça, qual é a caminhada mais curta da rainha que ela pode fazer?
O desafio
Dada uma espiral de números inteiros em uma grade retangular, escreva uma função que retorne um dos caminhos mais curtos possíveis (contados pelo número de células viajadas) entre dois números nessa grade espiral usando os movimentos de uma rainha do xadrez.
Por exemplo, de 16
para 25
:
25 10 11 12 13
24 9 2 3 14
23 8 1 4 15
22 7 6 5 16
21 20 19 18 17
Alguns caminhos possíveis incluem 16, 4, 2, 10, 25
e 16, 5, 1, 9, 25
.
Regras
- A entrada será dois inteiros positivos.
- A saída será um caminho de números inteiros (incluindo os dois pontos de extremidade) através da espiral, usando apenas movimentos ortogonais e diagonais.
- O comprimento de um caminho é contado pelo número de células percorridas.
- Sua resposta pode ser um programa ou uma função.
- Isso é código de golfe, então o menor número de bytes vence.
Como sempre, se o problema não estiver claro, entre em contato. Boa sorte e bom golfe!
Casos de teste
>>> queen_spiral(4, 5)
4, 5
>>> queen_spiral(13, 20)
13, 3, 1, 7, 20
>>> queen_spiral(14, 14)
14
>>> queen_spiral(10, 3)
10, 11, 3
>>> queen_spiral(16, 25)
16, 4, 2, 10, 25
>>> queen_spiral(80, 1)
80, 48, 24, 8, 1
fonte
Respostas:
APL (Dyalog Unicode) ,
5957 bytes SBCSExperimente online!
-2 bytes graças a @ngn.
Função anônima que aceita dois pontos de extremidade como argumentos esquerdo e direito.
Ungolfed & como funciona
A rainha se move diagonalmente primeiro, portanto é suficiente pré-calcular as coordenadas de cada número até
max(start,end)
.O algoritmo de geração de coordenadas é inspirado em várias respostas sobre o desafio relacionado , mas é um pouco diferente de qualquer uma das respostas existentes:
r=1 2 3 4 5 6 7 8 9 10
n=1 1 2 2 3 3 4 4 5 5
r
porn
.1 2 3 3 4 4 5 5 5 6 6 6 7 7 7 7 8 8 8 8 9 9 9 9 9 10 10 10 10 10
Então, quando o vetor de coordenadas
v
estiver pronto, podemos facilmente converter entre o índice espiral e as coordenadas usandov[i]
ev⍳coord
(localizando o primeiro índice decoord
inv
).fonte
(⍵⊃v)-⍺⊃v
->⊃⍵⍺-.⊃⊂
(⍺⌷v)
->v[⍺]
Mathematica
615530 bytesIsso constrói uma grade numérica, a converte em um gráfico e localiza um caminho mais curto entre os dois números que foram inseridos.
UnGolfed
numberSpiral
é da Mathworld Prime Spiral . Cria um n por n Ulam Spiral (sem destacar os números primos).findPath
converte a grade numérica em um gráfico. As arestas são movimentos válidos da rainha na grade numérica.Exemplos
{4,5}
{13,3,1,7,22}
{16,4,1,9,25}
O caminho mais curto de 80 para 1 contém 5, não 6, vértices.
{80, 48, 24, 8, 1}
Golfe
fonte
Scala (830 bytes)
Constrói a espiral em uma matriz quadrada 2D usando quatro funções mutuamente recursivas. Outra pesquisa recursiva para criar a lista de caminhos.
Ungolfed
fonte
Ruby,
262218216 bytesEsta é uma porta da minha resposta Python . Sugestões de golfe são bem-vindas.
Edit: 45 bytes, graças a Jordan e suas sugestões de
d=[0]*n=m*m;*e=c=0;*t=a
,.rect
,0<=>x
ex,y=(e[a]-g=e[b]).rect; t<<d[(g.real+x)*m+g.imag+y]
. Outro byte de(x+y*1i)
para(x+y.i)
.Ungolfed:
fonte
q=
da sua resposta, pois não está contando os bytes.c=0;e=[c];t=[a]
pode ser reduzido para*e=c=0;*t=a
. Você pode substituirz=e[a]-e[b];x,y=z.real,z.imag
porx,y=(e[a]-e[b]).rect
ex+=x<0?1:x>0?-1:0
comx+=0<=>x
(o mesmo paray
). Eu acho que reduz para 229 bytes.d
pord=[0]*m*m
e substituad[c.real][c.imag]
pord[c.real*m+c.imag]
ed[e[b].real+x][e[b].imag+y]
pord[(e[b].real+x)*m+e[b].imag+y]
.t<<d[(e[b].real+x)*m+e[b].imag+y]
pode ser reduzida parau,v=e[b].rect;t<<d[(u+x)*m+v+y]
.d=[0]*m*m
parad=[0]*n=m*m
e(m*m).times
paran.times
. Isso é 219.x,y=(e[a]-e[b]).rect
parax,y=(e[a]-g=e[b]).rect
, excluindou,v=e[b].rect
e alterandot<<d[(u+x)*m+v+y]
parat<<d[(g.real+x)*g.imag+v+y]
(basicamente revertendo meu penúltimo comentário).Python 3, 316 bytes
Essa resposta examina as coordenadas da espiral
a
eb
da espiral (usando números complexos) e adiciona os movimentos diagonais primeiro, depois os movimentos ortogonais.Ungolfed:
fonte