As fitas circulares são empolgantes?

32

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 .

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]
Zgarb
fonte
11
Podemos escolher caracteres distintos e consistentes em vez de <>01!?
Mr. Xcoder
11
Uma matriz de instruções é uma entrada aceitável?
Arnauld 23/02
@ Mr.Xcoder Não, você deve usar esses caracteres exatos.
Zgarb 23/02
@ Arnauld Uma matriz de caracteres é próxima o suficiente de uma string, eu permitirei.
Zgarb

Respostas:

6

Haskell, 119 bytes

t#'<'=last t:init t
(h:t)#c|c<'#'=1-h:t|c>'='=t++[h]|1<2=read[c]:t
f p=[n|n<-[1..length p],sum(foldl(#)(0<$[1..n])p)>0]

Experimente online!

Function #é o intérprete para um único comando c. Todo o programa pé executado por folding #com a fita começando em p. fexecuta ppara cada fita e mantém aquelas em que a soma das células é pelo menos 1.

nimi
fonte
n<-[1..length p] ... 0<$[1..n]parece bastante longo, deve haver um caminho mais curto.
nimi 23/02
Não vejo um caminho mais curto. O problema que vejo é que você realmente precisa do valor de ncomo resultado; portanto, se você construiu 0<$[1..n]uma maneira diferente (digamos com scanr(:)), precisaria aceitar o valor length. (Eu também tentei usar 1(para substituir lengthcom sum) ou False(para usar orpara o teste) em vez de 0, mas não saiu mais curto.)
Ørjan Johansen
@ ØrjanJohansen: sim, eu tentei n<-init$scanr(:)[]$0<$p ... nque é 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.
nimi 24/02
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 .
Ørjan Johansen
4

Stax , 56 54 43 38 35 bytes CP437

è¥%►BΣ░ÜY⌂y(â&.═ªê►V½▲y▌)▀♫♂╣ª?√»!#

42 bytes quando descompactado,

%fz(y{{|(}{|)}{B!s+}{0_]e&}4ls"><! "I@!F|a

Execute e depure online!

-2 bytes por comentário por @recursive

Explicação

Usarei a versão com um prefixo i(ie i%fz(y{{|(}{|)}{B!s+}{0_]e&}4ls"><! "I@!F|a) para explicar e explicarei por que o ipode ser removido

i               Suppress implicit eval
                    This prevents the test case "110" from being interpreted as a number
                    However, this can be removed because a program containing only numbers cannot be exciting and the output will be empty anyway.
                    This is based on the fact that the program is boring on non-circular tapes
 %f             Filter range [1..n] with the rest of this program
                    Where n is the length of the input
                    Implicit output the array after filtering, one element per line
   z(           Initialize the tape
     y{  F      Run the program
          |a    Any cell is non-zero

Código para executar o programa:

{|(}                                 Block to rotate left by one element
    {|)}                             Block to rotate right by one element
        {B!s+}                       Block to perform logical not on the element at index 0
              {0_]e&}                Block to obtain current instruction,
                                         Convert it to a number
                                         And assign to element at index 0

                     4l              Pack the 4 blocks in an array
                       s"<>! "I      Find the index of current instruction in string, if not found, the index will be -1
                                         And when indexed with -1, it wraps around to the 4th element.

                               @!    And execute the corresponding block.
Weijun Zhou
fonte
11
Adicionei um caso de teste de todos os dígitos para validar seu icheque.
Zgarb 23/02/19
0]*pode ser substituído por z(. Além disso, se você alterar a seqüência de "<>!", Em seguida, 0e 1dará índice de -1, de modo que maneira sua lista de bloqueio precisa apenas 4 blocos, em vez de 5. Isto irá funcionar desde que os 0e 1manipuladores são de qualquer maneira idêntica.
recursivo
@recursive Bom argumento.
Weijun Zhou 28/02
3

CJam , 57 56 49 46 bytes

-7 graças a @MartinEnder

{:T,({)0a*T{i23%")!+(+ W0tW1t)\+"3/=~}/:+},:)}

Experimente online!

Esolanging Fruit
fonte
2

Perl 5 ( -F), 101 bytes

map{$,=@a=(0)x$_;map{$,+=/>/-/</;$a[$,%@a]=$&if/0|1/;$a[$,%@a]=!$a[$,%@a]if/!/}@F;say if@a~~/1/}1..@F

Experimente online!

Xcali
fonte
2

Vermelho , 243 bytes

func[p][repeat n length? p[b: copy[]insert/dup b 0 n i: 1
parse p[any["<"(i: i - 1 if i < 1[i: n])|">"(i: i + 1 if i > n[i: 1])|"0"(b/(i): 0)|"1"(b/(i): 1)|"!"(b/(i): either b/(i) = 0[1][0])|
skip]]s: 0 foreach c b[s: s + c]if s > 0[print n]]]

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

f: func[p][ 
    repeat n length? p[
        b: [] 
        insert/dup b 0 n
        i: 1
        parse p[
            some [
                 "<" (i: i - 1 if i < 1[i: n])
               | ">" (i: i + 1 if i > n[i: 1])
               | "0" (b/(i): 0)
               | "1" (b/(i): 1)
               | "!" (b/(i): either b/(i) = 0 [1][0])
               | skip 
            ]
        ]
        s: 0
        foreach c b[s: s + c]
        if s > 0 [print n]
    ]
]
Galen Ivanov
fonte
2

Python 2 , 139 135 133 132 132 131 bytes

-3 bytes graças ao Sr. Xcoder

def f(p):i=0;exec"i+=1;s=[0]*i\nfor c in p:c=ord(c)-61;s=c>-2and s[c:]+s[:c]or[[s.pop(0)^1,0,1][c%7]]+s\nif 1in s:print i\n"*len(p)

Experimente online!

Cajado
fonte
131 bytes?
Sr. Xcoder
2

Retina , 121 bytes

.+
$.&*0¶$&
\G0
0$`¶
{ms`^.(?=.*¶¶(0|1))
$1
"¶¶!"&mT`d`10`^.
"¶¶>"&`(.)(.*)¶
$2$1¶
"¶¶<"&`(.*)(.)¶
$2$1¶
)`¶¶.
¶¶
G`1
%`.

Experimente online! Explicação:

.+
$.&*0¶$&
\G0
0$`¶

Crie uma matriz de fitas de cada comprimento até o comprimento do programa de entrada.

{

Faça um loop até o programa ser consumido.

ms`^.(?=.*¶¶(0|1))
$1

Se o próximo caractere no programa for 0 ou 1, altere o primeiro caractere de cada linha para esse caractere.

"¶¶!"&mT`d`10`^.

Se for um !, alterne o primeiro caractere em cada linha.

"¶¶>"&`(.)(.*)¶
$2$1¶
"¶¶<"&`(.*)(.)¶
$2$1¶

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.

G`1

Mantenha apenas as linhas emocionantes.

%`.

Conte o comprimento de cada linha.

Neil
fonte
2

JavaScript (ES6), 126 118 bytes

Guardado 3 bytes graças a @ user71546

Recebe entrada como uma matriz de seqüências de caracteres de 1.

f=(s,l=0,p=0,t=[])=>s[l++]?s.map(c=>1/c?t[p%l]=+c:c>'='?p++:c>';'?p+=l-1:t[p%l]^=1)&&+t.join``?[l,...f(s,l)]:f(s,l):[]

Experimente online!

Arnauld
fonte
Substituindo 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.
Shieru Asakoto,
2

APL (Dyalog Unicode) , 79 64 54 bytes ( SBCS de Adám )

⍸⊂{∨/⍎⍕(↓',',⍨5 3'0@11@1~@1 1⌽¯1⌽')['01!<'⍳⌽⍺]⍵}¨0=,\

Experimente online!

-15 agradecimentos a Adám (esqueceu-se da monádica ).
-10 graças a ngn .

Erik, o Outgolfer
fonte
64
Adám 08/0318
@ Adám Hm, parece que isso não é o ideal (por exemplo, você não precisa do ). Vou dar uma olhada e atualizar. :)
Erik the Outgolfer
Mas se você remover o, precisará de um ;, não?
Adám
@ Adám não , por que você faria?
Erik the Outgolfer
1

MATL , 46 39 bytes

f"@:~G"@59>?@61-YS}@33=?t1)~}@U]1(]]a?@

Experimente online! Ou verifique todos os casos de teste .

Como funciona

f             % Push indices of nonzero chars of (implicit) input string: gives
              % [1 2 ... n] where n is input length
"             % For each k in [1 2 ... n]. These are the possible tape lengths
  @:~         %   Push array of k zeros. This is the tape, in its initial state
  G           %   Push input string
  "           %   For each char in the input string
    @59>?     %     If code point of current char exceeds 59 (so it is '<' or '>')
      @61-    %       Push code point minus 61: gives -1 for '<', or 1 for '>'
      YS      %       Circularly shift the tape by that amount. Instead of moving
              %       the head, we shift the tape and keep the head at entry 1
    }         %     Else
      @33=?   %       If code point of current char is 33 (so it is '!')
        t1)   %         Duplicate the array representing the tape, and get its
              %         first entry
        ~     %         Logical negate
      }       %       Else
        @U    %         Push current char (it is '0' or '1') converted to number
      ]       %       End
      1(      %       Write (either 0, 1 or old value negated) at entry 1
    ]         %     End
  ]           %   End
  a?          %   If the tape contains at least a nonzero value
    @         %     Push tape length, k
              %   End (implicit)
              % End (implicit)
              % Display (implicit)
Luis Mendo
fonte
1

APL (Dyalog Unicode) , 192 78 bytes

⊂{t/⍵⊣⍵{t[m]←('01!'⍳⍵)⊃0 1,e,⍨~et[m←⍺|ii+←¯1 1 0⊃⍨'<>'⍳⍵]}¨⍺⊣i←⊃t←⍬⍳⍺}¨1+⍳∘≢

Experimente 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:

Observe que esse é o seu programa exato, exceto usando indexação em vez de interna: Ifs e recolhendo: For-loops para {_} ¨ enquanto fornece um argumento à esquerda para substituir o global.

A função assume ⎕IO←0 .


Quão?

(Esta explicação usa uma versão "não destruída" para facilitar a leitura)

⊂{                                   Enclose
      i←⊃t←⍬⍳⍺                       Assign a vector of 0s to t (the tape), then assign the first 0 to i.
      t/⍵⊣⍵{                         Use  as left argument for the nested function, then compress the result into t. If there is a 1 anywhere in t, the result will be a vector of the result. If not, the result is an empty vector.
          i+←¯1 1 0⊃⍨'<>'⍳⍵          Map the string '<>' to the argument (which is the BF program). That yields 0 for <, 1 for >, and 2 for anything else.
                                     The resulting vector will then be used as the argument for  to add -1 (index 0), 1 (index 1) or 0 (index 2) to the variable i.
          et[m←⍺|i]                 Assign i mod  (left arg) to m, and use it to index t. Then, assign the value to e.
          t[m]←('01!'⍳⍵)⊃0 1,e,⍨~e   Map the string '01!' to ⍵. As before, this yields 0 for 0, 1 for 1, 2 for ! and 3 for anything else.
                                     Then, concatenate (not e) with e, then concatenate that with the vector 0 1. This is used as argument to be picked from, and it is assigned to t[m].
      }¨⍺                            Do that for each argument
  1+⍳∘≢                            And do that for each possible tape length from 1 to the length of the input.
J. Sallé
fonte
11
Salve um byte criando t←l⍴0be t←l⍴i←0e removendo a linha acima dele. Você também pode salvar outro alterando t[i|⍨≢t]←1-t[i|⍨≢t]para t[i|⍨≢t]←~t[i|⍨≢t].
Zacharý
2
@ Zacharý à direita e salve mais 112 bytes adicionais . Exatamente o mesmo código, apenas jogou um pouco de golfe.
Adám 08/0318
Sim, é apenas jogado "um pouco". Você não precisa dos ?
Zacharý
@ Zacharý O que é? É uma função tácita.
Adám
@ Zacharý Eu consideraria este um belo Adám'd, não é?
J. Sallé
0

C (clang) , 171 bytes

l,i;f(S){for(char*p,t[l=strlen(S)];l;memchr(t,1,l)&&printf("%d ",l),l--)for(memset(t,i=0,l),p=S;*p;p++)*p==60?i=i?i-1:l-1:*p==62?i=i^l-1?i+1:0:*p^33?t[i]=*p-48:(t[i]^=1);}

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 em strlenvez 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.

gastropner
fonte
Sugerir em i=0,bzero(t,l)vez de memset(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)
ceilingcat 20/12/19