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 -- https://mail.python.org/mailman/listinfo/python-list
