Tag vi (1)
vi, ngrams, hats
Mood: excited
Posted on 2007-05-18 09:42:00
Tags: vi ngrams
Words: 378
I found this great article on why vi is so awesome yesterday, which includes some handy tips that I didn't know. (my vi-fu is not particularly strong, although I do use it a lot) On the same site there's a wonderful graphical cheat sheet that I now have at my fingertips. (literally!)
Here's the first little applications using the Wikipedia n-grams - a simple interface to count the number of times a word shows up. Problems: it doesn't work in IE (sigh...I'll fix it soonish) and there's no progress indicator, so wait a minute after clicking "Submit". Edit: also, there are some crazy results: "zi" (1841) is more common than "carrie" (1361). Another sigh.
So there's this neat hat problem that's been making the rounds. n people (who are allowed to discuss strategy beforehand) each have either a red or blue hat put on (so you can see the other n-1 hats but not your own). Then, without communicating and simultaneously, each has to guess what color their hat is, or decline to guess. If at least one person guesses and all guesses are right, they all win; otherwise, they all lose. Here's an article that describes the problem and the optimal solution for 3 people. Apparently there are very good solutions for 2^n-1 people (3, 7, 15, ...), but the solution for 7 people, say, is way less elegant than the one for 3.
A coworker and I were talking about this problem yesterday and how to find the optimal solution. For the n person problem, a strategy for one person can be described in 2^(n-1) characters of "R" (guess red), "B" (guess blue), "N" (don't guess), since this covers all the cases of the hats that person can see. So, a complete strategy is 2^(n-1)*n such characters. It's pretty clear how to evaluate what percentage of the time a strategy will work (just try all 2^n possibilities), so if the number of strategies (3^(2^(n-1)*n)) is small enough you could just try everything. For the 7 people case this works out to 5.6*10^213 strategies - clearly too many! But you could use a genetic algorithm to breed solutions together based on their fitness.
So anyway, I may take a break from n-grams to code up some stuff relating to this.
This backup was done by LJBackup.