Dada una tabla de verdad, genera un programa Stackylogic que lo satisfaga

17

Stackylogic es un lenguaje de programación que inventé en un desafío anterior: ejecutar Stackylogic . Lea esa publicación para obtener todos los detalles y ejemplos, pero así es como funciona parafraseado:

Stackylogic toma 0's y 1' s para entrada y salida una sola 0 o 1al finalizar.

Un programa consta de líneas que solo contienen los caracteres 01?, así como exactamente uno <al final de una de las líneas. Las líneas pueden no estar vacío y la línea con el <deben tener al menos una 0, 1o ?antes de ella.

Aquí hay un programa de muestra que calcula la NAND de dos bits:

1
?<
11
?
0

Cada línea de un programa se considera una pila , con la parte inferior a la izquierda y la superior a la derecha. Implícitamente, hay una pila vacía (es decir, una línea vacía) antes de la primera línea de un programa y después de la última línea.

El <, llamado cursor, marca la pila para comenzar cuando se ejecuta un programa. La ejecución procede de la siguiente manera:

  1. Saque el carácter superior de la pila a la que apunta actualmente el cursor.

    • Si el personaje es ?, solicite al usuario a 0o a 1y actúe como si ese fuera el personaje.
    • Si el personaje es 0, mueva el cursor una pila hacia arriba (a la línea sobre la línea actual).
    • Si el personaje es 1, mueva el cursor una pila hacia abajo (a la línea debajo de la línea actual).

  2. Si la pila a la que se mueve el cursor está vacía, muestre el último valor que se extrajo de una pila (siempre una 0o 1) y finalice el programa.

  3. De lo contrario, si la pila a la que se mueve el cursor no está vacía, regrese al paso 1 y repita el proceso.

La clave para darse cuenta de este desafío es que todos los programas de Stackylogic equivalen a una tabla de verdad . Se ingresa un número predeterminado de valores booleanos y exactamente un booleano se emite de manera determinista.

Entonces, su tarea es producir un programa Stackylogic que satisfaga o simule, es decir, tenga el mismo resultado que cualquier tabla de verdad dada. Pero no es obvio que Stackylogic pueda simular cualquier tabla de verdad, así que aquí hay una prueba por inducción :

Caso base

Las dos tablas de verdad de 0 entradas son las tablas que siempre generan 0o 1. Los equivalentes Stackylogic de estas tablas son 0<y 1< respectivamente.

Paso inductivo

Suponga que Stackylogic puede simular cualquier tabla de verdad de N-input. Deje M = N + 1.

Una tabla de entrada M, T, se puede expresar como dos tablas de entrada N, T 0 y T 1 , más el bit de entrada adicional B. Cuando B es 0, se utiliza el resultado de T 0 . Cuando B es 1, se utiliza el resultado de T 1 .

Por ejemplo, la tabla de verdad de 3 entradas correspondiente al pseudocódigo

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

es

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

que son realmente las dos tablas de verdad de 2 entradas para NAND y OR apiladas una encima de la otra con el bit de mutación B.

Supongamos que S 0 y S 1 sean los programas de Stackylogic que satisfacen T 0 y T 1 respectivamente (sabemos que existen en función del primer supuesto). El programa S que satisface T puede ser construido como:

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

Esta disposición efectivamente cambia entre S 0 y S 1 en función del primer bit de entrada (desde la línea ?<). Si esto es 0 , el cursor se desplazará por los anexos 0hasta la posición original del cursor de S 0 , que luego estará bordeada arriba y abajo por pilas vacías, y así se ejecutará exactamente idéntico al S 0 original . Del mismo modo, si 1se ingresa, el cursor se desplazará 1hacia abajo hasta la posición del cursor S 1 y procederá a ejecutarlo como si estuviera solo.

Por ejemplo, los programas Stackylogic para OR y NAND son

?
?<

y

1
?<
11
?
0

Se pueden combinar para simular

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

al igual que:

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

Por lo tanto, cualquier tabla de verdad puede ser simulada por un programa Stackylogic.

Desafío

Escriba un programa o función que tome una tabla de verdad de entrada N (N> 0) en forma de una lista de 2 valores booleanos N que representan las salidas de la tabla en orden binario ascendente.

Cualquier formato de entrada razonable está bien. por ejemplo, para una tabla de verdad OR

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

cualquiera de estos estilos de entradas estaría bien:

0111

0, 1, 1, 1

0
1
1
1

[False, True, True, True]

Imprima o devuelva un programa Stackylogic que satisfaga la tabla de verdad, es decir, tenga exactamente la misma salida dada la misma entrada. Cualquier programa finito que satisfaga esa tabla es una salida válida. No necesita seguir el método de construcción de la prueba inductiva. Los programas Stackylogic no necesitan ser óptimamente cortos.

Por ejemplo, si la entrada fuera 11100111, una salida válida sería

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

Pero hay muchos otros.

El código más corto en bytes gana.

Vea el desafío original de Stackylogic si necesita un intérprete.

code-golf binary code-generation logic-gates logic Pasatiempos de Calvin
fuente
¿Podemos tomar N como segunda entrada?
Leaky Nun
@LeakyNun Sí (o 2 ^ N), si es necesario.
Hobbies de Calvin

Respuestas:

8

Pyth, 53 bytes

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

Probar en línea

Esta es una implementación exacta del sistema descrito en el desafío de cómo implementar tablas de verdad arbitrarias en Stackylogic. Simplemente cortamos la tabla de verdad a la mitad, la implementamos recursivamente y luego agregamos 0 y 1 según corresponda.

Esto define una función recursiva, cuyo valor de retorno es [1, ['0', '?', '1']], donde el primer número es la ubicación del puntero y el resto es un programa 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.
isaacg
fuente
Bueno ... acabo de regresar a casa para corregir mi solución ...
Leaky Nun
3

Python 3, 352 208 205 bytes

Esto todavía es muy poco golfista, e intentaré agregar una explicación más adelante. Después de algunas modificaciones, logré eliminar 144 147 bytes.

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

Una función fque toma la entrada de los valores de la tabla de verdad como una lista de booleanos de la forma ['1','1','1','0','0','1'...], donde '1'es verdad y'0' es falso, y devuelve un programa Stackylogic.

Pruébalo en Ideone

Si desea probar un programa producido, puede usar el intérprete convexo de GamrCorps aquí .

Cómo funciona

Esta es una función recursiva y utiliza el método inductivo descrito en la pregunta.

En el nivel de recursión indexado a cero a, la función crea n/2 a+1programas Stackylogic de entrada a partir de los n aprogramas de entrada de la lista. Esto se hace uniendo todos los pares adyacentes de dos programas en la lista con ?; Como el cursor está siempre en el elemento central de cada programa constituyente, la adición requerida de 0o 1se puede realizar iterando sobre cada línea de los programas que se unen y agregando si el índice de la línea actual es menor o igual a / mayor que o igual al índice medio según corresponda. Si la lista contiene solo dos programas, la siguiente llamada recursiva dará el programa final; Como esto requiere un cursor, la unión se produce en su lugar ?<.

Cuando la lista tiene longitud 1, la lista debe contener solo un elemento que contenga el programa completo. Por lo tanto, todas las líneas del programa se unen en una nueva línea y luego se devuelven.

Un ejemplo ayuda a ilustrar esto:

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
TheBikingViking
fuente