Programming puzzle with boolean circuits

[Joel Goldstick]

On Mon, Dec 9, 2013 at 6:49 AM, Johannes Bauer <dfnsonfsduifb at 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 at speranza.aioe.org>
> --
> https://mail.python.org/mailman/listinfo/python-list
>



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