Path: csiph.com!usenet.pasdenom.info!weretis.net!feeder4.news.weretis.net!rt.uk.eu.org!newsfeed.xs4all.nl!newsfeed4.news.xs4all.nl!xs4all!news.tele.dk!news.tele.dk!small.news.tele.dk!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
MIME-Version: 1.0
In-Reply-To: <CAPTjJmoz1A2ASai3sZFXdJ9jaYDV-BGPgfdgGGTz-b4e3uuqKQ@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> <CAPTjJmoz1A2ASai3sZFXdJ9jaYDV-BGPgfdgGGTz-b4e3uuqKQ@mail.gmail.com>
Date: Tue, 10 Dec 2013 19:50:40 +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.3815.1386665450.18130.python-list@python.org>
Lines: 78
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:61452

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