По следам наших выступлений

[spamsink]

...или лыко, мочало, начинай сначала.

Почти 9 лет назад я писал про очень сложный алгоритм. Не далее как несколько часов назад пришлось объяснять его молодому поколению.

К счастью, на этот раз программа (уже совершенно другая, написанная с нуля другими людьми) не затыкалась, а, почуяв неладное (строки длиннее 16 символов), давала ответ "не знаю", а это, как вы понимаете, для сельской местности, может, и годится, а для индустриальной - уже нет, потому претензии и возникли.

Comments

[sab123]

ЖЖ говорит, что нет такой страницы.

[spamsink]

Спасибо, последняя буква урла была утрачена.

[yurikhan]

Для индус-триальной версии вполне приемлемо для задач размера больше порогового говорить «доступно после регистрации».

[spamsink]

Софт, о котором я говорю - исключительно для индустриальных применений. Под "сельской местностью" я имел в виду внутренние тесты. :)

[dijifi]

Интересная задачка. Так и хочется утянуть для интервью.

Каждая строчка описывает 2^N разных бинарных строк, где N - число иксов в строке

Если мы изначально знаем, что эти подмножества не пересекаются, то тупо считаем иксы и узнаём сколько вариантов покрыто. Если нет, то надо уметь считать пересечения и их исключать.

Еще можно попробовать сливать строки: поглощать (строки эквивалентны за исключением позиций где одна из них содержит икс) или объединять (строки эквивалентны за исключением одной позиции где одна содержит 1 а другая 0). Чтобы легче сливать, надо отсортировать как надо. (А как лень думать, и как доказать что всегда сработает ксли решение есть тоже некогда)

0хххх
10ххх
110хх
1110х
1111х сливаются по одной снизу вверх

[spamsink]

Нет, что они не пересекаются, никто не обещал. Возможны наборы вида

xxxx1
xxx1x
xx1xx
x1xxx
1xxxx
00000

Приведенное в старом посте исправленное решение работает, и весьма эффективно.

[vanja_y]

This is SAT in disguise.

For each word w we can define a conjunction c(w) in variables x1,...,xN and their negations, with xi in c(w) if the i-th element of w is 1, and not(xi) in c(w) if the i-th element of w is 0. The variable xi does not appear in c(w) if the i-the element of w is X. By construction c(w) is TRUE on all binary sequences described by w and FALSE on all the other sequences.

Now define boolean function f as the disjunction of functions c(w) over all given words w. Then the set of given words covers all binary sequences if and only if f is a tautology.

Denote by h the negation of f. Observer that applying de Morgan rules we can write h in conjunctive normal form and CNF is a standard input for SAT-solvers.

Finally, f is a tautology if and only if SAT-solver returns FALSE for h.