08.08.09
Posted in boggle, math, programming at 10:35 am by danvk
Why is finding the highest-scoring Boggle board so difficult? It’s because there are so many boards to consider: 2^72 for the 4×4 case and 2^40 for the 3×3 case. At 10,000 boards/second the former corresponds to about 2 billion years of compute time, and the latter just two years. Just enumerating all 2^72 boards would take over 100,000 years.
So we have to come up with a technique that doesn’t involve looking at every single board. And I’ve come up with just such a method! This is the “exciting news” I alluded to in the last post.
Here’s the general technique:
- Find a very high-scoring board (maybe this way)
- Consider a large class of boards
- Come up with an upper bound on the highest score achieved by any board in the class.
- If it’s lower than the score in step #1, we can eliminate all the boards in the class. If it’s not, subdivide the class and repeat step #2 with each subclass.
Classes of Boards
By “class of boards”, I mean something like this:
| {a,e,i,o,u} |
{a,e,i,o,u} |
r |
| {b,c,d,f,g,h} |
a |
t |
| d |
e |
{r,s,t,v} |
The squares that contain a set of letters can take on any of those letters. So this board is part of that class:
and so is this:
All told, there are 5 * 5 * 6 * 4 = 600 boards that are part of this class, each with its own score. Other fun classes of boards include “boards with only vowels” (1,953,125 members) and “boards with only consonants” (794,280,046,581 members).
Follow me past the fold for more…
Read the rest of this entry »
Permalink
08.04.09
Posted in boggle at 6:18 pm by danvk
There is exciting news to report in the land of Boggle!
Last we spoke about Boggle, we used Simulated Annealing to get at the question “what is the highest-scoring Boggle board?”
We found a board with 3625 points on it this way. It would have been nice to say that it was the best of all possible boards, but that would have been too rash. While it is a very good board and I have never seen a higher-scoring one, that doesn’t mean there isn’t one out there. Maybe I’ve just been looking in the wrong places.
To prove that the 3625-pointer is the best board, we’d need to show that every other board scores fewer points. In a previous post, I estimated that there were 2^69 possible boggle boards. At 10,000 boards/second, this would take 1.9 billion years of compute time!
When you run up against a computationally intractable problem, there are a few standard ways to deal with it:
- Give up.
- Come up with a brilliant new algorithm to solve the problem more quickly.
- Solve a simpler problem.
Option 1 is the easiest. Option 2 is the hardest. And option 3 is the compromise we’ll be taking for the next few danvk.org boggle posts. Our simpler problem today: 3×3 boggle.
If we drop seven letters (4×4 – 3×3 = 7), we’re left with only 26^9 / 8 ≅ 2^39 boards to consider. If we can achieve 10,000 boards/sec, this would be just over two years’ worth of computation. That’s still a lot, but it’s much more reasonable than 1.9 billion years!
I believe I have solved the 3×3 boggle problem using an approach that is only slightly more clever than this. I used simulated annealing to find very high-scoring 3×3 boards. This was the best one I found, along with its 4×4 best board buddy:
It’s worth noting that the optimal 3×3 board has a 2×3 region in common with the 3625 point 4×4 board.
In the next post we’ll talk about how I showed that this board was higher-scoring than all 2^39 others in significantly less than two years (it took one day). As a teaser, I’ve included all the 3×3 boards with more than 500 points worth of words below the fold.
Read the rest of this entry »
Permalink
06.14.09
Posted in san francisco at 3:26 pm by danvk
The analogy struck me when I saw the de Young Tower from the aptly-named Grand View Park. Maybe the resemblance isn’t quite so clear as it was in my mind.
Also, arcologies? Anyone want to hazard a guess what fraction of people familiar with the term learned about it from SimCity 2000? I’m going to say 99.
Permalink
05.25.09
Posted in personal, san francisco at 11:44 am by danvk
While walking around my block with an out-of-town friend the other day, I found myself pointing out all the restaurants I had never been to. How could I be so remiss? Part of it is the sheer number of food places: 40 within a three block radius.
Here they are. I’ve been to the bolded places. The links go to Yelp.
Within one block (3/4):
- Cafe du Soleil
- rotee (Indian)
- S&W Market
- Two Jack’s Seafood
Within two blocks (8/13):
- Chili Cha Cha’s Thai Food
- Cu Co’s Restaurant
- Estela’s Fresh Sandwiches
- Indian Oven
- Kate’s Kitchen
- Lo-Cost Meat and Fish Market
- Metro’s Caffe
- Nickie’s (bar)
- Roland’s Bakery
- Squat & Gobble
- Thep-Phnom (Thai)
- Three Twins Ice Cream
- Volare Pizza
Within three blocks (12/23):
- Abe’s Market
- Bistro St. Germaine
- Burger Meister
- Cafe International
- Castro Coffee
- Golden Natural Foods
- Hanabi Japanese Restaurant
- La Carreta Taqueria
- Love ‘n Haight Deli & Cafe
- Mad Dog in the Fog
- Memphis Minnie’s
- Molotov’s (bar)
- Mythic Pizza
- Naan and Chutney
- Noc-Noc (bar)
- O’Looney’s Market
- PeaCock Lounge (bar)
- Raja Cuisine
- Rosamunde (“the sausage place”)
- Tacqueria El Castillito
- Toronado (bar)
- Uva Enoteca
- Whole Foods Co
Now that I have a list, there’s no excuses!
Permalink
03.03.09
Posted in personal, web at 10:50 am by danvk
As danvk.org regulars know, I recently joined Twitter. I had a great experience with it last weekend and came away feeling as though I’d “seen the future”.
I ran into Tyler Hinman last weekend at a friend’s Oscars party. Tyler’s claim to fame was that he’d won the American Crosssword Puzzle Tournament the previous four years, starting in 2005 when the movie Wordplay was filmed. Tyler played a major role in that movie.
Tyler told us that he’d be trying to make it five times in a row the next weekend. So, come the weekend, I was curious to see how he did.
After one day of competition, the official results page showed Tyler in fourth with one puzzle left before the finals. If you’ve seen Wordplay, you know that fourth place is a bad spot to find yourself. Only the top three finishers qualify for the finals.
On Sunday, the standard news sources weren’t helpful. A crossword tournament is not exactly front-page material. The official tournament page hadn’t been updated. Even the bloggers would take another few days to tell the story. So I tried Twitter.
I searched for #acpt and saw these two results:
Not only did I immediately get the bit of news I wanted, I also got to watch it on video!
I’m not saying this is a great way to get news in general. A crossword puzzle tournament is more likely draw the twitterers than most events. But just consider that this would not have been possible even one year ago.
Permalink
« Previous Page — « Previous entries
Next entries » — Next Page »
