Um derivado de Brainfuck
Vamos definir uma linguagem de programação simples, do tipo Brainfuck . Possui uma fita bidirecional de células, e cada célula contém um bit. Todos os bits são inicialmente 0. Há uma cabeça móvel na fita, inicialmente na posição 0. Um programa é uma sequência sobre os caracteres <>01!
, executada da esquerda para a direita, com a seguinte semântica:
<
move a cabeça um passo para a esquerda.>
move a cabeça um passo para a direita.0
coloca 0 na célula atual.1
coloca 1 na célula atual.!
vira a célula atual.
Como não há loops, um programa de n caracteres termina após exatamente n etapas. Um programa é chato se todas as células contiverem 0 no final da execução e empolgante se houver pelo menos um 1. Observe que o tamanho da fita não está especificado; portanto, dependendo da implementação, ela pode ser infinita ou bidirecional. circular.
Um programa de exemplo
Considere o programa 1>>>!<<<<0>!>>>!
. Em uma fita infinita, a execução prossegue da seguinte maneira:
v
00000000000000 Put 1
v
00000100000000 Move by >>>
v
00000100000000 Flip
v
00000100100000 Move by <<<<
v
00000100100000 Put 0
v
00000100100000 Move by >
v
00000100100000 Flip
v
00000000100000 Move by >>>
v
00000000100000 Flip
v
00000000000000
No final, todas as células são 0, então esse programa é chato. Agora, vamos executar o mesmo programa em uma fita circular de comprimento 4.
v
0000 Put 1
v
1000 Move by >>>
v
1000 Flip
v
1001 Move by <<<< (wrapping around at the edge)
v
1001 Put 0
v
1000 Move by > (wrapping back)
v
1000 Flip
v
0000 Move by >>>
v
0000 Flip
v
0001
Desta vez, há uma célula com o valor 1, então o programa é emocionante! Vemos que se um programa é chato ou excitante depende do tamanho da fita.
A tarefa
Sua entrada é uma seqüência de caracteres não vazia <>01!
que representa um programa na linguagem de programação acima. Uma matriz de caracteres também é um formato de entrada aceitável. É garantido que o programa seja entediante quando executado em uma fita infinita. Sua saída deve ser a lista de comprimentos de fita em que o programa é interessante. Observe que você só precisa testar o programa em fitas menores que a duração do programa.
A solução com a menor contagem de bytes em cada idioma é a vencedora. Aplicam-se as regras padrão de código de golfe .
Casos de teste
> : []
110 : []
1>0<! : [1]
0>>1>0<<>! : [1]
1>>>!<<<<0>!>>>! : [2, 4]
!<!<><<0>!>!<><1!>>0 : [2]
>>!>><>001>0<1!<<!>< : [1, 2, 3]
1!><<!<<<!!100><>>>! : [1, 3]
!!1>!>11!1>>0<1!0<!<1><!0<!<0> : [3, 4]
<><<>>!<!!<<<!0!!!><<>0>>>>!>> : [1, 2, 4]
0>>><!<1><<<0>!>>!<<!!00>!<>!0 : [3]
0000!!!!><1<><>>0<1><<><<>>!<< : []
!>!>!>!>!>1>!>0<!<!<!<0<!<0<!<!<!<1>!>0<<! : [1, 2, 5, 7]
<!!>!!><<1<>>>!0>>>0!<!>1!<1!!><<>><0<<!>><<!<<!>< : [1, 2, 4, 5]
!>1<<11<1>!>!1!>>>0!!>!><!!00<><<<0<<>0<<!<<<>>!!> : [1, 2, 3, 5, 6]
<>01!
?Respostas:
Haskell, 119 bytes
Experimente online!
Function
#
é o intérprete para um único comandoc
. Todo o programap
é executado porfold
ing#
com a fita começando emp
.f
executap
para cada fita e mantém aquelas em que a soma das células é pelo menos 1.fonte
n<-[1..length p] ... 0<$[1..n]
parece bastante longo, deve haver um caminho mais curto.n
como resultado; portanto, se você construiu0<$[1..n]
uma maneira diferente (digamos comscanr(:)
), precisaria aceitar o valorlength
. (Eu também tentei usar1
(para substituirlength
comsum
) ouFalse
(para usaror
para o teste) em vez de0
, mas não saiu mais curto.)n<-init$scanr(:)[]$0<$p ... n
que é 2 bytes mais curto, mas ele retorna uma lista de fitas iniciais em vez de seu comprimento, por exemplo[[0],[0,0,0]]
. Com um pouco de flexão de regra, as fitas podem ser vistas como números unários; talvez esteja tudo bem.init$
pode ser substituído colocando uma[0]
lista como inicial, mas ainda não foi curta o suficiente. Eu acho que unário é permitido apenas para idiomas sem uma representação numérica mais natural .Stax ,
5654433835 bytes CP43742 bytes quando descompactado,
Execute e depure online!
-2 bytes por comentário por @recursive
Explicação
Usarei a versão com um prefixo
i
(iei%fz(y{{|(}{|)}{B!s+}{0_]e&}4ls"><! "I@!F|a
) para explicar e explicarei por que oi
pode ser removidoCódigo para executar o programa:
fonte
i
cheque.0]*
pode ser substituído porz(
. Além disso, se você alterar a seqüência de "<>!", Em seguida,0
e1
dará índice de -1, de modo que maneira sua lista de bloqueio precisa apenas 4 blocos, em vez de 5. Isto irá funcionar desde que os0
e1
manipuladores são de qualquer maneira idêntica.CJam ,
57564946 bytes-7 graças a @MartinEnder
Experimente online!
fonte
Perl 5 ,
83827977 bytesInclui
+3
para-F
Dê instruções como uma linha no STDIN
Experimente online!
fonte
Perl 5 (
-F
), 101 bytesExperimente online!
fonte
Vermelho , 243 bytes
Experimente online!
Implementação bastante detalhada e direta. A indexação 1 de Red não me permite reduzir a contagem de bytes usando aritmética modular para fazer um loop pelas fitas circulares.
Ungolfed
fonte
Python 2 ,
139135133132 132131 bytes-3 bytes graças ao Sr. Xcoder
Experimente online!
fonte
Retina , 121 bytes
Experimente online! Explicação:
Crie uma matriz de fitas de cada comprimento até o comprimento do programa de entrada.
Faça um loop até o programa ser consumido.
Se o próximo caractere no programa for 0 ou 1, altere o primeiro caractere de cada linha para esse caractere.
Se for um
!
, alterne o primeiro caractere em cada linha.Se for um
>
ou<
então gire a linha. (Mais fácil do que mover a cabeça.)Exclua a instrução e termine o loop.
Mantenha apenas as linhas emocionantes.
Conte o comprimento de cada linha.
fonte
JavaScript (ES6),
126118 bytesGuardado 3 bytes graças a @ user71546
Recebe entrada como uma matriz de seqüências de caracteres de 1.
Experimente online!
fonte
t.some(x=>x)?
por,+t.join``?
verifique a matriz como dígitos (e 0 indica uma fita zero), mas com 3 bytes a menos.APL (Dyalog Unicode) ,
796454 bytes ( SBCS de Adám )Experimente online!
-15 agradecimentos a Adám (esqueceu-se da monádica
⍸
).-10 graças a ngn .
fonte
↓
). Vou dar uma olhada e atualizar. :)↓
precisará de um;
, não?MATL ,
4639 bytesExperimente online! Ou verifique todos os casos de teste .
Como funciona
fonte
APL (Dyalog Unicode) ,
19278 bytesExperimente online! (resultado não achatado)
Experimente online! (achatado)
Depois de algum tempo batendo com a cabeça na parede, decidi fazer um Tradfn em vez de um Dfn. Esse é o resultado. Pessoas mais inteligentes do que eu podem ser capazes de jogar fora disso.Surpresa, surpresa, alguém mais esperto que eu fiz golf o Parreira sair desta. Obrigado Adám por 114 bytes.
Ele disse:
A função assume
⎕IO←0
.Quão?
(Esta explicação usa uma versão "não destruída" para facilitar a leitura)
fonte
t←l⍴0
bet←l⍴i←0
e removendo a linha acima dele. Você também pode salvar outro alterandot[i|⍨≢t]←1-t[i|⍨≢t]
parat[i|⍨≢t]←~t[i|⍨≢t]
.∇
?∇
é? É uma função tácita.Geléia , 41 bytes
Experimente online!
fonte
C (clang) , 171 bytes
Experimente online!
Tive que usar clang, já que usar
char*p,t[l=strlen(S)]
como expressão de inicialização por algum motivo faz o GCC pensar que quero declarar emstrlen
vez de chamá-lo.Bem direto: executa o programa em fitas circulares de comprimento decrescente, produzindo qualquer comprimento que resultou em 1 em algum lugar da fita.
Tentei encurtar o emaranhado dos operadores ternários, mas acabou precisando de mais parênteses do que o normal.
fonte
i=0,bzero(t,l)
vez dememset(t,i=0,l)
e em*p-62?t[i]=*p^33?*p-48:t[i]^1:(i=~i+l?i+1:0)
vez de*p==62?i=i^l-1?i+1:0:*p^33?t[i]=*p-48:(t[i]^=1)