p150

p150.py

def triangle_generator():
    t = 0
    s = []
    for k in range(1,500501):
        t = (615949*t + 797807) % 2**20
        s.append(t - 2**19)
        #First I generate the s values
    triangle = []
    r = 1000
    while r != 0:
        row = []
        for x in range(r):
            temp = s.pop(-1)
            row.insert(0,temp)
        triangle.insert(0, row)
        r -= 1
    #Now I make it into a triangle, mabye not the most efficient method
    return triangle
  
def compute():
    triangle = triangle_generator()
    row_sum_triangle = triangle_generator()
    #Generate 2 identical triangles, one will be used to keep a cumulative sum of the rows
    for row in range(len(row_sum_triangle)):
        row_sum_triangle[row].insert(0,0) 
        #Add a zero at the beginning of a row, otherwise we cannot sum easily sum an entire row
        for col in range(1, len(row_sum_triangle[row])):
            row_sum_triangle[row][col] += row_sum_triangle[row][col-1]
    #With this we have a running total of the sum in a row, so if we want to calculate a partial sum say from
    #triangle[5][2] to triangle[5][6] all we need is row_sum_triangle[5][7] - row_sum_triangle[5][2]
    minimum = 0
    for x in range(len(triangle)): #Denotes row
        for y in range(len(triangle[x])): #Denotes position in row
            curr_sum = triangle[x][y]
            #Check if the single value is a minimum
            if curr_sum < minimum:
                minimum = curr_sum #I update it like this to minimise memory usage
            curr_y = y + 2 #We need to offset by 2 because row_sum_triangle starts with 0
            for next_x in range(x+1,1000):
                curr_sum += row_sum_triangle[next_x][curr_y] - row_sum_triangle[next_x][y]
                #Check if the next level triangle is the minimum
                if curr_sum < minimum:
                    minimum = curr_sum
                curr_y += 1
    return minimum