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]

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

[juan_gandhi]

This is fucking impressive!!!

[flamedancerii]

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