Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!news.mixmin.net!rt.uk.eu.org!newsfeed.xs4all.nl!newsfeed4.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
MIME-Version: 1.0
In-Reply-To: <CAPM-O+yssdgztsRZjZOWE8k8OaB_2sg3nnd1zQM=osZ0ggE0ow@mail.gmail.com>
References: <l84aor$3mj$1@news.albasani.net> <CAPM-O+z4vuhoyKuEVdoYxJe42qhXT89GQTyQEHGjvm+c8yV3NQ@mail.gmail.com> <CAPM-O+yssdgztsRZjZOWE8k8OaB_2sg3nnd1zQM=osZ0ggE0ow@mail.gmail.com>
Date: Tue, 10 Dec 2013 13:21:46 +1100
Subject: Re: Programming puzzle with boolean circuits
From: Chris Angelico <rosuav@gmail.com>
Cc: "python-list@python.org" <python-list@python.org>
Content-Type: text/plain; charset=UTF-8
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.3807.1386642111.18130.python-list@python.org>
Lines: 66
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:61430

On Tue, Dec 10, 2013 at 1:03 PM, Joel Goldstick
<joel.goldstick@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