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.

4 comments

Comment from wonderjess:
2007-05-18T12:03:39+00:00
it sounds like a game with symmetric strategies and maybe symmetric pay-offs; that should let you take some shortcuts to finding best responses.

Comment from gregstoll:
2007-05-18T12:49:07+00:00
Unfortunately I don't think the strategy is necessarily symmetric - for example, you could tell person #1 to do something different than person #2. And it seems like that would be necessary for strategies with lots of people...

Comment from djedi:
2007-05-18T12:21:12+00:00
Yeah, it's a neat game that's got a neat relation to Hamming codes.

Here's my thing with vi. First, I always stupidly use vi instead of vim, big difference. Second, I spend 50% of my time thinking, 45% of my time typing and 5% editing. But it's not in that order necessarily. The editing is done in little bits as I type. Thus, I've found when I try to use vi, I'm hitting escape approximately every fifth key. This vastly outweighs any savings this particular editor could offer over other powerful editors. I would constantly be back and forth so much that I'd often end up in the wrong mode and do things I didn't want.

Plus, the vi version we have here doesn't allow arrow usage, the delete key, nor the backspace key in typing mode.

Comment from kernelm:
2007-05-23T17:01:52+00:00
I love vi so very very much. (Well, ok, vim, but regular vi is good too.) It's pretty much the only thing I use for any kind of text editing, including all my code. I often find myself wishing I could use vi style editing on things like web form fields. I've also got vi mode enabled for everything that uses readline. :-D

If you want some tips on vim, let me know. I'm still by no means a true guru, but I've accumulated quite a few cool things. I used to use control-[ to Esc, but I mapped 'jj' in insert mode to it as well, and it's so useful. (Of course my caps lock is remapped to control.) I've also got some things to help manage tabbed windows. And stuff.

This backup was done by LJBackup.