Brainf *** NOPs generieren

26

Wenn Sie Brainfuck-Code schreiben, müssen Sie ihn manchmal länger als nötig machen, um das Debuggen zu fördern . Sie könnten es tun, indem Sie einfach einen reinstecken ><, aber was für ein Spaß ist das? Sie brauchen etwas längeres und weniger NOPey, um jemanden zu verwirren, der Ihren Code liest.

Schnelle Einführung in Brainfuck

Brainfuck ist eine esoterische Programmiersprache, die 1993 von Urban Müller entwickelt wurde und sich durch extremen Minimalismus auszeichnet. (Wikipedia)

Brainfuck ist eine Sprache , basierend auf acht Befehle: +-><,.[]. Der Code wird auf so etwas wie einer Turing-Maschine ausgeführt: einem unendlichen Band, auf dem Werte geändert werden können. In dieser Herausforderung konzentrieren wir uns auf die ersten vier:

+    increment the value at the pointer
-    decrement the value at the pointer
>    move the pointer right
<    move the pointer left

Brainfuck NOPs

Ein Brainfuck-NOP ist eine Folge von Brainfuck-Zeichen, die, wenn sie aus einem beliebigen Zustand ausgeführt werden, zu keiner Änderung des Zustands führen. Sie bestehen aus den vier oben genannten Zeichen.

Die Herausforderung

Die Herausforderung besteht darin, ein Programm oder eine Funktion zu schreiben, die bei Ausführung eine zufällige Brainfuck-NOP der angegebenen Länge generiert.

Eingang

Sie erhalten als Eingabe eine nicht negative gerade Ganzzahl n. (NOPs sind für ungerade unmöglich n.)

Ausgabe

Sie geben eine zufällige Brainfuck-NOP der Länge aus n.

Regeln

  • Die Definition von NOP: Wenn die Ausgabe des Programms an einer beliebigen Stelle in ein Brainfuck-Programm eingefügt wird, darf sich das Verhalten des Programms in keiner Weise ändern. Mit anderen Worten, es darf den Status des Interpreters nicht ändern.
    • Beachten Sie, dass dies beispielsweise +>-<falsch ist, da die Werte der beiden Zellen geändert werden, ohne dass sie zurückgesetzt werden. Bitte testen Sie Ihre Lösung für diese vor dem Posten.
    • Beachten Sie auch, dass +>-<->+<es sich um eine NOP handelt, die nicht einfach durch Entfernen auf Null reduziert werden kann>< <> +- -+ . Daher können Sie keinen Algorithmus verwenden, der diese nur ineinanderfügt.
  • Jede gültige NOP der Länge n muss eine von Null verschiedene Chance haben, in der Ausgabe zu erscheinen. Die Verteilung muss jedoch nicht einheitlich sein.
  • Der fragliche Brainfuck-Interpreter hat ein doppelt unendliches Band beliebig präziser Zellen. Das heißt, Sie können unendlich in beide Richtungen gehen und jede Zelle auf unbestimmte Zeit inkrementieren / dekrementieren.
  • Das Programm muss innerhalb von 1 Minute für n= 100 beendet sein auf meinem Computer beendet sein, damit nicht alle möglichen NOPs generiert und eine ausgewählt werden.
  • Bei einer ungültigen Eingabe (nicht ganzzahlig, negativ, ungerade usw.) können Sie alles tun, was Sie möchten, einschließlich Absturz.

Wertung

Das ist , also gewinnt die kürzeste Antwort in Bytes.

Beispiele

Hier sind alle gültigen Ausgaben für n= 4:

++--    +-+-    +--+    --++    -+-+    -++-
>><<    ><><    ><<>    <<>>    <><>    <>><
><+-    ><-+    <>+-    <>-+
>+-<    >-+<    <+->    <-+>
+><-    -><+    +<>-    -<>+
+-><    -+><    +-<>    -+<>

Hier sind einige mögliche Ausgaben für n= 20:

+>>->+<->-<<<->>++<<
>+>-<+<->+-<>->+<-<+
+--+-++--++-+--+-++-
>>>>>>>>>+-<<<<<<<<<
PurkkaKoodari
quelle
18
Hier ist ein Brainfuck-NOP, der nicht so verwendet wird, +-<>wie Sie es gewünscht haben:a
undergroundmonorail
1
Ich glaube nicht, dass es nicht einfache NOPs gibt, also können Sie diese Qualifikation wahrscheinlich entfernen. .hat eine Nebenwirkung, ,überschreibt einen Wert, der nicht ohne die Verwendung von wiederhergestellt werden kann []. []Wird aber am Ende einen Wert auf Null setzen. Dadurch wird auch ein Wert überschrieben (sodass wir einen anderen Wert benötigen [], um ihn wiederherzustellen), es sei denn, wir können sicher sein, dass die betroffene Zelle von Anfang an Null war. Wir müssten jedoch mit so etwas wie nach einer solchen Zelle suchen [>], und es ist unmöglich, zuverlässig zu der Position zurückzukehren, von der wir gekommen sind.
Martin Ender
4
@Eumel "Der fragliche Brainfuck-Interpreter hat ein doppelt unendliches Band beliebiger Präzisionszellen."
Martin Ender
2
Bitte beachten Sie, dass "Brainfuck" in Fragentiteln auf Systemebene nicht mehr erlaubt ist . Es scheint, dass Sie die Einschränkung umgehen konnten, indem Sie Nicht-ASCII-Zeichen verwendeten. Bitte halten Sie sich in Zukunft an diese Einschränkung.
Alex A.
2
@undergroundmonorail Nun, es ist Turing komplett ... also kann man technisch wie jede andere Sprache ein PRNG darin schreiben. (Obwohl die Aussaat schwierig sein könnte.)
PurkkaKoodari

