Quine–McCluskey algorithm

[vak]

На днях обсуждали со spamsink минимизацию булевских функций. Тема из далёкого студенчества. Задачка нетривиальная, но давно и глубоко проработанная. Озадачил нею Грока, получил два решения:

на Питоне: minimize-boolean-function.py

на Rust: minimize-boolean-function.rs

Функция с 8 переменными вычисляется на Rust за шесть секунд:

$ rustc minimize-boolean-function.rs

$ /usr/bin/time ./minimize-boolean-function 

Truth table: 0000000000X10000000000000000000000000000000000000000000000000000010X010X010X010X010X010X010X010X010X010X010X010X010X010X010X010X00000000001X0000000000000000000000000000000000001X1X1X1X1X1X1X1X0000000000000000000000000000000000000000000000000000000000000000
8-variable result: ~ABH + ~B~C~DE~FG + A~BCD
        6.26 real         6.22 user         0.03 sys

Comments

[spamsink]

А на Питоне за сколько минут?

[vak]

За 12 секунд:

Truth table: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 'X', 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 'X', 0, 1, 0, 'X', 0, 1, 0, 'X', 0, 1, 0, 'X', 0, 1, 0, 'X', 0, 1, 0, 'X', 0, 1, 0, 'X', 0, 1, 0, 'X', 0, 1, 0, 'X', 0, 1, 0, 'X', 0, 1, 0, 'X', 0, 1, 0, 'X', 0, 1, 0, 'X', 0, 1, 0, 'X', 0, 1, 0, 'X', 0, 1, 0, 'X', 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 'X', 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 'X', 1, 'X', 1, 'X', 1, 'X', 1, 'X', 1, 'X', 1, 'X', 1, 'X', 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
8-variable result: ~ABH + ~ABH + ~ABH + ~ABH + ~ABH + ~ABH + ~ABH + ~ABH + ~ABH + ~ABH + ~ABH + ~ABH + ~ABH + ~ABH + ~ABH + ~ABH + ~B~C~DE~FG + A~BCD + A~BCD + A~BCD + A~BCD + A~BCD + A~BCD + A~BCD + A~BCD

real 0m12.881s
user 0m12.800s
sys 0m0.074s

[vak]

Улучшенная версия на Rust справляется за 0.2 секунды:
https://github.com/sergev/vak-opensource/blob/master/languages/rust/qmc/src/minimizer.rs

Правда, имена переменных печатает неправильно, не с того конца.

[spamsink]

~ABH + ~ABH + ~ABH + ~ABH + ~ABH + ~ABH + ~ABH + ~ABH + ~ABH + ~ABH + ~ABH + ~ABH + ~ABH + ~ABH + ~ABH + ~ABH

Что за бардак?

[juan_gandhi]

This is fucking impressive!!!

[vak]

Есть и минус. В коде от Грока бывают тонкие ошибки в логике, которые он неспособен не только исправить, но и осознать. Сколько я ни бился, потратил несколько часов вчера. Ни подробные юнит тесты, ни построчная отладочная печать не помогают. Как баран об новые ворота.

Так что естественный ум в программировании всё ещё необходим.

[juan_gandhi]

У естественного ума иной раз тоже бывают проблемы. Сейчас рефакторю мои старые тесты...

[vak]

Где-то пропала проверка на уникальность.

[spamsink]

ИИ такой ИИ.

[vak]

Оказывается, интеллект и ум это разные вещи. 😀

[vak]

Починил я питоновскую версию, теперь не глючит.

$ ./minimize-boolean-function.py
2-variable input: [0, 1, 0, 1]
          result: B
3-variable input: [0, 1, 'X', 0, 1, 0, 'X', 1]
          result: AB + A~C + ~A~BC
3-variable input: [0, 1, 0, 1, 'X', 1, 'X', 0]
          result: ~AC + ~BC
4-variable input: [0, 1, 'X', 0, 1, 0, 0, 1, 'X', 0, 0, 1, 0, 1, 'X', 1]
          result: ABD + ACD + ~AB~C~D + ~A~B~CD + BCD
4-variable input: [1, 0, 'X', 0, 0, 1, 0, 'X', 0, 0, 1, 0, 'X', 0, 0, 1]
          result: ~ABD + ~A~B~D + BCD + ~BC~D
5-variable input: ['X', 0, 0, 1, 0, 0, 0, 0, 0, 1, 'X', 0, 0, 0, 0, 0, 0, 1, 0, 0, 'X', 0, 0, 0, 0, 1, 0, 0, 0, 0, 'X', 1]
          result: ABCD + A~C~DE + ~A~B~CDE + B~C~DE
8-variable input: ['X', 'X', 'X', 'X', 'X', 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
          result: ABCDEFGH + ~ABC~D~EF~G~H + ~A~B~C~D~FG~H

[spamsink]

А также мудрость и хитрость.

[flamedancerii]

Самое продвинутое, что я накопал в свое время по теме был https://en.wikipedia.org/wiki/Espresso_heuristic_logic_minimizer , проект старый.
Мое личное, ничем не подкрепленное мнение: минимизация булевских функций стала сильно пересекаться с криптографией и тему из паблика убрали.
Там еще можно как-то минимизировать через SAT solvers, но это руки не дошли.
А Квайна МакКласки я, замахавшись студентом рисовать карты Карно, написал на Basic на ПК-01 "Львов" влет, получил ответ и дурак выключил, лень было магнитофон подключать.
Через неделю на Spectrum повторить не смог.

[vak]

Минимизатор на бейсике это круто! Жаль не сохранился.
Эспрессо известный тул, жаль не сопровождается больше. Многие пакеты используют espresso, к примеру pyeda. Из-за этого имеют проблемы с установкой.