Number of paths in square grid (Project Euler problem 15)

Description of the problem (from here ):
Starting in the top left corner of a 22 grid, there are 6 routes (without backtracking) to the bottom right corner.

How many routes are there through a 2020 grid?


A: We can observe that:

•  every path has exactly 2*n moves, every move being either right or down (backtracking isn't allowed)
• in every 2*n path there are n moves down and n moves right. 

So, the number of all the distinct possibilities is the number of ways we can arrange n right moves from 2*n positions:

Number of digits in Fibonacci term (Project Euler problem 25)

Q: The question from the problem 25  is to find the first term in the Fibonacci sequence to contain 1000 digits. 


A: The answer comes from wiki: 


Since F_n is asymptotic to , the number of digits in  is asymptotic to . As a consequence, for every integer d > 1 there are either 4 or 5 Fibonacci numbers with d decimal digits.


So, 1000/0.2090 is approximately  4784, and the first Fibonacci term with 1000 digits is the 4782th term.

Maximal sum in a triangle (Project Euler problem 67)

The problem description is here. For a given triangle you have to find the path with the maximum path. Given an input triangle :
3
7 4
2 4 6
9 5 9 3


We can compute the maximum sum path using 2 approaches:

Solution 1 : bottom-up. Build maximum path from bottom.  From the next-to-last row, up to the first, add the maximum corresponding sub-triangle. So the initial triangle becomes iteratively:


3
7    4
11 13 15
9    5    9  3


3
20 19
11 13 15
9    5    9  3


23
20 19
11 13 15
9    5    9  3

So the maximum sum is 23, and the maximum path 

3
7 4
2 4 6
9 5 9 3

Solution 2: same result is obtained with a top-down approach. Starting from the second row, compute the maximum-sum path to every element. So the initial triangle becomes iteratively:

3
10  7
2 4 6
9 5 9 3

3
10  7
12 14 13
9 5 9 3

3
10  7
12 14 13
21 19 23 16

We get same result for the maximum sum.

Simple python Implementation for the bottom-up solution:

def get_numbers():
    #lines = open("tri_small.txt", "r")    
    lines = open("tri.txt", "r")    
    
    listOfRows = []
    
    for line in lines:
        currRow = [int(x) for x in line.split()]
        listOfRows.append(currRow)
    
    return listOfRows
    
def solve():
    row_list = get_numbers()
    length = len(row_list)
    
    for i in xrange(length-2, -1, -1) :
        len_row = len(row_list[i])                   
        for j in range(0, len_row) :
            row_list[i][j] += max(row_list[i+1][j], row_list[i+1][j+1])
        
    print row_list[0]
    return 0