Programming puzzle with boolean circuits
antoon.pardon at rece.vub.ac.be
Tue Dec 10 15:25:42 CET 2013
Op 09-12-13 12:49, Johannes Bauer schreef:
> 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).
Well I would make some kind of connecter type, that would have a binary
vector associated with it. How do we calculate bit n of a connector?
Take the three input signals, i0, i1, i2, these can be seen as a binary
digits. So suppose we have input 0, 1, 0 then bit 2 of the connector
would be the value of that connector with these input signals.
The original three connectors would have the following values:
01010101, 00110011, 00001111.
What you can do now is make new connectors by combining them with
an or, and or not port and search for those whose value is 10101010,
11001100 and 11110000.
More information about the Python-list