Stackylogic ist eine Programmiersprache, die ich in einer früheren Herausforderung erfunden habe : Führen Sie Stackylogic aus . Lesen Sie diesen Beitrag für alle Details und Beispiele, aber hier ist, wie es umschrieben funktioniert:

Stackylogic verwendet 0's und 1' s für die Ein- und Ausgabe eines einzelnen 0 oder 1nach Abschluss.

Ein Programm besteht aus Zeilen, die nur die Zeichen 01?sowie genau eine <am Ende einer der Zeilen enthalten. Zeilen dürfen nicht leer sein und die Zeile mit dem <muss mindestens eins 0haben 1, oder ?davor.

Hier ist ein Beispielprogramm, das das NAND von zwei Bits berechnet :

1
?<
11
?
0

Jede Zeile in einem Programm wird als Stapel betrachtet , mit dem unteren Rand links und dem oberen Rand rechts. Implizit steht ein leerer Stapel (dh eine leere Zeile) vor der ersten Zeile in einem Programm und nach der letzten Zeile.

Der so <genannte Cursor markiert den Stapel, auf dem gestartet werden soll, wenn ein Programm ausgeführt wird. Die Ausführung erfolgt wie folgt:

1. Entfernen Sie das oberste Zeichen vom Stapel, auf den der Cursor gerade zeigt.

   • Wenn dies der Fall ist ?, fordern Sie den Benutzer zur Eingabe von a 0oder a auf, 1und tun Sie so, als wäre dies der Charakter.
   • Wenn das Zeichen ist 0, bewegen Sie den Cursor einen Stapel nach oben (bis zur Zeile über der aktuellen Zeile).
   • Wenn das Zeichen ist 1, bewegen Sie den Cursor einen Stapel nach unten (in die Zeile unter der aktuellen Zeile).

2. Wenn der Stapel, auf den sich der Cursor bewegt, leer ist, geben Sie den letzten Wert aus, der von einem Stapel abgefallen ist (immer ein 0oder 1), und beenden Sie das Programm.

3. Wenn der Stapel, auf den sich der Cursor bewegt, nicht leer ist, kehren Sie zu Schritt 1 zurück und wiederholen Sie den Vorgang.

Der Schlüssel für diese Herausforderung ist, dass alle Stackylogic-Programme einer Wahrheitstabelle entsprechen . Eine vorbestimmte Anzahl von Booleschen Werten wird eingegeben und genau ein Boolescher Wert wird deterministisch ausgegeben.

Ihre Aufgabe ist es also, ein Stackylogic-Programm zu erstellen, das befriedigt oder simuliert, dh die gleiche Ausgabe wie jede gegebene Wahrheitstabelle hat. Aber es ist nicht offensichtlich , dass Stackylogic kann jede Wahrheitstabelle simulieren, also hier ist ein Beweis durch Induktion :

Base Case

Die beiden Wahrheitstabellen mit 0 Eingängen sind die Tabellen, die immer 0oder ausgeben 1. Die Stackylogic Äquivalente dieser Tabellen sind 0<und 1< jeweils.

Induktiver Schritt

Angenommen, Stackylogic kann jede Wahrheitstabelle mit N Eingängen simulieren. Sei M = N + 1.

Eine M-Eingabetabelle T kann als zwei N-Eingabetabellen T ₀ und T ₁ plus dem zusätzlichen Eingabebit B ausgedrückt werden . Wenn B 0 ist, wird das Ergebnis von T ₀ verwendet. Wenn B 1 ist, wird das Ergebnis von T ₁ verwendet.

Zum Beispiel die Wahrheitstabelle mit 3 Eingängen, die dem Pseudocode entspricht

if B:
    result = x OR y
else:
    result = x NAND y

ist

B x y | result
0 0 0 | 1
0 0 1 | 1
0 1 0 | 1
0 1 1 | 0
1 0 0 | 0
1 0 1 | 1
1 1 0 | 1
1 1 1 | 1

