Friday, July 31, 2009

Smalltalk's become() in python

Posting this here because blogger's sucky comment system won't let me post formatted code in a comment on this post. This is an implementation of Smalltalk's become() in python. It will not work on strings, int etc. but otherwise is identical

#! /usr/bin/python def become(a, b): swap(a, b, "__class__") swap(a, b, "__dict__") def swap(a, b, attr): tmp = getattr(a, attr) setattr(a, attr, getattr(b, attr)) setattr(b, attr, tmp) class Animal(object): def __init__(self, name): self.name = name class Dog(Animal): def Cry(self): print "%s says woof" % self.name class Sheep(Animal): def Cry(self): print "%s says baa" % self.name a = Dog("rover") b = Sheep("shaun") c = a a.Cry() c.Cry() become(a, b) a.Cry() c.Cry()
This prints
rover says woof rover says woof shaun says baa shaun says baa
Note how both a and c are now sheep. To do the same thing in perl you monkey around with bless and resetting all the hash entries, it's a bit uglier.

Wednesday, July 29, 2009

Answer to 1 of the 2 puzzles and a new puzzle.

I take Nicole's comment to mean she gives up, although Nicole, it turns out that your comment has a deep relation to this problem and raises a new question.

To find out on average how many items are left unmoved by a random permutation, you can consider every permutation and how many are left unmoved by each, add them all up and divide by the total number of permutations. To avoid mathsy notations I'm going to write a tiny program that calculates this total.

total = 0 # Check what every permutation does to every item, if it leaves it # in the same place then increase the total by 1 for p in perms: for i in 1..N: if p(i) == i: total = total + 1
Now, here's the key to this problem - swap the loops. The final answer stays the same we just end up adding things up in a different order.
total = 0 # Check what every permutation does to every item, if it leaves it # in the same place then increase the total by 1 for i in 1..N: for p in perms: if p(i) == i: total = total + 1
So now what we're doing is looping over the items and counting how many permutations leave that item in place and that's something we can work out. The number of permutations that fix a given item is (N-1)! (where ! is factorial) because when you fix 1 item, you're left with N-1 other items which you move around however you like so it's just the number of permutations of N-1 items which is (N-1)!. So now the code can be just
total = 0 # Check what every permutation does to every item, if it leaves it # in the same place then increase the total by 1 for i in 1..N: total = total + (N-1)!
which is just adding (N-1)! N times. That's N x (N-1)! which is just N!. Now we have to divide that by the total number of permutations which is also N! to get an average of 1.

You can also get to this answer by drawing a grid with all the permutations across the top and all the items down the side. You put a tick in a cell in the grid if the permutation on the top leaves the item on the left unmoved. Now count the ticks. Doing it column by column is hard but doing it row by row is easy because there will be (N-1)! ticks in each row.

So the conclusion is that if you do a perfect shuffle of a deck of cards, on average 1 card will end up in the same places as before.

So where does Nicole's comment come in? I knew it was Ralph Wiggum who said it but I couldn't remember the context turns out. I found it here. It's

  Lisa: Hey Ralph, want to come with me and Alison to play "Anagrams"?
Alison: We take proper names and rearrange the letters to form a
        description of that person.
 Ralph: My cat's breath smells like cat food.
and what we've just shown is that given a random anagram, you'd expect 1 letter on average to end up in the same place - well kind of, that's only true if there are no repeated letters. I hadn't thought of this in terms of anagrams before and that adds a nice twist in terms of repeated letters. Thanks Nicole!

So the new puzzle is - given a string written in scrabble tiles (it can have repeated letters), if you mess up the tiles and make a new string at random, how many letters do you expect to be in the same place as before?

Sunday, July 26, 2009

Saturday, July 25, 2009

Pat, "the cope" Gallagher: dishonest or just an idiot?

In his letter to the Indo calling for a "yes" to Lisbon, Pat defends our membership of the Euro. I think there are upsides and downsides to it but for Pat even the downsides are upsides. He happily points out that

The eurozone has ensured that billions of euro have been made available to Irish banks via the operation of the European Central Bank.
and that
As a member of the eurozone, Ireland has benefited from very low interest rates, notwithstanding the very difficult economic situation that faces us.

Surely he must know that these 2 things are the root cause of our massive bubble. The IMF and even Brian Lenihan have said as much. So if he knows this, then to list them as upsides of eurozone membership is basically swearing that black is white and up is down. There is of course that odd "notwithstanding the very difficult economic situation that faces us" which seems to be an attempt to cover all angles - as if to say "yes I know this is what fucked up the country but still it was great craic at the time."

Of course maybe he truly disagrees with me and thinks that the oversupply of cheap credit was an entirely positive thing and we should be thankful for it. This would certainly be compatible with FF's policy over the last decade, right up the point where the shit hit the fan.

Thursday, July 16, 2009

2 fun maths puzzles

I guess they're fun because I figured them out! If there's anyone actually reading this, post your solutions in the comments. If I get any responses I'll post solutions and if I don't, I might not.

  1. On average, given a random permutation of N items, how many elements do we expect to stay put? E.g. if N=3 there are only 6 perumtations, 1 leaves all 3 in place, 3 leave 1 in place and 2 shift all of them (left or right). So that's (1*3 + 3*1) / 6 = 1.
  2. On average, given a random function from 1..N->1..N which may or may not be injective or surjective (that is there may be X and Y such that f(X) = F(Y) and there maybe be a Z such that f(X) != Z for any X), how many elements do we expect to stay put - f(X)=X? E.g. if N=2 there are 4 possible functions, f(X) = X, f(X) = 1, f(X) = 2 and f(X) = 3-X. These fix 2, 1, 1 and 0 elements respectively. So on average that's (2+1+1)/4 = 1 but what about larger N?