Antworten:

13

CJam, 62 59 Bytes

Danke an nhahtdh für das Speichern von 3 Bytes.

Da keine bestimmte Verteilung erforderlich ist, solange jedes No-Op mit endlicher Wahrscheinlichkeit angezeigt wird, können wir dies erheblich vereinfachen, indem wir einfach eine Zeichenfolge mit einer ausgeglichenen Anzahl von -+und <>bzw. erstellen, um zu testen, ob es sich um eine NOP handelt, und sie gegebenenfalls sortieren ist nicht.

Natürlich führt dies bei längeren Eingaben fast immer zu einer sortierten Ausgabe, aber Sie können den Code mit einigen Eingaben testen, um 8zu sehen, dass er im Prinzip jede NOP mit der angegebenen Länge erzeugen kann.

ri_0a*\2/{;"-+<>":L2/mR}%smr:SL["Xa.Xm"3/2e*L]z:sers~0-S$S?

Probieren Sie es online aus.

Martin Ender
quelle
1
Ja ... das willkürliche Limit sollte unter 10 Sekunden n = 1000 sein. Computer sind heute einfach zu schnell ^^ Weil die algorithmische Antwort sie in weniger als einer Sekunde löst, sogar für n = 1000
Falco
Für noch größere n ist es meiner Meinung nach möglich, die Ausgabe einfach zu sortieren, wenn die symmetrische Zeichenfolge nicht NOP ist. Die Verteilung ist furchtbar schief, aber die Frage erlaubt es.
n̴̖̋h̷͉̃a̷̭̿h̷̭̿d̷̰̀ĥ̷̳
@ n̴̖̋h̴̖̋ã̷͉h̷̭̿d̷̰̀ĥ̷̳ das ist eine nette Idee.
Martin Ender
@ n̴̖̋h̴̖̋ã̷͉h̷̭̿d̷̰̀ĥ̷̳ Danke, das spart auch hier drei Bytes.
Martin Ender
16

CJam, 118 116 Bytes

Dies geriet etwas außer Kontrolle ... vor allem in der zweiten Hälfte scheint es, als ob es sehr golfen könnte.

ri2/_)mr:R-"<>"R*mr_'=fm0\{1$+}%+__&e`]:\{mr1aa..+}*\@](\z:~\{~\("+-"*mr1$3$e=[{_,)mr_2$<@@>}*+]@@f{`1$`={(}@?\}W<}/

Teste es hier.

Das geht so N = 100ziemlich sofort. Ich habe jetzt keine Zeit, die vollständige Aufschlüsselung des Codes zu schreiben. Deshalb hier der Algorithmus:

  • Generieren einen Zufall ausgewogenes String <und >mit zufälliger (auch) Länge zwischen 0und Neinschließlich.
  • Riffeln Sie die Bandkopfpositionen in dieses Array. ZB "<>><"wird [0 '< -1 '> 0 '> 1 '< 0].
  • Holen Sie sich eine Liste aller im Prozess erreichten Positionen.
  • Initialisieren Sie für jede dieser Positionen eine leere Zeichenfolge. Bestimmen Sie auch, wie viele Zeichenpaare übrig bleiben, um eine Zeichenfolge zu erreichen N.
  • Für jedes verbleibende Paar +-an die Zeichenfolge einer zufälligen Position anhängen .
  • Mische alle diese Saiten.
  • Bestimmen Sie für jede Position, wie oft diese Position im geriffelten Array vorkommt, und teilen Sie die entsprechende Zeichenfolge in so viele Stücke (zufälliger Länge) auf.
  • Ersetzen Sie im geriffelten Array das Vorkommen der Position durch ihre zufälligen Abschnitte.

Getan. Dies basiert auf der Beobachtung, dass:

  • Jeder NOP muss den gleichen Betrag von <und haben >, um den Bandkopf in die ursprüngliche Position zurückzubringen.
  • Der Code ist ein NOP, solange jede Bandzelle so oft inkrementiert wird, wie sie dekrementiert wird.

Indem wir zufällige, aber ausgeglichene Mengen von +s und -s auf alle Stellen verteilen, an denen sich der Bandkopf auf einer bestimmten Zelle befindet, stellen wir sicher, dass wir jede mögliche NOP finden.

Martin Ender
quelle
4

Mathematica, 350 Bytes

