Project Euler 150 - Searching a triangular array for a sub-triangle having minimum-sum

Official link:

Thought Process

First thing I did was create an actual triangle array, makes it easier to understand. (See my triangle_generator function below)

Now given an apex of a triangle say (a,b) the triangle including the line below will have (a+1,b) and (a+1,b+1), the next layer and will have (a+2,b), (a+2,b+1) and (a+2, b+2), notice with this arrangement we are essentially summing each row from y to y + x, where x is the row. Therefore if we have a method to quickly sum a row the problem is done.

I did this by creating a second triangle (see row_sum_triangle) which keeps a running total of each row, this means that instead of summing up to 1000 values (in the last row) we can simply take the value representing the sum up till that point and subtract the start sum.

To illustrate if we want to sum from triangle[6][2] to triangle [6][6] we would normally need 5 summations however using row_sum_triangle we need only do row_sum_triangle[6][7] - row_sum_triangle[6][2] (Notice we offset by 1 because we need the first value in each row of row_sum_triangle to be 0 otherwise we cannot sum the entire row)

Interactive Code

Not much to interact with here, I provide my code below