Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #82577

Re: Neat little programming puzzle

Show key headers only | View raw

[Multipart message — attachments visible in raw view] - view raw

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

Back to comp.lang.python | Previous | Next | Find similar | Unroll thread

Thread

Re: Neat little programming puzzle Ian Kelly <ian.g.kelly@gmail.com> - 2014-12-16 00:01 -0700

csiph-web