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

Groups > comp.lang.python > #82576 > unrolled thread

Neat little programming puzzle

Back to article view | Back to comp.lang.python

Contents

  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

#82576 — Neat little programming puzzle

[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

[toc] | [next] | [standalone]

#82579

On Tue, 16 Dec 2014 00:46:16 -0500, Jason Swails wrote:

> I liked this problem because naive solutions scale as O(2^N), begging for
> a more efficient approach.

Project Euler has this one, twice; problems 18 and 67.

The difference between the two is that problem 18 has 15 rows while
problem 67 has 100 rows. Problem 18 can realistically be solved by a
brute-force approach, problem 67 can't.

[toc] | [prev] | [next] | [standalone]

#82584

On Tuesday, December 16, 2014 12:52:58 AM UTC-5, 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.
> 
> 
> Have fun,
> Jason

Here is a program in Picat, which has a built-in tabling mechanism for dynamic programming solutions:

http://picat-lang.org/euler/p18.pi

Cheers,
NF

[toc] | [prev] | [next] | [standalone]

#82585

On Monday, December 15, 2014 9:52:58 PM UTC-8, 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.
> 
> 
> Have fun,
> Jason

If you really like these kinds of problems, you should really check out Project Euler.  Many of them are easy to solve via brute force, but some, while you could easily produce a brute force program, would take millions of years to solve and so require you to be clever.

https://projecteuler.net/

As someone else mentioned, this is similar to problems 18 and 67.  You could probably solve it with a path-finding algorithm, but there are probably even more clever methods than that.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web