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

Groups > comp.lang.python > #82576

Neat little programming puzzle

Show key headers only | View raw

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

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

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

Thread

Neat little programming puzzle Jason Swails <jason.swails@gmail.com> - 2014-12-16 00:46 -0500
  Re: Neat little programming puzzle Nobody <nobody@nowhere.invalid> - 2014-12-16 08:24 +0000
  Re: Neat little programming puzzle neng.zhou@gmail.com - 2014-12-16 09:36 -0800
  Re: Neat little programming puzzle sohcahtoa82@gmail.com - 2014-12-16 10:04 -0800

csiph-web