Fwd: Programming puzzle with boolean circuits

Path	csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!eu.feeder.erje.net!newsfeed.xs4all.nl!newsfeed2.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
Return-Path	<joel.goldstick@gmail.com>
X-Original-To	python-list@python.org
Delivered-To	python-list@mail.python.org
X-Spam-Status	OK 0.014
X-Spam-Evidence	'H': 0.97; 'S': 0.00; 'output': 0.05; '"""': 0.07; '"__main__":': 0.09; '__name__': 0.09; 'bits': 0.09; 'python': 0.11; 'def': 0.12; 'posted': 0.15; 'boolean': 0.16; 'chris,': 0.16; 'inputs': 0.16; 'subject:Programming': 0.16; 'zero,': 0.16; 'to:name:python-list@python.org': 0.22; 'print': 0.22; 'post': 0.26; 'values': 0.27; 'header:In-Reply-To:1': 0.27; 'message-id:@mail.gmail.com': 0.30; 'operators': 0.31; 'restricted': 0.31; 'url:05': 0.31; 'url:2008': 0.31; 'figure': 0.32; 'skip:# 10': 0.33; 'subject:with': 0.35; 'but': 0.35; 'received:google.com': 0.35; 'yours,': 0.36; 'two': 0.37; 'list.': 0.37; 'skip:& 10': 0.38; 'to:addr:python-list': 0.38; 'skip:& 20': 0.39; "couldn't": 0.39; 'to:addr:python.org': 0.39; 'mailing': 0.39; 'either': 0.39; 'skip:\xc2 10': 0.60; 'subject:Fwd': 0.61; 'here': 0.66; '8bit%:100': 0.72; 'goal': 0.75; 'pleasure.': 0.84; 'joel': 0.91
DKIM-Signature	v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :content-type; bh=6HsrryERxwiQA1qQ0k2mEhXSqlT2yGfeUk4JmIiUNsw=; b=q5Yrc7MyaOgf597TraKQH4diKLJaHPckLHWhRjkDAuRygv6+i6noTKXAY/EHzdqHp8 8a8WZoArJ65rvUkCPX+Rs7WyG9YLY+K1cbc29Q3IX7CZxULZz0ATZDUvhqhciZiFhAtP cSGNlQCReTTtrPe31ao57p+DK1X2Mlqvx+xMBmiA6nlL9vUv7bja/th75f8+4IRNLpU8 O3mhb6goiXHlwd/uKZl7tLAk/hdBiQl7zOWXpGDNKTnjm7sFjwwM1whegGtZi5mrfa7N GB5IIyuHVKRIxwtRKllSGwxKqeB1pXMbOJbDPj6MaMI08EpRIC7vOE6QC5rgGhKYgWyA Upxg==
MIME-Version	1.0
X-Received	by 10.53.9.201 with SMTP id du9mr509178vdd.36.1386641001200; Mon, 09 Dec 2013 18:03:21 -0800 (PST)
In-Reply-To	<CAPM-O+z4vuhoyKuEVdoYxJe42qhXT89GQTyQEHGjvm+c8yV3NQ@mail.gmail.com>
References	<l84aor$3mj$1@news.albasani.net> <CAPM-O+z4vuhoyKuEVdoYxJe42qhXT89GQTyQEHGjvm+c8yV3NQ@mail.gmail.com>
Date	Mon, 9 Dec 2013 21:03:21 -0500
Subject	Fwd: Programming puzzle with boolean circuits
From	Joel Goldstick <joel.goldstick@gmail.com>
To	"python-list@python.org" <python-list@python.org>
Content-Type	multipart/alternative; boundary=001a1133b1ac4ebff104ed2484ac
X-BeenThere	python-list@python.org
X-Mailman-Version	2.1.15
Precedence	list
List-Id	General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe	<https://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive	<http://mail.python.org/pipermail/python-list/>
List-Post	<mailto:python-list@python.org>
List-Help	<mailto:python-list-request@python.org?subject=help>
List-Subscribe	<https://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Newsgroups	comp.lang.python
Message-ID	<mailman.3806.1386641004.18130.python-list@python.org> (permalink)
Lines	107
NNTP-Posting-Host	2001:888:2000:d::a6
X-Trace	1386641004 news.xs4all.nl 2841 [2001:888:2000:d::a6]:51031
X-Complaints-To	abuse@xs4all.nl
Xref	csiph.com comp.lang.python:61429

Show key headers only | View raw

[Multipart message — attachments visible in raw view] - view raw

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

Thread

Programming puzzle with boolean circuits Johannes Bauer <dfnsonfsduifb@gmx.de> - 2013-12-09 12:49 +0100
  Re: Programming puzzle with boolean circuits Chris Angelico <rosuav@gmail.com> - 2013-12-10 00:25 +1100
    Re: Programming puzzle with boolean circuits Johannes Bauer <dfnsonfsduifb@gmx.de> - 2013-12-11 14:52 +0100
  Re: Programming puzzle with boolean circuits Joel Goldstick <joel.goldstick@gmail.com> - 2013-12-09 15:19 -0500
  Spoiler alert? (Re: Programming puzzle with boolean circuits) John Ladasky <john_ladasky@sbcglobal.net> - 2013-12-09 12:39 -0800
    Re: Spoiler alert? (Re: Programming puzzle with boolean circuits) Joel Goldstick <joel.goldstick@gmail.com> - 2013-12-09 15:45 -0500
  Re: Programming puzzle with boolean circuits Chris Angelico <rosuav@gmail.com> - 2013-12-10 12:41 +1100
  Fwd: Programming puzzle with boolean circuits Joel Goldstick <joel.goldstick@gmail.com> - 2013-12-09 21:03 -0500
  Re: Programming puzzle with boolean circuits Chris Angelico <rosuav@gmail.com> - 2013-12-10 13:21 +1100
  Re: Programming puzzle with boolean circuits Chris Angelico <rosuav@gmail.com> - 2013-12-10 19:50 +1100
  Re: Programming puzzle with boolean circuits Antoon Pardon <antoon.pardon@rece.vub.ac.be> - 2013-12-10 15:25 +0100

csiph-web