Stackylogic est un langage de programmation que j'ai inventé dans un défi précédent: exécuter Stackylogic . Lisez cet article pour plus de détails et d'exemples, mais voici comment cela fonctionne paraphrasé:

Stackylogic prend les 0'et les 1' pour les entrées et les sorties un seul 0 ou 1à la fin.

Un programme se compose de lignes qui ne contiennent que les caractères 01?ainsi qu'exactement un <à la fin de l'une des lignes. Les lignes ne peuvent pas être vide et la ligne avec le <doivent avoir au moins un 0, 1ou ?devant elle.

Voici un exemple de programme qui calcule la NAND de deux bits:

1
?<
11
?
0

Chaque ligne d'un programme est considérée comme une pile , le bas à gauche et le haut à droite. Implicitement, il y a une pile vide (c'est-à-dire une ligne vide) avant la première ligne d'un programme et après la dernière ligne.

Le <, appelé curseur, marque le début de la pile lors de l'exécution d'un programme. L'exécution se déroule comme suit:

1. Retirez le premier caractère de la pile vers laquelle pointe le curseur.

   • Si le caractère est ?, demandez à l'utilisateur un 0ou un 1et agissez comme si c'était le caractère.
   • Si le caractère est 0, déplacez le curseur d'une pile vers le haut (jusqu'à la ligne au-dessus de la ligne actuelle).
   • Si c'est le cas 1, déplacez le curseur d'une pile vers le bas (jusqu'à la ligne située sous la ligne actuelle).

2. Si la pile vers laquelle le curseur se déplace est vide, affichez la dernière valeur qui a été extraite d'une pile (toujours un 0ou 1) et terminez le programme.

3. Sinon, si la pile vers laquelle le curseur se déplace n'est pas vide, revenez à l'étape 1 et répétez le processus.

La chose clé à réaliser pour ce défi est que tous les programmes Stackylogic correspondent à une table de vérité . Un certain nombre prédéterminé de valeurs booléennes sont entrées et exactement un booléen est sorti de manière déterministe.

Votre tâche consiste donc à produire un programme Stackylogic qui satisfait ou simule, c'est-à-dire qui a la même sortie que n'importe quelle table de vérité donnée. Mais il n'est pas évident que Stackylogic puisse simuler n'importe quelle table de vérité, alors voici une preuve par induction :

Cas de base

Les deux tables de vérité à 0 entrée sont les tables qui produisent toujours 0ou 1. Les équivalents Stackylogic de ces tableaux sont 0<et 1< respectivement.

Étape inductive

Supposons que Stackylogic puisse simuler n'importe quelle table de vérité à N entrées. Soit M = N + 1.

Une table d'entrée M, T, peut être exprimée sous la forme de deux tables d'entrée N, T ₀ et T ₁ , plus le bit d'entrée supplémentaire B. Lorsque B est égal à 0, le résultat de T ₀ est utilisé. Lorsque B est 1, le résultat de T ₁ est utilisé.

Par exemple, la table de vérité à 3 entrées correspondant au pseudocode

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

est

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

qui est vraiment les deux tables de vérité à 2 entrées pour NAND et OR empilées l'une sur l'autre avec le bit de multiplexage B.

Soit S ₀ et S ₁ les programmes Stackylogic qui satisfont respectivement T ₀ et T ₁ (nous savons qu'ils existent sur la base de la première hypothèse). Le programme S qui satisfait T peut alors être construit comme:

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

Cette disposition muxise effectivement entre S ₀ et S ₁ sur la base du premier bit d'entrée (à partir de la ligne ?<). Si tel est le cas 0, le curseur montera les éléments ajoutés 0jusqu'à la position d'origine du curseur de S ₀ , qui sera ensuite bordée en haut et en bas par des piles vides, et fonctionnera donc exactement de la même manière que le S _{0 d'origine} . De même, si 1est entré, le curseur 1descendra le s à la position du curseur de S ₁ et procédera à son exécution comme s'il était seul.

Par exemple, les programmes Stackylogic pour OR et NAND sont

?
?<

et

1
?<
11
?
0

Ils peuvent être combinés pour simuler

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

ainsi:

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

Ainsi, toute table de vérité peut être simulée par un programme Stackylogic.

Défi

Écrivez un programme ou une fonction qui prend une table de vérité d'entrée N (N> 0) sous la forme d'une liste de 2 ^N valeurs booléennes qui représentent les sorties de la table dans l'ordre binaire croissant.

Tout format d'entrée raisonnable est correct. par exemple pour une table de vérité OU

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

n'importe lequel de ces styles d'entrées conviendrait:

0111

0, 1, 1, 1

0
1
1
1

[False, True, True, True]

Imprimer ou renvoyer un programme Stackylogic qui satisfait la table de vérité, c'est-à-dire qui a exactement la même sortie avec la même entrée. Tout programme fini qui satisfait cette table est une sortie valide. Vous n'avez pas besoin de suivre la méthode de construction de la preuve inductive. Les programmes Stackylogic n'ont pas besoin d'être courts de manière optimale.

Par exemple, si l'entrée était 11100111, une sortie valide serait

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

mais il y en a beaucoup d'autres.

Le code le plus court en octets gagne.

Voir le défi Stackylogic original si vous avez besoin d'un interprète.

Pyth, 53 octets

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

Essayez en ligne

Il s'agit d'une implémentation exacte du système décrit dans le défi sur la façon d'implémenter des tables de vérité arbitraires dans Stackylogic. Nous coupons simplement la table de vérité en deux, l'implémentons récursivement, puis ajoutons 0 et 1 selon le cas.

Ceci définit une fonction récursive, dont la valeur de retour est [1, ['0', '?', '1']], où le premier nombre est l'emplacement du pointeur, et le reste est un programme stackylogic.

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 octets

Ce n'est toujours pas très bon, et j'essaierai d'ajouter une explication plus tard. Après quelques modifications, j'ai réussi à supprimer 144 147 octets.

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

Une fonction fqui prend en entrée les valeurs de la table de vérité comme une liste de booléens de la forme ['1','1','1','0','0','1'...], où '1'est véridique et '0'est falsey, et renvoie un programme Stackylogic.

Essayez-le sur Ideone

Si vous souhaitez tester un programme produit, vous pouvez utiliser l' interpréteur Convex de GamrCorps ici .

Comment ça fonctionne

Il s'agit d'une fonction récursive et utilise la méthode inductive décrite dans la question.

Au niveau de récursivité indexée zéro a, la fonction crée des n/2 a+1programmes Stackylogic -input à partir des n aprogrammes -input de la liste. Cela se fait en joignant toutes les paires adjacentes de deux programmes dans la liste avec ?; puisque le curseur est toujours à l'élément central de chaque programme constitutif, l'ajout requis de 0ou 1peut être effectué en itérant sur chaque ligne des programmes joints et en ajoutant si l'index de la ligne actuelle est inférieur ou égal à / supérieur supérieur ou égal à l'indice médian selon le cas. Si la liste ne contient que deux programmes, le prochain appel récursif donnera le programme final; car cela nécessite un curseur, la jointure se produit à la place ?<.

Lorsque la liste a une longueur 1, la liste doit contenir un seul élément contenant le programme complet. Par conséquent, toutes les lignes du programme sont jointes sur une nouvelle ligne, puis renvoyées.

Un exemple permet d'illustrer ceci:

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