Programming puzzle with boolean circuits

[Antoon Pardon]

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.

-- 
Antoon Pardon