08.07.07
Posted in music, personal at 11:00 pm by danvk
Not being able to remember the name of a song whose instrumental part is stuck in your head. It’s maddening!
NPR plays these fifteen second instrumental clips from popular songs between segments on some shows. I’ve listened to enough music that I’m usually really good at picking out the song. But this one escapes me. And there’s no words, so I can’t search for it!
It brings the whole issue of literacy into focus for me. I don’t think twice about writing a thought down on paper, but when it’s a bit of music, I’m totally powerless. I can’t really reproduce it (it’s got some weird reverb effects going on) and I certainly can’t convey it to someone else. It’s a prisoner in my mind. All I can say is it’s got bass and syncopated, reverbed percussion, like Squarepusher’s “Iambic 5 Poetry“, only more upbeat.
The only way out: I have to listen to every song in my library until I find it. ARGH!!!
Update: Two days later, my fifth guess paid off! It was 0:15 through about 0:30 of “Warning Sign” off More Songs About Buildings and Food by the Talking Heads. For the record, my previous guesses were: Pixies, Pavement, R.E.M. and Boards of Canada.
Permalink
08.02.07
Posted in boggle, math at 8:45 pm by danvk
I’ve taken a several months break from my Boggle series, mostly because I think everyone got tired of it. I’m going to come back to it, but hopefully at a slower pace this time around.
Last time, we completed a board solver that could score 10,000 boards per second. So what to do with all that power? One option was to compute statistics on random boards. Another is to hunt for the holy grail of Boggle: the highest possible scoring Boggle board. The next few posts will be devoted to the search for this board.
Before undertaking any search, you need to get a feel for your search space. In our case, that’s the set of all 4×4 Boggle boards. How many are there? We can do a few back-of-the-envelope calculations.
To create a board, you roll 16 dice. Each has six possible letters on it, which gives 6^16 possibilities. These dice land in some permutation on the board, which gives another factor of 16!. Finally, a 4×4 board has eight-fold symmetry, which takes us down to 6^16 * 16! / 8 = 7.3e24 ≈ 2 ^ 83.
That’s one upper bound. But it assumed that all 6*16 = 96 symbols on the dice were unique. Obviously they’re not. After a roll, each of the 16 squares will have one of 26 letters on it. Divide by the symmetries, and you get 26 ^ 16 / 8 = 5e21 ≈ 2^72. Much better!
I haven’t been able to come up with any better upper bounds than these. The main flaw in the second approximation is that not all boards can be rolled with the sixteen dice that Hasbro provides. A board of all z’s or qu’s simply can’t occur. If we knew the probability that any sixteen character sequence could be rolled, this would give a true approximation of the number of distinct boards.
The easiest way to do this is with a computer program. It picks a random sequence of sixteen characters, checks whether this board can be rolled, and repeats several thousand times. I believe that checking whether a given board can be rolled is NP-Complete, but in this case the greedy approximation works quite well. I wrote a program (leave a comment if you want to see it) to do this, and processed one million 16-character sequences. Only 84,492 could be represented with the usual dice, or 8.4%. This gives a total of
(26 ^ 16 / 8) * (84,492 / 1,000,000) = 4.6e20 ≈ 2^69.
If you like confidence intervals, my sample size of one million boards gives a 95% confidence interval of [4.545e24, 4.666e24] for the total number of boards. Pretty good.
So, assuming we could enumerate all these boards quickly, how long would it take for our faster solver to find the best board? At 10k boards/sec, we’re looking at 4.5e16 seconds = 1.9 billion years! Clearly we need to do better.
Permalink