HiveBrain v1.2.0
Get Started
← Back to all entries
patternpythonMinor

Project Euler #18: Maximum path sum I

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
pathmaximumprojecteulersum

Problem

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))

Solution

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.

Code Snippets

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

Context

StackExchange Code Review Q#105441, answer score: 2

Revisions (0)

No revisions yet.