Desenhar o triângulo de Sierpinski foi feito até a morte . Há outras coisas interessantes que podemos fazer com isso. Se apertarmos os olhos com força o triângulo, podemos ver os triângulos de cabeça para baixo como nós de um gráfico fractal. Vamos encontrar o caminho desse gráfico!
Primeiro, vamos atribuir um número a cada nó. O maior triângulo invertido será o nó zero e, em seguida, desceremos camada por camada (largura primeiro), atribuindo números consecutivos na ordem superior esquerda esquerda:
Clique para uma versão maior, onde os números pequenos são um pouco menos embaçados.
(Claro, esse padrão continuar ad infinitum dentro dos triângulos azuis.) Outra forma de definir a numeração é que o nó central tem o índice 0
, e os filhos de nó i
(triângulos adjacentes do lado de menor escala) têm índices 3i+1
, 3i+2
e 3i+3
.
Como nos movemos neste gráfico? Existem até seis etapas naturais que você pode seguir em qualquer triângulo:
- Sempre é possível mover-se pelo ponto médio de uma das arestas para um dos três filhos do nó atual. Vamos designar esses movimentos como
N
,SW
eSE
. Por exemplo, se estamos atualmente no nó2
, elas levariam a nós7
,8
,9
, respectivamente. Outros movimentos pelas bordas (para descendentes indiretos) não são permitidos. - Também é possível mover-se através de um dos três cantos, desde que não toque a borda do triângulo, para o pai direto ou um dos dois ancestrais indiretos. Vamos designar esses movimentos como
S
,NE
eNW
. Por exemplo, se atualmente estamos no nó31
,S
levaria a10
,NE
seria inválido eNW
levaria a0
.
O desafio
Dados dois números inteiros não negativos x
e y
, encontre o caminho mais curto de x
para y
, usando apenas os seis movimentos descritos acima. Se houver vários caminhos mais curtos, imprima qualquer um deles.
Observe que seu código deve funcionar além dos 5 níveis descritos no diagrama acima. Você pode assumir isso x, y < 1743392200
. Isso garante que eles caibam dentro de um número inteiro assinado de 32 bits. Observe que isso corresponde a 20 níveis da árvore.
Seu código deve processar qualquer entrada válida em menos de 5 segundos . Embora isso exclua uma pesquisa de força bruta pela primeira vez, deve ser uma restrição bastante frouxa - minha implementação de referência lida com entradas arbitrárias para profundidade 1000 em meio segundo (ou seja, números de ~ 480 dígitos para os nós).
Você pode escrever um programa ou função, recebendo entrada via STDIN (ou alternativa mais próxima), argumento da linha de comando ou argumento da função e emitindo o resultado via STDOUT (ou alternativa mais próxima), valor de retorno da função ou parâmetro da função (saída).
A saída deve ser uma lista simples, sem ambiguidades das cordas N
, S
, NE
, NW
, SE
, SW
, usando qualquer separador razoável (espaços, Linefeeds, vírgulas, ","
...).
Aplicam-se as regras padrão de código de golfe .
Casos de teste
Os primeiros casos de teste podem ser trabalhados manualmente, usando o diagrama acima. Os outros garantem que as respostas sejam suficientemente eficientes. Para aqueles, pode haver outras soluções do mesmo comprimento que não estão listadas.
0 40 => N N N N
66 67 => S SW N N N
30 2 => NW NW -or- NE SW
93 2 => NE SW
120 61 => NW NW NW NW N SE SW N
1493682877 0 => S S NW NW
0 368460408 => SW SW N N SW SW SE SW SW N SE N N SW SW N SE SE
1371432130 1242824 => NW NW NE NW N SE SW SW SW SE SE SW N N N N SW
520174 1675046339 => NE NW NE NE SE SE SW SW N SE N SW N SW SE N N N N SE SE SW SW
312602548 940907702 => NE NW S SW N N SW SE SE SE SW SE N N SW SE SE SE SW
1238153746 1371016873 => NE NE NE SE N N SW N N SW N SE SE SW N SW N N SE N SE N
547211529 1386725128 => S S S NE NW N N SE N SW N SE SW SE SW N SE SE N SE SW SW N
1162261466 1743392199 => NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE NE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE
fonte
APL (Dyalog Unicode) ,
144132129118133132130124117 bytes SBCSMuito obrigado a Ven e ngn por sua ajuda no golfe no The APL Orchard , um ótimo lugar para aprender a língua APL.
⎕IO←0
. Sugestões de golfe são bem-vindas.Editar: -12 bytes graças a Ven e ngn, alterando como
n
é definido e alternando da indexação 1 para a indexação 0. -3 devido à correção de um erro no qual nem tudo foi alterado para indexação 0. -11 bytes devido à alteração de comoP
eQ
são definidos. +15 bytes devido à correção de um problema em que meu algoritmo estava incorreto com muitos agradecimentos ao ngn pela ajuda na definição das[⊃⍋|M-s]
seção. -2 bytes de reorganizar o método de encontrar o caminho de retorno e +1 byte para a correção de erros. -2 bytes graças a Adám por reorganizar a definição deI
. -6 bytes graças ao ngn de reorganizar a definição'S' 'NE' 'NW' 'N' 'SW' 'SE'
e de reorganizar comot
é definido (não é mais uma variável separada). -7 bytes graças a ngn de golfing comos
é definido.Experimente online!
Uma explicação do erro no algoritmo
O problema básico é que pensei que o caminho mais curto passava diretamente pelo ancestral comum e não podia, de fato, passar por um ancestral do ancestral comum. Isso está incorreto, como os exemplos a seguir demonstrarão.
De 66 a 5
De 299792458 a 45687
Explicação do código
Solução alternativa usando Dyalog Extended e dfns
Se usarmos
⎕CY 'dfns'
aadic
função, ela implementará nossa numeração bijetiva base-n (que foi a inspiração para a versão que eu uso) por muito menos bytes. Mudar para o Dyalog Extended também economiza bastante bytes, e aqui estamos. Muito obrigado a Adám por sua ajuda no golfe. Sugestões de golfe são bem-vindas!Editar: -8 bytes devido à alteração de como
P
eQ
são definidos. -14 bytes devido à mudança para o Dyalog Extended. -2 devido ao uso de um programa completo para remover os colchetes dfn{}
. +17 bytes devido a fixação de um problema onde meu algoritmo foi incorreto com muitos agradecimentos para NGN para ajudar com descobrir as[⊃⍋|M-s]
seção. +1 byte para correção de bugs. -2 bytes graças a Adám por reorganizar a definiçãoI
e -1 byte de lembrar de colocar meus golfs em ambas as soluções. -3 bytes graças ao ngn, reorganizando a geração das direções cardinais, +1 byte para corrigir um buggy e -3 bytes graças ao ngn, reorganizando comot
é definido (não é mais uma variável separada). -7 bytes graças ao ngn, reorganizando comos
é definido.APL (Dyalog extendida) ,
12311510199116117114109102 bytesExperimente online!
fonte