Programming puzzle with boolean circuits

Johannes Bauer dfnsonfsduifb at gmx.de
Wed Dec 11 14:52:40 CET 2013


On 09.12.2013 14:25, Chris Angelico wrote:

>> I found this puzzle again and was thinking about: How would I code a
>> brute-force approach to this problem in Python?
> 
> Ooooh interesting!

Ha, I thought so too :-)

> Well, here's a start: There's no value in combining the same value in
> an AND or an OR, ergo every gate you add must bring together two
> different values.
> 
> To start with, you have three values (the three inputs). Every time
> you combine two of them, with either type of gate, you create a new
> value. You can also combine a single value with a NOT to create its
> inverse, but only if you have done so no more than once.
> 
> The goal is to produce something which is provably the opposite of
> each of the three inputs.
> 
> I'm not sure if this helps or not, but one thing I learned from
> geometry is that setting down everything you know and need to know is
> a good basis for the search!

Absolutely.

> 
> The hardest part, so far, is proving a result. The algorithm that's
> coming to mind is this:
> 
> def find_solution(inputs, not_count):
>     # TODO: First, see if inputs contains three values that are the inverses of
>     # the three values i1,i2,i3. If they are, throw something, that's probably
>     # the easiest way to unwind the stack.
>     if not_count < 2:
>         for val in inputs:
>             find_solution(inputs + [not val], not_count + 1)
>     for val1 in inputs:
>         for val2 in inputs:
>             if val1 is not val2:
>                 find_solution(inputs + [val1 and val2], not_count)
>                 find_solution(inputs + [val1 or val2], not_count)
> 
> find_solution([i1, i2, i3], 0)

I understand your approach, it has given me some ideas too. Thanks for this!

> So, here's a crazy idea: Make i1, i2, i3 into objects of a type with
> an __eq__ that actually does the verification. Schrodinger's Objects:
> they might be True, might be False, and until you call __eq__, they're
> in both states. This probably isn't the best way, but I think it's the
> most fun!

Haha, it surely is a very cool idea!

Thanks for the ideas and your very cool approach. I'll try to tackle it
myself (I think I have a good point to start) and will post the code
once I'm finished.

Best regards,
Joe

-- 
>> 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>



More information about the Python-list mailing list