1
\$\begingroup\$

The Quine-McCluskey algorithm merges disjunctors in a disjunction like $$ \lnot x_0 \land \lnot x_1 \land \lnot x_2 \land \lnot x_3 \lor\\ x_0 \land \lnot x_1 \land x_2 \land \lnot x_3 \lor\\ \lnot x_0 \land x_1 \land x_2 \land \lnot x_3 \lor\\ \lnot x_0 \land \lnot x_1 \land \lnot x_2 \land x_3 \lor\\ \lnot x_0 \land x_1 \land \lnot x_2 \land x_3 \lor\\ x_0 \land x_1 \land \lnot x_2 \land x_3 \lor\\ \lnot x_0 \land x_1 \land x_2 \land x_3 \lor\\ x_0 \land x_1 \land x_2 \land x_3 $$ into fewer disjunctors in an equivalent disjunction: $$ x_1 \land x_3 \lor\\ \lnot x_0 \land \lnot x_1 \land \lnot x_2 \lor\\ \lnot x_0 \land x_1 \land x_2 \lor\\ x_0 \land \lnot x_1 \land \lnot x_2 \land x_3 $$ by merging like this: $$x_0\land x_1\lor\lnot x_0\land x_1 \iff (x_0\lor\lnot x_0)\land x_1\iff x_1$$.

https://www.mathematik.uni-marburg.de/~thormae/lectures/ti1/code/qmc/ will generate test cases to taste.

Your task

Your task is to write a function transforming any disjunction into an equivalent disjunction of minimal disjunctor count.

The QMC algorithm imperative in the headline is a sloppy summary and a mere recommendation, no hard requirement.

You can encode the data any way fit, that is $$\lnot x_1 \land \lnot x_2 \land x_3$$ can become

  • [3,0,0,1]
  • [(1,0),(2,0),(3,1)]
  • (14,8)

This is code-golf. Shortest code wins.

\$\endgroup\$
4
  • 3
    \$\begingroup\$ More test cases would be helpfull \$\endgroup\$
    – mousetail
    Commented May 14, 2023 at 12:40
  • \$\begingroup\$ i added another link to more test cases, will that suffice? \$\endgroup\$ Commented May 14, 2023 at 12:51
  • 2
    \$\begingroup\$ "task is" does not require Quine-McCluskey. QMC merely yields the most keywordy headline, the most sensible approach, and leaves liberties anyways, so feel free to submit a QMC contender. \$\endgroup\$ Commented May 14, 2023 at 20:01
  • \$\begingroup\$ Why was this reopened? Nothing's been changed since it was closed. \$\endgroup\$
    – Shaggy
    Commented May 17, 2023 at 18:15

2 Answers 2

3
\$\begingroup\$

Kamilalisp, 139 bytes

(defun s m \let-seq(def a \⍸ \= 1 \⌼ $(foldl1 +)@/= m m)(↩ (= 0 \⍴ a) m)(def p m$[⍎ a])\^⍪ p \⍠ m \[tie@* ⍎ $(foldl1 =)] p)

"Ungolfed":

(⍥← s m \○⊢¨
  (○← a \⍸ \= 1 \⌼ $(⌿⊙← +)∘≠ m m)   ; Find all possible rows we can join.
  (↩ (= 0 \⍴ a) m)                    ; If we can't join anything, yield.
  (○← p m$[⍎ a])                      ; Determine the contents of the rows in the matrix to be joined.
  \^⍪ p \⍠ m \[⌿⊙⍧∘* ⍎ $(⌿⊙← =)] p) ; Adjoin the new row, remove the merged two.

In essence, the algorithm finds two rows in the matrix that represents the expression (where every cell, either -1, 1, or 0 represents that the boolean literal is either negated, taken as given, or not used), that differ at most by one entry. Then, if no such rows are found, the algorithm returns the original matrix. If at least one such pair exists, it is removed from the matrix, the difference between is computed as a mask (e.g. for -1 -1 1 1 and -1 -1 1 -1, the mask is 1 1 1 0), which is then multiplied by the first (or equivalently second) element of the pair to form a new entry in the expression matrix.

Some test cases, etc:

Attempt This Online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ A direct APL translation with the same semantics as the KamilaLisp program at 42 bytes: {0=≢x←⍸1=∘.(+/≠)⍨⍵:⍵⋄∇(⍵∘~,∘⊂⊢⊃⍤×=/)⍵[⊃x]} \$\endgroup\$ Commented May 18, 2023 at 17:38
-3
\$\begingroup\$

Haskell, 340 bytes

import Data.Bits;import Data.List;import Data.List.Ordered
o d[]=d;o _ s=s
p(a:b:c)|a==b=a|0<1=p(b:c)
q(_,b)(c,d)=c.&.b==c.&.d
r t s=and[or[q f e|e<-s]|f<-t]
s(a,b)(c,d)=[(a.&.complement x,b.&.d)|a==c,let x=xor b d,1==popCount x]
t d=nubSort$concatMap(\c->o[c]$concatMap(s c)d)d
u d=head$sortOn length$filter(r d)$subsequences$p$iterate t d

Here a disjunctor is represented by (significantbitmask,setbits) fiddled by q and s. s combines two disjunctors if they have the same significantbitmask and differ in exactly one bit. o[c] prevents disjunctors from disappearing if they combine with nobody. u computes a minimal disjunction: t merges antivalents in d until p no more merges occur, then it filters for r sufficient subsets as the merges can produce superfluous disjunctors.

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.