Entries from August 2008 ↓

Here is the first bit of code I’ve ever written at college (on my own computer though, I’ve concentration problems in the lab). I was solving problem 39 of the project euler problem set (and I am ashamed of my work). So the question is:

That gives us a dictionary whose (key, value) pairs are (perimeter, count). We need the max count and then pick the corresponding perimeter. I hence wrote a small function (which was very inefficient) to make the value the keys and the keys the values. I think it is the second time I used “lambda”:

and finally, to complete the script:

So, here are the rather shameful execution stats:

$ time python euler39.py
840

real    3m15.140s
user    0m0.046s
sys     0m0.015s

I suggest you throw a glance at the awesome header that http://desk.stinkpot.org:8080/blog/ has.

Happy Coding.

It is my first time in a large laboratory and I am loving the silence (although I don’t know how silent this place will be next week and I am also quite apprehensive about letting other majors roam about Computer Scientist territory) Ahem, I am in the Lawson CS Building, in an air conditioned Linux Lab where all the machines run Gentoo and after having created my home account, the first thing I did was get all my scripts (the ones I’ve got on this blog) over to my account. Then, I ran a very huge file full of words through my anagram detector and the results were astonishing, a record 1.93 seconds to parse over 10000 words and pick anagrams. Okay, that isn’t too fast but still, I love sitting amidst these machines and it gives me an exhilarating feeling like I am the owner of this place or something like that.

At purdue, I haven’t really done any memorable stuff aside from the fact that I met Daniel Tang in the same lab as I am now yesterday and I thoroughly enjoyed the two hours I spent talking to him.

You can view all the words I ran through my anagram generator at: http://www.speech.cs.cmu.edu/sphinx/models/hub4opensrc_jan2002/language_model.vocabulary

And I’ve uploaded the file containing the anagrams here.

Besides that, here are the courses I have taken:

CS 180 (Intro to java seemingly)

CS 191 (Foundations of Computing)

CS 182 (Turns out that 180 is a prerequisite to 182 but since I am super-smart…)

MATH 162 (A non-honors Calc 2 cuz the honors class doesn’t really operate in comfortable timings)

Psychology 120 (An intro psychology course. you know that Alonzo church attributed his invention, lambda calculus to his background in philosophy and how it helped him literally make a career out of mastering foundation theory which so many have failed at. This is not to say that I am anywhere as smart as Church but I still plan to be like him).

So, that makes 16 credits. Turns out that there are conflicting views about this foreign language thingy and I plan to test outta that soon (others think I shouldn’t). Anyway,this was my first post from Purdue University, West Lafayette, home of RCS, DTella, Debian and Shriphani Palakodety.

Oh and yes, my name is pronounced: Shree Funny(shriphani) Pala Code ate EEE(palakodety)

And now I am going to gloat over this empire of a lab that in completely in my control.

I was trying to solve the lexicographic permutation problem yesterday and out of plain curiosity, I decided to carry out some research on Wikipedia. I found this thing called factoradic which is a factorial-based number system. I conveniently used this thing to approach the solution and decided to work out how factoradic actually worked.

I decided to assign this thing called a rank to the permutation. So assuming that we have 9 digits [1, 2, 3, 4, 5, 6, 7, 8, 9] and that we need to find the 2092nd lexicographic permutation, we begin as follows.

Assume that the first digit is 1 (the smallest of the digits we have). There are 8 remaining digits. So, the maximum number starting with one should occupy the 40320th position ( 8! = 40320 ). Since 2092 < 40320, we know that the first digit is 1.

Now, we place the next smallest digit beside 1. We have 7 digits left and the maximum number whose 1st two digits are 1 and 2 occupies the position 5040. 2092 < 5040 and hence, we can confirm that the first two digits are 1 and 2 indeed. We now append 3 at the end of our current permutation. We have 6 other digits and hence the maximum number of numbers we can get with 123 in front is 720. Now, 2092 > 720 and this means that the number placed 2092 is greater than “123xxxxxx” where the “x” represent the digits we have not come across yet.

We now replace 3 by 4 (the permutation becomes “124xxxxxx”). The maximum number of numbers is 720 + 720 = 1440 which is still lesser than 2092 and we can safely replace 4 by 5 and the maximum position we get is 1440 + 720 = 2160 which is greater than 2092. So the permutation now looks like “125xxxxxx”.

Placing the minimum number from the remaining numbers after 5 in our permutation (the number is 3), we get something like “1253xxxxx”. The maximum rank is 1440 + 5! = 1440 + 120 = 1570. This falls short of 2092. So we replace 3 by 4, the maximum position is 1440 + 120 + 120 = 1690. Still short, put 6 there, the maximum position is 1810. Put 7 there, the rank becomes 1930. Put 8 there and the rank becomes 2050. Still short, replace 8 by 9 and 2170 is what we get. So our permutation now looks like “1259xxxxx”.

It should be straightforward from here on. Proceed in this fashion and you should end up at 125963784.

If you look at the above procedure and note down the number of replacements, you get the factoradic! It is as simple as that.

So, I whipped up a small script to get the factoradic:

First a straightforward factorial function:

Then, a function that greedily chooses the digit of the factoradic:

Finally a function that generates the entire factoradic:

Testing this on 2092 with an initial number containing 9 elements, we get:
[0,0,2,5,2,0,1,1,0]

Which leads us to the answer from my calculations.

I decided to solve the project euler problem (number 24) on lexicographic permutations using this algorithm and the factoradic I obtained was [2, 6, 6, 2, 5, 1, 2, 1, 1, 0] which leads us to 2783915460 which turned out to be the right answer.

