Posts from — May 2008
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
