Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!eu.feeder.erje.net!news.stack.nl!newsfeed.xs4all.nl!newsfeed3.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.034 X-Spam-Evidence: '*H*': 0.93; '*S*': 0.00; 'python.': 0.02; 'exercise': 0.04; 'paths': 0.07; 'rows': 0.09; 'url:github': 0.09; 'adjacent': 0.16; 'begging': 0.16; 'compute': 0.16; 'example).': 0.16; 'it;': 0.16; 'subject:programming': 0.16; 'to:name:python list': 0.16; 'triangle': 0.16; '(or': 0.24; 'task': 0.26; 'scale': 0.29; 'message-id:@mail.gmail.com': 0.30; 'enjoyed': 0.31; 'problem': 0.35; 'received:google.com': 0.35; 'fun,': 0.36; 'possible': 0.36; 'example,': 0.37; 'jason': 0.38; 'to:addr :python-list': 0.38; 'little': 0.38; 'to:addr:python.org': 0.39; 'enough': 0.39; 'read': 0.60; 'liked': 0.60; 'free': 0.61; 'challenge': 0.61; 'numbers': 0.61; 'simple': 0.61; 'such': 0.63; 'maximum': 0.63; 'sum': 0.64; 'more': 0.64; 'posed': 0.84; 'approach.': 0.91; 'optimum': 0.93 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:date:message-id:subject:from:to:content-type; bh=6CSJcxpfWL8C/Im/RbOG0682izp87U5CvNOfAUDtSFQ=; b=BiK3IJqVVGhHars4w/+fXASsP+LDME5ddyef5jTzcQbBdRTxEZsiwSi925V8t/dfp8 wikarE0Ql1tLOO6eYKpHimgE/BUODESl4uz906D+yF7N+spFAa8XQkk7McFpYZd5p8Ee Xcea+yyM1n4pFteS1kIsdc5e3gebq8wdN+AR8AQOYjHAetmkS+BqaJlKG/9EADQbN4oy 5c5W1GxgODxh0HXWb6zz4T5E88DfE8pwAP208tduCMz+ONUwg1sn+5BrtwItmHH17Asd 4HRYjQb81ebtSesBZv8/Qbsm6yQswaicnvTPHaM9lioG99MGsuTUkKB51a1ik2kuWMup 7uwg== MIME-Version: 1.0 X-Received: by 10.236.41.226 with SMTP id h62mr18379593yhb.182.1418708776329; Mon, 15 Dec 2014 21:46:16 -0800 (PST) Date: Tue, 16 Dec 2014 00:46:16 -0500 Subject: Neat little programming puzzle From: Jason Swails To: python list Content-Type: multipart/alternative; boundary=089e013a29e0a725e9050a4ee043 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: 72 NNTP-Posting-Host: 2001:888:2000:d::a6 X-Trace: 1418709166 news.xs4all.nl 2954 [2001:888:2000:d::a6]:58799 X-Complaints-To: abuse@xs4all.nl Xref: csiph.com comp.lang.python:82576 --089e013a29e0a725e9050a4ee043 Content-Type: text/plain; charset=UTF-8 This was a problem posed to me, which I solved in Python. I thought it was neat and enjoyed the exercise of working through it; feel free to ignore. For people looking for little projects to practice their skills with (or a simple distraction), read on. You have a triangle of numbers such that each row has 1 more number than the row before it, like so: 1 3 2 8 6 1 5 10 15 2 The task is to find the maximum possible sum through the triangle that you can compute by adding numbers that are adjacent to the value chosen in the row above. In this simple example, the solution is 1+3+6+15=25. As the number of rows increases, the possible paths through the triangle grows exponentially (and it's not enough to just look at the max value in each row, since they may not be part of the optimum pathway, like the '8' in row 3 of the above example). The challenge is to write a program to compute the sum of https://gist.github.com/swails/17ef52f3084df708816d. I liked this problem because naive solutions scale as O(2^N), begging for a more efficient approach. Have fun, Jason --089e013a29e0a725e9050a4ee043 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
Th= is was a problem posed to me, which I solved in Python.=C2=A0 I thought it = was neat and enjoyed the exercise of working through it; feel free to ignor= e.=C2=A0 For people looking for little projects to practice their skills wi= th (or a simple distraction), read on.

You have a triangle of numbers such that each row has 1 mor= e number than the row before it, like so:

=C2=A0 =C2=A0 =C2=A0 =C2=A0 1
=C2=A0 =C2=A0 =C2=A03 =C2=A0 =C2=A02
=C2=A0 =C2=A08 = =C2=A0 =C2=A06 =C2=A0 =C2=A01
5 =C2=A0 =C2=A010 =C2=A0 15 =C2=A02

The task is to find the maximum possible sum t= hrough the triangle that you can compute by adding numbers that are adjacen= t to the value chosen in the row above.=C2=A0 In this simple example, the s= olution is 1+3+6+15=3D25.=C2=A0 As the number of rows increases, the possib= le paths through the triangle grows exponentially (and it's not enough = to just look at the max value in each row, since they may not be part of th= e optimum pathway, like the '8' in row 3 of the above example).

The challenge is to write = a program to compute the sum of=C2=A0https://gist.github.com/swails/17ef52f3084df70881= 6d.

I liked this pr= oblem because naive solutions scale as O(2^N), begging for a more efficient= approach.
Have fun,
Jason
--089e013a29e0a725e9050a4ee043--