Programming puzzle with boolean circuits

[Chris Angelico]

On Tue, Dec 10, 2013 at 1:21 PM, Chris Angelico <rosuav at gmail.com> wrote:
> Output: (I tweaked my __repr__ functions to parenthesize for clarity)
>
> (((not ((($1 and $2) or ($1 and $4)) or ($2 and $4)) and not ((($1 and
> $2) and $4) or (not ((($1 and $2) or ($1 and $4)) or ($2 and $4)) and
> (($1 or $2) or $4)))) or ((not ((($1 and $2) or ($1 and $4)) or ($2
> and $4)) and (($1 or $2) or $4)) and ($2 or $4))) or ((not ((($1 and
> $2) and $4) or (not ((($1 and $2) or ($1 and $4)) or ($2 and $4)) and
> (($1 or $2) or $4))) and ((($1 and $2) or ($1 and $4)) or ($2 and
> $4))) and ($2 and $4)))
> (((not ((($1 and $2) or ($1 and $4)) or ($2 and $4)) and not ((($1 and
> $2) and $4) or (not ((($1 and $2) or ($1 and $4)) or ($2 and $4)) and
> (($1 or $2) or $4)))) or ((not ((($1 and $2) or ($1 and $4)) or ($2
> and $4)) and (($1 or $2) or $4)) and ($1 or $4))) or ((not ((($1 and
> $2) and $4) or (not ((($1 and $2) or ($1 and $4)) or ($2 and $4)) and
> (($1 or $2) or $4))) and ((($1 and $2) or ($1 and $4)) or ($2 and
> $4))) and ($1 and $4)))
> (((not ((($1 and $2) or ($1 and $4)) or ($2 and $4)) and not ((($1 and
> $2) and $4) or (not ((($1 and $2) or ($1 and $4)) or ($2 and $4)) and
> (($1 or $2) or $4)))) or ((not ((($1 and $2) or ($1 and $4)) or ($2
> and $4)) and (($1 or $2) or $4)) and ($2 or $1))) or ((not ((($1 and
> $2) and $4) or (not ((($1 and $2) or ($1 and $4)) or ($2 and $4)) and
> (($1 or $2) or $4))) and ((($1 and $2) or ($1 and $4)) or ($2 and
> $4))) and ($2 and $1)))
>
> Okay, so maybe the brute-force-discovered version isn't so bad after all. :)

I added the same parenthesizing to the brute force searcher and reran
it through 'time'.

~$1 = (($4 or not (($1 and $2) or ($4 and ($1 or $2)))) and (($4 and
not (($1 and $2) or ($4 and ($1 or $2)))) or (($2 or not (($1 and $2)
or ($4 and ($1 or $2)))) and (($2 and not (($1 and $2) or ($4 and ($1
or $2)))) or not (($2 or ($1 or $4)) and (($2 and ($1 and $4)) or not
(($1 and $2) or ($4 and ($1 or $2)))))))))
~$2 = (($4 or not (($1 and $2) or ($4 and ($1 or $2)))) and (($4 and
not (($1 and $2) or ($4 and ($1 or $2)))) or (($1 or not (($1 and $2)
or ($4 and ($1 or $2)))) and (($1 and not (($1 and $2) or ($4 and ($1
or $2)))) or not (($2 or ($1 or $4)) and (($2 and ($1 and $4)) or not
(($1 and $2) or ($4 and ($1 or $2)))))))))
~$4 = (($2 or not (($1 and $2) or ($4 and ($1 or $2)))) and (($2 and
not (($1 and $2) or ($4 and ($1 or $2)))) or (($1 or not (($1 and $2)
or ($4 and ($1 or $2)))) and (($1 and not (($1 and $2) or ($4 and ($1
or $2)))) or not (($2 or ($1 or $4)) and (($2 and ($1 and $4)) or not
(($1 and $2) or ($4 and ($1 or $2)))))))))

real 362m12.261s
user 362m7.186s
sys 0m0.064s

Yes, that is indeed six full hours of CPU time for a simple problem. Ha!

It seems to have come up with something fairly similar, actually. A
bit shorter than the algebraic solution.

brute: (($4 or not (($1 and $2) or ($4 and ($1 or $2)))) and (($4 and
not (($1 and $2) or ($4 and ($1 or $2)))) or (($2 or not (($1 and $2)
or ($4 and ($1 or $2)))) and (($2 and not (($1 and $2) or ($4 and ($1
or $2)))) or not (($2 or ($1 or $4)) and (($2 and ($1 and $4)) or not
(($1 and $2) or ($4 and ($1 or $2)))))))))

algebra: (((not ((($1 and $2) or ($1 and $4)) or ($2 and $4)) and not
((($1 and $2) and $4) or (not ((($1 and $2) or ($1 and $4)) or ($2 and
$4)) and (($1 or $2) or $4)))) or ((not ((($1 and $2) or ($1 and $4))
or ($2 and $4)) and (($1 or $2) or $4)) and ($2 or $4))) or ((not
((($1 and $2) and $4) or (not ((($1 and $2) or ($1 and $4)) or ($2 and
$4)) and (($1 or $2) or $4))) and ((($1 and $2) or ($1 and $4)) or ($2
and $4))) and ($2 and $4)))

Here's the most notable difference:
two_or_three = (a & b) | (a & c) | (b & c)
can be simplified to:
two_or_three = (a & b) | (c & (a | b))
That's one less gate in an early step. Even applying that change,
though, the brute-forced solution is still a bit shorter. Looks like
the algebraic solution could have a bit of optimization done!

ChrisA