Weblog of an Aspiring Computer Scientist
Random header image... Refresh for more!

Category — Mathematics

First Look at the Big O Notation

by Shriphani

Well, it is the first time I’ve really had a serious look at the big O notation. I actually knew what it was about etc, but I never really delved into it.

I was debating whether I needed to shell out money on a Cormen + Leiserson work but then I came across the penultimate draft of “Algorithms” by Umesh Virkumar Vazirani, Sanjoy Dasgupta and Chris Papadimitriou (how do you pronounce it? ) on Vazirani’s homepage: http://www.cs.berkeley.edu/~vazirani/algorithms.html

I decided to pick the big O notation and after not reading it right the first three times, I finally began to get a hang of things and decided to solve the problems at the end of the big O notation chapter and here is how it went:

Question 1 is boring and simple algebra, so we skip it.

Question 2):

Show that if c is a positive real number, then g(n) = 1 + c + c2 + c3 + . . . . + cn is :

(a). ?(1) if c < 1

(b). ?(n) if c = n

(c). ?(cn) if c > 1

The solution is simple. We know that g(n) is the sum of a geometric sequence. When the common ratio is less than 1, we know that the value of g(n) becomes: 1 / (1 - c). Since this solution has clearly defined bounds, we know that g(n) when c < 1 is ?(1).

Next, when c = 1, we know that every single term is going to be 1 (1 raised to any power is 1). Hence, the computer steps required to approach the solution are:

  • (n-1) steps to go from c to cn and list them down as ones.
  • 1 step to perform the addition.

The result is ?(n).

The final problem can be solved by observing that:

Here a = 1 and r = c.

It can be observed that 1 - r in the denominator is a constant and can be removed. After carrying out a similar process in the numerator we are left with rn+1 . This can be written as r * rn and since r is a constant, we can safely assume that g(n) is ?(cn).

I actually liked the prologue (believe it or not, this was part of the prologue. I have to get to the first chapter).

Disclaimer: In this post, one image was copied off Wikipedia and the question solved can be found in the penultimate draft of the book, “Algorithms” by Umesh Virkumar Vazirani, C. H. Papadimitriou and Sanjoy Dasgupta.

Enjoy this treat, I am not too sure how much money you need to shell out for the final edition of the book.

June 17, 2008   No Comments

A Few More Math Sums; Combinatorics and Triangular Numbers

by Shriphani

I solved a couple of sums from the Project Euler archives and feel quite stupid since this is the first time in the last few weeks that a post has some code in it. I really ought to improve my efficiency. Well, the first sum I did was no. 42 and extremely special since it is the ultimate answer to the ultimate question. Well, the question was:

By converting each letter in a word to a number corresponding to its alphabetical position and adding these values we form a word value. For example, the word value for SKY is 19 + 11 + 25 = 55 = t10. If the word value is a triangle number then we shall call the word a triangle word.

Using words.txt (right click and ‘Save Link/Target As…’), a 16K text file containing nearly two-thousand common English words, how many are triangle words?

So, I whipped up a solution in no time. I was only hindered when it came to figuring out whether a number was a perfect square or not and I was trying to explore better algorithms that mine which involved squaring the integral part of the square root of type float obtained by using math.sqrt(num) and squaring this integral part to see if we return to the original number again. I couldn’t really find a decent solution so I just implemented my own answer:

#!/usr/bin/env python
#Author: Shriphani Palakodety
#Example 42, Project Euler Archives.

import string
import math

def makeAlphaDict():
        alpha_dict = {}
        for i in range(len(string.uppercase)):
                alpha_dict[string.uppercase[i]] = i + 1
        return alpha_dict

alpha_dict = makeAlphaDict()

def checkTriangular(word):
        word_sum = 0
        for char in word:
                if char == ‘"’:
                        continue
                else:
                        word_sum += alpha_dict[char]
        discrmnt = 8 * word_sum + 1
        if checkOdd(int(math.sqrt(discrmnt))) == True and checkPerfSquare(discrmnt) == True:
                return True
        else:
                return False
       
def checkPerfSquare(num):
        probable = int(math.sqrt(num))
        if probable * probable == num:
                return True
        else:
                return False

def checkOdd(num):
        if num % 2 == 0:
                return False
        else:
                return True

input = open("words.txt", "r")
words_list = input.readlines()[0].split(",")
input.close()
word_count = 0

for word in words_list:
        print word
        if checkTriangular(word) == True:
                word_count += 1
        else:
                continue

print word_count
 

Thats the first question. The next problem I solved was #53;

How many values of nCr, for 1 ? n ? 100, are greater than one-million?

Since \binom {n} {r} is a symmetric function about the middle term while r increases from 0 to n, I figured out that once we hit upon one (n, r) pair, without computing the rest, we could obtain the other values of r for a fixed value of n that crossed the million mark. Remember, if n is even, the number of terms is odd and if n is odd, number of terms is even. In case the number of terms is even, the middle terms are n / 2 and n / 2 1. In case, the number of terms is odd, the middle term is (n 1) / 2. Using just these three I could get to the solution in no time. Here is the code:

#!/usr/bin/env python
#Author: Shriphani Palakodety
#Project Euler Problem 53

def factorial(number):
        if number == 0 or number == 1:
                return 1
        else:
                return number * factorial(number - 1)

def combination(n, r):
        n_fact = factorial(n)
        r_fact = factorial(r)
        n_r_fact = factorial(n - r)

        return n_fact / (r_fact * n_r_fact)

def midTerm(n):
        if n % 2 == 0:
                mid_term_1 = n / 2
                return mid_term_1
        else:
                mid_term = (n + 1) / 2
                return mid_term

comb_num = 0

def countComb(n, r):
        ”‘If a particular value is found to be greater than 0,
           it adds a certain number to comb_sum using properties of
           combinatorics.’”
       
        if n % 2 != 0:
                num_to_add = 2 * (n / 2 - r + 1)
                return num_to_add
       
        else:
                num_to_add = 2 * ((n+1)/2 - r) + 1
                return num_to_add

for n in range(101):
        for r in range(midTerm(n) + 1):
                if combination(n, r) > 1000000:
                        comb_num += countComb(n, r)
                        break
                else:
                        continue

print comb_num

Thats the solution. And of course, who’ll forget the time taken to get to the solution.

shriphani@psp-laptop:~/project_euler$ time python ex53.py
4075

real    0m1.116s
user    0m0.140s
sys     0m0.024s
shriphani@psp-laptop:~/project_euler$

Till the next time I put up a post, HAPPY CODING !

May 18, 2008   No Comments

Roman Numerals - More Python

by Shriphani

Since I love Python and since 90 % of those online judges won’t allow me to use Python to submit my solutions, I have to contend with writing the script and hoping it is right. I am now solving a few ICPC sums from last year and I absolutely love them. I first picked the North America, East/Central Problem Set and found this question on roman numerals. Basically subtracting two supplied roman numbers. Guess what this reminded me of, Claude Shannon of course ! Shannon designed a box that used only roman numbers. All hail God Shannon - the best the world had to offer. Well, I hacked up a simple solution in a few seconds. It looks horrible but who cares.

#!/usr/bin/env python
#Author: Shriphani Palakodety
#Roman Numerals Problem.
#Solution to:
#ICPC North America East-Central Problem1

#Roman to Decimal dictionary

rom2dec_dict = {"I":1, "V":5, "X":10, "L":50, "C":100, "D":500, "M":1000}

def romToDec(roman_string):
    ”‘Convert from Roman to Decimal’”
    #Move from right to left.
    number_dec = 0
    i = len(roman_string) - 1
    if i % 2 != 0:
        while i > 0:
            if rom2dec_dict[roman_string[i]] > rom2dec_dict[roman_string[i-1]]:
                number_dec += rom2dec_dict[roman_string[i]] - rom2dec_dict[roman_string[i-1]]
                i = i - 2    
                continue
            else:
                number_dec += rom2dec_dict[roman_string[i]] + rom2dec_dict[roman_string[i-1]]
                i = i - 2
                continue
    else:
        while i > 1:
            if rom2dec_dict[roman_string[i]] > rom2dec_dict[roman_string[i-1]]:
                number_dec +- rom2dec_dict[roman_string[i]] - rom2dec_dict[roman_string[i-1]]
                i = i - 2
                continue
            else:
                number_dec += rom2dec_dict[roman_string[i]] + rom2dec_dict[roman_string[i-1]]
                i = i - 2
                continue
        number_dec += rom2dec_dict[roman_string[0]]
    return number_dec

 

There, first ICPC problem. I would love to crunch this set in this week. Some problems seem tough and I really would love to solve them all. I found another interesting problem on circular combination locks. I am still thinking about that one and I hope I can solve it tomorrow.

Well, I am just loving the freedom. Happy Coding! :)

April 29, 2008   No Comments

Prime numbers, Miller-Rabin

by Shriphani

I was looking at a few interesting algorithms to figure out whether a given number was a prime, all because I wanted the fastest solutions possible while solving project euler sums involving prime numbers. And after that session, the sum is still not over and might never be as I have gotten around to post on this blog, the stuff I’ve gathered.The AKS algorithm is of extreme academic importance but has horrible speeds and hence is of no use to me whose main aim to get prime number with utter ease.

I then looked at the Miller-Rabin algorithm and then moved to try out an implementation on my own. I cheated by trying to look at implementations on the cookbook and understood nothing. So it was back to me to figure out something. The algorithm goes like this:

To check if “n” is prime, “n” should obviously be 2 or odd. Forget 2, because if you don’t, I will call you names ( and who needs miller-rabin to prove if 2 is prime ? ).

Since n is odd, n-1 is even. Try expressing n - 1 as {2}^{s}.d. It seems relatively simple. Here is the code to do that:

#!/usr/bin/python

#Miller-Rabin Primality Test.

#Author: Shriphani Palakodety a.k.a PSP#Now comes one of the world’s fastest primality tests:

def twoPower(n):

 factors = []

 s = 0

 while n > 0:

        if n % 2 == 0:

                factors.append(0)

                n = n / 2

                s += 1

        else:

                factors.append(n)

                d = n

                break

 return s, d

Once that is done, we need to generate a random number which lies in the range \left[1, n - 1\right]. Here is the code to do that:

#!/usr/bin/pythonfrom random import randint

def randGen(n):
 return randint(1, n)

Ok, I agree there was no need for that snippet. Let us move on anyway. The crux of this algorithm lies in the following statement:

if a^d \not\equiv 1\ \bmod\ n and a^{{2^r}d}\ \not\equiv -1 \bmod\ n for all r in the range [0, s - 1\ ] then return composite.

Well, this is quite easy to implement in Python:

#!/usr/bin/env python

#Modulo Check
def moduloCheck(rand_int, odd_no, n):

 if rand_int ** odd_no == 1 % n:

        for i in range(0, n):

                if rand_int ** ( ( 2**i) * odd_no ) == -1 % n:

                        continue

                else:

                        break

                        return "Prime"

 else:

        return "Prime"

 return "Composite"

Now comes the trouble:

number = 73n = twoPower(number- 1)[0]

odd_no = twoPower(number - 1)[1]

rand_int = randGen(n - 1)

print moduloCheck(rand_int, odd_no, n)

Have a look at what I get:

shriphani@psp-laptop:~/project_euler$ python miller_rabin.py

Prime

shriphani@psp-laptop:~/project_euler$ python miller_rabin.py

Prime

shriphani@psp-laptop:~/project_euler$ python miller_rabin.py

Prime

shriphani@psp-laptop:~/project_euler$ python miller_rabin.py

Composite

BOOM !

The trick to avoiding such problems is to just run the moduloCheck function as many times as possible and if we get more Primes than Composites, then the number is Prime, else Composite :)

I then decided to create a parameter “k” which would determine the number of times the moduloCheck function should run. Then I implemented a counter to check the frequency of the strings - “Prime” and “Composite” thrown out by the script. Here is the code:

k = randint(1, n)

def freqCheck(k, odd_no, n):
        freq_list = []
        for i in range(0, k):
                freq_list.append(moduloCheck(randGen(n - 1), odd_no, n))
        if freq_list.count("Prime") > freq_list.count("Composite"):
                return "Prime"
        else:
                return "Composite"

So, the entire script looks like this: http://shriphani.com/scripts/miller-rabin.html

April 9, 2008   No Comments

One step forward two steps back…

by Shriphani

I am very sorry Stanford - you won’t have the honor to call yourself the breeding place of the next biggest character in the history of Computer Science. I feel extremely sorry to being you this bad news.

Anyway, in a bout of stupidity (induced by an intense feeling to optimize a stupid script of no apparent worth) I ended up rewriting problem 16 on projecteuler.net using memoization. Well, I guess I am going to be a computer scientist right ?

Well, have a look at it:

#!/usr/bin/env python
#Author: Shriphani Palakodety a.k.a PSP

cache = {}
cache[ 2 ** 0] = 1

def cachePopulator():
        for i in range(1, 1001):
                if cache.has_key(2 ** (i - 1)):
                        cache[2 ** i]= 2 * cache[2 ** (i-1)]

cachePopulator()

cachestring = str(cache[2 ** 1000])
cache_string_list = [ int(x) for x in cachestring ]
print sum(cache_string_list)

Next comes a dose of creativity. This is my algorithm to generate the powerset of a given set. A powerset of a set is basically the set whose elements are subsets of a given set. Now, if the cardinal number of a set is “n”, then it should have {2}^{n} subsets. How? Simple combinatrics.

Subsets can be considered as selections. From a set of n elements, we end up selecting 0, 1, 2 ….. n elements. Hence we have something of the form:

{^n}C{_0}} + {^n}C{_1} + {^n}C{_2} + .......... + {^n}C{_n} = 2{^n}

Now, how do we obtain the powerset of a given set ? I came up with an idea to use binary numbers to get to the answer. Consider that we have a set composed of elements a, b and c.
S =<br /> \begin{Bmatrix}<br /> a, b, c &<br /> \end{Bmatrix}

Let i be allowed to increment from 0 to {2}^{n}. Now observe the magic of the binary system:

i binary Element(s)
0 000 -
1 001 c
2 010 b

and so on. So, depending on the location of 1 in the binary number, we accordingly pick an element from the set and get to the solution. Well, here is the code needed to generate a list containing the digits of the corresponding binary number as over here we need to obtain the indices of 1.

#!/usr/bin/env python
#Convert a number in the decimal system to the binary system
#file: decimaltobinary.py

def converter(i, num_length):
        b = ”
        while i > 0:
                j = i &amp; 1
                b = str(j) + b
                i >>=  1
        bin_string = [ int(x) for x in str(b)]
        reqd_bin_string = [0] * ( num_length - len(bin_string) ) + bin_string
        return reqd_bin_string

Then comes the code to generate the powerset:

#!/usr/bin/env python
#Author: Shriphani Palakodety a.k.a PSP
#file: powerset.py

import decimaltobinary

def powerSetMaker(set_name):
        powerset = []
        for i in range(len(set_name)):
                bin_list = decimaltobinary.converter(i)
                subset = []
                for n in range(len(bin_list)):
                        if bin_list[n] == 1:
                                subset.append(set)
                        else:
                                continue
                powerset.append(subset)
        return powerset

That should do it :)

Ah right, owing to the mess my life has become ( getting shafted by colleges everywhere ) I have been incapable of responding to comments. I apologize and promise that I will get to making this blog the best in the world soon :)

HAPPY CODING !

March 31, 2008   No Comments

Number Triangles and Python Power

by Shriphani

Its time for an overdose of Math!

I encountered this problem in the Project Euler archives which involved a small triangle of numbers in which I had to find the maximum sum from top to bottom. The solution - brute force.

Wrong,

The main rule I follow and I believe most aspiring computer scientists follow involves the easiest way to solve a sum. Brute force doesn’t cut it as the best method to solve this sum when you are confronted with a grid as large as the one presented in question 67 (click here to see the mammoth of a triangle ).

I was trying to figure out the answer to that question and I came up with this idea, to move up from the base of the triangle. Here is how it works:

1. Consider the following triangle:

 

Triangle of numbers

 

2. Replace each number in the second line with the number which happens to be the maximum of the numbers obtained

by adding that number to the two numbers adjacent to it in the line below. In this case, the pair giving the maximum

is represented in red.

Sum representation

Proceed in the same fashion and you will end up with 23 as the final number. 23 is the maximum sum obtained when going from top to bottom and this method is a quick way of getting to the answer.

 

Here is the code for the triangle provided in question 18:

 

 

#!/usr/bin/env python
#Author: Shriphani Palakodety a.k.a P.S.P

triangle = """\
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23"""

def triangleMaker(triangle):
        triangle_list = [ line.split() for line in triangle.splitlines() ]
        return triangle_list

#start from the lowermost line and work your way up.

def getMax(triangle):
        #pick the second last line of the triangle
        our_line = triangle[-2]
        for i in range(len(our_line)):
                new_num_list = []
                new_num_list.append(int(triangle[-2][i]) + int(triangle[-1][i]))
                new_num_list.append(int(triangle[-2][i]) + int(triangle[-1][i + 1]))
                triangle[-2][i] = str(max(new_num_list))
        triangle.pop()
        return triangle

tri_grid = triangleMaker(triangle)
for i in range(len(tri_grid) - 1):
        tri_grid = getMax(tri_grid)

print tri_grid

For an idea on how effective this solution is, question 67 took 0.18 seconds to solve.

Happy coding :)

March 24, 2008   2 Comments

Grid Magic

by Shriphani

Well, a new sum on ProjectEuler enabled me to test my meager math and Python skills. This one however wasn’t as much of a Python challenge as it was a math challenge. Let me introduce you to problem 15 of the Project Euler problem set. The problem describes the number of ways you can move across a 2 x 2 grid.

Grid

The solution turned out to be dead simple if you regard the possible movements as follows:

  • A horizontal move is represented by x
  • A vertical move is represented by y

Consider the first block in the above picture. The bold line can be represented as;

x x y y

using our notation.

The bold line in the second block can be represented as;

x y x y

This is but a permuation of the letters we get in the first series.

So we get that the length of any path from the starting point to the last point in a grid of order “n” is 2n units and compulsorily contains “n” horizontal moves and “n” vertical moves. Our problem is limited to dividing 2n possible moves into n horizontal and n vertical moves. The answer as known to any mathematician with brains is:

2nCn

In case of a 20 x 20 grid that becomes: “Out of 40, choose 20″. Therefore: 40C20. The required code ( I am sure there isn’t any need, but I am too lazy to find my calc and punch in the numbers):

#!/usr/bin/env python
#Author: Shriphani Palakodety a.k.a PSP

def factorial(n):
        if n == 0 or n == 1:
                return 1
        else:
                return n * factorial(n - 1)

def no_of_paths(order):
        return (factorial(order * 2)) / (factorial(order)) ** 2

print no_of_paths(20)

Happy Coding :)

March 24, 2008   2 Comments

Math and Python - the combination rocks

by Shriphani

As I sit admiring the rain (which I believe has come a bit too early in the year thanks to global warming), I am churning out code. I just love seeing functions. Each function performing an individual action and all of these interacting to achieve the objective of the program - I LOVE IT !!!

I wrote this script the day before MIT’s results were announced and due to a mistake committed by the admissions office ( :D ) which had me in a bad mood for sometime, this script stayed underground.

The objective of this script was to solve question 22 of the Project Euler problem set ( the greatest set of problems ever ).

Here is the solution:

#!/usr/bin/env python

#Author: Shriphani Palakodety a.k.a PSP

import string

f = open("names.txt", "r")

names_list = f.read().split(‘","’)

names_list[0] = names_list[0][1:]

names_list[-1] = names_list[-1][0:6]

names_list.sort() #Arrange in alphabetical order.

def alphaDict():

 alphadict = {}

 alphastring = string.uppercase

 for char in alphastring:

       alphadict[char] = alphastring.find(char) + 1

 return alphadict

def scorer(word):

 ”‘Make a score for each word’”

 alphadict = alphaDict()

 scores_list = []

 for letter in word:

       scores_list.append(alphadict[letter])

 return sum(scores_list)

scores_list = []

for name in names_list:

 scores_list.append((names_list.index(name) + 1) * scorer(name))

print sum(scores_list)

That particular solution took 0.83 seconds which I guess is ok considering what one of my brute force attempts on the collatz theorem took, 52 seconds. Well, I am happy with 0.83 seconds and I request and welcome everyone else to provide better solutions.

Well, here is the solution to question number 11 .

import numpy

from operator import mulnumbers = ”‘\

08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08

49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00

81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65

52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91

22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80

24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50

32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70

67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21

24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72

21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95

78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92

16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57

86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58

19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40

04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66

88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69

04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36

20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16

20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54

01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48′”

def gridMaker(numbers):

 grid = {}

 index = 0

 for numstring in numbers.splitlines():

       bummer = [ int(char) for char in numstring.split() ]

       grid[index] = bummer

       index += 1

 return grid

grid = gridMaker(numbers)

def horizontalProd(index, grid):

 ”‘The structural unit of this function is a list’”

 prods_list = []

 num_list = grid[index]

 for num_index in range(0, len(num_list) - 3):

       prods = reduce(mul, num_list[num_index:num_index+4])

       prods_list.append(prods)

 return max(prods_list)

def verticalProd(vertical_index, grid):

 ”‘The structural unit of this function is a vertical column i.e. dict[index][0]

    for index between 0 and 20′”

 prods_list = []

 num_list = []

 for index in range(0, 20):

       num_list.append(grid[index][vertical_index])

 for num_index in range(0, len(num_list) -3):

       prods = reduce(mul, num_list[num_index:num_index+4])

       prods_list.append(prods)

 return max(prods_list)

def prepareMatrix(grid):

 num_matrix = []

 for i in range(0, 20):

       num_matrix.append(grid[i])

 return num_matrix

def diagonalProd(grid_key, grid_value, grid):

 base_matrix = numpy.mat(prepareMatrix(grid))

 sub_matrix = base_matrix[grid_key:grid_key+4, grid_value:grid_value+4]

 return reduce(mul, numpy.diagonal(sub_matrix))

def prepareInvertMatrix(grid):

 num_matrix = []

 for i in range(0, 20):

       num_list = grid[i]

       num_list.reverse()

       num_matrix.append(num_list)

 return numpy.mat(num_matrix)

def inverseDiagonalProd(grid_key, grid_value, grid):

 base_matrix = prepareInvertMatrix(grid)

 sub_matrix = base_matrix[grid_key:grid_key+4, grid_value:grid_value+4]

 return reduce(mul, numpy.diagonal(sub_matrix))

def maxHorProdList(grid):

 prods_list = []

 for i in range(0, 17):

       prods_list.append(horizontalProd(i, grid))

 return prods_list

def maxVerProdList(grid):

 prods_list = []

 for i in range(0, 17):

       prods_list.append(verticalProd(i, grid))

 return prods_list

def maxDiagProdList(grid):

 prods_list = []

 for i1 in range(0, 17):

       for i2 in range(0, 17):

               prods_list.append(diagonalProd(i1, i2, grid))

 return prods_list

def maxInvertDiagProdList(grid):

 prods_list = []

 for i1 in range(0, 17):

       for i2 in range(0, 17):

               prods_list.append(inverseDiagonalProd(i1, i2, grid))

 return prods_list

print max[maxHorProdList(grid) + maxVerProdList(grid) + maxDiagProdList(grid) + maxInvertDiagProdList(grid)]

This solution is “big” and I know it. But I wanted to get a basic hang of numpy and found that this sum would be an excellent opportunity to do so. Well, happy coding :)

March 22, 2008   No Comments

Update…

by Shriphani

Lots of stuff happening in the past week. Let me begin with that news which should come as a blow to storage enthusiasts. The HD-DVD format is going forever. Toshiba says it will no longer create HD-DVD players/records. Now, I liked the HD-DVD format for its ECMAScript support. Well thats over. Then the US blew up a satellite, China’s pissed and wants to know more about the mission, my board exams are getting closer ( bleagh! ). Anyway, here is an update on my “work” in the past week.

Oh BTW, while solving a question related to the Fibonacci sequence, I found a supercool formula - the Binet’s formula. Let the greatest integer function be represented by “[]”

f(x) = [x]

let F represent the Fibonacci sequence. The Binet’s formula states that

F(n) = [{(1 + sqrt(5))^n}-{(1-sqrt(5))^n} / (2^n * sqrt(5))]

There ! Now you can solve that Fibonacci problem in the project euler archives.

I solved another sum. Here is the question:

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n). If d(a) = b and d(b) = a, where a ? b, then a and b are an amicable pair and each of a and b are called amicable numbers.For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220. Evaluate the sum of all the amicable numbers under 10000.

Here is the solution:

#!/usr/bin/env python
#Amicable numbers

def makeFactors(number):
        factor_list = []
        if number % 2 == 0:
                for i in range(1, number / 2 + 1):
                        if number % i == 0:
                                factor_list.append(i)
                        else:
                                continue
        else:
                for i in range(1, (number + 1)/2):
                        if number % i == 0:
                                factor_list.append(i)
                        else:
                                continue
        return factor_list

def checkAmicable(number):
        factor_list = makeFactors(number)
        factor_sum = sum(factor_list)
        new_factor_list = makeFactors(factor_sum)
        new_factor_sum = sum(new_factor_list)
        if new_factor_sum == number and factor_sum != number:
                return True
        else:
                return False

amicable_list = []
for number in range(0, 10001):
        if checkAmicable(number):
                amicable_list.append(number)
        else:
                continue

print sum(amicable_list)

Thats it for now, goodbye !

February 22, 2008   1 Comment

Why me worry ?…..

by Shriphani

Shaun ( of #computers on irc.icq.net ) once mentioned that children are quite clever till people teach them things. I am currently in such a state. I’ve got ignorant people, ignorant about their ignorance, all around me and what’s more, this super-brain society feels that it is up to them to set me on the path to success. When you set their skills to test, they confuse between Perl and vim and feel that programming includes just taking things into consideration and typing instructions in English. I am just cheesed off by this lot. What do I do when I am in am in this towering temper ? I code. Well, let us begin this technical dose guaranteed to bring calm and quiet to the oppressed mind.

During my search for good number theory questions ( not already included in the Project Euler problem archive ). I discovered Kaprekar’s brilliant work.

Observe the following numbers:

(a). 197:

Arrange the digits of 197 in increasing order and you get 179. Reverse this and you get 971. 971-179 = 792. Do the same with 792.

972-279 = 693

963-369 = 594

954-459 = 495

STOP ! 495 is the kaprekar constant for 3 digit numbers. Pick any 3 digit number and carry out the aforementioned process. You will end up at 495. This is called the Kaprekar method. I hacked up a Python script to measure the depth of the Kaprekar process. It supports 3 digit numbers only atm. I will hack it up a bit more to figure out the kaprekar constant and then calculate the depth. So fellow code enthusiasts, enjoy !;

#!/usr/bin/python 

#Kaprekar process length

from copy import copy 

kaprekar_constant = 495 

def kapLength(number): 

        difference = numAppend(number)[2] 

        i = 0 

        while difference != kaprekar_constant: 

                i = i + 1 

                difference = numAppend(difference)[2] 

        else: 

                return i 

def numAppend(number): 

        numlist = [] 

        for char in str(number): 

                numlist.append(char) 

        numlist.sort() 

        new_numlist = copy(numlist) 

        new_numlist.reverse() 

        smallest_number = int("".join(numlist)) 

        greatest_number = int("".join(new_numlist)) 

        difference = greatest_number - smallest_number 

        return (smallest_number, greatest_number, difference) 

print kapLength(197)

Change the number in the last argument to try out new numbers. I will write about something I have stumbled upon in the world of semantic filesystems tomorrow.

February 9, 2008   1 Comment

← Previous Entries