# Programming puzzle with boolean circuits

Chris Angelico rosuav at gmail.com
Tue Dec 10 03:21:46 CET 2013

```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

```