Fwd: Programming puzzle with boolean circuits

Joel Goldstick joel.goldstick at gmail.com
Tue Dec 10 03:03:21 CET 2013


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


-- 
Joel Goldstick
http://joelgoldstick.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20131209/c52665ba/attachment.html>


More information about the Python-list mailing list