Czy okrągłe taśmy są ekscytujące?

32

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 .

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]
Zgarb
źródło
1
Czy możemy wybrać jakieś wyraźne i spójne postacie zamiast <>01!?
Pan Xcoder
1
Czy tablica instrukcji jest akceptowalnym wejściem?
Arnauld
@ Mr.Xcoder Nie, powinieneś używać dokładnie tych znaków.
Zgarb
@Arnauld Tablica znaków jest wystarczająco blisko ciągu, pozwolę na to.
Zgarb

Odpowiedzi:

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.

nimi
źródło
n<-[1..length p] ... 0<$[1..n]wydaje się dość długa, musi być krótsza droga.
nimi
Nie widzę krótszej drogi. Problem, który widzę, polega na tym, że tak naprawdę potrzebujesz wartości njako wyniku, więc jeśli skonstruowałeś 0<$[1..n]inny sposób (powiedzmy z scanr(:)), musisz wziąć lengthto. (Próbowałem też za pomocą 1(wymienić lengthz sum) lub False(by użyć ordo testu) zamiast 0, ale to nie wyjdzie krótszy.)
Ørjan Johansen
@ ØrjanJohansen: tak, próbowałem, n<-init$scanr(:)[]$0<$p ... nktóry jest o 2 bajty krótszy, ale zwraca listę początkowych taśm zamiast ich długości, np [[0],[0,0,0]]. Przy odrobinie wyginania reguł mógłbym zobaczyć taśmy jako liczby jednoargumentowe, więc może jest w porządku.
nimi
init$można go zastąpić umieszczeniem [0]listy początkowej, ale wciąż nie była wystarczająco krótka. Myślę, że jednoargumentowe jest dozwolone tylko w przypadku języków bez bardziej naturalnej reprezentacji liczb .
Ørjan Johansen
4

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.
Weijun Zhou
źródło
1
Dodałem przypadek testowy wszystkich cyfr, aby sprawdzić poprawność iczeku.
Zgarb
0]*można zastąpić z(. Ponadto, jeśli zmienisz ciąg znaków na „<>!”, Wtedy 0i 1da indeks -1, więc w ten sposób twoja lista bloków potrzebuje tylko 4 bloków zamiast 5. To zadziała, ponieważ 0i 1handlery i tak są identyczne.
rekursywny
@recursive Dobra uwaga.
Weijun Zhou
2

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!

Xcali
źródło
2

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]
    ]
]
Galen Iwanow
źródło
2

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!

Pręt
źródło
131 bajtów?
Pan Xcoder
2

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.

Neil
źródło
2

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!

Arnauld
źródło
Zamieniając t.some(x=>x)?na +t.join``?zamiast tego sprawdź tablicę jako cyfry (a 0 oznacza całkowicie zerową taśmę), ale o 3 bajty mniej.
Shieru Asakoto
2

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 .

Erik the Outgolfer
źródło
64
Adám
@ Adám Hm, wygląda na to, że nie jest to optymalne (na przykład nie potrzebujesz ). Zajrzę do niego i zaktualizuję. :)
Erik the Outgolfer
Ale jeśli je usuniesz , będziesz potrzebować ;, nie?
Adám
@ Adám nie , dlaczego miałbyś?
Erik the Outgolfer
1

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)
Luis Mendo
źródło
1

APL (Dyalog Unicode) , 192 78 bajtów

⊂{t/⍵⊣⍵{t[m]←('01!'⍳⍵)⊃0 1,e,⍨~et[m←⍺|ii+←¯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.
          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é
źródło
1
Zapisz jeden bajt, tworząc t←l⍴0be t←l⍴i←0i usuwając linię nad nim. Możesz także zapisać inny, zmieniając t[i|⍨≢t]←1-t[i|⍨≢t]na t[i|⍨≢t]←~t[i|⍨≢t].
Zacharý
2
@ Zacharý prawo, i dodatkowo zapisać dodatkowe 112 bajtów . Dokładnie ten sam kod, tylko trochę grałem w golfa.
Adám,
Tak, to tylko trochę „gol”. Nie potrzebujesz s?
Zacharý
@ Zacharý What s? Jest to funkcja ukryta.
Adám
@ Zacharý Rozważałbym ten ładny Adám'd, prawda?
J. Sallé,
0

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.

gastropner
źródło
Sugeruj i=0,bzero(t,l)zamiast memset(t,i=0,l)i *p-62?t[i]=*p^33?*p-48:t[i]^1:(i=~i+l?i+1:0)zamiast*p==62?i=i^l-1?i+1:0:*p^33?t[i]=*p-48:(t[i]^=1)
ceilingcat