Теперь Кью работает в режиме чтения

Мы сохранили весь контент, но добавить что-то новое уже нельзя

Напишите код на Пайтон, который решает в несколько минут следующую задачу Евгения Джобса?

Пустые клетки можно произвольно заполнять нулями или единицами.
Разбор Джобса опирается на таблицы истинности.
ПрограммированиеPython+3
Борис Державец
  · 1,4 K
Идея:
так как у нас есть некоторые подсказки значений в виде неполной таблицы истиности, и она маленькой размерности, то можно просто проверить все перестановки.
Мне показалось, что искать перестановки будет удобнее, если подбирать таблицу по столбцам, поэтому запишу условие задачи вот так (None, естественно, соответствует пустой клетке):
patterns = [
    [None, None, 1   ],
    [None, 1,    None],
    [None, None, None],
    [1,    1,    None],
]

results = [
    0,
    0,
    0
]
Далее, генерируем уникальные перестановки (a, b, c, d) и используем некоторую функцию (название мне было придумывать лень, назвал её fs) для проверки подойдет ли данная комбинация паттерну из условия задачи (таких комбинаций может быть несколько у подобных задач, но конкретно для этой таблицы будет только одна подходящая комбинация)
def search(patterns, results):
    for variant in permutations(('a', 'b', 'c', 'd'), 4):
        correct_variant = fs(variant, patterns, results)
        if correct_variant: 
            print(variant)
Ну и далее основа решения - функция fs.
Данная функция это классический поиск в дереве состояний (эх, Prolog, тут был бы однозначно кстати).
В ней мы построчно идем по таблице-паттерну, для пустых None значений мы рекурсивно проверяем оба возможных варианта 0 или 1, учитывая требования задачи к уникальности строк таблицы.
def fs(positions, patterns, results, position=(0, 0)):
    count_results = len(results) # == len(patterns[i])
    count_positions = len(positions)
    i, j = position

    while i < count_results:
        current_is_none = patterns[j][i] is None
        if current_is_none:
            isOk = False
            for value in (0, 1):
                patterns[j][i] = value
                isOk = isOk or fs(positions, patterns, results, position=(i, j))                
            patterns[j][i] = None
            return isOk
        j += 1
        if j == count_positions:
            # попали в неуникальную строку, нужно делать откат
            if len(set('_'.join(str(column[k]) for column in patterns) for k in range(i+1))) != i+1:
                return False

            # проверяем совпадает ли результат выполнения функции F с тем который нам нужен по условию
            if results[i] != F(**{
                name: patterns[j2][i] for j2, name in enumerate(positions)
            }):
                return False
            i += 1
            j = 0

    return True
Ну и код целиком:
from itertools import *

# kwargs = {
#     'a': a,
#     'b': b,
#     'c': c,
#     'd': d,
# },
def F(a, b, c, d):
    return int(a and not(b) or (a or b) and c or d)


def search(patterns, results):
    for variant in permutations(('a', 'b', 'c', 'd'), 4):
        correct_variant = fs(variant, patterns, results)
        if correct_variant: 
            print(variant)

def fs(positions, patterns, results, position=(0, 0)):
    count_results = len(results) # == len(patterns[i])
    count_positions = len(positions)
    i, j = position

    while i < count_results:
        current_is_none = patterns[j][i] is None
        if current_is_none:
            isOk = False
            for value in (0, 1):
                patterns[j][i] = value
                isOk = isOk or fs(positions, patterns, results, position=(i, j))                
            patterns[j][i] = None
            return isOk
        j += 1
        if j == count_positions:
            # попали в неуникальную строку, нужно делать откат
            if len(set('_'.join(str(column[k]) for column in patterns) for k in range(i+1))) != i+1:
                return False

            if results[i] != F(**{
                name: patterns[j2][i] for j2, name in enumerate(positions)
            }):
                return False
            i += 1
            j = 0

    return True

if __name__ == '__main__':
    patterns = [
        [None, None, 1   ],
        [None, 1,    None],
        [None, None, None],
        [1,    1,    None],
    ]

    results = [
        0,
        0,
        0
    ]

    search(patterns, results)
1 эксперт согласен
Я уж испугался, что вы тут Пролог навелосипедите, мне тоже в голову первое, что пришло, это pattern matching... Читать дальше
Меня зовут Быстров Кирилл. Я увлекаюсь научными технологиями будущего. Давайте ответим на...  · 5 окт 2022
Код на Python: print('a b c d') for a in range(2): for b in range(2): for c in range(2): for d in range(2): if (a and not(b) or (a or b) and c or d)==0: print(a, b, c, d) На экран нам выведутся следующие строки: a b c d 0 0 0 0 0 0 1 0 0 1 0 0 1 1 0 0 Подставляя эти значения в таблицу истинности, данную в задании, определяем, что b - последняя колонка, а - вторая... Читать далее
1 эксперт не согласен
Кирилл, вы уж извините, но эта программа не решает поставленную задачу. Она помогает в одном из этапов решения, но... Читать дальше