Pochodna Brainfuck

Zdefiniujmy prosty język programowania podobny do Brainfuck . Ma dwukierunkową taśmę komórek, a każda komórka zawiera jeden bit. Wszystkie bity mają początkowo wartość 0. Na taśmie porusza się głowa, początkowo w pozycji 0. Program to ciąg znaków nad znakami <>01!, wykonywany od lewej do prawej, z następującą semantyką:

• < przesuwa głowę o krok w lewo.
• > przesuwa głowę o krok w prawo.
• 0 wstawia 0 w bieżącej komórce.
• 1 wstawia 1 do bieżącej komórki.
• ! odwraca bieżącą komórkę.

Nie ma pętli, więc program n znaków kończy się dokładnie po n krokach. Program jest nudny, jeśli wszystkie komórki zawierają 0 na końcu wykonywania, i ekscytujący, jeśli jest co najmniej jeden. Zauważ, że rozmiar taśmy nie jest określony, więc w zależności od implementacji może być dwukierunkowy nieskończony lub okólnik.

Przykładowy program

Rozważ program 1>>>!<<<<0>!>>>!. Na nieskończonej taśmie wykonanie przebiega w następujący sposób:

     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

Na koniec wszystkie komórki mają wartość 0, więc ten program jest nudny. Teraz uruchommy ten sam program na okrągłej taśmie o długości 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

Tym razem jest komórka o wartości 1, więc program jest ekscytujący! Widzimy, że to, czy program jest nudny czy ekscytujący, zależy od rozmiaru taśmy.

Zadanie

Twoje dane wejściowe to niepusty ciąg znaków <>01!reprezentujący program w powyższym języku programowania. Tablica znaków jest również dopuszczalnym formatem wejściowym. Program na pewno będzie nudny, gdy zostanie uruchomiony na nieskończonej taśmie. Twój wynik będzie listą długości taśm, na których program jest ekscytujący. Pamiętaj, że musisz przetestować program tylko na taśmach krótszych niż długość programu.

Zwycięzcą jest rozwiązanie o najniższej liczbie bajtów w każdym języku. Obowiązują standardowe zasady gry w golfa .

Przypadki testowe

> : []
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 bajtów

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]

Wypróbuj online!

Funkcja #jest tłumaczem pojedynczego polecenia c. Cały program pjest uruchamiany przez foldwłożenie #taśmy początkowej do p. fwykonuje się pdla każdej taśmy i zachowuje te, w których suma komórek wynosi co najmniej 1.

Stax , 56 54 43 38 35 bajtów ^CP437

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

42 bajty po rozpakowaniu,

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

Uruchom i debuguj online!

-2 bajty na komentarz przez @recursive

Wyjaśnienie

Użyję wersji z prefiksem i(tj. i%fz(y{{|(}{|)}{B!s+}{0_]e&}4ls"><! "I@!F|a), Aby wyjaśnić i wyjaśnię, dlaczego imożna ją usunąć

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

Kod do uruchomienia programu:

{|(}                                 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 bajtów

^{-7 dzięki @MartinEnder}

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

Wypróbuj online!

Perl 5 , 83 82 79 77 bajtów

Obejmuje +3dla-F

Podaj instrukcje jako jedną linię na STDIN

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

Wypróbuj online!

Perl 5 ( -F), 101 bajtów

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

Wypróbuj online!

Czerwony , 243 bajty

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

Wypróbuj online!

Prety pełne i proste wdrożenie. 1-indeksowanie Reda nie pozwala mi zmniejszyć liczby bajtów przy użyciu arytmetyki modułowej do zapętlania okrągłych taśm.

Bez golfa

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 bajtów

-3 bajty dzięki 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)

Wypróbuj online!

Siatkówka , 121 bajtów

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

Wypróbuj online! Wyjaśnienie:

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

Utwórz tablicę taśm o każdej długości do długości programu wejściowego.

{

Pętla, aż program zostanie zużyty.

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

Jeśli następnym znakiem w programie jest 0 lub 1, zmień pierwszy znak w każdym wierszu na ten znak.

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

Jeśli jest !to, przełącz pierwszy znak w każdej linii.

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

Jeśli jest to >czy <następnie obrócić linię. (Łatwiejsze niż poruszanie głową.)

)`¶¶.
¶¶

Usuń instrukcję i zakończ pętlę.

G`1

Zachowaj tylko ekscytujące linie.

%`.

Policz długość każdej linii.

JavaScript (ES6), 126 118 bajtów

Zaoszczędzono 3 bajty dzięki @ user71546

Pobiera dane wejściowe jako tablicę ciągów 1 znaków.

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

Wypróbuj online!

APL (Dyalog Unicode) , 79 64 54 bajtów ( SBCS Adáma )

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

Wypróbuj online!

-15 dzięki Adámowi (zapomniałem o monadic ⍸).
-10 dzięki ngn .

MATL , 46 39 bajtów

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

Wypróbuj online! Lub sprawdź wszystkie przypadki testowe .

Jak to działa

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 bajtów

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

Wypróbuj online! (nie spłaszczony wynik)

Wypróbuj online! (spłaszczony)

Po pewnym czasie walenia głową w ścianę postanowiłem zrobić Tradfn zamiast Dfn. To jest wynik. Mądrzejsi ludzie ode mnie mogą grać w golfa.

Niespodzianka, niespodzianka, ktoś mądrzejszy ode mnie nie grał w golfa. Dziękuję Adám za 114 bajtów.

Powiedział:

Zauważ, że jest to twój dokładny program, z wyjątkiem użycia indeksowania zamiast wewnętrznego: Ifs i zwijania: pętle For do {_} ¨, podając lewy argument zastępujący globalny.

Funkcja zakłada ⎕IO←0 .

W jaki sposób?

(W tym objaśnieniu użyto wersji „bez golfa”, aby ułatwić czytanie)

⊂{                                  ⍝ 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.

Galaretka , 41 bajtów

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

Wypróbuj online!

C (clang) , 171 bajtów

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

Wypróbuj online!

Musiałem użyć clang, ponieważ użycie char*p,t[l=strlen(S)]z jakiegoś powodu wyrażenia inicjującego powoduje, że GCC myśli, że chcę zadeklarować strlenzamiast go wywoływać.

Całkiem proste: uruchamia program na okrągłych taśmach o malejącej długości, generując dowolną długość, która dawała 1 gdzieś na taśmie.

Próbowałem skrócić plątaninę operatorów trójskładnikowych, ale ostatecznie potrzebowałem więcej nawiasów niż było to zdrowe.