Programming puzzle with boolean circuits
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!
> 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.
>> 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