Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!eu.feeder.erje.net!newsfeed.xs4all.nl!newsfeed3a.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.004 X-Spam-Evidence: '*H*': 0.99; '*S*': 0.00; 'python.': 0.02; 'exercise': 0.04; 'paths': 0.07; 'python3': 0.07; 'sys': 0.07; '"__main__":': 0.09; '__name__': 0.09; 'main()': 0.09; 'rows': 0.09; 'url:github': 0.09; 'def': 0.12; 'adjacent': 0.16; 'begging': 0.16; 'compute': 0.16; 'example).': 0.16; 'it;': 0.16; 'main():': 0.16; 'subject:programming': 0.16; 'triangle': 0.16; 'wrote:': 0.18; 'solution.': 0.20; '8bit%:5': 0.22; 'programming': 0.22; 'import': 0.22; 'email addr:gmail.com>': 0.22; 'mon,': 0.24; '(or': 0.24; '>': 0.26; '15,': 0.26; 'task': 0.26; 'values': 0.27; 'header:In-Reply-To:1': 0.27; 'raise': 0.29; 'scale': 0.29; 'dec': 0.30; 'message-id:@mail.gmail.com': 0.30; 'enjoyed': 0.31; 'skip:# 10': 0.33; 'problem': 0.35; 'received:google.com': 0.35; '8bit%:9': 0.36; 'possible': 0.36; 'example,': 0.37; 'jason': 0.38; 'to:addr:python-list': 0.38; 'pm,': 0.38; 'little': 0.38; 'skip:& 20': 0.39; 'to:addr:python.org': 0.39; 'enough': 0.39; 'skip:u 10': 0.60; 'read': 0.60; 'liked': 0.60; 'skip:\xc2 10': 0.60; 'free': 0.61; 'challenge': 0.61; 'numbers': 0.61; 'simple': 0.61; 'real': 0.63; 'such': 0.63; 'maximum': 0.63; '8bit%:10': 0.64; 'sum': 0.64; 'more': 0.64; 'skip:r 30': 0.69; '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:in-reply-to:references:from:date:message-id:subject:to :content-type; bh=tOO2IMbIR30rbWT6YfrCRKZ29CmQcWzl9l7YE2yqqmI=; b=WwDZg7Isk3dtTbCrFlXuCqYudQ3OccTCUorN7YEH+RD2nwNFjDe0MrrugBugyF6BE/ zhAdWSWoGLVaHQDHNNGcyZmfxYrH6o/0IIGw0wAUCMJ8conqcn1NogF8yY8HESE507Bm cJXd3CJrt3i3+cBrjsudWVQetE08lQvukUaUCoSqCEOFhS/N6Lo009I4p13g4+pJSZx4 m9W0ZQNgLV3NMGGZc00jDNeF0nsyLCOImryzB57u+tEzLpxoEB4ECQSYYmL6ASNmsS95 +Vp8TEtEAl7KIWr5kMcw5PA4FmZ3JRKUw6aN1bcZ0TRgqC13ESsoOPLMQl/Kj/y+xa6z DLuw== X-Received: by 10.70.14.130 with SMTP id p2mr46642657pdc.101.1418713353336; Mon, 15 Dec 2014 23:02:33 -0800 (PST) MIME-Version: 1.0 In-Reply-To: References: From: Ian Kelly Date: Tue, 16 Dec 2014 00:01:52 -0700 Subject: Re: Neat little programming puzzle To: Python Content-Type: multipart/alternative; boundary=047d7bd74b4e76beff050a4ff179 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: 124 NNTP-Posting-Host: 2001:888:2000:d::a6 X-Trace: 1418713362 news.xs4all.nl 2839 [2001:888:2000:d::a6]:40989 X-Complaints-To: abuse@xs4all.nl Xref: csiph.com comp.lang.python:82577 --047d7bd74b4e76beff050a4ff179 Content-Type: text/plain; charset=UTF-8 On Mon, Dec 15, 2014 at 10:46 PM, Jason Swails wrote: > > 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. This pretty much screams for a dynamic programming solution. ikelly@hephaestus ~ $ cat triangle_sum.py #!/usr/bin/env python3 from urllib.request import urlopen import sys def main(): triangle = read_triangle(urlopen(sys.argv[1])) print("Maximum possible sum is", triangle_sum(triangle)) def read_triangle(from_file): rows = [] for line in from_file: values = [int(x) for x in line.strip().split()] rows.append(values) if len(values) != len(rows): raise ValueError("Invalid triangle input") return rows def triangle_sum(triangle): dp_row = triangle[-1] for row in reversed(triangle[:-1]): dp_row = [row[i] + max(dp_row[i], dp_row[i+1]) for i in range(len(row))] return dp_row[0] if __name__ == "__main__": main() ikelly@hephaestus ~ $ time python3 triangle_sum.py https://gist.githubusercontent.com/swails/17ef52f3084df708816d/raw/aae1c494e69f0b3dad1eb6ea818f8f36d05be7a3/gistfile1.txt Maximum possible sum is 724269 real 0m0.582s user 0m0.191s sys 0m0.013s --047d7bd74b4e76beff050a4ff179 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
On Mon, Dec 15, 2014 at 10:46 PM, Jason Swails <jason.swails@gmail.com> wrote:>
> This 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; f= eel free to ignore.=C2=A0 For people looking for little projects to practic= e 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 r= ow 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=A0= 6 =C2=A0 =C2=A01
> 5 =C2=A0 =C2=A010 =C2=A0 15 =C2=A02
>
>= ; The task is to find the maximum possible sum through the triangle that yo= u can compute by adding numbers that are adjacent to the value chosen in th= e row above.=C2=A0 In this simple example, the solution is 1+3+6+15=3D25.= =C2=A0 As the number of rows increases, the possible paths through the tria= ngle grows exponentially (and it's not enough to just look at the max v= alue in each row, since they may not be part of the optimum pathway, like t= he '8' in row 3 of the above example).
>
> The challeng= e is to write a program to compute the sum of https://gist.github.com/swails/17ef52f30= 84df708816d.
>
> I liked this problem because naive solutio= ns scale as O(2^N), begging for a more efficient approach.

This= pretty much screams for a dynamic programming solution.

ikelly@hephaestus ~ $ cat triangle_sum.py
#!/usr/bin/= env python3

from urllib.request import urlopen
import sys

def main():
=C2=A0 =C2= =A0 triangle =3D read_triangle(urlopen(sys.argv[1]))
=C2=A0 =C2= =A0 print("Maximum possible sum is", triangle_sum(triangle))

def read_triangle(from_file):
=C2=A0 =C2=A0 = rows =3D []
=C2=A0 =C2=A0 for line in from_file:
=C2=A0= =C2=A0 =C2=A0 =C2=A0 values =3D [int(x) for x in line.strip().split()]
=C2=A0 =C2=A0 =C2=A0 =C2=A0 rows.append(values)
=C2=A0 =C2= =A0 =C2=A0 =C2=A0 if len(values) !=3D len(rows):
=C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 raise ValueError("Invalid triangle input&q= uot;)
=C2=A0 =C2=A0 return rows

def tria= ngle_sum(triangle):
=C2=A0 =C2=A0 dp_row =3D triangle[-1]
=C2=A0 =C2=A0 for row in reversed(triangle[:-1]):
=C2=A0 =C2= =A0 =C2=A0 =C2=A0 dp_row =3D [row[i] + max(dp_row[i], dp_row[i+1])
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 for i in r= ange(len(row))]
=C2=A0 =C2=A0 return dp_row[0]

if __name__ =3D=3D "__main__":
=C2=A0 =C2=A0 mai= n()
Maximum possible sum is 724269

real =C2=A0 =C2=A00m0.582s
user =C2=A0 =C2=A00m0.= 191s
sys =C2=A0 =C2=A0 0m0.013s

--047d7bd74b4e76beff050a4ff179--