Programming puzzle with boolean circuits

[Johannes Bauer]

Hi group,

it's somewhat OT here, but I have a puzzle to which I would like a
solution -- but I'm unsure how I should tackle the problem with Python.
But it's a fun puzzle, so maybe it'll be appreciated here.

The question is: How do you design a boolean circuit that contains at
most 2 NOT gates, but may contain as many AND or OR gates that inverts
three inputs? IOW: Build three inverters by using only two inverters
(and an infinite amount of AND/OR).

Surprisingly, this is possible (and I even know the solution, but won't
give it away just yet).

I found this puzzle again and was thinking about: How would I code a
brute-force approach to this problem in Python? And to my surprise, it
isn't as easy as I thought. So I'm looking for some advice from you guys
(never huts to improve ones coding skills).

Best regards,
Johannes

--
>> Wo hattest Du das Beben nochmal GENAU vorhergesagt?
> Zumindest nicht �ffentlich!
Ah, der neueste und bis heute genialste Streich unsere gro�en
Kosmologen: Die Geheim-Vorhersage.
- Karl Kaos �ber R�diger Thomas in dsa <hidbv3$om2$1...@speranza.aioe.org>

[Chris Angelico]

On Mon, Dec 9, 2013 at 10:49 PM, Johannes Bauer <dfnson...@gmx.de> wrote:
> The question is: How do you design a boolean circuit that contains at
> most 2 NOT gates, but may contain as many AND or OR gates that inverts
> three inputs? IOW: Build three inverters by using only two inverters
> (and an infinite amount of AND/OR).
>

> I found this puzzle again and was thinking about: How would I code a
> brute-force approach to this problem in Python?

Ooooh interesting!

Well, here's a start: There's no value in combining the same value in
an AND or an OR, ergo every gate you add must bring together two
different values.

To start with, you have three values (the three inputs). Every time
you combine two of them, with either type of gate, you create a new
value. You can also combine a single value with a NOT to create its
inverse, but only if you have done so no more than once.

The goal is to produce something which is provably the opposite of
each of the three inputs.

I'm not sure if this helps or not, but one thing I learned from
geometry is that setting down everything you know and need to know is
a good basis for the search!

The hardest part, so far, is proving a result. The algorithm that's
coming to mind is this:

def find_solution(inputs, not_count):
# TODO: First, see if inputs contains three values that are the inverses of
# the three values i1,i2,i3. If they are, throw something, that's probably
# the easiest way to unwind the stack.
if not_count < 2:
for val in inputs:
find_solution(inputs + [not val], not_count + 1)
for val1 in inputs:
for val2 in inputs:
if val1 is not val2:
find_solution(inputs + [val1 and val2], not_count)
find_solution(inputs + [val1 or val2], not_count)

find_solution([i1, i2, i3], 0)

So, here's a crazy idea: Make i1, i2, i3 into objects of a type with
an __eq__ that actually does the verification. Schrodinger's Objects:
they might be True, might be False, and until you call __eq__, they're
in both states. This probably isn't the best way, but I think it's the
most fun!

I couldn't make this work with the and/or/not operators, so I'm using
the &/|/~ operators, which can be overridden.

So! There's the basics, but it's a depth-first search, which means
it's bound to hit the recursion limit. Refinement needed;
specifically, it needs to not add any input that's equal to any other.
That's easy enough.

Unfortunately I haven't been able to prove that the code works,
because even with some changes it's taking way too long. But hey, it's
a crazy fun piece to work with!



class Schrodinger:
def __init__(self, bit):
self.state = bit
def coalesce(self, master):
return bool(master & self.state)
def __len__(self):
return 1;
def __invert__(self):
return Negated(self)
def __and__(self, other):
return Anded((self, other))
def __or__(self, other):
return Ored((self, other))
def __eq__(self, other):
for master in range(8):
if self.coalesce(master) != other.coalesce(master):
return False
return True
def __repr__(self):
return "$%d" % self.state

class Negated(Schrodinger):
def coalesce(self, master):
return not self.state.coalesce(master)
def __len__(self):
return len(self.state) + 1
def __repr__(self):
return "not %r" % self.state

class Anded(Schrodinger):
def coalesce(self, master):
return self.state[0].coalesce(master) and self.state[1].coalesce(master)
def __len__(self):
return len(self.state[0]) + len(self.state[1]) + 1
def __repr__(self):
return "%r and %r" % self.state

class Ored(Schrodinger):
def coalesce(self, master):
return self.state[0].coalesce(master) or self.state[1].coalesce(master)
def __len__(self):
return len(self.state[0]) + len(self.state[1]) + 1
def __repr__(self):
return "%r or %r" % self.state

class SolutionFound(Exception):
pass

