Programming puzzle with boolean circuits

[Chris Angelico]

On Tue, Dec 10, 2013 at 1:03 PM, Joel Goldstick
<joel.goldstick at gmail.com> wrote:
> Chris, and all.. Since you posted yours, I post this for your pleasure.  I
> couldn't figure out what you were doing.
> [chomp Python implementation of a fairly elegant solution]

That's a fairly nice piece of code that comes from a deliberate
solution. What the OP asked was how to devise a brute-force solver.

Grab the four class definitions from my code a few posts ago, and then
tweak your code to use them:

a = Schrodinger(1)
b = Schrodinger(2)
c = Schrodinger(4)
all_ones = a & b & c
two_or_three = (a & b) | (a & c) | (b & c)
zero_or_one = ~two_or_three
one_one = zero_or_one & (a | b | c)
zero_or_two = ~(all_ones | one_one)
zero_ones = zero_or_one & zero_or_two
two_ones = zero_or_two & two_or_three

# the output is true if all the inputs are zero, | if one of the
inputs is zero & it is either b | c
# | two inputs are zero & they are b & c
# ditto f| other two inputs
x = zero_ones | (one_one & (b | c)) | (two_ones & (b & c))
y = zero_ones | (one_one & (a | c)) | (two_ones & (a & c))
z = zero_ones | (one_one & (b | a)) | (two_ones & (b & a))
if x == ~a: print(x)
if y == ~b: print(y)
if z == ~c: print(z)

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. :)

The classes allow "a and b == c" to be evaluated for all possible
values of a, b, and c, so the brute-forcing actually accumulates data
and only subsequently evaluates it. It's far from the most efficient
solution (took hours on an i5 CPU), but it's fun :)

ChrisA