On Tue, Dec 10, 2013 at 1:21 PM, Chris Angelico <ros...@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 -- https://mail.python.org/mailman/listinfo/python-list
