I just wrote (for school) a Haskell compiler from Kernel Esterel to the Lustre programming language. It's called kesterel2lustre (how original). You can have a look at the README if you need more information.

Not sure it's worth a blog post, but just in case someone needs this...

Do you know about "^W"? This is Control-W, a readline binding to delete the previous word. For quite some time, I knew that you could use it like ^H to show off your geekiness^W^W^W^Wpretend that words are erased in text. Then, I noticed that someone I know used it regularly, started to imitate them, and now I'm heavily dependent on it.

The thing is that ^W is not intended to be faster because it's less keypresses than multiple ^H's. It's faster because you can use it to erase an unknown number of letters, up to the beginning of the word.

Let me explain. When you touch type, you usually notice it when you fumbled. Sometimes, you can even press backspace the right number of times and correct your mistake without even having to look or think, because you know the exact wrong sequence that you typed and how to fix it. In some cases, however, you fumbled, but don't know what the exact state of the text is, and you have to look consciously at what you typed to erase the right number of letters until you can start over. Yes, the burden of hitting multiple ^H's until the mistake is fixed seems slight, especially since you're usually looking at the text anyway, but I find it more distracting than when I subconsciously fix typos with backspace. There are also those cases where you're not looking at the screen, or when you don't have any feedback on what you're doing (crappy connections...).

Contrast this with ^W. The key is that your mistakes are usually restricted to one word. With ^W, you don't have to think about the current state of the text : you can just press ^W and start over from the current word. Small trick, but a useful one, and I discovered it quite late...

Another one of those standard small tools which should exist but that I couldn't find... nlsplit is a tool to split natural language text in chunks at reasonable language boundaries. The program takes as argument a maximal size for chunks, reads stdin and produces chunks smaller than the maximal size on stdout.

If you want more info, see the README. You can also retrieve the C source directly.

If you've played Portal, you must be acquainted with GLaDOS and her very odd way of speaking, which sounds like TTS but was actually recorded by an actress (Ellen McLain) and digitally edited.

It turns out that there is a common free TTS program, espeak, packaged for Ubuntu and Debian, which is not a very convincing imitation of a human, but which sounds a bit like GLaDOS:

echo "Hello, and, again, welcome to the Aperture Science " \
  "Computer-aided Enrichment Center" |
  espeak -ven+f3 -m --stdout -p 60 -s 180 |
  oggenc -q1 - > espeak1.ogg

In my opinion, though, the most striking thing about GLaDOS's speech is its seemingly random pitch. My point is that we can approximate this by adding some SSML markup.

echo "Hello, and, again, welcome to the Aperture Science " \
  "Computer-aided Enrichment Center" |
  for a in `cat`; do
    V=$(((($RANDOM) % 100) - 50))
    echo -n "<prosody pitch=\"+$V\">$a</prosody> " |
      sed 's/+-/-/' 
  done |
  espeak -ven+f3 -m --stdout -p 60 -s 180 |
  oggenc -q1 - > espeak2.ogg

Approximating Still alive using this technique is left as an exercise to the reader. ;-)

A pompous title, because the underlying math isn't that complicated, but still, here we go.

The game of Russian roulette is played as follows:

We have a revolver with a p-round cylinder loaded with only one round. The cylinder is spun so that the round lies in a position which is assumed to be random. We have n players numbered 0, 1, 2, ..., n-1 standing in a circle. Each player, starting at player 0, will try to shoot themself in the head. If the player dies, the game stops. If the player misses, they pass the revolver to the next player (player n-1 passes to player 0).

There are two main variants: either players don't spin the cylinder when they give it to the next player, or they spin it (and we assume that it puts the bullet in a new random position chosen uniformly at random and independently from other draws).

Players spin

In this version, the cylinder is spun before passing the revolver. This is equivalent to each player rolling a p-sided die, or drawing from an urn with replacement. In this section, we will write f = 1/p for brevity.

Here is my take at solving this one. Let us denote by q_i the probability that player i is the one to die. Notice that this game is memoryless in the sense that if a certain number k of rounds have been played without anyone dying, then the situation is exactly the same as in the beginning of the game (except the revolver might be in someone else's hands). For this reason, we have q_i = (1 - f)·q_i-1 for all i: a player's odds of dying are that of the previous player times the probability of the revolver not firing. It isn't very hard to see that this is true for the first round, and the observation about the game being memoryless explains why this continues to be true.

Now, we use the fact that the probabilities sum to one, ie. q₀ + q₁ + ⋯ + q_n-1 = 1. This means that q₀ + q₀(1 - f) + ⋯ + q₀(1 - f)^n-1, which is q₀((1 - f)⁰ + (1 - f)¹ + ⋯ + (1 - f)^n-1), is equal to 1. Using the geometric series formulae, we can write that q₀(1 - (1 - f)ⁿ) = 1 - (1 - f) = f. Now that we know q₀ and can express q_i as a function of q₀, we have the general solution:

q_i = f(1 - f)ⁱ / (1 - (1 - f)ⁿ)

Notice that for an (countable) infinite number of players, the denominator becomes 1, and the formula q_i = f(1 - f)ⁱ. This makes sense: for an infinite number of players, each players gets the revolver at most once, and their odds of dying is the odds that each of the previous players survived times the odds that they die. Also note that, obviously, the game is not fair, and that for i < j, q_i > q_j. Of course, the game is more unfair for larger values of f (because the penalty for being among the first to play is higher if the probability of dying is higher and the number of expected rounds is lower).

Players don't spin

This would be the version where players draw from an urn without replacement.

At first glance, this might seem more complicated, because the game isn't memoryless anymore. You might be tempted to think of it as a tree: either player 1 dies with probability 1/p, or player 2 dies with probability (1 - 1/p) · (1/(p-1)) = 1/p (interesting!), or player 3 dies with probability (1 - 1/p) · (1 - 1/(p-1)) · (1/(p-2)) = 1/p (very interesting!), and a pattern seems to emerge...

Well, this is not at all the right way to think about the problem, and I am ashamed to admit that I did not see why before someone explained to me. The right way to see things is that when you're spinning the cylinder at the beginning, you are effectively choosing which player will die, uniformly at random. If p ≤ n, then it is now obvious that the first p players have probability 1/p of dying and the others have probability 0. If p > n, then it's harder to write but not much more complicated: writing p = u n + v (where u is the quotient and v the remainder), we have q_i = (u + 1)/p for i < v and q_i = u/p for i ≥ v.

As a consequence, this variant is fair if (and only if) p is a multiple of n.