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

Groups > comp.lang.python > #61452

Re: Programming puzzle with boolean circuits

Show key headers only | View raw

On Tue, Dec 10, 2013 at 1:21 PM, Chris Angelico <rosuav@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

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