Производная Brainfuck

Давайте определим простой Brainfuck- подобный язык программирования. Он имеет двунаправленную ленту ячеек, и каждая ячейка содержит один бит. Все биты изначально равны 0. На ленте имеется движущаяся головка, первоначально в позиции 0. Программа - это строка над символами <>01!, выполняемая слева направо, со следующей семантикой:

• < перемещает голову на один шаг влево.
• > перемещает голову на один шаг вправо.
• 0 ставит 0 в текущей ячейке.
• 1 ставит 1 в текущей ячейке.
• ! переворачивает текущую ячейку.

Циклов нет, поэтому программа из n символов завершается ровно после n шагов. Программа скучна, если все ячейки содержат 0 в конце выполнения, и захватывающая, если есть хотя бы один 1. Обратите внимание, что размер ленты не указан, поэтому в зависимости от реализации он может быть двусторонним бесконечным или круговой.

Пример программы

Рассмотрим программу 1>>>!<<<<0>!>>>!. На бесконечной ленте выполнение выполняется следующим образом:

     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

В конце все ячейки равны 0, так что эта программа скучная. Теперь давайте запустим ту же программу на круговой ленте длиной 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

На этот раз есть ячейка со значением 1, поэтому программа захватывающая! Мы видим, что скучная или захватывающая программа зависит от размера ленты.

Задание

Ваш ввод представляет собой непустую строку, <>01!которая представляет программу на вышеуказанном языке программирования. Массив символов также является приемлемым форматом ввода. Программа гарантированно будет скучной при запуске на бесконечной ленте. Ваш вывод должен быть списком длин ленты, на которых программа является захватывающей. Обратите внимание, что вам нужно тестировать программу только на лентах, которые короче длины программы.

Решение с наименьшим количеством байтов на каждом языке является победителем. Применяются стандартные правила игры в гольф .

Контрольные примеры

> : []
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]

Haskell, 119 байт

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]

Попробуйте онлайн!

Функция #является интерпретатором для одной команды c. Вся программа pуправляет foldING #со стартовой лентой в p. fвыполняется pдля каждой ленты и сохраняет те, где сумма ячеек составляет не менее 1.

Stax , 56 54 43 38 35 байт ^CP437

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

42 байта в распакованном виде,

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

Запускать и отлаживать онлайн!

-2 байта за комментарий @recursive

объяснение

Я буду использовать версию с префиксом i (то есть i%fz(y{{|(}{|)}{B!s+}{0_]e&}4ls"><! "I@!F|a), чтобы объяснить, и я объясню, почему iможно удалить

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

Код для запуска программы:

{|(}                                 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.

CJam, 57 56 49 46 bytes

^{-7 thanks to @MartinEnder}

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

Try it online!

Perl 5, 83 82 79 77 bytes

Includes +3 for -F

Give instructions as one line on STDIN

#!/usr/bin/perl -F
1~~@$m&&say$m until++$m>map{*r=\$$m[($n+=/>/-/</)%$m];$r=/\d/?$&:$r^/!/}@F

Try it online!

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

Try it online!

Red, 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]]]

Try it online!

Prety verbose and straightforward implementation. Red's 1-indexing doesn't allow me to reduce the byte count by using modular arithmetic for looping through the circular tapes.

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]
    ]
]

Python 2, 139 135 133 132 131 bytes

-3 bytes thanks to Mr. 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)

Try it online!

Retina, 121 bytes

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

Try it online! Explanation:

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

Create an array of tapes of each length up to the length of the input program.

{

Loop until the program is consumed.

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

If the next character in the program is a 0 or 1, change the first character on each line to that character.

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

If it is a ! then toggle the first character on each line.

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

If it is a > or < then rotate the line. (Easier than moving the head.)

)`¶¶.
¶¶

Delete the instruction and end the loop.

G`1

Keep only the exciting lines.

%`.

Count the length of each line.

JavaScript (ES6), 126 118 bytes

Saved 3 bytes thanks to @user71546

Takes input as an array of 1-character strings.

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):[]

Try it online!

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

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

Try it online!

-15 thanks to Adám (forgot about monadic ⍸).
-10 thanks to ngn.

MATL, 46 39 bytes

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

Try it online! Or verify all test cases.

How it works

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)

APL (Dyalog Unicode), 192 78 bytes

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

Try it online! (non-flattened result)

Try it online! (flattened)

After some time spent banging my head against the wall, I decided to make a Tradfn instead of a Dfn. This is the result. Smarter people than me may be able to golf the heck out of this.

Surprise, surprise, someone smarter than me did golf the heck out of this. Thank you Adám for 114 bytes.

He said:

Notice that it is your exact program, except using indexing instead of the inner :Ifs and collapsing :For-loops to {_}¨ while giving a left argument to replace the global.

The function assumes ⎕IO←0.

How?

(This explanation uses an "ungolfed" version to facilitate reading)

⊂{                                  ⍝ 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.
          e←t[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.

Jelly, 41 bytes

JR0ṁð3“1⁺¦01¦¬1¦ṙ1 ṙ- ”s“10!<>”,yẎvЀ⁸Ẹ€T

Try it online!

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);}

Try it online!

Had to use clang, since using char*p,t[l=strlen(S)] as the initialisation expression for some reason makes GCC think I want to declare strlen instead of calling it.

Pretty straight-forward: Runs the program on circular tapes of decreasing length, outputting any length that resulted in a 1 somewhere on the tape.

Tried shortening the tangle of the ternary operators, but ended up needing more parenthesis than was healthy.