def find_solution(inputs, not_count):
# First see if the newest input is equal to anything we already have.
# If it is, we gain nothing by probing this.
if inputs[-1] in inputs[:-1]: return
# Then, see if inputs contains three values that are the inverses of
# the three values i1,i2,i3. If they are, throw something, that's probably
# the easiest way to unwind the stack.
try:
raise SolutionFound("""Solution:
~$1 = %r
~$2 = %r
~$4 = %r""" % (
inputs[inputs.index(~inputs[0])],
inputs[inputs.index(~inputs[1])],
inputs[inputs.index(~inputs[2])],
))
except ValueError:
pass # ValueError means one of the negations wasn't found.
if not_count < 2:
for val in inputs:
find_solution(inputs + [~val], not_count + 1)
for val1 in inputs:
for val2 in inputs:
find_solution(inputs + [val1 & val2], not_count)
find_solution(inputs + [val1 | val2], not_count)

i1 = Schrodinger(1)
i2 = Schrodinger(2)
i3 = Schrodinger(4)
find_solution([i1, i2, i3], 0)



ChrisA

[Joel Goldstick]

On Mon, Dec 9, 2013 at 6:49 AM, Johannes Bauer <dfnson...@gmx.de> wrote:

Hi group,

it's somewhat OT here, but I have a puzzle to which I would like a
solution -- but I'm unsure how I should tackle the problem with Python.
But it's a fun puzzle, so maybe it'll be appreciated here.

The question is: How do you design a boolean circuit that contains at
most 2 NOT gates, but may contain as many AND or OR gates that inverts
three inputs? IOW: Build three inverters by using only two inverters
(and an infinite amount of AND/OR).

Surprisingly, this is possible (and I even know the solution, but won't
give it away just yet).

I found this puzzle again and was thinking about: How would I code a
brute-force approach to this problem in Python? And to my surprise, it
isn't as easy as I thought. So I'm looking for some advice from you guys
(never huts to improve ones coding skills).

Best regards,
Johannes

I studied Electrical Engineering in college, so this puzzle grabbed my attention.  For a couple of hours I played around thinking about how to attack this problem  My first thought was that if you had two inverters (NOT gates), you needed to create an inverter with and and or gates.  That goes nowhere.  So, I googled around and found this: http://www.thelowlyprogrammer.com/2008/05/not-puzzle-solution.html (spoiler alert).  It discusses how you can solve the problem, but it doesn't give python code.  As it ends up I implemented that solution in 18 lines of code

So, my hint is that it can be solved by creating several simultaneous equations

I'll send my code along if someone asks, but I don't want to post it here because I'm sure others will want to figure it out on their own.

 

--
>> Wo hattest Du das Beben nochmal GENAU vorhergesagt?

> Zumindest nicht öffentlich!
Ah, der neueste und bis heute genialste Streich unsere großen
Kosmologen: Die Geheim-Vorhersage.
 - Karl Kaos über Rüdiger Thomas in dsa <hidbv3$om2$1...@speranza.aioe.org>
--
https://mail.python.org/mailman/listinfo/python-list

--

Joel Goldstick

http://joelgoldstick.com

[John Ladasky]

It has been ages since I've thought about logic gates, but...

