SPOJ Best Solutions for The Double Helix

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

Project Euler - 15 - Lattice paths

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]

Project Euler - 14 - Longest Collatz sequence - memoization

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

Project Euler - Problem 5 - Smallest multiple

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

Project Euler - Problem 18, Problem 67 - Maximum path sum

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.

Ubuntu 13.04 - Execute scripts on double click

After upgrading to Ubuntu 13.04, I was facing this problem. I was not able to execute any script file just by double clicking on it, even though it has execute permission. Then I figured out, how to fix this problem.

I opened the file explorer Files. Pressed Alt+F10 and selected Preferences. It showed something like this.



In the Behavior tab, I selected Ask each time and closed it. By default, it was in View executable text files when they are opened. Now whenever I double click on a shell script, it will ask me what to do. If you want to straight away execute the script, select the first option Run executable text files when they are opened.

gitclean - a git clean wrapper

Last week, I had to make some changes to the code. I was keep on making changes but forgot to add them to git and to take backup. When I am almost done I wanted to commit and before committing I checked the changed files with this.

git status

it listed all the files which have got changed and few other temporary files and compiled binaries, which I don't want to keep in the repository. So I did

git clean -qfxd

That's it. This cleared everything, including my newly added untracked files and all my hardwork went in vain. Then I read about git clean here and got to know what I could have done to avoid this problem. And then I was thinking, if there is a script which would remind me that, the following files will also be removed and only when I say `yes` it would go ahead and clean the repository. So I made this gitclean script. This would collect the status of the files with git status --porcelain and then compare it with the list of extensions specified in the config file. If they match, it would report to the user and ask his consent before beginning to clean.

Github

Github Repository : https://github.com/thefourtheye/gitclean.

Installation

To install this script, please follow these steps

wget https://raw.github.com/thefourtheye/gitclean/master/gitclean
chmod 544 gitclean
./gitclean install

1. The first step will download the script from github
2. The second step changes the permissions of the file to 544
3. The third step installs the script. Basically, it copies itself to the user's home directory and creates the gitclean alias in the $HOME/.bashrc file
   

Configuration

Users can specify the extensions, gitclean has to report in the $HOME/.gitclean_extenstions file. By default, gitclean will report the extension-less files and directories as well. But, it does not report the empty directory. My .gitclean_extenstions file has the following items.

cpp
js

Sample Runs

1. With no files changed

~/gitclean$ gitclean

Interesting Extensions found in [/home/thefourtheye/.gitclean_extensions] are as follows
[cpp]
[js]

0 interesting files found, in total 0 files. Cleaning was not done. Exiting...
~/gitclean$ 

2. With one interesting file [Test.js]

~/gitclean$ gitclean

Interesting Extensions found in [/home/thefourtheye/.gitclean_extensions] are as follows
[cpp]
[js]

Test.js

1 interesting files found, in total 1 files. Are you sure want to clean? [y/Y - Yes, Any other Key - No] : n
Cleaning was not done. Exiting...
~/gitclean$ 

3. With one interesting file [Test.js] and a non-empty directory

~/gitclean$ gitclean

Interesting Extensions found in [/home/thefourtheye/.gitclean_extensions] are as follows
[cpp]
[js]

Test.js
Test/

2 interesting files found, in total 2 files. Are you sure want to clean? [y/Y - Yes, Any other Key - No] : y
Cleaning...

~/gitclean$ 

4. With one interesting file [Test.js] and a non-empty directory and a non-interesting file [Test.txt]

~/gitclean$ gitclean

Interesting Extensions found in [/home/thefourtheye/.gitclean_extensions] are as follows
[cpp]
[js]

Test.js
Test/

2 interesting files found, in total 3 files. Are you sure want to clean? [y/Y - Yes, Any other Key - No] : y
Cleaning...

~/gitclean$