Учитывая таблицу истинности, выведите программу Stackylogic, которая ее удовлетворяет

17

Stackylogic - это язык программирования, который я создал в предыдущем испытании: Run Stackylogic . Прочтите этот пост для получения полной информации и примеров, но вот как это работает, перефразируя:

Stackylogic принимает 0и вводит 1и выводит один 0 или 1после завершения.

Программа состоит из строк, которые содержат только символы, 01?а также ровно одну <в конце одной из строк. Линии не могут быть пустыми и линия с <должна иметь по крайней мере один 0, 1, или ?перед ним.

Вот пример программы, которая вычисляет NAND из двух битов:

1
?<
11
?
0

Каждая строка в программе считается стеком , нижняя часть слева и верхняя справа. Неявно, есть пустой стек (т.е. пустая строка) перед первой строкой в ​​программе и после последней строки.

<, Называемый курсором, отмечает стек , чтобы начать при запуске программы. Исполнение происходит следующим образом:

  1. Удалите верхний символ из стека, на который в данный момент указывает курсор.

    • Если это символ ?, предложите пользователю ввести a 0или a 1и действуйте так, как если бы это был символ.
    • Если это символ 0, переместите курсор на одну стопку вверх (на строку выше текущей строки).
    • Если это символ 1, переместите курсор на одну стопку вниз (на строку ниже текущей строки).

  2. Если стек, в который перемещается курсор, пуст, выведите последнее значение, извлеченное из стека (всегда a 0или 1), и завершите программу.

  3. В противном случае, если стек, в который перемещается курсор, не пуст, вернитесь к шагу 1 и повторите процесс.

Главное, что нужно понять для решения этой проблемы, заключается в том, что все программы Stackylogic соответствуют таблице истинности . Некоторое заранее определенное число логических значений вводится, и точно одно логическое значение выводится детерминистически.

Итак, ваша задача - создать программу Stackylogic, которая удовлетворяет или имитирует, то есть имеет тот же результат, что и любая заданная таблица истинности. Но не очевидно, что Stackylogic может моделировать любую таблицу истинности, поэтому вот доказательство по индукции :

Базовый вариант

Две таблицы истинности с 0 входами - это таблицы, которые всегда выводят 0или 1. Стекилогические эквиваленты этих таблиц есть 0<и 1< соответственно.

Индуктивный шаг

Предположим, что Stackylogic может моделировать любую таблицу истинности N-входных данных. Пусть M = N + 1.

M-входная таблица T может быть выражена в виде двух N-входных таблиц, T 0 и T 1 , плюс дополнительный входной бит B. Когда B равно 0, используется результат T 0 . Когда B равно 1, используется результат T 1 .

Например, таблица истинности с 3 входами, соответствующая псевдокоду

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

это две таблицы истинности с двумя входами для NAND и OR, расположенные друг над другом битом мультиплексирования B.

Пусть S 0 и S 1 - программы Stackylogic, которые удовлетворяют T 0 и T 1 соответственно (мы знаем, что они существуют на основе первого предположения). Программа S, которая удовлетворяет T, может тогда быть построена как:

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

Эта компоновка эффективно мультиплексирует между S 0 и S 1 на основе первого входного бита (из строки ?<). Если это так 0, курсор переместит добавленные 0до исходной позиции курсора S 0 , которая затем будет ограничена сверху и снизу пустыми стеками и, таким образом, будет работать точно так же, как и исходная S 0 . Аналогичным образом, если 1введен, курсор переместится 1вниз до S 1 положения курсора и продолжит выполнять его, как если бы он был один.

Например, программы Stackylogic для OR и NAND

?
?<

и

1
?<
11
?
0

Их можно комбинировать для симуляции

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

вот так:

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

Таким образом, любая таблица истинности может быть смоделирована программой Stackylogic.

Вызов

Напишите программу или функцию, которая принимает N входной таблицы истинности (N> 0) в форме списка из 2 N логических значений, которые представляют выходные данные таблицы в возрастающем двоичном порядке.

Любой разумный формат ввода в порядке. например, для таблицы истинности ИЛИ

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

любой из этих стилей ввода будет хорошо:

0111

0, 1, 1, 1

0
1
1
1

[False, True, True, True]

Распечатайте или верните программу Stackylogic, которая удовлетворяет таблице истинности, то есть имеет точно такой же вывод при том же вводе. Любая конечная программа, удовлетворяющая этой таблице, является допустимым выводом. Вам не нужно следовать методу построения индуктивного доказательства. Программы Stackylogic не обязательно должны быть оптимально короткими.

Например, если бы вход был 11100111, один действительный выход был бы

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

но есть много других.

Самый короткий код в байтах побеждает.

Посмотрите оригинальное задание Stackylogic, если вам нужен переводчик.

code-golf binary code-generation logic-gates logic Кальвин Хобби
источник
Можем ли мы взять N в качестве второго входа?
Дрянная Монахиня
@ LeakyNun Да (или 2 ^ N), если необходимо.
Увлечения Кэлвина

Ответы:

8

Pyth, 53 байта

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

Попробуй онлайн

Это точная реализация системы, описанной в задаче о том, как реализовать произвольные таблицы истинности в Stackylogic. Мы просто разрезаем таблицу истинности пополам, реализуем ее рекурсивно, а затем добавляем 0 и 1 соответственно.

Это определяет рекурсивную функцию, чье возвращаемое значение равно [1, ['0', '?', '1']], где первое число - это местоположение указателя, а остальное - стилогическая программа.

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
источник
Ну ... Я просто вернулся домой, чтобы исправить свое решение ...
Утренняя монахиня
3

Python 3, 352 208 205 байт

Это все еще очень безрассудно, и я постараюсь добавить объяснение позже. После некоторых модификаций мне удалось удалить 144 147 байт.

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

Функция, fкоторая принимает ввод значений таблицы истинности в виде списка логических значений вида ['1','1','1','0','0','1'...], где '1'истина и '0'ложь, и возвращает программу Stackylogic.

Попробуйте это на Ideone

Если вы хотите протестировать созданную программу, вы можете использовать интерпретатор GamrCorps Convex здесь .

Как это устроено

Это рекурсивная функция и использует индуктивный метод, описанный в вопросе.

На уровне рекурсии с нулевым индексом aфункция создает n/2 a+1программы Stackylogic -input из программ n a-input из списка. Это делается путем объединения всех соседних пар двух программ в списке с помощью ?; Поскольку курсор всегда находится в среднем элементе каждой составляющей программы, необходимое добавление 0или 1может быть выполнено путем итерации по каждой строке соединяемых программ и добавления, если индекс текущей строки меньше или равен / больше чем или равно среднему индексу в зависимости от ситуации. Если список содержит только две программы, следующий рекурсивный вызов даст окончательную программу; поскольку для этого требуется курсор, вместо этого происходит соединение ?<.

Когда список имеет длину 1, список должен содержать только один элемент, содержащий полную программу. Следовательно, все строки в программе объединяются на новую строку, а затем возвращаются.

Пример помогает проиллюстрировать это:

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
источник