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

Groups > comp.lang.python > #61471

Re: Programming puzzle with boolean circuits

Show all headers | View raw

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

Back to comp.lang.python | Previous | Next — Previous 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