Quiet@(For[a="+",If[{##4}=={},#3!=0||Union@#!={0},Switch[#4,"+",#0[ReplacePart[#,#2->#[[#2]]+1],#2,#3,##5],"-",#0[ReplacePart[#,#2->#[[#2]]-1],#2,#3,##5],">",#0[#~Append~0,#2+1,#3+1,##5],"<",If[#2<2,#0[#~Prepend~0,1,#3-1,##5],#0[#,#2-1,#3-1,##5]]]]&@@{{0},1,0}~Join~Characters@a,a=""<>RandomSample@Flatten@RandomChoice[{{"+","-"},{">","<"}},#/2]];a)&

Viel zu lang? Ja. Interessiert es mich überhaupt? Erst wenn jemand anderes eine gültige Antwort veröffentlicht.

LegionMammal978
quelle
4
Würde es Ihnen etwas ausmachen, eine Erklärung hinzuzufügen, damit die Leute sich selbst davon überzeugen können, dass dies gültig ist? :)
Martin Ender
Wie genau funktioniert das? Wenn ich die Funktion mit einer Nummer aufrufe, wird nur zurückgegeben +.
Martin Ender
@ MartinBüttner Feste ... Derzeit erzeugt sie nur zufällige Programme mit einer gleichen Anzahl von +- -und <- >Paaren , bis man ein NOP passiert zu sein. Die Hälfte davon wird von einem einfachen BF-Dolmetscher übernommen.
LegionMammal978
erzeugt das tatsächlich ein gültiges no-op der länge 100 in weniger als einer minute?
Martin Ender
@ MartinBüttner Ja. Im Durchschnitt würde ich sagen, dass es ungefähr 5 Sekunden dauert. Zuerst habe ich völlig zufällige Programme ausprobiert, aber es wurde nie für die Länge 100 beendet.
LegionMammal978
2

Python 3 , 177 Bytes

from random import*
n=int(input())
r=[0]*n*3
p=0
a=[43,45]
s=choices(a+[60,62],k=n)
for c in s:p+=~c%2*(c-61);r[p]+=c%2*(44-c)
if any(r+[p]):s=a*(n//2)
print(*map(chr,s),sep='')

Probieren Sie es online!

Ich habe Code aus Bubblers Antwort für die BF-Simulation verwendet.

Tyilo
quelle
2

Python 3 , 163 Bytes

from random import*
n=int(input())
p=0;d=[0]*n;a=choices(b'+-<>',k=n)
for c in a:d[p]+=c%2*(44-c);p+=~c%2*(c-61)
if p|any(d):a=n//2*b'+-'
print(*map(chr,a),sep='')

Probieren Sie es online!

Vollständiges Programm, das die Ergebnisse an STDOUT ausgibt. Die Zeile, in der BF-Code ausgeführt wird, ist möglicherweise golfen.

Nahm Tyilos Ansatz an; Wenn der generierte BF-Code kein NOP ist, verwerfen Sie ihn vollständig und greifen Sie auf Repeat zurück '+-'.

Bubbler
quelle
Timeout für n = 100
l4m2
@ l4m2 Diese Anforderung wurde nicht beachtet. Fest.
Bubbler
1

JavaScript (Node.js) , 160 Byte

n=>[...s=c(i=n,t=c(n/2,r=[],f=_=>'+-'),f=_=>'+-<>'[Math.random()*4|0])].map(_=>_<'<'?(r[i]=_+1-~r[i]-1):(i+=_<'>'||-1))|r.some(eval)|i-n?t:s;c=n=>n?c(n-1)+f():r

Probieren Sie es online!

l4m2
quelle
1

Wolfram Language (Mathematica) , 224 Bytes

(s=RandomSample[##&@@@Table["<"">",(r=RandomInteger)[#/2]]];While[(g=Length@s)<#,s=Insert[s=Insert[s,"+",i=r@g+1],"-",RandomChoice@@Select[GatherBy[0~Range~++g,Count[#,"<"]-Count[#,">"]&@Take[s,#]&],!FreeQ[#,i]&]+1]];""<>s)&

Probieren Sie es online!

Hier ist die Version ohne Golf (oder besser gesagt mit Pre-Golf):

Function[{n},
 k = RandomInteger[n/2];
 s = RandomSample[## & @@@ Table["<" ">", k]];
 While[Length[s] < n,
   s = Insert[s, "+", i = RandomInteger[Length[s]] + 1];
   p = GatherBy[Range[0, Length[s]], 
     Count[#, "<"] - Count[#, ">"]& @ Take[s, #]&];
   j = RandomChoice @@ Select[p, ! FreeQ[#, i] &]];
   s = Insert[s, "-", j + 1];
   ];
 ""<>s]

Wir wählen zuerst eine Zufallszahl von < 's und> ' s aus und generieren eine zufällige Liste mit jeweils der gleichen Anzahl.

Um den Rest der Zeichen auszufüllen, wählen wir eine Position aus, an der ein Zeichen hinzugefügt werden +soll. Suchen Sie dann eine Position, an der der Zeiger auf dieselbe Stelle zeigt, und fügen Sie dort ein Zeichen ein -.

Wiederholen Sie diesen nVorgang, bis die Liste lang ist , und fassen Sie das Ergebnis zusammen.

Mischa Lawrow
quelle