Keepin’ static like wool fabric since 2006
It’s just entered totality, check it out if you’re awake. It’s shocking how many lights my apartment complex still has on at 3 AM. Although this is an unusually long eclipse, it’s going to be a brief one for me. Lunar eclipses are way cooler when they happen at a more reasonable time.
The Stanley Fish blog on the NY Times has a post looking at Hillary’s potential running mates this morning. This kind of piece does a lot to reinforce the “Hillary is inevitable” meme. I’m tempted to buy into it myself. Hillary’s been running the best campaign so far, and she’s been effective in all the debates. (Except for that quip about lobbyists representing the real America.)
At the same time, I know that the Hillary machine is trying to project a sense of inevitability. It’s all part of their plan, and I don’t want to buy into it.
A couple reactions to the article I linked to: Read the rest of this entry »
I’ve always wished I could link to Wikipedia on this blog by typing “[[Tiger Woods]]”, just like I would in a Wikipedia article. I even considered writing a WordPress plugin to do just that. Thanks to the WikipediaLink plugin by pixelbath, I don’t have to. It already works great. Mad props!
Novak Djokovic upset Rafael Nadal in the Rogers Masters semifinals this evening, making up for the Wimbledon semifinals earlier this year. It sets up an interesting final with Roger Federer tomorrow afternoon (noon PST) in Montreal. Fed’s never lost to Djokovic before, (he’s 4-0) but they haven’t played since Djokovic cracked the top ten earlier this year. This is the final I was rooting for at Wimbledon earlier this year, as those elusive “astute readers of danvk.org” will recall. I’m calling Fed two sets. I don’t think Djokovic can beat him.
This week and next also mark one of the more brain-dead stretches of the ATP tour. The top players are required to enter all nine Masters Series events, which are just one notch below the Grand Slams. Tomorrow is the Rogers Masters final, and on Monday the Cincinnati Masters begins. There’s not even a one day break, but the players are all required to enter both. This makes for some really exhausted players and surprising results at the Cincy Masters. Last year Federer won the Rogers Masters, but lost to #21 Andy Murray in early round play the next week. For a sense of what an aberration this was, Fed only lost to two players last year: Nadal and Andy Murray. It’s absurd that the ATP continues to schedule the Masters Series in this way.
Update: Novak made me eat my words, winning 7-6(2), 2-6, 7-6(2). Fed came quite close to winning the first set: he botched five set points before Djokovic sent it to the ‘breaker. Mad props to him, I underestimated him. He’ll be fun to watch at the US Open this fall.
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?
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.
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.
Design by Beccary and Weblogs.us
·
XHTML
·
CSS