A Few More Math Sums; Combinatorics and Triangular Numbers
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:
#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 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
and
. In case, the number of terms is odd, the middle term is
. Using just these three I could get to the solution in no time. Here is the code:
#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
Python Variables
For a very long time, I was under the impression that variables in Python were like boxes and I could throw objects in them. So, according to me, if I wrote a piece of code that went:
>>> a = "Shriphani Palakodety" >>> print a Shriphani Palakodety
I used to think that there is a new box and I’ve thrown the string “Shriphani Palakodety” in there. If I do:
>>> a = "Shriphani Palakodety" >>> a = "Doofus" >>> print a Doofus
the general idea is that “Doofus” replaces “Shriphani Palakodety” in box “a”.
I was reading a mail on Edu-Sig (Python) and John Zelle ( he wrote an introductory computer science book ) mentioned that variables were not boxes but merely labels ( or tags, or “Sticky Notes” whatever you want to call them ). So, if I do something like:
>>>a = "Shriphani Palakodety"
All I am doing is sticking “Sticky Note” “”a”" on an object ( in this case, “Shriphani Palakodety” ). When I do something like:
>>>a = "Shriphani Palakodety" >>>a = "Doofus"
all I have done is move the Sticky Note “a” to “Doofus” and not remove “Shriphani Palakodety” from box “a” and put “Doofus” in it. Here is my idea of a verification:
>>>a = "Shriphani Palakodety" >>>print id(a) 10353360 >>>a = "Doofus" >>>print id(a) 10386016
So, if a was a box, its location shouldn’t have changed. But we observe that a’s location changes.
But the Sticky Note analogy can’t be entirely applied to variables. In real life, I can stick one sticky note over another and I can have three sticky notes such that one is stuck to the object and the other two are stuck to the sticky note itself. The figure below should illustrate that:
The above picture should depict the following Python code:
>>> x = y = z = 0 >>> x 0 >>> y 0 >>> z 0
So far so good. But let us say, I want to remove the Sticky-Note “y”. In real life that move would be represented by:
This means that “z” would be affected too which is not how it works in case of Python. Hence we come to the conclusion that a sticky note should be stuck only on the object and not on another sticky note.
OR
Python’s variables ( Sticky Notes ) come with a special kind of glue that isn’t sticky on material from which the sticky notes are made. So “x”, “y” and “z” should be stuck to the object but not to one another.
This completes what I learned from the Edu-Sig mailing list so far and I hope I joined this list earlier. John Zelle ( who wrote the textbook that MIT now uses for its introductory CS ) is there and I hope to keep learning more.
Well, I would love comments that will improve my knowledge but a comment on my bad GIMP skills will earn you spam and of course, I will call you names as well.
May 11, 2008 2 Comments
Hatred for Media, Other News
I have observed a trend in the way people greet me:
“You’ve got brothers or sisters ?”
“No. I am the only one.”
“Ah, no wonder you’re like this.”
Right, wtf is wrong with me? I suppose thats some logic that’s escaped me and no amount of intelligence I use will help me figure out the answer.
Anyway, here is a pic of the South Indian film-star Rajnikanth which neenaoffline (it is a guy) showed me: http://neenaoffline.one09.net/crap/rajnikanth.jpg.
Here is what I think of the guy/girl who created that:
Bloody, worthless, IQ-devoid, Creativity-Devoid imbecile, Creep of the First Water, Plagarist. Ripping off Chuck Norris jokes?
If that came from the third class Indian media, here is the best piece of advice I can come up with:
F**k off and die while you guys are at it. I hate the stupid media.
In case you haven’t noticed, most of the stuff Times Now can come up with about cricketers who don’t belong to India: “mind games”. Symonds has shouted at some player, “Mind Games”. Amazing, I have really seen BBC’s website being updated quicker with news about South Asia than Times Now.
Well, I am learning GUI programming ( wxPython as I was told that it looks excellent ) because I am trying to build something and as usual, no details will be divulged till I finish working on it.
I am a bit sad about the decline in posts on my blog but I will find something interesting to post soon. I have not even solved one problem in the last few days and clearly this needs to change. I will come back soon with loads of posts.
BTW, two people on my Twitter followers list, Abhinav and Prani have finished their BTech Degrees. Congrats, in 4 years I am going to get my BS degree too.
May 9, 2008 No Comments
Tech Shows, Nonsense, Code
I happened to read on the BBC that they’ve managed to do a lot of spooky stuff on facebook with an application ( social networking sites are shit anyway ) which brings me to my current topic:
Why do hosts of “Tech Shows” in India look like the channel’s CEO’s friend’s son who needs a job ?
I am seriously pissed by the nonsense that they air on Headlines Today. The nutcase who hosts the show has no idea what he’s bickering about and one common phrase I hear is “This is the next generation of <insert something that half the people won’t care about>”. I remember an episode where he tried to demonstrate a few appliances you could use to record media and he said, “You can save TV shows on this device in all formats like MP3 ( ! ), MPG, WMV etc”. I was stunned as to how the editing staff, the host and everyone else missed that.
Then comes the great “Times of India”, whose staff knows everything there is to be learned. I once read an article some hare-brained guy wrote on software design:
Let us pick a hypothetical case. Anitha bought a CD and she wanted to play it on her computer. But then she realized that there was no way to skip to the next song. This is bad design on the part of the CD (!)
Then of course, who can forget the paper’s coverage of the Mohd. Haneef case where they detailed a list of uses a 320 GB hard drive could offer.
A 320 GB hard disk is very large memory and can act as a Webserver as well
I was like WTF ? I mean why do these bozos take to writing this stuff if they know nothing whatsoever? Why don’t they verify what they are distributing across a few million households in the nation ?
By, the way, I’ve found a few sums from Berkeley’s ICPC qualifier rounds and they seem to have a few decent questions on string manipulation. I’ve asked them if I can post solutions to their problems on my blog and if it goes down well with them, then it’ll be great ! Else, there’s a lot more places I can look at for problems.
By the way, MIT walked away with second place at this year’s ICPC. Sources at the department of EECS have shown concern over whether next year will be as fruitful as this, considering that the programming heavyweight - Shriphani Palakodety won’t be arriving on the campus. When last asked, Shriphani wasn’t available for comment.
Goodbye anyway !
May 2, 2008 1 Comment
Prime Minister’s Office - Comic Sans ?
In the recent controversy in the Indian government, a politician seems to have abused his power by assigning tenders ( ? ) to his son. A news channel showed us a letter yesterday that seems to have originated from the Prime Minister’s office concerning this and as the newsreader shouted at the top of his voice ( I hate all Indian news channels because the readers either smile while delivering news like mass murder or a large number of deaths and they shout at the top of their voice. This is probably what they learned at a young age when their parents told them to speak at the top of their voice in a debate. I just hate them ). A surge of anger cruised through me when I saw that letter. IT WAS WRITTEN IN COMIC SANS !
Which professional uses comic sans and that too to draft a letter from the Prime Minister’s Office ? Comic sans is the least professional typeface on the planet and using it to draft formal letters ? I want the PMO to give a public apology for their careless use of typefaces.
Right, in some other news concerning what I love - programming, I have managed to solve another sum from the North America, East/Central 2007 problems set. This problem was about a combination lock with a few conditions as follows:
1. The lock dial must first be spun clockwise at least one full rotation, ending with the number x at the top (with no intervening counterclockwise turns). Note this could be accomplished with consecutive clockwise turns.
2. The lock must be turned counterclockwise until the number y appears at the top for the second time. Note this could be accomplished with consecutive counterclockwise turns (but no intervening clockwise turns).
3. The lock must then be turned clockwise until the number z appears on top, without going more than one full rotation. Note this could be accomplished with consecutive clockwise turns (but no intervening counterclockwise turns).
I wrote this to solve the question:
#ICPC Locks Problem:
#Author: Shriphani Palakodety
class Lock:
”‘The lock class’”
def __init__(self, dig_on_dial, combination, x_state=0, y_state=0, z_state=0):
self.dig_on_dial = dig_on_dial
self.x_state = x_state
self.y_state = y_state
self.z_state = z_state
self.combination = combination
self.xturns = 0
self.yturns = 0
self.zturns = 0
def __str__(self):
return "(" + str(self.x_state) + ", " + str(self.y_state) + ", " + str(self.z_state) + ")"
def x_turn(self):
”‘One Clockwise turn of the first ring of numbers’”
if self.x_state == 0:
self.x_state = self.dig_on_dial
self.xturns += 1
return self
else:
self.x_state -= 1
return self
def y_turn(self, no_of_turns):
”‘One Counter Clockwise turn’”
if self.y_state == self.dig_on_dial:
self.y_state = 0
self.yturns += 1
return self
else:
self.y_state += 1
return self
def z_turn(self):
”‘One clockwise turn’”
if self.z_state == 0:
self.z_state = self.dig_on_dial
self.zturns += 1
return self
else:
self.z_state -= 1
return self
def isClosed(self):
”‘Check if lock is closed’”
if self.xturns < 1 or self.yturns < 1 or self.zturns < 1:
return True
elif not self.x_state == self.combination[0] and self.y_state == self.combination[1] and self.z_state == self.combination[2]:
return True
else:
return False
Well, I’ll post more on my problem solving spree. I posted on Prof. Phil G’s forums for his advice and he is one cool professor. I really want to keep my personal whatnots away from my blog so that won’t find its way here.
May 1, 2008 No Comments
In Honor of Professor Tim Berners Lee
I want to dedicate this post to professor Tim Berners Lee, the creator of the World Wide Web for having given us an excellent invention. The web has been integral to my education, to my recreation and in general in all walks of life. It has helped me reach out to individuals across the globe and learn from them.
Enough said, Happy 15th Birthday W3 !
April 30, 2008 1 Comment
Roman Numerals - More Python
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.
#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
School Life’s Finished
So, I’ve managed a measly 94 % overall in the Intermediate Public Examinations and life’s good.
Well, I guess that in my life there was math, code and more math. I have realized that I get this excellent feeling when beautifully written Python code ( ever saw Python code in Komodo ? With the indentation, it looks beautiful ) performs primality tests, crunches out the Kaprekar / Collatz depths. By now, I think I think ( and a few people certainly think ) that I might be the best candidate to replace an academic and why not ? Most of the people I idolize are in academia and I want to be there as well.
I was browsing through the archives of Scott Aaronson’s Blog and I happened to read an entry where he ranted on CollegeBoard’s decision to remove the CS AP exam. He mentioned that he ate up everything there was to eat in that computer science course. That is true love for the subject. I had a similar experience with the book, “Post’s Machine” by V. A. Uspensky ( the third time I have mentioned it on my blog ). I just kept reading again and again. Talk about great books and that should be mentioned. I knew from then on that whatever the author was, I wanted to be too. Well, Scott’s got a lot going for him. He went to Cornell for Undergrad, went to Berkeley for Grad and is now teaching quantum computing at MIT.
On the other hand, I am going to a less “glorious” place, will probably never end up as a decent computer scientist as well. Well, I can dream on, can’t I?
I have met a lot of interesting people online. Well, I am shit at doing anything in real life, I can at least act as a tiger online, can’t I? 
I’ve got an interesting reading list and I plan to read quite a lot in this week. First, I’ve got to read “Programming Pearls” completely. So far, I’ve been reading pieces of it. Then comes a book called “A Gentle Introduction to Symbolic Programming”. It is an excellent book. I would recommend that as well ( but since I have assigned the n00b status to myself, it might not be that good a read for everyone else ). I’ve got a few other *legally free* ebooks and I’m going to finish reading them tomorrow.
Well, I am out of school ( officially ) now and not a lot has changed. People on the IRC server I first wandered to still call me “charlie” owing to the fact that I have managed to make a complete fool of myself a lot of times when I spoke on topics like “British History”, “Politics” and so on.
I am going to solve a few puzzles I have collected ( Math Puzzles in case you were wondering ). Will blog about them soon. Till next time, goodbye
April 28, 2008 No Comments
A Book on Algorithms.
My Guru and an individual in whose service, I am ready to spend the rest of my life, Mr./ Uncle / Dr. ( I don’t know what he wants to be called ) Prashanth Mohan recommended that I get this cool book entitled, “Programming Pearls” by “Jon Bentley”. I happen to like the warnings the author puts into his book such as, “Boring Material Ahead. Skip to section 4.4 if drowsiness strikes.”. I love the fact the the pseudocode is laid out in such an excellent fashion ( compared so some “pseudocode” I have seen… ). I jumped straight away to the section on “Searching” and realized that I was doing injustice to the writing capabilities of Jon Bentley ( which deserve a lot of respect ).
The only requirements of the book are knowing how to program in a high level language and thats it ! I would recommend that people pick this marvel of a book and add it to their collection ( although looking at the popularity this book seems to enjoy in programmer circles, you might already have it in your collection ).
Oh by the way, I am working on something extremely useless but its a top-secret mission of mine and I will write about it later.
Got involved in some fight with a bunch of “elites” from India’s “elite” engr. college ( no need to ask ). I happened to mention that I liked CS a lot and the discussion veered to something more unrelated to the field such as the methods institutions chose to fill their computer science classes. I mentioned that those who had programmed should be given first priority because the guys would have had *some* idea about process. I realized that I had made the biggest mistake of my life then and there. What followed is:
elite_guy: CS is not about coding. If you want to code in college, why not take those IT courses that are abundant in this nation.
Me: I know what CS is, I might not have a paper which certifies that I am a Computer Scientist, but I have a fairly good idea of what CS is.
elite_guy: CS is about math.
Ah, the classic statement. Like I never knew.
Me: I know it is about math but its basically imperative knowledge of math as opposed to declarative knowledge.
elite_guy: It is declarative knowledge
elite guy links me to SICP.
There are only two conclusions I could come to with that statement:
- The guy skimmed through the book, encountered the words declarative and imperative and felt happy enough to throw them in without knowing what Prof. Abelson intended to say.
- The guy was not interested in getting what he said, right. His aim was to somehow contradict me, even at the cost of speaking the right thing.
By the way elite_guy is just some stupid nick I could come up with. I didn’t want to stain his reputation by directly mentioning his name.
Got to go and work. Goodbye !
April 26, 2008 3 Comments
Sorting Algorithms - Python Implementations
Well, I have to admit, I don’t know how to begin 1/2 the posts on topics like these. Let me just point out that I was trying to arrange a list of words in dictionary order without using the sort() method available for lists in Python and since I am a lazy what-not, I only wrote a small bubblesort implementation the crux of which was:
alphas = string.uppercase
alpha_dict = {}
for i in range (1, 27):
alpha_dict[alphas[i-1]] = i
So, I created a dictionary which went like:
{”A”: 1, “B”: 2, “C”: 3 ………, “Z”: 26}
One of the words in the list which had to be sorted was “BABELFISH”. Using the dictionary, I created a list consisting of numbers corresponding to the letters which composed the word.
for char in word:
nums_list.append(str(alpha_dict[char]))
num = int(("").join(nums_list))
Then comes the actual bubblesort implementation. And when OpenBySource dissed me for sticking to something so inefficient, I decided I would go and read as much about sorting as I could and well, here is what I have learned.
First, the sorting algorithm that I always knew, BubbleSort. The algorithm is pretty simple. Begin at the first element, if this element is greater than the next element, swap their positions and proceed to the next element. This is how it is supposed to go. Here is a Python implementation:
#Author: Shriphani Palakodety
#Bubble Sort Algorithm Implementationimport copy
def sorter(num_list):
new_num_list = copy.copy(num_list)
n = 0
for i in range(len(num_list)-1):
if num_list[i] < num_list[i+1]:
continue
else:
num_list[i+1] = new_num_list[i]
num_list[i] = new_num_list[i+1]
new_num_list = copy.copy(num_list)
n += 1
return num_list, n
num_list = [2,7,1,5,8,6]
def checker(num_list):
while True:
sacred_tuple = sorter(num_list)
if sacred_tuple[1] != 0:
num_list = sacred_tuple[0]
else:
return sacred_tuple[0]
print checker(num_list)
I can see the question coming up ( if it isn’t, please don’t bother telling me ). “What is that checker() doing there ?”. The thing is that you can always keep running the sorter function. The checker stops the sorting process run by the sorter function when no sorting is performed when sorter(list_name) is run.
The next algorithm I encountered struck me as stupid. Every single kid must have used it. I am ashamed of myself to even have written this thing. Anyway, it is called the “Selection Sort” algorithm. You pick the least valued term in a list, assign it to the first position, from the remaining elements, pick the smallest number, put it at the second position and so on. Here is what I wrote ( and what every 5 year old out there could have written ):
#Author: Shriphani Palakodety
def selSort(list_name):
sorted_list = []
while True:
least_number = min(list_name)
sorted_list.append(least_number)
list_name.remove(least_number)
if len(list_name) == 0:
return sorted_list
break
else:
continue
unsorted_list = [2, 1, 8, 10, 12, 9, 42, 21]
print selSort(unsorted_list)
Actually the code displayed above is a cross between what is known as the “Insertion Sort” algorithm and the “Selection Sort” algorithm. In the insertion sort algorithm, the sorted list is built one element at a time.
The next algorithm I am going to cover is the “Merge Sort” algorithm. This algorithm works by diving a list into a number of sublists and then merging them back to get a sorted list.
Here is the merge function:
left_index, right_index = 0, 0
result = []
while left_index < len(left) and right_index < len(right):
if left[left_index] < right[right_index]:
result.append(left[left_index])
left_index = left_index + 1
else:
result.append(right[right_index])
right_index = right_index + 1
result += left[i:]
result += right[j:]
return result
And of course, now comes the splitter() function. I am too tired to explain wtf is going on.
if len(list_name) < 2:
return list
else:
middle = len(list_name) / 2
left = splitter(list_name[:middle])
right = splitter(list_name[middle:])
return merger(left, right)
Happy Coding.
April 17, 2008 No Comments