Das sind wirklich die zwei Wahrheitstabellen mit zwei Eingängen für NAND und OR, die mit dem Muxing-Bit B übereinander gestapelt sind.

Sei S ₀ und S ₁ die Stackylogic-Programme, die T ₀ bzw. T ₁ erfüllen (wir wissen, dass diese aufgrund der ersten Annahme existieren). Das Programm S, das T erfüllt, kann dann wie folgt konstruiert werden:

[lines of S0 excluding the cursor, with 0 appended to all lines below the cursor]
?<
[lines of S1 excluding the cursor, with 1 appended to all lines above the cursor]

Diese Anordnung wandelt effektiv zwischen S ₀ und S ₁ basierend auf dem ersten Eingangsbit (von der Leitung ?<). Ist dies 0der Fall, fährt der Cursor die angehängten 0Zeichen bis zur ursprünglichen Cursorposition von S ₀ hoch , die dann von leeren Stapeln oben und unten umrandet wird und somit exakt identisch mit der ursprünglichen S _{0 abläuft} . Wenn 1eingegeben wird, fährt der Cursor auf die Cursorposition 1von S ₁ herunter und fährt mit der Ausführung fort, als ob er alleine wäre.

Zum Beispiel sind Stackylogic-Programme für OR und NAND

?
?<

und

1
?<
11
?
0

Sie können zu Simulationszwecken kombiniert werden

if B:
    result = x OR y
else:
    result = x NAND y

wie so:

1
?
110
?0
00
0
?<
?1
?

Somit kann jede Wahrheitstabelle durch ein Stackylogic-Programm simuliert werden.

Herausforderung

Schreiben Sie ein Programm oder eine Funktion, die eine Wahrheitstabelle mit N Eingängen (N> 0) in Form einer Liste von 2 ^N Booleschen Werten aufnimmt , die die Ausgaben der Tabelle in aufsteigender binärer Reihenfolge darstellen.

Jedes sinnvolle Eingabeformat ist in Ordnung. zB für eine ODER Wahrheitstabelle

x y | OR
0 0 | 0
0 1 | 1
1 0 | 1
1 1 | 1

Jeder dieser Arten von Eingaben wäre in Ordnung:

0111

0, 1, 1, 1

0
1
1
1

[False, True, True, True]

Ein Stackylogic-Programm ausgeben oder zurückgeben, das die Wahrheitstabelle erfüllt, dh die exakt gleiche Ausgabe bei gleicher Eingabe hat. Jedes endliche Programm, das diese Tabelle erfüllt, ist eine gültige Ausgabe. Sie müssen die Konstruktionsmethode des Induktionsnachweises nicht befolgen. Die Stackylogic-Programme müssen nicht optimal kurz sein.

Wenn zum Beispiel die Eingabe 11100111wäre, wäre eine gültige Ausgabe

1
?
110
?0
00
0
?<
?1
?

aber es gibt noch viele andere.

Der kürzeste Code in Bytes gewinnt.

Sehen Sie sich die ursprüngliche Stackylogic-Herausforderung an, wenn Sie einen Dolmetscher benötigen.

Pyth, 53 Bytes

L?tb,lehJyMc2bsX0.e.e+W>_Wk-Yhb0ZkebJ\?,0]`hbjXF+yQ\<

Versuchen Sie es online

Dies ist eine genaue Implementierung des Systems, das in der Aufforderung zur Implementierung beliebiger Wahrheitstabellen in Stackylogic beschrieben wurde. Wir halbieren einfach die Wahrheitstabelle, implementieren sie rekursiv und hängen dann 0 und 1 an.

Dies definiert eine rekursive Funktion, deren Rückgabewert ist [1, ['0', '?', '1']], wobei die erste Zahl die Position des Zeigers ist und der Rest ein Stackylogic-Programm ist.

L?tb,lehJyMc2bsX0.e.e+W>_Wk-Yhb0ZkebJ\?,0]`hbjXF+yQ\<
                                                         Q = eval(input())
