Greatest Hacker Ever

This story from slashdot is simply hilarious.

Personal projects and work

I'm wondering how do people find the energy to do open source projects while working? I have often felt that I do not have enough physical time to do what I want to do. Or maybe it is stamina? Often, after a very productive week comes one that is very much unproductive: I feel tired and I can't make any progress. I feel trapped in an iterative waterfall. In the evening I get home and I am tired. I can't stop thinking that I haven't done anything particularily interesting that day. So, even if I know it is wrong, I take a book with me in bed and start reading. It's wrong because I usually take a serious book that I ought to read with a pencil in my hand and certainly not while staying in bed. Lately it is either The Art of Computer Programming, or collected papers by Knuth or something else (The Art of Problem Solving, an abstract algebra textbook etc.) Anyway, I digress. It is something serious because I feel I must do something serious that day, at least in the evening. But I am so tired that I don't really read actively. Sure, I do absorb some information, but overall I'm wasting my time. The effect is that I fell asleep rather late, the next day I can barely wake up and I go to work feeling tired. At work I am much more than I'd like to be immersed in small, trivial, many problems. I don't know if I mentioned but I still feel tired. I do some work. Maybe it's writting in my notebook my thoughts about designing the next part of the application or maybe I write some code. After some time (two hours) I can't stop thinking: Hey, at least today do something interesting. And, instead of finding something interesting in my work, I shift (or should I say loose) my focus and search for interesting things in my inbox, in forums like the one at TopCoder or Devnet, or in blogs I'm subscribed to. Then I get back to work and continue with trivial stuff. Yuck. I realise that this multi-tasking made my productivity behave like 1/x going to infinity and I feel guilty. I must stay a bit more to do at least something today. I start to think (finally) of what I can do that is both interesting and valuable to my company. I find something. I make a plan. I look at the watch. Oh, my god: it is so late. I have no chance to do this well in one hour. It's probably better to start tommorow. And here we go again.

That's my worst possible day. I probably never did all that in one day until now. How does a good day look like then?

