Es ist ein lustiger Zufall, dass diese Welt nur eine Zeitdimension hat, aber es muss nicht so sein. Es ist einfach, sich Welten mit zwei oder mehr Zeitdimensionen vorzustellen, und in diesen Welten könnten Sie Computer bauen und Software darauf ausführen, genau wie in dieser.
Das System
Hier ist ein System zum Ausführen von Brainf * ck-Programmen in zwei Zeitdimensionen:
Die beiden Zeitdimensionen sind x und y. Jedes Brainf * ck-Programm besteht aus einem x-halben Programm und einem y-halben Programm, z. B. einem Programm
x: +>+
y: [-]
Die beiden Halbprogramme haben jeweils einen eigenen Programmzeiger, teilen sich jedoch einen einzigen Bandzeiger (d. H., Beide arbeiten in derselben Zelle des Bandes).
Die Zeit ist zweidimensional und besteht aus einem Gitter von Momenten:
Das x-Halbprogramm bewegt sich entlang der x-Dimension und führt einen Zeitschritt aus. Das y-Halbprogramm bewegt sich entlang der y-Dimension und führt einen Zeitschritt aus.
Nehmen wir zum Beispiel an, das Band beginnt als [0] 0 0( []stellt den Bandzeiger dar) und die x / y-Programme sind +und ->-. Die Ausführung dieses Programms würde folgendermaßen aussehen:
x y tape x-action y-action
0 0 [ 0] 0 0 + at 0 - at 0
1 0 [ 1] 0 0 (done) - at 0
0 1 [-1] 0 0 + at 0 move >
1 1 [ 0] 0 0 (done) move >
Beachten Sie, dass das x-Halbprogramm, während sich die Zeit in y-Richtung bewegt, immer wieder dasselbe tut, da seine Zeit nicht fortschreitet.
Das Band enthält zu jedem Zeitpunkt den kumulativen Effekt aller Aktionen, die in es eingehen (jede Aktion zählt einmal). So enthält beispielsweise das Band zum Zeitpunkt (2, 1) den kumulativen Effekt von:
- die x-Aktion von (0, 0)
- die x-Aktion von (1, 0)
- die x-Aktion von (0, 1)
- die x-Aktion von (1, 1)
- die y-Aktion von (0, 0)
- die y-Aktion von (1, 0)
- die y-Aktion von (2, 0)
Kumulativ bedeutet:
- Alle Inkremente und Dekremente einer Zelle summieren sich.
- Alle Bewegungen von links (-1) und rechts (+1) zum Bandzeiger summieren sich.
Befehlszeiger sammeln sich nicht an. Jedes Halbprogramm erhält seinen Anweisungszeiger aus dem vorherigen Moment in seiner Dimension. Das heißt, x-Programmzeiger werden nur in der x-Dimension und y-Programmzeiger nur in der y-Dimension fortgesetzt. So wäre beispielsweise im Programm ( [], +) ab [0] 0 0die Ausführung
x y tape x-action y-action x-prog-ptr y-prog-ptr
0 0 0 0 0 + at 0 0 0
1 0 0 0 0 + at 0 2 (from jump) 0
0 1 1 0 0 0 1
1 1 2 0 0 1 (from NO jump) 1
Einige weitere Momente aus der obigen ( +, ->-) Simulation sind:
x y tape x-action y-action x-prog-ptr y-prog-ptr
0 0 [ 0] 0 0 + at 0 - at 0 0 0
1 0 [ 1] 0 0 - at 0 1 0
2 0 [ 1] 0 0 - at 0 1 0
0 1 [-1] 0 0 + at 0 > 0 1
1 1 [ 0] 0 0 > 1 1
2 1 [-1] 0 0 > 1 1
0 2 -1 [ 0] 0 + at 1 - at 1 0 2
1 2 0 1 [ 0] - at 2 1 2
2 2 [-1] 1 0 - at 0 1 2
Folgende Brainf * ck-Operatoren sind zulässig (sie haben ihre Standardbedeutung):
+,-: Inkrementieren, Dekrementieren;[,]: Schleife bis Null (Verarbeitung eines[oder]dauert einen Zeitschritt, wie in Standard-Brainf * ck);<,>: Bewegen Sie sich auf dem Band nach links / rechts.
Komplexes Beispiel
Für das Programm ( >, +) beginnend mit [0] 0 0:
x y tape x-action y-action x-prog-ptr y-prog-ptr
0 0 [ 0] 0 0 > + at 0 0 0
1 0 0 [ 0] 0 + at 1 1 0
0 1 [ 1] 0 0 > 0 1
1 1 1 1 [ 0] 1 1
Für ( +, -) beginnend mit [0] 0 0:
x y tape x-action y-action x-prog-ptr y-prog-ptr
0 0 [ 0] 0 0 + at 0 - at 0 0 0
1 0 [ 1] 0 0 - at 0 1 0
0 1 [-1] 0 0 + at 0 0 1
1 1 [ 0] 0 0 1 1
Beachten Sie, dass die Bandenden wie [0] 0 0da jede +und -geschieht zweimal, zu 0 summiert.
Für das Programm ( >+, [-]) beginnend mit [0] 0 0:
x y tape x-action y-action x-prog-ptr y-prog-ptr
0 0 [ 0] 0 0 > 0 0
1 0 0 [ 0] 0 + at 1 1 0
2 0 0 [ 1] 0 2 0
0 1 [ 0] 0 0 > 0 3
1 1 0 0 [ 0] + at 2 1 3
2 1 0 1 [ 1] - at 2 2 1
0 2 [ 0] 0 0 > 0 3
1 2 [ 0] 0 0 + at 0 1 3
2 2 [ 1] 1 0 2 2
Diagramm mit Pfeilen
Das folgende Diagramm zeigt, wie die Aktionen und das Band berechnet werden:
Das Puzzle
Schreiben Sie ein 2D-Brainf * ck-Programm (mit einem x-Halbprogramm und einem y-Halbprogramm), um es auf einem 3-Zellen-Band auszuführen, das die beiden folgenden Bedingungen erfüllt:
- Beginnt das Band zum
[0] 0 0Zeitpunkt (5, 5) mit a0in der nullten Zelle. - Beginnt das Band zum
[1] 0 0Zeitpunkt (5, 5) mit a0in der nullten Zelle.
Das kürzeste Programm, das die Anforderungen erfüllt, gewinnt.
+und>? Wenn es ist1 1 [0](ziemlich verrückt, aber es ist, was die Spezifikation zu suggerieren scheint), wie kombinieren Anweisungszeiger? Wenn die beiden Threads+und sind[], dann wäre das auf1 2dem Datenband[3], aber ist der zweite Befehlszeiger innerhalb der Schleife ([]+Pfad) oder außerhalb ([+]Pfad) oder sogar illegal (+[])?+,>) auszuführen, um zu sehen, ob ich das gleiche Ergebnis wie Sie erhalte.(1,1)entweder durch(1,0)oder zu kommen kann(0,1), aber es beginnt mit einem Programm>und man beginnt mit+, dann ist sicherlich ihre relative Reihenfolge von Bedeutung?Antworten:
4 Bytes gesamt: (
[-],>)Ich habe einen Brute-Forcer geschrieben , um das kleinste derartige Programm zu finden.
Hier sind die Diagramme dieses Programms in Aktion. Diese Gitter sind in ähnlicher Weise wie das Gitter in der Spezifikation angeordnet, wobei (0,0) die linke untere Ecke, die x-Zeit entlang der x-Achse und die y-Zeit entlang der y-Achse ist. Die rechte obere Ecke enthält das Ergebnis.
Zunächst mit einem Band von
0 0 0:Jetzt mit einem Band von
1 0 0:Es gab ein paar Dinge, die in der Spezifikation nicht klar erklärt wurden, wie zum Beispiel die Tatsache, dass das 3-Zellen-Klebeband umwickelt ist.
Als Bonus ist hier die Visualisierung des (
>+,[-]) Beispiels:Und eines der (
>+,+>) Beispiele:Beachten Sie, dass sich die obere rechte Ecke von Ihrer Auflistung unterscheidet. Ich denke, dies ist ein Fehler in Ihrem Beispiel, da mein Code mit jedem anderen Beispiel übereinstimmt, das ich ausprobiert habe.
quelle