L?tb,lehJyMc2bsX0.e.e+W>_Wk-Yhb0ZkebJ\?,0]`hb
L                                                 def y(b): return
 ?tb                                              if b[1:] (base case on false)
                                      ,0]`hb      else: [0, str([0])]
                                                  then:
           c2b                                    Cut the input in half
         yM                                       Map y over the halves
        J                                         Store that in J
    ,leh                                          The cursor position is the length 
                                                  of the body of the first function
                 .e                 J             enum-map, where k is the index
                                                  and b is the value, over J
                   .e             eb              enum-map, Y is the index and
                                                  Z is the value, over body of b
                     +W         Zk                Add to Z (line) k (the overall 
                                                  index, 0 or 1) conditional on
                          -Yhb                    Y (line index) - cursor
                       _Wk                        Negated if k
                      >       0                   > 0
               X0                    \?           Add '?' to the first element
              s                                   Concatenate, giving the body

jXF+yQ\<
    yQ      Call the above on the input
   +  \<    Append a '<'
 XF         Splat the 3 element list into the 'append-at' function,
            adding the curson in the right place
j           Join on newlines and print.

Python 3, 352 208 205 Bytes

Dies ist immer noch sehr unrühmlich, und ich werde später versuchen, eine Erklärung hinzuzufügen. Nach einigen Änderungen konnte ich 144 147 Bytes entfernen .

f=lambda x,l=len,r=range:'\n'.join(*x)if l(x)<2 else f([[x[i][j]+['0',''][j<=l(x[i])//2]for j in r(l(x[i]))]+[['?','?<'][l(x)<3]]+[x[i+1][j]+['1',''][j>=l(x[i])//2]for j in r(l(x[i]))]for i in r(0,l(x),2)])

Eine Funktion f, die die Eingabe der Wahrheitstabellenwerte als eine Liste von Booleschen Werten der Form annimmt ['1','1','1','0','0','1'...], in der '1'wahr und '0'falsch ist, und ein Stackylogic-Programm zurückgibt.

Probieren Sie es auf Ideone

Wenn Sie ein erstelltes Programm testen möchten, können Sie hier den Convex-Interpreter von GamrCorps verwenden .

Wie es funktioniert

Dies ist eine rekursive Funktion und verwendet die in der Frage beschriebene induktive Methode.

Auf der Ebene ader n/2 a+1nullindizierten Rekursion erstellt die Funktion Stackylogic-Programme mit Eingabe aus den n aEingabeprogrammen in der Liste. Dies geschieht, indem alle benachbarten Paare von zwei Programmen in der Liste mit ?; da sich der Cursor immer auf dem mittleren Element jedes einzelnen Programms befindet, kann das erforderliche Anhängen von 0oder 1durchgeführt werden, indem über jede Zeile der zu verbindenden Programme iteriert und angehängt wird, wenn der Index der aktuellen Zeile kleiner oder gleich / größer ist als oder gleich dem mittleren Index. Wenn die Liste nur zwei Programme enthält, gibt der nächste rekursive Aufruf das endgültige Programm aus. da dies einen Cursor erfordert, erfolgt die Verknüpfung stattdessen am ?<.

Wenn die Liste eine Länge hat 1, darf die Liste nur ein Element enthalten, das das vollständige Programm enthält. Daher werden alle Zeilen im Programm in einer neuen Zeile zusammengefasst und dann zurückgegeben.

Ein Beispiel soll dies verdeutlichen:

Take the input ['1', '1', '1', '0', '0', '1', '1', '1'].

Level  Return value

0  [['1', '?', '1'], ['1', '?', '0'], ['0', '?', '1'], ['1', '?', '1']]
1  [['1', '?', '10', '?', '11', '?', '0'], ['0', '?', '10', '?', '11', '?', '1']]
2  [['1', '?', '10', '?', '110', '?0', '00', '?<', '01', '?1', '101', '?', '11', '?', '1']]
3  '1\n?\n10\n?\n110\n?0\n00\n?<\n01\n?1\n101\n?\n11\n?\n1'

which when printed gives:

1
?
10
?
110
?0
00
?<
01
?1
101
?
11
?
1