I wake up early: at 05:30. I do some workout, go outside with my dog and then eat something. Then I take some vitamins. It's 06:30. For one hour I read something interesting: from an article, from a textbook. I solve (or try to) solve a problem or two. I go to work. I try to solve a problem from TopCoder, preferably a medium problem from division 1 because that's where my "limit" stands. The easy problem is to easy and the hard one might take anywhere from one hour to a week. I do read a hard problem and keep it in the background for a few days. By now I feel full of energy. It is ten o'clock. I look at my todo list and make a plan for today. I try to make it realistic. It contains one or two things that without extra constraints (like old code) would take me three hours. Then I start working. I begin by thinking. I lay down what I think in my notebook. I read what I wrote and try to find a better solution. When I finally settle for something I start coding. I think hard about how to organize the code to make it fit well with what is already written. This means that I have to read the code that is related to my problem. Sometimes I find places where it can be improved. I do it: don't wait. Finally I code my piece. Then I test it. Does it work? If no then debug. Oh, and BTW, I try to write code for people to read not for machines to execute. As a result sometimes I write inefficient code if I can't see how to clearly code the more efficient version. I try to follow coding idioms so that the code has a certain uniformity but I'm not shy about breaking the rules if breaking them seems the right thing to do in a particular situation. The most important thing is to know that you are breaking the rules and only do it as a result of a conscient decision. Now it's already six o'clock. It took more than three hours but I also did more: I improved some old code, I found problems I didn't knew existed, I wrote the code more than once because I found an opportunity to improve it and now it looks rather nice. I'm proud of what I did and I feel good. I go home. Now I'm still full of energy. This morning I have read; now it's time to do. I take on a personal project or maybe a harder problem found in a book or on the internet (like Lars' contest problem). I work on it. I follow a cycle resembling very much the one at work: think it thru, do it, test it. It's nine o'clock and time for me to take a shower and go to sleep. Yeah, I feel great!

Now you've seen how my bad days look and how my good days look. The problem is that I seem to be incapable of breaking the good-bad-good-bad cycle! Distractions (like a late conference) can break a string of good days. Sometimes even a particularily good day can ruin my rythm because I say to myself "ok, now I deserve some more entertainment than the usual, let's stay up all night". The trasition from bad to good is almost invariably done thru a conscient effort to break the string of bad days.

Today is a bad day. I hope it is the last one in its string (although I do have a late conference today: why on earth is earth spherical? couldn't everybody have the same hour?).

I started to write this entry because I realised how insignificantly I have progressed in improving cfind. I have implemented a html parser and saw that performance plummeted. The format of the invereted index file required it to be constructed in-memory and then dumped in one step. This worked really fast while the swap memory wasn't used. Well, on my computer (192MB RAM) the addition of html tripped the balance. The indexing time went up from 1 minute to 20 minutes :(. So I have redesigned the format of the inverted index to allow efficient incremental updates. It's no rocket science: just good old B-trees. Not even their advanced cousins (B+ or B*). I have started to write the code and... that's where I am now. That's pathetic for almost two weeks! (That is about 10h since I have at most 1h per day to work on cfind). Ah, I have also designed a configuration file that will allow much control over the indexing process (including the ability to index archives, etc.). And... it is quite cool to have the OCaml manual, KDE help, and some html books indexed!

I hope I'll get over it and start a long string of good days really soon.

You know what else helps me have good days? Discussions with smart people. Yeah.. I know a couple so I'll try to do that. (The irony is that while I'm in a bad day I feel shy about talking to someone smart simply because I feel lousy and I don't feel up to the task.) It is amazing how bad habits support themselves. This seem to be a general rule. Many bad things in life are addictive: smoking, drinking, drugs, sex. Ok, strike the last one :)

Good Research

How does one do good research? I have recently read advices related to this question written by Dijkstra, Hamming and Peyton Jones.

Dijkstra has three advices:

1. Raise your quality standards as high as you can live with, avoid wasting your time on routine problems, and always try to work as closely as possible at the boundary of your abilities. Do this, because it is the only way of discovering how that boundary should be moved forward.
2. We all like our work to be socially relevant and scientifically sound. If we can find a topic satisfying both desires, we are lucky; if the two targets are in conflict with each other, let the requirement of scientific soundness prevail.
3. Never tackle a problem of which you can be pretty sure that (now or in the near future) it will be tackled by others who are, in relation to that problem, at least as competent and well-equipped as you.

Hamming says you should focus. First of all you should know what you want. If you decide that you want to be a first-class scientist then you should read to make sure what the important problems are, work hard on the important problems, work so hard that subconsciously you also do almost nothing else than work on those important problems. When you find out about some new result you should be able to instantly realise that it gives an attack on an important problem. Then start working. Don't waste time on things that don't make you a first-class scientist. Don't waste time fighting the system. Use it. Work on general problems: they are as hard as specific problems but more imporant. Make your results known, and make them readable. People don't want to read narrowly focused papers: they like to see the big picture so give them what they want. Better yet write books! But don't try to cover every detail of your field. People don't want to know every detail. Knowledge is increasing in mass at such a high rate that sedimenting the essentials is going to be more and more important. And, of course, you should work on important problems.

Peyton Jones writes about communicating your results. How to write a paper? How to give talk? One high-level advice he gives is that a paper should be written while doing research, not after doing research. Periodically trying to put what you know in a form readable by others will help you better understand what you know and so you'll make more progress. If you write your papers in this way you also have better chances of writing a good paper because you write everything while it is fresh in your mind. As to the specifics: learn by actively observing what sets apart papers you like from papers you don't like.

Which one is right? Dijkstra? Hamming? Jones? You guessed: all of them. You should probably pick the advices that work best for you and follow them.

But notice that there are some common threads in what these guys say. A good scientist (1) is hard working, (2) knows how to pick his problems and (3) presents well his results.

Functional C#

C# 2.0 looks better every time I look at it.

cfind 0.0.0

Today I have posted on the net the first version of cfind. Follow the link and you'll see what it is about. From time to time I'll use the code I write for cfind as a support for presenting various ideas in this blog.

Counting colorful objects: part 1

Suppose you have a set of objects and some classes of equivalence defined by symmetries. The Cauchy-Froebenius-Burnside Lemma gives a method of counting the classes of equivalence. If the original objects are made up of parts, each part having a color from a set then a simple version of Polya's enumeration theorem gives even a more precise method of counting the classes of equivalence.

(NOTE: I'll use only the name Burnside for the Lemma, although he's the only one who didn't have much to do with finding it. I'm also ignorant about what the whole Polya enumeration theorem says: I'll talk here only about a very simple case. See this for a few mathematical definitions -- not needed to read on.)

Let's make precise some terms used in the first paragraph. I'll denote the set of objects by A. Symmetries are functions s:A->A that form a group. In other words id is a symmetry, a composition of two symmetries is a symmetry and and each symmetry has an inverse symmetry (possibly itself). Let's say there are S symmetries; infinite cases are not of particular interest for the programmer. We can draw a directed graph with this. Its nodes are objects and there is an edge from x to y if and only if for some symmetry s(x)=y. You can check that from the symmetry group definition given above it follows that the graph can be partitioned into classes such that for each two objects in the same class there is an edge between them and there is no edge between different classes. Please take a moment to see that this is true.

Fixpoints are loops in this graph. Burnside essentially says that in each class there are exactly S loops, although the number of objects can be any divisor of S. So if we denote the number of classes by C, then counting all fixpoints yields CS. Counting fixpoints is usually done by counting fixpoints of one symmetry, then fixpoints of another symmetry, etc. For example, the number of fixpoints due to id is |A|. After we add up all this we get CS and then we get C dividing by the number of symmetries.

But why S fixpoints in each class? We'll prove this in two steps. First: The number of edges from x to y is a constant when x ranges over all members of the class. There is a symmetry s such that s(x)=y. Now observe that:

{s0, ..., sS-1} = {ss0, ..., ssS-1}

All the elements on the right hand side are distinct: s has an inverse. This means that the number of edges from x to y equals the number of y's loops: you get from x to y by following s(x) and then one of y's loops. Since symmetries are inversable we can also say that the number of edges is constant when x is fixed and y varies. The first statement says something about incoming edges in an object, while this second statement says something about outgoing edges of an object.

We can now see that for a certain class the number of edges from x to y is a constant. This is true event when x=y. Let's denote this constant by L. Since there are S outgoing edges from each object the number of objects in the class must be S/L; and each object has L loops therefore there are S loops in the class.

Let's see a very simple example. This actually came up in a TopCoder problem (but unfortunately I was unable to find it because I can't remember its name, and I remember the statement only vaguely). Consider some people that you line-up. Two line-ups are considered different if and only if the height profile is different. Moreover height profiles that can be obtained from one-another by reflexion are considered not different. In this problem there are two symmetries: id and reflexion. For some reason (I really can't remember the statement :( ) it was easy to find the number of fixpoints for each: a and b. So the answer is (a+b)/2. In this simple case one can reason in another way. If you don't care about reflexion then there are a configurations. But since there are b symmetric configurations it means we have counted the non-symmetric a-b ones twice. Hence the answer is b+(a-b)/2. This concludes the Burnside part. Polya's next.

Very often the objects we want to count have structure: they are made of parts and each part can be colored. Formally we can write A=KP, where K is the set of colors (the letter C is already taken by the word "class") and P is the set of parts. Thus each object can be written as (k0, ..., kP-1). For such objects every symmetry can be written as a permutation of the parts.

Let's see another very simple example. We may want to count in how many ways we can color a bracelet with six sectors in black and white (using exactly one color for each sector). Then we will probably want to consider rotations as symmetries: 123450, 234501, 345012, and so on. In cycle notation these are: (501234), (513)(402), (52)(41)(20). How many fixpoints do these symmetries have? Well, there are two for the first one: all white and all black; there are 4 for the second symmetry; there are 8 for the third. It is not hard to see that in general there are |K|h, where h is the number of cycles in the permutation representation of the symmetry. That doesn't mean it is obvious :)

The next posts in this series will contain some programs that actually count something using these ideas.

Random permutation

[Edit: For some reason this old post gets much traffic. Please note that Wikipedia has a much nicer presentation (but more verbose) of the Fisher–Yates shuffle.]

While browsing SGB I found a piece of code that looked especially nice. How would you generate a random permutation? That is, an array of size $n$ that contains a shuffle of $0$, $1$, $\ldots$, $n-1$. All orders should be equally probable. It's a nice exercise to try to do by yourself.

The solution in SGB takes linear time and is easy to code:

#include <stdlib.h>

int* random_permutation(int n) {
  int *p = malloc(n * sizeof(int));
  for (int i = 0; i < n; ++i) {
    int j = rand() % (i + 1);
    p[i] = p[j];
    p[j] = i;
  }
  return p;
}

Do you see why it works?

At (beginning of) step $i$ the array $p[0.\,.\, i-1]$ contains a permutation of the numbers $0.\,.\, i-1$. How can you construct in the array $p[0.\,.\,i]$ a permutation of $0..i$? Choose a random location to put $i$ and save the old value in that location at $p[i]$. If you think about it, this is pretty much a recursive solution. So, a nice problem is: how would you write it in a functional language?

PS: This implementation is not quite OK, because rand() % k is not uniformly distributed.