Unforgettable day. Got my solution featured, as one of the best Python solutions to "The Double Helix" problem.

In this post we are dealing with Project Euler - 15 - Lattice paths. This is one of the simple dynamic programming problems. We have to find the number of paths to reach the bottom right from the top left, moving only downwards and right sidewards. It was not so easy for me to see the solution even for the sample data given. It would be easy when we look from the bottom-left. For the sample 2x2 grid, lets say the bottom-left (2, 2) point has 0 path and 1,2 and 2,1 have 1 path each. It is evident that number of paths to reach (2, 2) from all the points on the bottom most row (0, 2), (1, 2) and the right most column (2, 0), (2, 1), as we cannot move upwards and left sidewards. Now, (1, 1) has two paths to reach (2, 2), either through (1, 2) or (2, 1). So it has the value 2. Same way, (0, 1) and (1, 0) have 3 ways ( (0, 1) can take (1, 1) (which has 2 paths to (2, 2) ) and (0, 2) (which has 1 path to (2, 2) ). So, (0, 0) has 6 paths to (2, 2) either via (0, 1) or via (1, 0). Applied this idea as a dynamic programming program and it solved this problem.

Total = 21

Array = [[0]*Total for i in xrange(Total)]
for i in xrange(Total): Array[i][Total - 1], Array[Total - 1][i] = 1, 1   #Initializing bottom row and right column with 1

def Rec(i, j):
    global Array
    if Array[i][j]: return Array[i][j]
    Rec(i+1, j)
    Rec(i, j+1)
    Array[i][j] = Array[i+1][j] + Array[i][j+1]

Rec (0, 0)
print Array[0][0]

This post is about the Project Euler - 14 - Longest Collatz sequence problem. This is one of the perfect examples of memoization technique. This is the actual problem.

The following iterative sequence is defined for the set of positive integers:

n → n/2 (n is even)
n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

Simple Solution

The problem statement looks pretty simple and a brute force will work just fine. This code runs in 20 seconds.

def Series(N):
    Counter = 1
    while N != 1:
        N = N/2 if N % 2 == 0 else 3*N+1
        Counter += 1
    return Counter

Max, Element = 0, 0
for x in xrange (1, 1000000):
    series = Series(x)
    if (Max < series):
        Max = series
        Element = x

print Max, Element

As I had to wait for 20 seconds to get the solution, I was thinking about improving the performance. Then I found this. From the problem statement, 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1, starting with any number, if it becomes 13 at any point of time, it has to take the same route and if it becomes 13 it will take 10 steps to become 1. So I wanted to store this information first time itself, so that I don't have to recalculate. This is called Memoization. Quoting from wikipedia

In computing, memoization is an optimization technique used primarily to speed up computer programs by having function calls avoid repeating the calculation of results for previously processed inputs

Optimized (Memoized) Solution

To optimize it, I just had to change the Series function alone. I stored the computed values in a dictionary and if the current number in the sequence happens to be in the dictionary, I ll just return the value corresponding to it. This program responded with the result in 2 seconds. That is 10 times faster than the first version.

Dict = {}

def Series(N):
    Counter = 1   #It is 1, because we are counting the initial N
    Original = N
    while N != 1:
        N = N/2 if N % 2 == 0 else 3*N+1
        if N in Dict:                    # Check if the length has been computed for this number already
            Counter += Dict[N]           # Add it to the current length counter
            Dict [Original] = Counter    # Store the computed value for future look back
            return Counter
        Counter += 1
    Dict [Original] = Counter            # Store the computed value for future look back
    return Counter

Today I came across this interesting problem. Project Euler's Problem 5 - Smallest Multiple.

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Definitely 20! (factorial of 20) is one, which will be evenly divisible by all of the numbers from 1 to 20. But the problem is to find the smallest positive number. So, I thought, it would be the number which is the product of all the prime numbers within 20. I calculated 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 = 9699690, which is wrong, since a number divisible by 2 might not be divisible by 4 and the same applies for other prime numbers and their multiples. After little thinking, I couldn’t get a way to find the solution. So I applied brute force and my solution got accepted.

Brute Force Solution

i = 21
while True:
    flag = True
    for X in xrange(1, 21):
        if (i % X != 0):
            flag = False
            break
    if flag:
        print i
        break
    i += 1

But the problem with this solution is, the time taken to produce the result. It took 162 seconds or 2 minutes and 32 seconds. I wondered if I can improve my solution to produce solution in a reasonable amount of time. I couldn’t, so I googled and got this page. Its high school maths.

Optimized Solution

LCM

Least Common Divisor (LCM) of numbers A and B, is a number which is the least number divisible by both A & B. Moreover LCM (A, B, C) = LCM (LCM (A, B), C) and so on.

Relation between LCM and GCD

LCM(A,B) = (A * B)/GCD(A*B)

Recursive Euclid's algorithm for GCD

Base Condition

GCD(A, 0) = A

Recurrence Relation

GCD(A, B) = GCD (B, A mod B)

So I modified my code like this and it produced the solution within 1 second.

def GCD(M, N):
    while (N != 0):
        M, N = N, M % N
    return M

LCM = 1
for X in xrange(1, 21):
    LCM = (X * LCM)/GCD(X, LCM)
print LCM

Its been quite sometime since I did some coding. Last Sunday, one of the best friends of mine (Clement Lloyd) asked me if I can solve Project Euler's Problem 18. The problem name is Maximum path sum. Finally I got some time today and it is a simple Dynamic Programming Problem. The basic idea is to, keep on adding two adjacent elements of each row with the corresponding element in the previous row and keep the maximum of them. For example,

 8
1 2

The maximum of 8+1 and 8+2 would be 10 and 10 would take 8's place. So we keep on doing this till we reach the top. For the sample input

3
  7 4
 2 4 6
8 5 9 3

After first Iteration,

3
   7  4
 10 13 15

After second Iteration,

3
  20 19

After third Iteration,

23

Here is the solution which I used

import sys
sys.stdin  = open ("Input.txt")
sys.stdout = open ("Output.txt", "w")
Array = []
for line in sys.stdin: Array.append (map (int, line.split()))
Array.reverse()
temp_array = [0] * (len(Array) + 1)
for Row in Array:
 for i in xrange (len(Row)):
  temp_array[i] = Row[i] + max (temp_array[i], temp_array[i + 1])
print max (temp_array)

This solution will solve Project Euler's Problem 67 as well.