Stackylogic é uma linguagem de programação que criei em um desafio anterior: Execute Stackylogic . Leia esse post para obter detalhes e exemplos completos, mas aqui está como ele é parafraseado:
Stackylogic pega
0
's' e1
's para entrada e saída uma única0
ou1
após a conclusão.Um programa consiste em linhas que contêm apenas os caracteres
01?
e exatamente um<
no final de uma das linhas. As linhas podem não estar vazio e a linha com o<
deve ter pelo menos um0
,1
ou?
antes dela.Aqui está um programa de exemplo que calcula a NAND de dois bits:
1 ?< 11 ? 0
Cada linha de um programa é considerada uma pilha , com a parte inferior à esquerda e a parte superior à direita. Implicitamente, há uma pilha vazia (ou seja, linha vazia) antes da primeira linha de um programa e depois da última linha.
O
<
, chamado cursor, marca a pilha para iniciar quando um programa é executado. A execução procede da seguinte maneira:
Retire o caractere superior da pilha para a qual o cursor está apontando.
- Se o personagem for
?
, solicite a0
ou a um usuário1
e aja como se fosse o personagem.- Se o caractere for
0
, mova o cursor uma pilha para cima (para a linha acima da linha atual).- Se o caractere for
1
, mova o cursor uma pilha para baixo (para a linha abaixo da linha atual).Se a pilha para a qual o cursor se move estiver vazia, imprima o último valor que foi retirado de uma pilha (sempre a
0
ou1
) e encerre o programa.Caso contrário, se a pilha para a qual o cursor se move não estiver vazia, volte para a etapa 1 e repita o processo.
O principal a realizar para esse desafio é que todos os programas Stackylogic equivalem a uma tabela de verdade . Algum número predeterminado de valores booleanos são inseridos e exatamente um booleano é produzido de forma determinística.
Portanto, sua tarefa é produzir um programa Stackylogic que satisfaça ou simule, ou seja, tenha a mesma saída que qualquer tabela de verdade. Mas não é óbvio que o Stackylogic possa simular qualquer tabela verdade, então aqui está uma prova por indução :
Caso base
As duas tabelas verdadeiras com 0 entradas são as tabelas que sempre produzem
0
ou1
. Os equivalentes Stackylogic destas tabelas são0<
e1<
respectivamente.Etapa indutiva
Suponha que o Stackylogic possa simular qualquer tabela verdade de entrada N. Seja M = N + 1.
Uma tabela de entrada M, T, pode ser expressa como duas tabelas de entrada N, T 0 e T 1 , mais o bit de entrada adicional B. Quando B é 0, o resultado de T 0 é usado. Quando B é um, o resultado do t 1 é utilizado.
Por exemplo, a tabela verdade de 3 entradas correspondente ao pseudocódigo
if B: result = x OR y else: result = x NAND y
é
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 são realmente as duas tabelas verdadeiras de 2 entradas para NAND e OR empilhadas umas sobre as outras com o bit de muxing B.
Sejam S 0 e S 1 os programas Stackylogic que satisfazem T 0 e T 1 respectivamente (sabemos que estes existem com base na primeira suposição). O programa S que satisfaz T pode então ser construído 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]
Esse arranjo efetivamente alterna entre S 0 e S 1 com base no primeiro bit de entrada (da linha
?<
). Se estiver0
, o cursor passará os anexos0
até a posição original do cursor de S 0 , que será delimitada superior e inferior por pilhas vazias e, portanto, executada exatamente idêntica à S 0 original . Da mesma forma, se1
for introduzido, o cursor vai rodar com a1
's até S um de posição do cursor e proceder para executá-lo como se fosse a única.Por exemplo, os programas Stackylogic para OR e NAND são
? ?<
e
1 ?< 11 ? 0
Eles podem ser combinados para simular
if B: result = x OR y else: result = x NAND y
igual a:
1 ? 110 ?0 00 0 ?< ?1 ?
Assim, qualquer tabela verdade pode ser simulada por um programa Stackylogic.
Desafio
Escreva um programa ou função que obtenha uma tabela verdade N de entrada (N> 0) na forma de uma lista de 2 N valores booleanos que representam as saídas da tabela em ordem binária crescente.
Qualquer formato de entrada razoável está bom. por exemplo, para uma tabela de verdade OR
x y | OR
0 0 | 0
0 1 | 1
1 0 | 1
1 1 | 1
qualquer um desses estilos de entradas seria bom:
0111
0, 1, 1, 1
0
1
1
1
[False, True, True, True]
Imprima ou retorne um programa Stackylogic que satisfaça a tabela verdade, ou seja, tenha exatamente a mesma saída, com a mesma entrada. Qualquer programa finito que satisfaça essa tabela é uma saída válida. Você não precisa seguir o método de construção da prova indutiva. Os programas Stackylogic não precisam ser otimamente curtos.
Por exemplo, se a entrada fosse 11100111
, uma saída válida seria
1
?
110
?0
00
0
?<
?1
?
mas existem muitos outros.
O código mais curto em bytes vence.
Veja o desafio Stackylogic original se precisar de um intérprete.
fonte
Respostas:
Pitão, 53 bytes
Experimente on-line
Esta é uma implementação exata do sistema descrito no desafio de como implementar tabelas de verdade arbitrárias no Stackylogic. Simplesmente cortamos a tabela verdade pela metade, implementamos recursivamente e, em seguida, anexamos 0 e 1 conforme apropriado.
Isso define uma função recursiva, cujo valor de retorno é
[1, ['0', '?', '1']]
onde o primeiro número é a localização do ponteiro e o restante é um programa empilógico.fonte
Python 3,
352208205 bytesIsso ainda é muito não-destruído, e tentarei adicionar uma explicação mais tarde.Após algumas modificações, consegui remover144147 bytes.Uma função
f
que recebe entrada dos valores da tabela verdade como uma lista de Booleanos do formulário['1','1','1','0','0','1'...]
, onde'1'
é verdade e'0'
é falsey, e retorna um programa Stackylogic.Experimente no Ideone
Se você quiser testar um programa produzido, pode usar o interpretador Convex do GamrCorps aqui .
Como funciona
Esta é uma função recursiva e usa o método indutivo descrito na pergunta.
No nível de recursão indexado a zero
a
, a função crian/2
a+1
programas Stackylogic -input a partir dosn
a
programas -input na lista. Isso é feito juntando todos os pares adjacentes de dois programas na lista com?
; como o cursor está sempre no elemento do meio de cada programa constituinte, o acréscimo necessário de0
ou1
pode ser executado iterando sobre cada linha dos programas que estão sendo unidos e acrescentando se o índice da linha atual for menor ou igual a / maior igual ou igual ao índice do meio, conforme apropriado. Se a lista contiver apenas dois programas, a próxima chamada recursiva fornecerá o programa final; como isso requer um cursor, a união ocorre em vez disso?<
.Quando a lista tem tamanho
1
, a lista deve conter apenas um elemento que contém o programa completo. Portanto, todas as linhas do programa são unidas em uma nova linha e, em seguida, retornadas.Um exemplo ajuda a ilustrar isso:
fonte