(Spoiler alert? I'm not sure...)
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

My thought is that with two NOT logic gates, you can only build a flip-flop memory circuit. That strongly suggests to me that a memory circuit would actually be used to solve the problem somehow.

I'm thinking that feedback loops would have to be involved, no matter what the solution is. A need for feedback loops would make it very hard to write code to look for the solution automatically. The dimensionality of the search space will be high.

[Joel Goldstick]

On Mon, Dec 9, 2013 at 3:39 PM, John Ladasky <john_l...@sbcglobal.net> wrote:

It has been ages since I've thought about logic gates, but...

My thought is that with two NOT logic gates, you can only build a flip-flop memory circuit.  That strongly suggests to me that a memory circuit would actually be used to solve the problem somehow.

Two NOT gates plus as many AND and OR gates as you need.
 

I'm thinking that feedback loops would have to be involved, no matter what the solution is.  A need for feedback loops would make it very hard to write code to look for the solution automatically.  The dimensionality of the search space will be high.

--
https://mail.python.org/mailman/listinfo/python-list

[Chris Angelico]

On Tue, Dec 10, 2013 at 12:25 AM, Chris Angelico <ros...@gmail.com> wrote:
> Unfortunately I haven't been able to prove that the code works,
> because even with some changes it's taking way too long. But hey, it's
> a crazy fun piece to work with!

Well... it eventually solved the problem. I don't know how many CPU
hours it took but it threw a SolutionFound exception eventually.

Unfortunately I didn't parenthesize the display. The solution seems to
involve using a NOT gate and then splitting its output, so you'll see
more than two instances of 'not' in the output. This is definitely not
an optimal solution, but hey, you asked for a brute-force solver!

~$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

ChrisA

[Joel Goldstick]

Chris, and all.. Since you posted yours, I post this for your pleasure.  I couldn't figure out what you were doing.

#!/usr/bin/env python

"""
This is a puzzle brought up on the python mailing list.
The goal is to take 3 bits and invert them using boolean logic, but restricted to only 2 NOT gates
Here is a solution I found via google:  http://www.thelowlyprogrammer.com/2008/05/not-puzzle-solution.html
"""

def invert_three(a,b,c):

    """ give three boolean values, return their inverted values
    Only 2 NOT operators are allowed
    Deduce these truths
    """
    all_ones = a and b and c
    two_or_three = (a and b) or (a and c) or (b and c)
    zero_or_one = not two_or_three
    one_one = zero_or_one and (a or b or c)
    zero_or_two = not (all_ones or one_one)
    zero_ones = zero_or_one and zero_or_two
    two_ones = zero_or_two and two_or_three
   
    # the output is true if all the inputs are zero, or if one of the inputs is zero and it is either b or c
    # or two inputs are zero and they are b and c
    # ditto for other two inputs
    x = zero_ones or (one_one and (b or c)) or (two_ones and (b and c))
    y = zero_ones or (one_one and (a or c)) or (two_ones and (a and c))
    z = zero_ones or (one_one and (b or a)) or (two_ones and (b and a))
    return int(x), int(y), int(z)
   
if __name__ == "__main__":
    for a in range(2):
        for b in range(2):
            for c in range(2):
                print "Input: ", a, b, c,
                x, y, z = invert_three(a,b,c)
                print "Output: ", x, y, z

[Chris Angelico]

On Tue, Dec 10, 2013 at 1:03 PM, Joel Goldstick
<joel.go...@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

[Chris Angelico]

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

[Antoon Pardon]

Op 09-12-13 12:49, Johannes Bauer schreef:

> Hi group,
>
> it's somewhat OT here, but I have a puzzle to which I would like a
> solution -- but I'm unsure how I should tackle the problem with Python.
> But it's a fun puzzle, so maybe it'll be appreciated here.
>
> The question is: How do you design a boolean circuit that contains at
> most 2 NOT gates, but may contain as many AND or OR gates that inverts
> three inputs? IOW: Build three inverters by using only two inverters
> (and an infinite amount of AND/OR).
>
> Surprisingly, this is possible (and I even know the solution, but won't
> give it away just yet).
>
> I found this puzzle again and was thinking about: How would I code a
> brute-force approach to this problem in Python? And to my surprise, it
> isn't as easy as I thought. So I'm looking for some advice from you guys
> (never huts to improve ones coding skills).

Well I would make some kind of connecter type, that would have a binary
vector associated with it. How do we calculate bit n of a connector?

Take the three input signals, i0, i1, i2, these can be seen as a binary
digits. So suppose we have input 0, 1, 0 then bit 2 of the connector
would be the value of that connector with these input signals.

The original three connectors would have the following values:
01010101, 00110011, 00001111.

What you can do now is make new connectors by combining them with
an or, and or not port and search for those whose value is 10101010,
11001100 and 11110000.

--
Antoon Pardon

[Johannes Bauer]

On 09.12.2013 14:25, Chris Angelico wrote:

>> I found this puzzle again and was thinking about: How would I code a
>> brute-force approach to this problem in Python?
>
> Ooooh interesting!

Ha, I thought so too :-)

> Well, here's a start: There's no value in combining the same value in
> an AND or an OR, ergo every gate you add must bring together two
> different values.
>
> To start with, you have three values (the three inputs). Every time
> you combine two of them, with either type of gate, you create a new
> value. You can also combine a single value with a NOT to create its
> inverse, but only if you have done so no more than once.
>
> The goal is to produce something which is provably the opposite of
> each of the three inputs.
>
> I'm not sure if this helps or not, but one thing I learned from
> geometry is that setting down everything you know and need to know is
> a good basis for the search!

Absolutely.

>
> The hardest part, so far, is proving a result. The algorithm that's
> coming to mind is this:
>
> def find_solution(inputs, not_count):
> # TODO: First, see if inputs contains three values that are the inverses of
> # the three values i1,i2,i3. If they are, throw something, that's probably
> # the easiest way to unwind the stack.
> if not_count < 2:
> for val in inputs:
> find_solution(inputs + [not val], not_count + 1)
> for val1 in inputs:
> for val2 in inputs:
> if val1 is not val2:
> find_solution(inputs + [val1 and val2], not_count)
> find_solution(inputs + [val1 or val2], not_count)
>
> find_solution([i1, i2, i3], 0)

I understand your approach, it has given me some ideas too. Thanks for this!

> So, here's a crazy idea: Make i1, i2, i3 into objects of a type with
> an __eq__ that actually does the verification. Schrodinger's Objects:
> they might be True, might be False, and until you call __eq__, they're
> in both states. This probably isn't the best way, but I think it's the
> most fun!

Haha, it surely is a very cool idea!

Thanks for the ideas and your very cool approach. I'll try to tackle it
myself (I think I have a good point to start) and will post the code
once I'm finished.

Best regards,
Joe

--
>> Wo hattest Du das Beben nochmal GENAU vorhergesagt?

> Zumindest nicht öffentlich!
Ah, der neueste und bis heute genialste Streich unsere großen
Kosmologen: Die Geheim-Vorhersage.