Brainf *** -Unterprogramme mit einzigartigen Ausgaben

19

Sie sollten ein 100 Byte langes Brainfuck-Programm (BF) schreiben.

Ein Zeichen entfernt auf jede erdenkliche Weise die 100 neuen (99 Byte langen) Programme. ZB für das Programm++.>. der 5 Unterprogramme sind +.>., +.>., ++>., ++..und ++.>.

Ihre Punktzahl ist die Anzahl der eindeutigen Ausgaben, die die 100 Programme generieren. Eine höhere Punktzahl ist besser.

Einzelheiten

  • Ihre Programme werden nach der Ausgabe des ersten Zeichens beendet.
  • Ungültige oder nicht beendete Programme und Programme, die leere Ausgaben erzeugen, werden nicht in die Punktzahl eingerechnet.
  • Die BF-Zellen sind 8-Bit-Wrapping-Zellen. (255 + 1 = 0, 0-1 = 255)
  • Ihr Programm erhält keine Eingabe. Wenn Sie ,im Code verwenden, wird die aktuelle Zelle auf gesetzt0 .
  • Auf der linken Seite der Startposition befinden sich keine Zellen. ZB <.ist ungültig, aber .<gültig, da die Ausführung um beendet wird. . Das Band ist in die andere Richtung ungebunden.
  • Programme mit unsymmetrischen Klammern ( [und ]) sind ungültig.
  • Ihr ursprüngliches Programm kann kürzer als 100 Bytes sein, da es leicht auf 100 Bytes erweitert werden kann, ohne die Punktzahl zu ändern.
  • Ihr ursprüngliches Programm muss kein gültiger BF-Code sein.

Sie können dieses python3-Programm (ideone link) verwenden , um die Bewertung Ihrer Antwort zu ermitteln. (Bei Programmen mit langer Laufzeit müssen Sie möglicherweise die maxstepVariable ändern .)

Beispiel

(Der Einfachheit halber ist dieses Programm kürzer als 100 Bytes.)

Solution: ++,+[-]+><.-,-.

Score: 3

Explanation:

Subprogram     => Output

