Sind Rundbänder spannend?

32

Ein Brainfuck-Derivat

Definieren wir eine einfache Brainfuck- ähnliche Programmiersprache. Es verfügt über ein bidirektionales Zellenband, und jede Zelle enthält ein Bit. Alle Bits sind anfänglich 0. Auf dem Band befindet sich ein sich bewegender Kopf, der sich anfänglich an Position 0 befindet. Ein Programm ist eine Zeichenfolge über den Zeichen <>01!, die von links nach rechts mit der folgenden Semantik ausgeführt wird:

  • < bewegt den Kopf einen Schritt nach links.
  • > bewegt den Kopf einen Schritt nach rechts.
  • 0 setzt 0 in die aktuelle Zelle.
  • 1 setzt 1 in die aktuelle Zelle.
  • ! Kippt die aktuelle Zelle.

Da es keine Schleifen gibt, endet ein Programm mit n Zeichen nach genau n Schritten. Ein Programm ist langweilig, wenn alle Zellen am Ende der Ausführung 0 enthalten, und aufregend, wenn mindestens eine 1 vorhanden ist. Beachten Sie, dass die Größe des Bandes nicht angegeben ist. Je nach Implementierung kann sie also in beide Richtungen unendlich oder unendlich sein kreisförmig.

Ein Beispielprogramm

Betrachten Sie das Programm 1>>>!<<<<0>!>>>!. Auf einem unendlichen Band läuft die Ausführung wie folgt ab:

     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

Am Ende sind alle Zellen 0, daher ist dieses Programm langweilig. Lassen Sie uns nun dasselbe Programm auf einem kreisförmigen Band der Länge 4 ausführen.

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

Dieses Mal gibt es eine Zelle mit dem Wert 1, das Programm ist also aufregend! Wir sehen, ob ein Programm langweilig oder aufregend ist, hängt von der Größe des Bandes ab.

Die Aufgabe

Ihre Eingabe ist eine nicht leere Zeichenfolge <>01!, die ein Programm in der obigen Programmiersprache darstellt. Ein Array von Zeichen ist auch ein akzeptables Eingabeformat. Das Programm ist garantiert langweilig, wenn es auf einem endlosen Band abgespielt wird. Ihre Ausgabe soll die Liste der Bandlängen sein, auf denen das Programm spannend ist. Beachten Sie, dass Sie das Programm nur auf Bändern testen müssen, die kürzer als die Programmlänge sind.

Die Lösung mit der niedrigsten Byteanzahl in jeder Sprache ist der Gewinner. Es gelten die Standardregeln für .

Testfälle

> : []
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
quelle
1
Können wir stattdessen eindeutige und konsistente Zeichen wählen <>01!?
Mr. Xcoder
1
Ist ein Array von Anweisungen eine akzeptable Eingabe?
Arnauld
@ Mr.Xcoder Nein, Sie sollten genau diese Zeichen verwenden.
Zgarb
@Arnauld Ein Array von Zeichen ist nah genug an einer Zeichenfolge, ich werde es zulassen.
Zgarb

Antworten:

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]

Probieren Sie es online!

Function #ist der Interpreter für einen einzelnen Befehl c. Das gesamte Programm pwird durch laufen folding #mit dem Startband in p. fwird pfür jedes Band ausgeführt und behält diejenigen bei, bei denen die Summe der Zellen mindestens 1 beträgt.

nimi
quelle
n<-[1..length p] ... 0<$[1..n]scheint ziemlich lang zu sein, es muss einen kürzeren Weg geben.
nimi
Ich kann keinen kürzeren Weg sehen. Das Problem, das ich sehe, ist, dass Sie tatsächlich den Wert von nals Ergebnis benötigen. Wenn Sie also 0<$[1..n]einen anderen Weg konstruieren (sagen wir mit scanr(:)), müssen Sie den lengthdavon nehmen. (Ich habe auch versucht, 1(zu ersetzen lengthdurch sum) oder False( orfür den Test zu verwenden) 0, aber es kam nicht kürzer heraus.)
Ørjan Johansen
@ ØrjanJohansen: ja, ich habe versucht, n<-init$scanr(:)[]$0<$p ... ndie 2 Bytes kürzer ist, aber es gibt eine Liste der Startbänder anstelle ihrer Länge zurück, z [[0],[0,0,0]]. Mit ein bisschen Regelbiegen könnten die Bänder also als unäre Zahlen angesehen werden, also ist es vielleicht ok.
nimi
init$kann durch eine [0]erste Liste ersetzt werden, wurde aber immer noch nicht kurz genug. Ich denke, Unary ist nur für Sprachen ohne eine natürlichere Zahlendarstellung zulässig .
Ørjan Johansen
4

Stax , 56 54 43 38 35 Bytes CP437

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

42 Bytes beim Auspacken,

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

Online ausführen und debuggen!

-2 Bytes pro Kommentar von @recursive

Erläuterung

