Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #61409

Re: 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!newsfeed4.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!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.035
X-Spam-Evidence '*H*': 0.93; '*S*': 0.00; 'python.': 0.02; 'solution,': 0.09; 'tackle': 0.09; 'cc:addr:python-list': 0.11; 'python': 0.11; '&gt;&gt;': 0.16; 'ah,': 0.16; 'boolean': 0.16; 'discusses': 0.16; 'equations': 0.16; 'googled': 0.16; 'hint': 0.16; 'subject:Programming': 0.16; 'thought.': 0.16; '\xc2\xa0-': 0.16; 'wrote:': 0.18; '(not': 0.18; 'code.': 0.18; 'coding': 0.22; 'python?': 0.22; 'cc:addr:python.org': 0.22; 'creating': 0.23; 'own.': 0.24; 'guys': 0.24; 'mon,': 0.24; 'question': 0.24; 'cc:2**0': 0.24; '&gt;': 0.26; 'appreciated': 0.26; 'this:': 0.26; 'post': 0.26; 'nicht': 0.27; 'header:In-Reply-To:1': 0.27; 'am,': 0.29; "doesn't": 0.30; 'dec': 0.30; 'message-id:@mail.gmail.com': 0.30; 'along': 0.30; "i'm": 0.30; 'url:mailman': 0.30; 'code': 0.31; 'lines': 0.31; 'url:05': 0.31; 'url:2008': 0.31; 'figure': 0.32; 'url:python': 0.33; 'implemented': 0.33; 'maybe': 0.34; 'problem': 0.35; 'subject:with': 0.35; 'advice': 0.35; 'but': 0.35; 'received:google.com': 0.35; 'url:listinfo': 0.36; 'das': 0.36; "i'll": 0.36; 'possible': 0.36; 'url:org': 0.36; 'should': 0.36; 'so,': 0.37; 'two': 0.37; 'ends': 0.38; 'needed': 0.38; 'sure': 0.39; 'und': 0.40; 'url:mail': 0.40; 'how': 0.40; 'even': 0.60; 'easy': 0.60; 'solve': 0.60; 'most': 0.60; 'first': 0.61; 'group,': 0.63; 'thomas': 0.65; 'hours': 0.66; 'here': 0.66; 'attention.': 0.68; 'unsere': 0.68; 'electrical': 0.74; 'circuit': 0.84; 'college,': 0.84; 'gates.': 0.84; 'karl': 0.84; 'played': 0.84; 'heute': 0.91; 'joel': 0.91; '2013': 0.98
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 :cc:content-type; bh=IOb+VrvXR5WMenoTHzZ3fSpDHa+ao9AmIxrWKD4Rf5Q=; b=Kcn6yvu9Hx4/zxEuxaPgazNlDxdjWP5ZdxgQ9FDY/ESwMHXgvJUF6oX1nh6IVZescQ ScFHu8YFaLNprEPzC0LPa+EPlZyO+AebpT2yVQPeLk2k5y3oRYG0mCegSCo8kRS6XjOe paFsYtUuxS1MRGfliuO6C5uu1S6L8RmgmE8w57868JWyGaXiDbVmXsz5FXKVAXuK8Csw x59xC9N0dYCo1AC55pB31e/0tUUWOrqAaQf3DTGZ25bDi2S4/jp4mywKlN16Quvgsghv AnBr6u2e1CQ1RqtdD/YQgHSOnpKO9BP0SZ7SBQxs5I2KwnZGG8vKeYvqE7GdqSNcAiH6 UsnA==
MIME-Version 1.0
X-Received by 10.220.186.202 with SMTP id ct10mr11990994vcb.14.1386620365544; Mon, 09 Dec 2013 12:19:25 -0800 (PST)
In-Reply-To <l84aor$3mj$1@news.albasani.net>
References <l84aor$3mj$1@news.albasani.net>
Date Mon, 9 Dec 2013 15:19:25 -0500
Subject Re: Programming puzzle with boolean circuits
From Joel Goldstick <joel.goldstick@gmail.com>
To Johannes Bauer <dfnsonfsduifb@gmx.de>
Content-Type multipart/alternative; boundary=047d7b676fd053d2cb04ed1fb696
Cc "python-list@python.org" <python-list@python.org>
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.3792.1386620372.18130.python-list@python.org> (permalink)
Lines 130
NNTP-Posting-Host 2001:888:2000:d::a6
X-Trace 1386620372 news.xs4all.nl 2839 [2001:888:2000:d::a6]:40083
X-Complaints-To abuse@xs4all.nl
Xref csiph.com comp.lang.python:61409

Show key headers only | View raw

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

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

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

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