Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #61430

Re: Programming puzzle with boolean circuits

Show key headers only | View raw

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

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Programming puzzle with boolean circuits Johannes Bauer <dfnsonfsduifb@gmx.de> - 2013-12-09 12:49 +0100
  Re: Programming puzzle with boolean circuits Chris Angelico <rosuav@gmail.com> - 2013-12-10 00:25 +1100
    Re: Programming puzzle with boolean circuits Johannes Bauer <dfnsonfsduifb@gmx.de> - 2013-12-11 14:52 +0100
  Re: Programming puzzle with boolean circuits Joel Goldstick <joel.goldstick@gmail.com> - 2013-12-09 15:19 -0500
  Spoiler alert? (Re: Programming puzzle with boolean circuits) John Ladasky <john_ladasky@sbcglobal.net> - 2013-12-09 12:39 -0800
    Re: Spoiler alert? (Re: Programming puzzle with boolean circuits) Joel Goldstick <joel.goldstick@gmail.com> - 2013-12-09 15:45 -0500
  Re: Programming puzzle with boolean circuits Chris Angelico <rosuav@gmail.com> - 2013-12-10 12:41 +1100
  Fwd: Programming puzzle with boolean circuits Joel Goldstick <joel.goldstick@gmail.com> - 2013-12-09 21:03 -0500
  Re: Programming puzzle with boolean circuits Chris Angelico <rosuav@gmail.com> - 2013-12-10 13:21 +1100
  Re: Programming puzzle with boolean circuits Chris Angelico <rosuav@gmail.com> - 2013-12-10 19:50 +1100
  Re: Programming puzzle with boolean circuits Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2013-12-10 15:25 +0100

csiph-web