Golf um programa ou função que forneça a localização do gnu que começa no quadrado em um tabuleiro de xadrez infinito numerado em uma espiral quadrada no sentido anti-horário, onde o gnu sempre visita o quadrado numerado mais baixo ela pode alcançar o que ela ainda não visitou.
Inspiração: The Trapped Knight e OEIS A316667 .
Editar: Esta sequência está agora no OEIS como A323763 .
O código pode produzir o local , os primeiros locais ou gerar a sequência sem entrada.
Sinta-se à vontade para fornecer a localização dela após (ou até) saltos, mas, se houver, indique isso claramente em sua resposta e certifique-se de que uma entrada de produza 1
(ou, [1]
se apropriado).
Como código é golfe , o objetivo é produzir o código de trabalho no menor número de bytes possível no idioma escolhido.
Nota: o GNU fica preso (bem como o cavaleiro em sua localização em , praça , e o camelo em sua localização em , praça ) em seu 12899744968 ^ {\ text {th}} localização no quadrado 12851850258 . O comportamento do seu código pode ser indefinido para n maior que isso. (Obrigado ao Deadcode pelo código C ++ que encontrou isso!)
Detalhe
O quadro se parece com o abaixo e continua indefinidamente:
101 100 99 98 97 96 95 94 93 92 91
102 65 64 63 62 61 60 59 58 57 90
103 66 37 36 35 34 33 32 31 56 89
104 67 38 17 16 15 14 13 30 55 88
105 68 39 18 5 4 3 12 29 54 87
106 69 40 19 6 1 2 11 28 53 86
107 70 41 20 7 8 9 10 27 52 85
108 71 42 21 22 23 24 25 26 51 84
109 72 43 44 45 46 47 48 49 50 83
110 73 74 75 76 77 78 79 80 81 82
111 112 113 114 115 116 117 118 119 120 121
Um gnu é uma peça de xadrez de fada "gnu" - uma peça de xadrez não-padrão que pode se mover tanto como cavaleiro (um ) e como um camelo (um ).
Como tal, ela poderia mudar para qualquer um desses locais a partir do local inicial :( 1 , 3 ) 1
. . . . . . . . . . .
. . . . 35 . 33 . . . .
. . . . 16 . 14 . . . .
. . 39 18 . . . 12 29 . .
. . . . . (1) . . . . .
. . 41 20 . . . 10 27 . .
. . . . 22 . 24 . . . .
. . . . 45 . 47 . . . .
. . . . . . . . . . .
O mais baixo deles é e ela ainda não visitou esse quadrado; portanto, é o segundo termo na sequência.
Em seguida, ela poderia passar de para qualquer um desses locais:
. . . . . . . . . . .
. . . . . . 14 . 30 . .
. . . . . . 3 . 29 . .
. . . . 6 1 . . . 53 86
. . . . . . . (10) . . .
. . . . 22 23 . . . 51 84
. . . . . . 47 . 49 . .
. . . . . . 78 . 80 . .
. . . . . . . . . . .
No entanto, ela já visitou a praça portanto, sua terceira localização é a praça , a mais baixa que ela ainda não visitou.
Os primeiros termos do caminho do GNU são:
1, 10, 3, 6, 9, 4, 7, 2, 5, 8, 11, 14, 18, 15, 12, 16, 19, 22, 41, 17, 33, 30, 34, 13, 27, 23, 20, 24, 44, 40, 21, 39, 36, 60, 31, 53, 26, 46, 25, 28, 32, 29, 51, 47, 75, 42, 45, 71, 74, 70, 38, 35, 59, 56, 86, 50, 78, 49, 52, 80, 83, 79, 115, 73, 107, 67, 64, 68, 37, 61, 93, 55, 58, 54, 84, 48, 76, 43, 69, 103, 63, 66, 62, 94, 57, 87, 125, 82, 118, 77, 113, 72, 106, 148, 65, 97, 137, 91, 129, 85
Os primeiros saltos são movimentos de cavaleiro, de modo que os primeiros termos coincidem com o A316667 .
Respostas:
JavaScript (Node.js) ,
191 ... 166164 bytesEconomizou 2 bytes graças a @grimy .
Retorna oN º prazo.
Experimente online! ou Veja uma versão formatada
Quão?
Índices espirais
Para converter as coordenadas(x,y) no índice espiral I , primeiro calculamos a camada L com:
Que dá:
Em seguida, calculamos a posição na camada com:P
Que dá:
O índice final é dado por:Eu
NB: A fórmula acima fornece uma espiral indexada em 0.
No código JS, computamos imediatamente com:4 L2
E subtraia com:P
Movimentos do GNU
Dada a posição atual , os 16 quadrados-alvo possíveis do gnu são testados na seguinte ordem:( x , y)
Nós os percorremos aplicando 16 pares de valores assinados . Cada par é codificado como um único caractere ASCII.( dx , dy)
Nós manter o controle do valor mínimo encontrado na e das coordenadas da célula correspondente em .m ( H, V)
Uma vez encontrado o melhor candidato, o marcamos como visitado, definindo uma flag no objeto , que também é nossa principal função recursiva.g
Na primeira iteração, começamos com e . Isso garante que a primeira célula selecionada seja e que seja a primeira célula a ser marcada como visitada.x = 1 y= 2 ( 0 , 0 )
fonte
Buffer
para forçar cada caractere a ser interpretado como um único byte?Buffer
construtor ainda aceita uma string. Portanto, sim, essa é uma maneira bastante barata de convertê-lo em uma lista de bytes - ao contrário de[..."string"].map(c=>do_something_with(c.charCodeAt()))
.Coco ,
337276 bytesRetorna um gerador de valores. Provavelmente poderia ser jogado mais. (Especialmente a sequência de tuplos de diferença.) Algoritmo espiral feita de esta resposta math.se .
Experimente online!
fonte
for a,b in (
->for a,b in(
(talvez você também possa jogar golfe na tupla delta das tuplas)q
e um zip é menor para as tuplas: é possível que 306 bytes ainda possam ser jogados, é claro0.5
->.5
para outro byte salvo;A**2
->A*A
por mais um.05AB1E ,
7765585752 bytes-6 bytes graças a @Arnauld usando uma porta de sua fórmula.
Experimente on-line (o
ï
rodapé remove o.0
para tornar a saída mais compacta, mas fique à vontade para removê-lo para ver o resultado real).Explicação do código:
Explicação geral:
global_array
[1]
X
[0,0]
X
Qual é a mesma fórmula que @Arnauld está usando em sua resposta , mas escrita de forma diferente para usar os componentes internos do 05AB1E para duplo, quadrado, -1, +1, etc.
(Se você quiser ver apenas essa parte espiral do código em ação: experimente online .)
global_array
global_array
X
Depois de repetir a
input
quantidade de vezes, o programa produzirá issoglobal_array
como resultado.fonte