Its time for an overdose of Math!
I encountered this problem in the Project Euler archives which involved a small triangle of numbers in which I had to find the maximum sum from top to bottom. The solution - brute force.
Wrong,
The main rule I follow and I believe most aspiring computer scientists follow involves the easiest way to solve a sum. Brute force doesn’t cut it as the best method to solve this sum when you are confronted with a grid as large as the one presented in question 67 (click here to see the mammoth of a triangle ).
I was trying to figure out the answer to that question and I came up with this idea, to move up from the base of the triangle. Here is how it works:
1. Consider the following triangle:
2. Replace each number in the second line with the number which happens to be the maximum of the numbers obtained
by adding that number to the two numbers adjacent to it in the line below. In this case, the pair giving the maximum
is represented in red.
Proceed in the same fashion and you will end up with 23 as the final number. 23 is the maximum sum obtained when going from top to bottom and this method is a quick way of getting to the answer.
Here is the code for the triangle provided in question 18:
#Author: Shriphani Palakodety a.k.a P.S.P
triangle = """\
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23"""
def triangleMaker(triangle):
triangle_list = [ line.split() for line in triangle.splitlines() ]
return triangle_list
#start from the lowermost line and work your way up.
def getMax(triangle):
#pick the second last line of the triangle
our_line = triangle[-2]
for i in range(len(our_line)):
new_num_list = []
new_num_list.append(int(triangle[-2][i]) + int(triangle[-1][i]))
new_num_list.append(int(triangle[-2][i]) + int(triangle[-1][i + 1]))
triangle[-2][i] = str(max(new_num_list))
triangle.pop()
return triangle
tri_grid = triangleMaker(triangle)
for i in range(len(tri_grid) - 1):
tri_grid = getMax(tri_grid)
print tri_grid
For an idea on how effective this solution is, question 67 took 0.18 seconds to solve.
Happy coding 
Comments 2
hey kiddo,
Posted 24 Mar 2008 at 4:16 pm ¶well now i can clearly say you are a Maths addict & of course a great hacker.keep good work going. hopefully
you make it 2 gsoc this time
best wishes..
Ty. BTW, GSoC is only for College-Goers I suppose. I will be eligible in 2009/10
Posted 25 Mar 2008 at 7:36 am ¶Post a Comment