Programming puzzle with boolean circuits

[Chris Angelico]

On Mon, Dec 9, 2013 at 10:49 PM, Johannes Bauer <dfnsonfsduifb at 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