Path: csiph.com!usenet.pasdenom.info!weretis.net!feeder4.news.weretis.net!rt.uk.eu.org!newsfeed.xs4all.nl!newsfeed2.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail Return-Path: X-Original-To: python-list@python.org Delivered-To: python-list@mail.python.org X-Spam-Status: OK 0.087 X-Spam-Evidence: '*H*': 0.83; '*S*': 0.00; 'output,': 0.09; 'solution,': 0.09; 'changes': 0.15; 'from:addr:rosuav': 0.16; 'from:name:chris angelico': 0.16; 'splitting': 0.16; 'subject:Programming': 0.16; 'threw': 0.16; 'exception': 0.16; 'wrote:': 0.18; 'seems': 0.21; 'to:name:python-list@python.org': 0.22; "haven't": 0.24; 'header:In-Reply-To:1': 0.27; 'chris': 0.29; 'am,': 0.29; 'dec': 0.30; 'message-id:@mail.gmail.com': 0.30; 'asked': 0.31; 'code': 0.31; 'long.': 0.31; 'piece': 0.31; 'subject:with': 0.35; 'problem.': 0.35; 'but': 0.35; 'received:google.com': 0.35; 'crazy': 0.36; 'instances': 0.36; "didn't": 0.36; 'too': 0.37; 'two': 0.37; 'to:addr:python-list': 0.38; 'to:addr:python.org': 0.39; 'how': 0.40; 'even': 0.60; 'skip:u 10': 0.60; 'eventually': 0.60; 'took': 0.61; "you'll": 0.62; 'more': 0.64; 'taking': 0.65; 'hours': 0.66; 'hey,': 0.75; "'not'": 0.84; '2013': 0.98 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :content-type; bh=oaIjFJViCyvvhLNHDYc6Y2uNdDVxQVTPYiQ9BoHN9Do=; b=q6nGR7Ae3fVN2osyqNxJLaWMd9VeURByBpSaV+wiftSyrWG50VHAUd6Vd/Z7aeFDyF 9cLTjahB1c2/yC/XgoVCLtBkJ8OT+CMXq2aj9ru/PlIg9LQUEgWd0K8Wc9cm9K9udXo7 TksN9lnjcunm9B9G8wNceWfRJ1PSRu5YBzVZtiM/vXKEjkG29LBgMmpHa3et0KXUoNi0 Gk68/Hb5A7aNeT8UZJdYNQNQkcwM/1sl5YWZMuUbBuuC82jB1yw5dgxwr3efb3YUC06B a6fIGj2oIM7ZnxpD7Iw2saijniC0iWaj6TCNeHx9bB8t/UJNgkiPdQfv3v3iitqKZyDk adaA== MIME-Version: 1.0 X-Received: by 10.68.196.193 with SMTP id io1mr24516354pbc.46.1386639706263; Mon, 09 Dec 2013 17:41:46 -0800 (PST) In-Reply-To: References: Date: Tue, 10 Dec 2013 12:41:46 +1100 Subject: Re: Programming puzzle with boolean circuits From: Chris Angelico To: "python-list@python.org" Content-Type: text/plain; charset=UTF-8 X-BeenThere: python-list@python.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: General discussion list for the Python programming language List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Newsgroups: comp.lang.python Message-ID: Lines: 27 NNTP-Posting-Host: 2001:888:2000:d::a6 X-Trace: 1386639709 news.xs4all.nl 2834 [2001:888:2000:d::a6]:44768 X-Complaints-To: abuse@xs4all.nl Xref: csiph.com comp.lang.python:61427 On Tue, Dec 10, 2013 at 12:25 AM, Chris Angelico wrote: > Unfortunately I haven't been able to prove that the code works, > because even with some changes it's taking way too long. But hey, it's > a crazy fun piece to work with! Well... it eventually solved the problem. I don't know how many CPU hours it took but it threw a SolutionFound exception eventually. Unfortunately I didn't parenthesize the display. The solution seems to involve using a NOT gate and then splitting its output, so you'll see more than two instances of 'not' in the output. This is definitely not an optimal solution, but hey, you asked for a brute-force solver! ~$1 = $4 or not $1 and $2 or $4 and $1 or $2 and $4 and not $1 and $2 or $4 and $1 or $2 or $2 or not $1 and $2 or $4 and $1 or $2 and $2 and not $1 and $2 or $4 and $1 or $2 or not $2 or $1 or $4 and $2 and $1 and $4 or not $1 and $2 or $4 and $1 or $2 ~$2 = $4 or not $1 and $2 or $4 and $1 or $2 and $4 and not $1 and $2 or $4 and $1 or $2 or $1 or not $1 and $2 or $4 and $1 or $2 and $1 and not $1 and $2 or $4 and $1 or $2 or not $2 or $1 or $4 and $2 and $1 and $4 or not $1 and $2 or $4 and $1 or $2 ~$4 = $2 or not $1 and $2 or $4 and $1 or $2 and $2 and not $1 and $2 or $4 and $1 or $2 or $1 or not $1 and $2 or $4 and $1 or $2 and $1 and not $1 and $2 or $4 and $1 or $2 or not $2 or $1 or $4 and $2 and $1 and $4 or not $1 and $2 or $4 and $1 or $2 ChrisA