3
\$\begingroup\$

I've solved Project Euler #18 in Python but think my code and algorithm can be improved. Here is the problem:

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:

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

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!

And I want with an bottom-up calculation to find the best path down. Here is my code:

import time

num_pyr = '''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 break_pyramid(num_pyr):
    '''
    Breaks the number string into an array
    '''
    pyramid = []
    rows = num_pyr.split('\n')
    for row in rows:
        pyramid.append([int(i) for i in row.split(' ')])
    return pyramid

def add_from_under(upper_row, lower_row):
    '''
    Takes the maximum of the legs under upper row to each index to add up from bottom
    Parameters
    ----------
    upper_row : len n
    lower_row : len n + 1

    Returns
    -------
    new_upper_row
    '''
    greater_vals = [max(lower_row[i:i+2]) for i in range(len(upper_row))]
    return [x + y for x, y in zip(upper_row, greater_vals)]


def main():
    pyramid = break_pyramid(num_pyr)[::-1]
    for i in range(len(pyramid)-1):
        new_upper = add_from_under(pyramid[1], pyramid[0])
        pyramid[1] = new_upper
        del pyramid[0]
    return pyramid[0][0]


if __name__ == '__main__':
    t1 = time.time()
    best_path = main()
    op_time = 1000000 * (time.time() - t1)  # us
    print("Calculated {} in {:.1f} us".format(best_path, op_time))

I think improvements can be made in my main() since I am using del. Should del be avoided for any reason?

\$\endgroup\$
  • \$\begingroup\$ "Should del be avoided for any reason?" Let's turn it around: why do you feel you need it in this case? \$\endgroup\$ – Mast Dec 4 '17 at 18:23
  • \$\begingroup\$ it just seemed to simplify the loop since the other option is to have a counter to keep track of what row I'm on. But I'm already doing that with for i in range(len(pyramid)-1) so I can just make the first line new_upper = add_from_under(pyramid[i+1], pyramid[0]). then that would remove the entire del line from the loop. \$\endgroup\$ – TheStrangeQuark Dec 4 '17 at 18:47
3
\$\begingroup\$

In break_pyramid you use list comprehension to split a row into numbers – why not use list comprehension as well to split the input into rows?

def break_pyramid(num_pyr):
    '''
    Breaks the number string into an array
    '''
    pyramid = [[int(col) for col in row.split(' ')] for row in num_pyr.split('\n')]
    return pyramid

In add_from_under, this

greater_vals = [max(lower_row[i:i+2]) for i in range(len(upper_row))]

creates many intermediate slices. The alternative

greater_vals = [max(l, r) for l, r in zip(lower_row, lower_row[1:])]

seems to be slightly faster. You can even combine both zip operations into a single one:

def add_from_under(upper_row, lower_row):
    return [upper + max(lower_left, lower_right)
         for upper, lower_left, lower_right in zip(upper_row, lower_row, lower_row[1:])]

so that no intermediate list is created.


The main loop applies add_from_under cumulatively to the pyramid rows (in reverse order). That is a "reduce" operation and can be done with functools.reduce:

from functools import reduce

def main():
    pyramid = break_pyramid(num_pyr)
    final_row = reduce(add_from_under, reversed(pyramid))
    return final_row[0]

if we exchange the parameter order in add_from_under to

def add_from_under(lower_row, upper_row):
    return [upper + max(lower_left, lower_right)
         for upper, lower_left, lower_right in zip(upper_row, lower_row, lower_row[1:])]

Now the pyramid variable is just iterated over, but not modified anymore.

\$\endgroup\$
2
\$\begingroup\$

Since you are not using i anywhere in the loop, the better approach is to loop for row in pyramid. Now you only need to track your new_upper:

    new_upper = pyramid[0]
    for row in pyramid[1:]:
        new_upper = add_from_under(new_upper, row)
    return new_upper[0]

Other than that, the algorithm is correct, the code is clean and well-structured.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.