Project Euler #18: Maximum path sum I

Question

Problem

I want to receive advice on my code, which takes 0.012 seconds.

import numpy as np
import time
start_time = time.time()
raw_data= """
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 data_input():
    a = raw_data.split("\n")
    new_a = [x.split(" ") if True else None for x in a]
    del(new_a[0]) # delete first element in new_a
    del(new_a[-1])
    return(new_a) # [['75'], ['95', '64'], ['17', '47', '82'], ['18', '35', '87', '10'], ['20', '04', '82', '47', '65'],...

def make_memoi_table():
    #make a table from below to above (to the top)
    new_a = data_input() # new_a : original raw_input data
    size = len(new_a)
    memoi_table = np.zeros((size,size))
    memoi_table[size-1] = [int(x) for x in new_a[size-1]]
    for i in range(2,size + 1):
        for j in range(len(new_a[size-i])):
            memoi_table[size-i][j] = int(new_a[size-i][j]) + max(memoi_table[size-i+1][j],memoi_table[size-i+1][j+1])
    return(memoi_table[0][0],memoi_table)

print(make_memoi_table())



print("--- %s seconds ---" % (time.time() - start_time))

Answer 1

You can save a bit in your input parser. You can run the list comprehension to replace the old list instead of making a new one. It's also easier to just return the list truncated with slicing rather than delete the start and end of it. Also x if True else y will always return x, so I don't know what the point of that is?

Also I'd pass in the data as a parameter, as well as give these variables and the function better names

def parse_data(raw_data):
    data = raw_data.split("\n")
    data = [line.split(" ") for line in data]
    return data[1:-1]

You're also performing inaccurate time testing. You take the start time at the beginning of the whole script. That means that it's measuring how long it takes to initialise constants and create the functions as well as running both functions. For a simple time testing approach, take a look at timeit.

Answer 2

• I don't see a need for memoi_table. Lists are mutable; you may modify values in place.

• I recommend to convert input to integers while you are parsing it. Expanding on @SuperBiasedMan suggestion,

  lines = raw_data.split('\n')
  data = [[int(x) for x in line.split(' ')] for line in lines[1:-1]]
  

• Working up the table suggests using a reverse range:

  for i in range(size, 1, -1):
  

Answer 3

You might prefer to measure running time in bash, outside of script. It is easier to code.

time python script.py 

Reverse range could also be made more idiomatic.

for i in reversed(range(size)):

Answer 4

Not sure if it´s faster, but it´s definitely more simple code:

triangle = [[int(x) for x in y.split(" ")] for y in reversed(raw_data.split("\n"))]


for i,line in enumerate(triangle):
    for idx,val in enumerate(line):
        line[idx] += 0 if i == 0 else  max(triangle[i-1][idx], triangle[i-1][idx+1])


print triangle[-1][0]