I am fascinated by problems that are easy to describe, and which appear simple when solved correctly, but where the implementation must contain surprising complexity in order to do what people expect.
Example: play a list of songs in a random order.
When I had to implement this feature for MotoGP, my first attempt was indeed simple:
Song PickRandomSong()
{
return allSongs[GetRandomNumber() % allSongs.Count];
}
A few days later, one of the testers filed a bug:
Symptom: when music is set to random, the same song is sometimes played twice in a row.
Expected: a different song should be chosen every time.
Dang it! But this tester was quite right. If I gave a stack of albums to a DJ and told him to play them in a random order, of course he would never play the same song twice in a row. As is often the case, when we said "random" we actually had more specific requirements than just a sequence of independent random selections.
My second attempt was to randomize the entire list of songs in one go, like shuffling a deck of cards as opposed to repeatedly rolling a dice:
Song PickRandomSong()
{
if (pendingSongs.Count == 0)
pendingSongs = ShuffleIntoRandomOrder(allSongs);
return pendingSongs.Dequeue();
}
This version has two desirable properties:
But it still has a flaw. After the entire list of songs has been played, we shuffle them again into a new random order, at which point it is possible the same song could be repeated. That could be avoided by weighting the random selection, biasing it to pick songs that have not recently been played (although care must be taken not to make the bias too strong, which could force the songs to always repeat in the exact same order). But I went with a simpler approach, far from mathematically elegant but good enough to get the job done:
Song PickRandomSong()
{
if (pendingSongs.Count == 0)
pendingSongs = ShuffleIntoRandomOrder(allSongs);
if (pendingSongs.Peek() == lastPlayedSong)
pendingSongs.Enqueue(pendingSongs.Dequeue());
return pendingSongs.Dequeue();
}