08.11.07

Another advantage of biking to work

Posted in personal at 4:49 pm by danvk

I filled up on gas today for the first time in almost exactly a month.

It’s always struck me that miles per gallon is a terrible metric. I can increase my average miles per gallon by going on a long road trip with lots of highway driving. But I certainly haven’t saved any gas or money by doing so. The better metric is gallons per week, or maybe even dollars per week. By those standards, I’m using 2.6 gallons/week = $7.70/week at $3/gal. I suspect those are both quite low, whereas I only get just over 20 miles per gallon, a pretty piddling number. What are your numbers?

Permalink 4 Comments

08.07.07

What’s worse than a song stuck in your head?

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 2 Comments

08.02.07

How many Boggle boards are there?

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 8 Comments

07.21.07

Baffled by Beckham

Posted in news, sports, tv at 8:35 pm by danvk

I don’t get the wave of excitement about David Beckham coming to America to join the L.A. Galaxy and play in the MLS soccer league. ESPN was advertising this like mad. His wife, a former spice girl, is even getting her own reality show.

First thing I don’t get: How does an MLS team have $250 million to pay this guy? Does the entire league bring in that much money?

Second thing I don’t get: Why does anyone expect this to get American’s excited about soccer? Getting the World Cup in 1996 couldn’t do it, so how could one man? But there’s no arguing with the true believers.

The whole hysteria has made me very cynical today. If you want to get people excited about something, you don’t tell them how great it is or try to explain why they should be excited. No, you just act as though the rest of the country already is excited. I’ve often wondered if ESPN could pull this off with a lesser-known sport like disc golf. If they covered professional disc golf events on SportsCenter and brought in some talking heads for a “Disc Golf Tonight” show to analyze the week’s events, people would start to care about it.

Permalink 1 Comment

07.19.07

New iPod!

Posted in music, personal at 10:15 pm by danvk

Either through misplacement or theft, I lost the dano, my iPod nano, sometime last week. It’s OK. It was only a 1 GB nano, and I won it in a drawing. I paid nothing.

In fact, I last bought an iPod in April, 2004. Here’s what it looked like:

That red glow was totally trendy. It’s pretty wild to compare the technical specs on each. The prices were identical – $300 each. What’s 3+ years done to the iPod?

So all the specs have improved, and the thing’s gotten smaller. Who ever said the march of technology was a bad thing? I’m mostly excited about the video capabilities. If I throw some TV episodes on there, I can jog with my iPod, commercial-free!

Permalink 1 Comment