Imagine um caminho feito de <e >e terminando em um @, por exemplo,
><>@
Um caminhante começa na célula mais à esquerda. Ele percorrerá o caminho da seguinte maneira:
- Se o caminhante estiver em uma
@cela, ele alcançou a meta e está feito. - Se o caminhante estiver em uma
>célula, todo o caminho muda um passo para a direita, ciclicamente, levando o caminhante com ele . - Se o caminhante estiver em uma
<célula, todo o caminho se desloca um passo para a esquerda, ciclicamente, levando o caminhante com ele . - Depois, o caminhante dá um único passo. Se ele estiver em um dos extremos do caminho, ele se afasta do final. Caso contrário, ele continua se movendo na direção em que se moveu no último passo (ignorando a rotação), caminhando para a direita inicialmente.
Vamos trabalhar com o exemplo acima. A posição do caminhante está marcada com ^:
><>@ --rotate--> @><>
^ ^
step right (first step):
@><> --rotate--> ><>@
^ ^
step right:
><>@ --rotate--> @><>
^ ^
step left (dead end):
@><> --rotate--> ><>@
^ ^
step left:
><>@ --rotate--> @><>
^ ^
step left:
@><> Goal reached!
^
O caminhante visitou 6 células no processo (incluindo a célula inicial e a @, e contando cada célula com a mesma frequência que é visitada).
Aqui está um pequeno exemplo, onde o andador é transportado através das bordas por uma rotação:
>>@ --rotate--> @>>
^ ^
step right (first step):
@>> --rotate--> >@>
^ ^
step right (dead end):
>@> Goal reached!
^
Desta vez, o caminhante visitou 3 células.
Podemos facilmente transformar isso em uma sequência inteira:
- Você recebe um número inteiro positivo N , por exemplo
9. - Você calcula a representação binária desse número inteiro, por exemplo
1001. - Em seguida, vire
1em>e0em<e acrescentar um@:><<>@. - Associamos com N o número de células visitadas pelo andador no número construído dessa maneira.
Os primeiros elementos da sequência resultante são:
2, 3, 3, 4, 6, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6,
6, 10, 6, 10, 8, 8, 6, 10, 8, 8, 6, 6, 6, 6, 7, 7
Isso pode parecer bastante arbitrário, mas a sequência resultante acaba tendo muita estrutura:
Para referência, você pode encontrar os primeiros 2048 números da sequência nesta pasta .
O desafio
Você adivinhou: você deve calcular a sequência acima. Você pode fazer isso de três maneiras:
- Você pode produzir uma sequência infinita (enquanto a memória permitir), emitindo continuamente valores (separados por caracteres não numéricos) ou usando alguma forma de gerador infinito nos idiomas que os suportam. Se você imprimir um fluxo infinito no STDOUT, não precisará imprimir os números um por um, mas verifique se todos os números serão impressos após um período finito de tempo (e em ordem). Se você usar esta opção, não deverá receber nenhuma entrada.
- Pode levar um número inteiro N de entrada e produzir o N ° termo da sequência.
- Você pode tomar um inteiro N como entrada e produzir tudo até o N ° termo da seqüência, como uma lista ou string usando um separador inequívoca.
Como não quero penalizar idiomas que não podem ser facilmente convertidos entre bases, em vez do número inteiro N, você pode usar a representação binária de N , usando 0s e 1s como de costume (como uma lista ou string), com o máximo de -significante primeiro.
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).
Aplicam-se as regras de código-golfe padrão .
fundo
Na verdade, isso calcula o número de "ticks" que um intérprete direto da minha linguagem de programação esotérica Labirinto precisaria para interpretar o "caminho" como código-fonte. Nesse caso, o "andador" é simplesmente o ponteiro da instrução (que possui uma posição e uma direção), o @comando finaliza o programa <e >são comandos de modificação do código-fonte.
Respostas:
Gelatina , 10 bytes
Esta função aceita um único número inteiro na forma da lista de seus dígitos binários como entrada.
O algoritmo é equivalente ao da resposta de @ Agawa001 .
Experimente online! ou gere os primeiros números 2048 .
fundo
Enumere as posições abaixo do caminho de 0 a L , fornecendo um total de posições L + 1 . L coincide com o número de dígitos binários do número N que codifica o caminho. Com esta notação, o caminhante começa na posição 0 , o objetivo na posição L .
A cada passo que o caminhante dá, ele se aproxima um pouco do objetivo (na direção em que está caminhando). Além disso, a cada passo do turno, dependendo de ele caminhar com ou contra a direção da mudança, ele aumenta ou diminui sua posição em 2 módulos L + 1 , ou permanece na posição atual.
Para mudar de direção, ele precisa pousar na posição L - 1 (voltada para L ) ou na posição 1 (voltada para 0 ), e depois se deslocar em sua direção. O próximo passo que ele der o trará de volta à sua posição anterior, de frente para a direção oposta.
Se L é par, L-1 é ímpar, então ele não pode avançar de sua posição inicial para L-1 diretamente. A única maneira de alcançá-lo é passando por L , sendo transportado para 0 e dando o próximo passo para pousar em 1 , depois avançando para a direita. Isso requer avançar posições 2L , o que pode ser feito em nada menos que L etapas.
No entanto, depois de dar L passos sem mudar de direção, ele terá atingido a meta. Adicionando um para a célula inicial, obtemos um total de células visitadas L + 1 nesse caso.
Se L é ímpar, L-1 é par, então ele pode alcançar essa posição deslocando-se (L-1) / 2 vezes para a direita. Se a posição L-1 estiver abaixo de 1 naquele momento, ele será deslocado para a posição L , girará e pisará na posição L-1 (voltada para a esquerda).
Isso pode ou não acontecer antes que ele atinja seu objetivo, então há dois casos a serem analisados:
Se houver menos de (L + 1) / 2 ocorrências de 1 na expansão binária de N , executar L etapas não será suficiente para virar a direção. Como essas etapas L levam o caminhante à sua meta, adicionando uma para a célula inicial, obtemos um total de células visitadas L + 1 nesse caso.
Se houver pelo menos (L + 1) / 2 ocorrências de 1 na expansão binária de N , avançar para a ((L + 1) / 2) quinta ocorrência exigirá I etapas, onde eu é a posição inicial dessa ocorrência de 1 .
Assim, depois de dar os passos I , o andador está na posição L - 1 , voltado para a esquerda. Para mudar de direção novamente, ele teria que andar para a esquerda para a posição 1 . No entanto, como no caso par, já que (L - 1) - 1 é ímpar, isso exigirá passar por 0 e não dar menos que L passos.
Como a distância inicial para o gol na direção esquerda é 1 , após dar os passos I , o caminhante se encontra à distância de I + 1 do gol após mudar de direção. Como I <L , temos que I + 1 ≤ L , então os próximos passos I + 1 o levarão à meta.
Isso fornece um total de I + I + 1 = 2I + 1 medidas tomadas. Adicionando um para a célula inicial, obtemos um total de 2I + 1 + 1 = 2 (I + 1) células visitadas neste caso.
Como funciona
fonte
Matlab (pontuação = 230, n = inf)
infse você deseja manter o infinito).h=1000000000000000000000000000000000000000000000000000;w(h,h+1)para garantir.O algoritmo segue uma abordagem matemática que explicarei mais adiante, e confirma a lista de referências de Martin, com base neste programa:
Como o algoritmo verifica 2048 primeiros casos de teste, assumirei cegamente que o faria para qualquer caso de teste, portanto, meu algoritmo funciona com relação a poucas propriedades que descobri nesse processo sem a necessidade de mudar e mover o ponteiro:
1- se o dobro do número de 1 na conversão binária não exceder o comprimento da sequência,
Lentão a saída seráL+12- se o comprimento da sequência for regular e a condição anterior não estiver definida, a saída será a mesma
L+13- caso contrário, a saída será duas vezes o
L/2th th de 1.fonte
a=dec2bin(input(''));c=find(a=='1');g=nnz(a)+1;if nnz(c)<g/2|mod(g,2);g,else,2*c(g/2),end, o que fornece apenas um único elemento da sequência.Python,
122119113110108107103 bytesRecebe a entrada como uma lista de dígitos binários. Função auxiliar para testar:
Crédito para Lynn por salvar 7 bytes.
fonte
p-d-1in[-2,w]economize um byte.d*=2*(1!=d-p>~w)-1economiza mais quatro! ° v °Python 2, 99 bytes
Porta Python da brilhante resposta de Agawa001.
Versão legível:
fonte
MATL,
31, 25 bytesEsta é apenas uma versão MATL do algoritmo de Agawa001, exceto que ela recebe uma entrada inteira N e retorna o N-ésimo termo na sequência. Foi complicado acompanhar todos os elementos da pilha! Eu tive que recorrer ao uso de uma prancheta para evitar enlouquecer. Você pode experimentá-lo online!
Pode ser transformado em um loop imprimindo os primeiros N termos, adicionando
:"@antes e]Ddepois do código .Obrigado a Luis Mendo por salvar 6 bytes inteiros!
fonte
Julia 0.4, 4̷4̷ 42 bytes
Esta função aceita um único número inteiro na forma da lista de seus dígitos binários como entrada.
O algoritmo é equivalente ao da resposta da @ Agawa001 e da minha resposta Jelly .
Experimente online!
Como funciona
find(x)retorna os índices baseados em 1 de todos os elementos diferentes de zero de x . Tentamos acessar a matriz resultante no índice k / 2 e, se for bem-sucedido, sobrescrevemos k com o dobro do índice selecionado.Isso falhará se e somente se uma das seguintes opções for verdadeira:
k / 2 é um float não integral e, portanto, InexactError é gerado.
A matriz de índice possui menos de k / 2 elementos, portanto, um BoundsError é gerado.
Em ambos os casos, a substituição de k falhará e, portanto, seu valor original será retornado.
fonte
JavaScript (ES6), 65 bytes
Aceita uma cadeia de caracteres binária. Usa a verificação de devolução das várias outras respostas.
fonte
Python 2, 74 bytes
Esta função aceita um único número inteiro na forma da lista de seus dígitos binários como entrada.
O algoritmo é equivalente ao da resposta da @ Agawa001 e da minha resposta Jelly .
Teste em Ideone .
Como funciona
nexttenta encontrar o primeiro número inteiro 2i para o qualk==2*sum(x[:i])retorna true. Comox[:i]contém elementos i , isso fornece o índice baseado em 1 do (k / 2) th 1 .nextfalhará se k / 2 for não integral ou se x contiver menos que k / 2 uns. Nesse caso, o valor padrão k é retornado.fonte
> <> , 63 bytes
Desde o momento em que vi o padrão de exemplo neste desafio, eu sabia qual idioma usar :)
Usando N para obter o N º prazo.
Entrada assumida como sendo binária na pilha. Em vez de mover o andador, essa solução depende principalmente do movimento da fita sob o andador.
Experimente online!
fonte