Ich werde die Version mit einem Präfix i(dh i%fz(y{{|(}{|)}{B!s+}{0_]e&}4ls"><! "I@!F|a) verwenden, um zu erklären, warum das ientfernt werden kann

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

Code zum Ausführen des Programms:

{|(}                                 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
quelle
1
Ich habe einen Testfall aller Ziffern hinzugefügt, um Ihren iScheck zu validieren .
Zgarb
0]*kann durch ersetzt werden z(. Auch, wenn Sie die Zeichenfolge ändern „<>“, dann 0und 1geben Index -1, so dass Art und Weise Ihre Sperrliste nur 4 Blöcke benötigt, statt 5. dies funktionieren wird , da die 0und 1Handler identisch ohnehin sind.
rekursive
@recursive Guter Punkt genommen.
Weijun Zhou
2

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

Probieren Sie es online!

Sehr ausführlich und unkompliziert. Mit der 1-Indizierung von Red kann ich die Byteanzahl nicht reduzieren, indem ich eine modulare Arithmetik zum Durchlaufen der kreisförmigen Bänder verwende.

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
quelle
2

Python 2 , 139 135 133 132 131 Bytes

-3 Bytes dank Herrn 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)

Probieren Sie es online!

Stange
quelle
131 Bytes?
Mr. Xcoder
2

Retina , 121 Bytes

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

Probieren Sie es online! Erläuterung:

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

Erstellen Sie ein Array von Bändern jeder Länge bis zur Länge des Eingabeprogramms.

{

Schleife, bis das Programm verbraucht ist.

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

Wenn das nächste Zeichen im Programm eine 0 oder 1 ist, ändern Sie das erste Zeichen in jeder Zeile in dieses Zeichen.

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

Wenn es sich um ein handelt, !schalten Sie das erste Zeichen in jeder Zeile um.

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

Wenn es ein >oder <ist, drehen Sie die Linie. (Einfacher als den Kopf zu bewegen.)

)`¶¶.
¶¶

Löschen Sie die Anweisung und beenden Sie die Schleife.

G`1

Behalte nur die aufregenden Linien.

%`.

Zählen Sie die Länge jeder Zeile.

Neil
quelle
2

JavaScript (ES6), 126 118 Byte

3 Bytes gespart dank @ user71546

Nimmt die Eingabe als Array von 1-Zeichen-Zeichenfolgen.

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

Probieren Sie es online!

Arnauld
quelle
Ersetzen t.some(x=>x)?durch, +t.join``?überprüfen Sie das Array stattdessen als Ziffern (und 0 zeigt ein Band mit Nullen an), aber 3 Bytes weniger.
Shieru Asakoto
2

APL (Dyalog Unicode) , 79 64 54 Byte ( Adáms SBCS )

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

Probieren Sie es online!

-15 Dank an Adám (vergessen über Monade ).
-10 danke an ngn .

Erik der Outgolfer
quelle
64
Adám
@ Adám Hm, sieht so aus, als wäre das nicht optimal (zum Beispiel brauchst du das nicht ). Ich werde es überprüfen und aktualisieren. :)
Erik der Outgolfer
Aber wenn du das entfernst, brauchst du ein ;, nein?
Adám
@Adam nein , warum würdest du?
Erik der Outgolfer
1

MATL , 46 39 Bytes

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

Probieren Sie es online! Oder überprüfen Sie alle Testfälle .

Wie es funktioniert

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
quelle
1

APL (Dyalog Unicode) , 192 78 Bytes

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

Probieren Sie es online! (nicht abgeflachtes Ergebnis)

Probieren Sie es online! (abgeflacht)

Nachdem ich einige Zeit damit verbracht hatte, meinen Kopf gegen die Wand zu schlagen, entschloss ich mich, einen Tradfn anstelle eines Dfn zu machen. Das ist das Ergebnis. Klügere Leute als ich sind vielleicht in der Lage, daraus Golf zu spielen.

Überraschung, Überraschung, jemand, der schlauer als ich war, hat das zum Teufel gemacht. Vielen Dank, dass Sie Adám für 114 Bytes.

Er sagte:

Beachten Sie, dass es sich um Ihr genaues Programm handelt, außer bei Verwendung der Indizierung anstelle des inneren: Ifs und Collapsing: For-Schleifen zu {_} ¨, während Sie ein linkes Argument angeben, um das globale zu ersetzen.

Die Funktion übernimmt ⎕IO←0.


Wie?

(Diese Erklärung verwendet eine "ungolfed" Version, um das Lesen zu erleichtern)

⊂{                                   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é
quelle
1
Speichern Sie ein Byte, indem Sie t←l⍴0be erstellen t←l⍴i←0und die darüber stehende Zeile entfernen. Sie können andere auch sparen , indem Sie t[i|⍨≢t]←1-t[i|⍨≢t]auf t[i|⍨≢t]←~t[i|⍨≢t].
Zacharý
2
@ Zacharý richtig, und weitere 112 Bytes speichern . Genau derselbe Code, nur ein bisschen Golf gespielt.
Adám
Ja, es ist nur "ein bisschen" goled. Brauchst du das nicht ?
Zacharý
@ Zacharý Was ist ? Es ist eine stillschweigende Funktion.
Adám
@ Zacharý Ich würde das für einen hübschen Adám'd halten, nicht wahr?
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);}

Probieren Sie es online!

Musste clang verwenden, da die Verwendung char*p,t[l=strlen(S)]als Initialisierungsausdruck aus irgendeinem Grund GCC denken lässt, dass ich deklarieren möchte, strlenanstatt es aufzurufen.

Ganz einfach: Führt das Programm auf kreisförmigen Bändern mit abnehmender Länge aus und gibt eine beliebige Länge aus, die irgendwo auf dem Band zu einer 1 führte.

Versuchte, das Gewirr der ternären Operatoren zu verkürzen, benötigte jedoch mehr Klammern als gesund.

Gastropner
quelle
Schlagen Sie vor, i=0,bzero(t,l)anstelle von memset(t,i=0,l)und *p-62?t[i]=*p^33?*p-48:t[i]^1:(i=~i+l?i+1:0)anstelle von*p==62?i=i^l-1?i+1:0:*p^33?t[i]=*p-48:(t[i]^=1)
Ceilingcat