By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.
**3** **7** 4 2 **4** 6 8 5 **9** 3
That is, 3 + 7 + 4 + 9 = 23.
Find the maximum total from top to bottom of the triangle below:
NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)
In [1]:
t4 = [
[3],
[7, 4],
[2, 4, 6],
[8, 5, 9, 3],
]
t4
Out[1]:
In [2]:
t15 = [
[75],
[95, 64],
[17, 47, 82],
[18, 35, 87, 10],
[20, 4, 82, 47, 65],
[19, 1, 23, 75, 3, 34],
[88, 2, 77, 73, 7, 63, 67],
[99, 65, 4, 28, 6, 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, 4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31],
[ 4, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 4, 23],
]
len(t15)
Out[2]:
In [3]:
from copy import deepcopy
In [4]:
def foo(t):
t = deepcopy(t)
for i in range(len(t))[::-1]:
r = t[i]
try:
nr = t[i+1]
except IndexError:
for j in range(len(t[i])):
t[i][j] = (t[i][j], None)
else:
for j in range(len(t[i])):
dir = (t[i+1][j+1][0] > t[i+1][j+0][0])
t[i][j] = (t[i][j] + t[i+1][j+dir][0], dir)
return t[0][0][0]
In [5]:
n = t4
%timeit foo(n)
foo(n)
Out[5]:
In [6]:
n = t15
%timeit foo(n)
foo(n)
Out[6]:
Let's try a somewhat functional approach. It is much easier to understand. I like that.
In [7]:
def foo(t):
old_row = []
for row in t:
stagger_max = map(max, zip([0] + old_row, old_row + [0]))
old_row = list(map(sum, zip(stagger_max, row)))
return max(old_row)
In [8]:
n = t4
%timeit foo(n)
foo(n)
Out[8]:
In [9]:
n = t15
%timeit foo(n)
foo(n)
Out[9]:
Try tuples instead of lists. It's a little bit faster and still readable. That's a good combination.
In [10]:
def foo(t):
old_row = tuple()
for row in t:
stagger_max = map(max, zip((0,) + old_row, old_row + (0,)))
old_row = tuple(map(sum, zip(stagger_max, row)))
return max(old_row)
In [11]:
n = t4
%timeit foo(n)
foo(n)
Out[11]:
In [12]:
n = t15
%timeit foo(n)
foo(n)
Out[12]:
Convert t4 and t15 to be tuples instead of lists. This does not affect readability. It is faster yet.
In [13]:
t4 = tuple(tuple(row) for row in t4)
t15 = tuple(tuple(row) for row in t15)
In [14]:
def foo(t):
old_row = tuple()
for row in t:
stagger_max = map(max, zip((0,) + old_row, old_row + (0,)))
old_row = tuple(map(sum, zip(stagger_max, row)))
return max(old_row)
In [15]:
n = t4
%timeit foo(n)
foo(n)
Out[15]:
In [16]:
n = t15
%timeit foo(n)
foo(n)
Out[16]:
I like cell 7 the most. For me, its lists are more readable than tuples.
2017-09-02 Now I play some more.
First, Consolidate the body of the loop into a single ugly long statement. It is a little bit faster.
In [17]:
def foo(t):
old_row = tuple()
for row in t:
old_row = tuple(map(sum, zip(
map(max, zip((0,) + old_row, old_row + (0,))), row)))
return max(old_row)
In [18]:
n = t4
%timeit foo(n)
foo(n)
Out[18]:
In [19]:
n = t15
%timeit foo(n)
foo(n)
Out[19]:
Next, eliminate the loop by using recursion. This code is much harder for me to understand. It is slower also.
It was good exercise to play with replacing a loop with recursion. Functional programming fans should like it.
In [20]:
def goo(t):
*upper_rows, bottom_row = t
if not upper_rows:
return tuple(bottom_row)
maximums = goo(upper_rows)
stagger_max = map(max, zip((0,) + maximums, maximums + (0,)))
return tuple(map(sum, zip(stagger_max, bottom_row)))
In [21]:
def foo(t):
return max(goo(t))
In [22]:
n = t4
%timeit foo(n)
foo(n)
Out[22]:
In [23]:
n = t15
%timeit foo(n)
foo(n)
Out[23]: