Posts from — March 2008
One step forward two steps back…
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:
#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 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:
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.
Let i be allowed to increment from 0 to . 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.
#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 & 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:
#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
New Tablet PC
Right, I am blogging from a brand new HP Tablet PC running Windows Vista - and I will continue to run Vista on it till I get a Ubuntu CD because I have exhausted all my bandwidth and can’t afford to download more ( We’ve got the world’s worst ISPs - they have no idea what their Linux authentication client looks like but they seemingly offer “24 x 7 Linux support” ).
Well, I am not too sure what to make of this PC but I can confidently say that AMDs run bloody hot - just too hot. For instance let me point out my ancient acer travelmate 4500 with 256 MB RAM and 1.6 GHz Intel Pentium M processor. The thing is as silent and the fan only goes whrrr… when I happen to watch flash videos in Mozilla IceWeasel ( from what I hastily gathered a few months ago, IceWeasel was FireFox without its icons but do correct me on this. IceWeasel is turning out to be a PITA since the last few updates ).
The keyboard’s OK and I can’t seem to be able to write anything with the pen but I am not too sure why I need to use it. I currently have this thing set at Maximum Battery life and the fan seems to have silenced.
Anyway, Vista seems to be ok but since I am practically logged in as root all the time on my Debian lappy, I have to get used to it asking the admin whether he really has any intention of changing his network settings ( please don’t comment on how dangerous it is to run as root all the time as those speeches happen to bore me. A true sysadmin always logs in as root ).
Setting up my favorite language on this pc:
Troubles all round.
Python’s website says that the amd64 package is to be used to install Python 2.5. I asked it to install the msi package and it told me something about wrong processor. Turns out that the package marked neither as w32 or 64 is suitable for installing it on my box. Oh well done.
The bright side is that I can finally see a powerful IDE in action ( I am using eclipse which doesn’t really run, let alone fly, on my acer Travelmate ).
I was looking for a tool like Glipper for Windows as I find it extremely hard to do anything with a clipboard that doesn’t have history. I found something called Ditto. It seems to be doing its job very well so I am quite OK with it.
I am still waiting for the Ubuntu CDs to arrive…. going by my experience during the the days of Feisty Fawn, the people at Launchpad take a good 6 weeks to send in those CDs.
BTW, I have taken up a few interesting pragmatic programming ideas and I will blog about them soon. Oh yeah, as my tweet says ( as of 4:04 pm IST ), I have received my rejection letter from MIT and I have scribbled all over it. To think, till a minute before the results, I was dreaming of working on the Semantic Web under prof. Tim Berners Lee and would have given two limbs to be there…… Oh stuff it.
If there’s one thing I suck at, it is ending blog posts, particularly posts like these.
March 27, 2008 2 Comments
mukt.in v2
Hi everyone, mukt.in v2 is just round the corner and we are really gearing up to make it one of the best tech events in Hyderabad. I am involved in the work for like 2 years in a row and it would be excellent if the FOSS community of Hyderabad took part in the proceedings. Volunteers can register here and you’ve got to introduce yourself to the community in our currently sparsely populated #mukt.in on the Freenode server or on irc.devnode.org.
We’ve got a sizable lot at the moment in our channel who are ready to help with the coordination during the pre-event and post-event periods. We are welcome to ideas from everyone and you can tell us about them on our wiki or in our channel on Freenode or Devnode and do not dare to talk about warez / trojans / sub7 and other worthless stuff that will most certainly earn you a ban and the wrath of a dozen community members.
Though we have a few dates and possible venues in mind, we want to be extremely sure that the conditions will increase the reach of our efforts and make it easy for people in the city to attend.
I will continue being the official voice of the movement and yes, mukt.in has its own blog somewhere on its site.
Please remember that mukt.in is not a FOSS fanboy’s paradise. It is an attempt to introduce newbies to the FOSS world. Ideas that will help us reach these goals are preferred and those involving M$ and darts are not.
Well, mukt.in awaits your ideas and help, Goodbye !
March 26, 2008 2 Comments
Number Triangles and Python Power
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:
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.
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:
#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
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.
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):
#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
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 ( 
) 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:
#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 .
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
Back on Track…
Let me bustle in with some code, I have had enough of pondering about MIT and lost opportunities and I want to continue doing what I always loved, coding. I am back to solving sums on Project Euler. Well, I am going to get back to web development now. I have stayed away from my loved tools for 5 whole days ! It is time to get back on track.
March 19, 2008 No Comments