You can obtain the factoradic generating script at http://shriphani.com/scripts/factoradic.py .

So, I’ve finally managed to write my first Knol. It was about the powerset construction script I once wrote. Enjoy: http://knol.google.com/k/shriphani-palakodety/powerset-construction-using-gray-code/2ktbww4a502kb/2#

I’ve caught incompetence on the part of news agencies yet again. In this article on the opening ceremony of the olympics by Xinhuanet News: http://news.xinhuanet.com/english/2008-08/09/content_9069055.htm. The article says that the ceremony was watched was 40 billion people. Dear Mr. Reporter, the population of this planet is just over 6.8 billion. So much for accuracy. 40 billion is like 33 billion people more than the population of this planet. Excellent stuff I say.

I am sure, the media is composed of a bunch of farts (except for Jon Stewart) and these nutjobs need a crash course in general awareness.

Alright, I know my previous attempt to describe this trip were horrible but I couldn’t prevent myself from writing about my promenade in the botanical gardens they have. There’s this thing called the orchidarium which has some excellent flowers. I got to see a pitcher plant, a few orchids and some variety of gingers (I never knew there were more in the family. I guess you can figure out how great at biology I am). So, here are the pitcher plants:

Then, I went to the Orchidarium and here are some of the best pictures I clicked (I think they are the best anyway):

I don’t know what these are, but they are the best pictures of the lot:

Then, I went for a walk in the ginger garden and I managed to click some excellent pics there:

I found these swans in this lake (tank, pool, lagoon? I don’t know):

Well, that is all. I hope you liked the pictures. The entire album can be viewed at http://picasaweb.google.com/shriphanip/SingaporeBotanicalGardens.

Ok, I’ve not written stuff like this for a very long time and since most of the educational boards have decided that I am a horrible speaker / writer etc (except ETS which conducts the TOEFL), I have little or no confidence on how to pull this off.

Right, I landed in Changi airport (I had no idea it was pronounced at Changee, I thought it was something like Chang-eye). I was rather surprised by the constant cleaning activity that employees were taking up. I discovered a bunch of keys lying on the ground, gave it to the Information guys and so on.

I was in Geylang for a week and from numerous sources I’ve figured that it is quite a shady location. We moved to Choa Chu Kang a week later and I find the MRT in Singapore to be quite decent.

There is this place in Singapore called Little India, its quite conspicuous courtesy the huge Tamil population (I am not exactly comfortable near these guys). There’s this place called the Mustafa Center which is HUGE !!!!. The thing is, I stepped out of the exit and all I could see around was Mustafa Jewellers, Mustafa Airlines (or was it Travels?) and Mustafa this, Mustafa that…. The guy (or his family, I don’t know if he’s alive) must be super-rich.

So, now I will come to the best experiences in Singapore: the aquarium in Sentosa and the botanical gardens (I don’t know where these are located and this makes me wonder whether I am the worst vacation-goer of all time).

I clicked a few pictures at the aquarium and these are some of my favorites:

This was a ray. Actually, you can touch these animals and it was the first time I touched an aquatic organism.

This is another pic I like a lot:

This animal is called a Dragon Moray Eel and I never knew something like this existed:

This is a glove crab:

This is the largest crab I’ve ever seen:

Here are some more pics of these crabs:

This thing is called a sea cow, at this stage I was in total awe as everything I saw was totally awesome and led me to think of life, the universe and everything:

I am sure everyone knows what this is:

It was feeding time and I managed to catch some of the action:

These guys feed these aquatic animals small fishes. What a sight!

I captured this ray feeding on a fish:

It was the first time I saw a jellyfish and it is rather cool:

The first time I saw symbiosis in action:

This is another weird creature, it is a dragon fish and mind you it looks exactly like a dragon:

You can actually view the entire album at http://picasaweb.google.com/shriphanip/SentosaAquarium

I am back from Singapore and it was a decent trip. I will be putting up pictures I clicked there soon. But first, while in S’pore, I implemented mergesort in Python.

Mergesort works by diving the given list down to groups of two, sorting them and merging these groups to get the sorted list.

So, the script that divides these lists into groups of two should be pretty straightforward:

Next, we need to somehow merge these sorted lists back. I decided to take a recursive approach:

• Suppose that two of the lists we’re merging are [x1, x2] and [y1, y2].
• If our final list can be called “final_list”, we add x1 or y1 whichever is the smaller value. Remove x1 or y1 from the list.
• We now have [x2] and [y1, y2] (I’m assuming that x1 is smaller). Repeat step 2 and keep doing it till one of the lists is reduced to [], the remaining part of the other list can be appended at the end of final_list because it is sorted already.

The next snippet recursively supplies lists to recurMerge() till a single list containing the sorted numbers is obtained.

You can download this mergesort implementation here.

Next comes the Collatz conjecture which goes something like this:

• Pick a number n.
• If n is even, n = n / 2.
• If n is odd, n = 3n + 1
• Go to step 2.

Do that with any n and you will always end up at 1. So, if n equals 13, the numbers resulting from applying the steps of the conjecture are:

• 40
• 20
• 10
• 5
• 16
• 8
• 4
• 2
• 1

See.

Project Euler has a question based on the Collatz Conjecture which asks you find that number under 1 million which takes the longest number of steps to get to 1.

Here is the code to solve that:

In 10 days, I will be at Purdue…. wow…. I just can’t believe how time flew and how I recovered from the MIT admissions result…. I guess I’ve moved on…..