+,+[-]+><.-,-. => 1
+,+[-]+><.-,-. => 1
+++[-]+><.-,-. => 1
++,[-]+><.-,-. => 1
++,+-]+><.-,-. => None
++,+[]+><.-,-. => None
++,+[-+><.-,-. => None
++,+[-]><.-,-. => 0
++,+[-]+<.-,-. => None
++,+[-]+>.-,-. => 0
++,+[-]+><-,-. => 255
++,+[-]+><.,-. => 1
++,+[-]+><.--. => 1
++,+[-]+><.-,. => 1
++,+[-]+><.-,- => 1

Unique outputs are [0, 1, 255]    
Score is 3 for ++,+[-]+><.-,-. (length = 15)

Bei Gleichstand gewinnt derjenige mit dem kürzeren Code. (Ihr Programm kann kürzer als 100 Byte sein, wie im Abschnitt Details angegeben.) Wenn die Codes gleich lang sind, ist der Gewinner das frühere Poster.

Bonus-Rätsel: Können Sie ohne die fett gedruckte Einschränkung ein Programm mit 100 Punkten finden?

randomra
quelle
Ich habe das Bonusrätsel gelöst. Die Antwort ist (zensiert).
AJMansfield
@AJMansfield Könnten Sie Ihren Kommentar bearbeiten, damit auch andere über das Rätsel nachdenken können? Ändern Sie beispielsweise Ihre Lösung in einen pastebin.com- Link, der die Antwort enthält.
Randomra
3
Hmm. Ich habe einen genetischen Optimierer für diese Frage geschrieben , um zu versuchen, Mikroverbesserungen für vorhandene Antworten zu finden, aber er ist bisher nicht sehr erfolgreich. Sie bleiben bei 79 und 43 hängen. Na ja - es war einen Versuch wert!
wchargin

Antworten:

12

Prüfungsergebnis: 35 41 69 78 79 83

(Entfernen Sie den Zeilenvorschub.)

-->+>->+>->+>->+>->+>->+>->+>->+>->+>->+>->+>->+>-
>+>->+>->+>->+>->+>->+>->+>->+>++[>[-<+++>]<<++]>.

Probieren Sie es online!

Ich weiß nicht genau, warum es funktioniert ...

Prüfungsergebnis: 79

X->>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>
+>+>+>+>+>+>+>+>+>+>+>+[>[-<+>>+<]+>[-<+>]<<<+]>>.

Probieren Sie es online!

Es sollte 2 * mem [i] * i summieren und die Anzahl der Zellen (+ const) addieren, in denen die Adressen von rechts nach links gezählt werden. Der Multiplikator 2 und die Anzahl der Zellen können bewirken, dass + und> mit unterschiedlicher Parität entfernt werden.

In der 69-Punkte-Version hat es in der Tat so geklappt. Aber die neueste Version hat das gebrochen und durch Zufall etwas anderes bekommen. Es berechnet die Summe (mem [i] * i + i + 1) und das Entfernen von + und> bewirkt fast dasselbe, mit Ausnahme der Summe (i), die eine Differenz der Anzahl der Zellen aufweist, die auch die Anzahl der verschiedenen Ausgaben ist Zum Entfernen von + und>.

Für den Bonus:

+. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +.

jimmy23013
quelle
Hinweis: Wenn Sie dies mit dem mitgelieferten Scorer-Programm testen, müssen Sie den maxstepWert (in def evaluate(r,maxstep=20000):) erhöhen, da einige Unterprogramme über einen längeren Zeitraum ausgeführt werden.
Randomra
1
Die Punktzahl kann 79durch Ersetzen ->+>+> ...durch->,>+> ...
BrainSteel 30.03.15
@BrainSteel Ich habe es gerade in ein No-Op geändert.
Jimmy23013
9

Prüfungsergebnis: 37 43

+>-,->,+-><->-[>---+-+<[--->>+><,+>>>++<><<<+<[>--]]><><+-+>+<<+<><+++<[[<[---->-<-]>++>],>,]<,]<+-.

EDIT: Jetzt erlaubt mein Programm einige eckige Klammern. Ich werde damit keine Preise gewinnen, aber das bekomme ich dafür, dass einige gewichtete RNGs die anstrengende Arbeit für mich erledigen.

Dies wurde durch ein Programm erzeugt, das ich in C geschrieben habe.

Für jedes Nentfernte Zeichen sind hier die Ausgaben:

N = 0 => 158
N = 1 => 158
N = 2 => 158
N = 3 => 187
N = 4 => 129
N = 5 => 100
N = 6 => 158
N = 7 => 13
N = 8 => 1
N = 9 => 211
N = 10 => 129
N = 11 => 1
N = 12 => 57
N = 13 => 255
N = 14 => Mismatched Braces
N = 15 => 59
N = 16 => 11
N = 17 => 11
N = 18 => 11
N = 19 => 117
N = 20 => 11
N = 21 => 117
N = 22 => 166
N = 23 => Mismatched Braces
N = 24 => 206
N = 25 => 206
N = 26 => 206
N = 27 => 147
N = 28 => 147
N = 29 => 158
N = 30 => 148
N = 31 => 188
N = 32 => 51
N = 33 => 17
N = 34 => 84
N = 35 => 84
N = 36 => 84
N = 37 => 158
N = 38 => 158
N = 39 => 94
N = 40 => 46
N = 41 => 94
N = 42 => 94
N = 43 => 94
N = 44 => 17
N = 45 => 196
N = 46 => Mismatched Braces
N = 47 => 149
N = 48 => No Termination
N = 49 => No Termination
N = 50 => Mismatched Braces
N = 51 => Mismatched Braces
N = 52 => 45
N = 53 => 77
N = 54 => 45
N = 55 => 77
N = 56 => 50
N = 57 => 209
N = 58 => 50
N = 59 => 251
N = 60 => 249
N = 61 => 99
N = 62 => 99
N = 63 => 117
N = 64 => 89
N = 65 => 207
N = 66 => 89
N = 67 => 115
N = 68 => 115
N = 69 => 115
N = 70 => 95
N = 71 => Mismatched Braces
N = 72 => Mismatched Braces
N = 73 => 104
N = 74 => Mismatched Braces
N = 75 => No Termination
N = 76 => No Termination
N = 77 => No Termination
N = 78 => No Termination
N = 79 => Left Overflow
N = 80 => 3
N = 81 => 2
N = 82 => No Termination
N = 83 => Mismatched Braces
N = 84 => No Termination
N = 85 => 133
N = 86 => 133
N = 87 => 0
N = 88 => Mismatched Braces
N = 89 => 158
N = 90 => 0
N = 91 => 4
N = 92 => Mismatched Braces
N = 93 => 0
N = 94 => 158
N = 95 => Mismatched Braces
N = 96 => 0
N = 97 => 157
N = 98 => 159
N = 99 => None

Es gibt insgesamt 37 eindeutige Ausgaben, die (in numerischer Reihenfolge) sind:

0, 1, 2, 3, 4, 11, 13, 17, 45, 46, 50, 51, 57, 59, 77, 84, 89, 94, 95, 99,
100, 104, 115, 117, 129, 133, 147, 148, 149, 157, 158, 159, 166, 187, 188, 
196, 206, 207, 209, 211, 249, 251, 255

Ich bin zu 90% zu 100% sicher, dass diese Lösung nicht optimal ist , aber zu beweisen, dass dies äußerst schwierig sein kann . Es gibt ein paar Dinge, die klar sind. .Bis zum letzten Zeichen keine Symbole zu haben, scheint der richtige Weg zu sein , und eckige Klammern ( []) scheinen eher nutzlos zu sein . Ich habe hier ein wenig nachgedacht, was ich kurz umreißen möchte:

Sei Ldie Länge des Codes in Bytes (in der Challenge 100) und ndie Anzahl der eindeutigen Ausgaben der Unterprogramme.

Für L=3gibt es mehrere optimale Lösungen der Form +-., in der n=2(in diesem Fall sind die Ausgänge 1 und 255 für +.und -.jeweils.) Dies stellt das beste Verhältnis für L = 3an n/L = 66.67%. Beachten Sie, dass dieses Verhältnis zumindest nicht zu übertreffen ist L<10.

Denn L=10die Lösungen sind einfach genug, um sie zu brachialisieren. Hier finden Sie die besten Lösungen n = 6:

++>-->+<+. => 6
++>-->+<+. => 6
+++>->+<+. => 6
--->->+<+. => 6
++>---><+. => 6
+++>--><+. => 6
-->++>-<-. => 6
+++>+>-<-. => 6
--->+>-<-. => 6
-->+++><-. => 6
--->++><-. => 6

Welches ergibt ein Score-Verhältnis von n/L = 60%.

Da L->infinityist klar, dass sich das Verhältnis 0 annähern muss, da es nur 255 mögliche Ausgänge für eine potenziell unendliche Zahl gibt L.

Das Verhältnis nimmt jedoch NICHT gleichmäßig ab. Es ist nicht möglich , eine Lösung zu konstruieren n=6, L=9, so das bestmögliche Verhältnis für L=9ist 5/9 = 55.56% < 60%.

Dies wirft die Frage auf, wie schnell und in welcher Hinsicht das Verhältnis abnimmt. Denn L = 100und um 10^9 checks/second, es würde mehrere Größenordnungen länger dauern als die Lebensdauer des Universums, um eine optimale Lösung zu erzwingen. Gibt es einen eleganten Weg, dies zu tun? Ich bezweifle sehr , dass es nach unten, ist 37%für L = 100.

Das Verhältnis steigt tatsächlich bis zu L=100. Zeigen Sie zur Bestätigung andere Antworten an.

Ich würde gerne Ihre Bewertungen der oben genannten hören. Ich konnte mich schrecklich geirrt haben.

BrainSteel
quelle