A nasality talisman for the sultana analyst

re: A nasality talisman for the sultana analyst

Alan — Thu, 05 Feb 2009 07:01:30 GMT

The general problem of writing a Scrabble playing program came up as a software project option in my final year at university (my group chose a different project because we thought Scrabble sounded too hard, we wrote a software simulation of the MC68000 CPU instead!).

The trick turned out to be the data structure that holds the dictionary. You can preprocess the dictionary into a Directed Acyclic Word Graph, start with a tree where each node holds a letter and each "edge" leads to another node that holds the next letter in each valid word that shares the prefix, then collapse all of the common suffixes so that they're shared wherever possible.

Once you've got the DAWG, any way you navigate through the directed graph will produce a valid word, so you can generate all the words for a given rack by following the letter combinations, chasing down multiple paths if you have a blank to play with, adding in letters already on the board at certain positions in the word, etc, etc.

The problem of making software play the game then comes down to what strategies can be applied to maximise the score (do you chase triple word scores? search for high value letters? look for word reuse/extension opportunities?).

Neat problem, neat solution (might not be the best/most efficient way of finding anagrams though)!

re: A nasality talisman for the sultana analyst

Thomas — Thu, 05 Feb 2009 07:24:51 GMT

This can be done more efficiently (in terms of computer time, not programmer's time) by building a histogram out of each word. Make an array of 26 buckets; entry 0 contains the number of A's, entry 1 the number of B's, etcetera. Then your comparisons are in O(1) instead of O(length_of_word), simply by comparing the histograms bucket-by-bucket. (Of course, this does not scale to languages with a larger alphabet. But I suppose that Chinese Scrabble doesn't exist anyway.)

As a bonus, an arbitrary number of blanks can easily be implemented. While comparing the histogram of the rack with the histogram of a dictionary word, pretend the blanks are not there. If there are more of a certain letter on the rack than there are in the dictionary word, you know that you can't form that word with your whole rack. If there are more of the letter in the dictionary word than on the rack, use as many blanks as you need. If you run out of blanks, you also know that the word can't be formed.

I estimate that this method will take less than 0.1 second to search a 2 MB dictionary.

Do I pass the Microsoft interview now? ;)

re: A nasality talisman for the sultana analyst

Brad — Thu, 05 Feb 2009 09:21:02 GMT

@Thomas

Just a note - although you're right that comparing the histograms is O(1), so is comparing the words really, since the word length for scrabble will never be longer than 7 or 8 letters in practice (occasionally you can continue to build on words and get longer, but he's not handling that case anyhow) so I'm not sure that comparing 26 buckets will really be faster than comparing the canonicalized strings.

The real issue is that you're O(n) in the size of the dictionary.

My first thought was to use tries (much like Alan describes) although it would be simpler to use a a hash table with the canonicalized strings mapped to the original. You couldn't just use a dictionary (since the same canonical form could be generated from several words), but it would be fairly simple to build. Building this would probably be bounded by the disk io of reading the word list, and finding the words would only require 26 lookups for one "?" and 676 for 2. It's though to imagine beating that by much.

re: A nasality talisman for the sultana analyst

Tanveer Badar — Thu, 05 Feb 2009 12:02:41 GMT

T9 mode in cell phones works quite similarly. Although, there are no wild card searches as yet. You group words by length in a table. Then, cycle through them when the user presses next word key.

re: A nasality talisman for the sultana analyst

Tim Long — Thu, 05 Feb 2009 16:22:01 GMT

Thanks for this interesting little article which nicely showcases how useful Linq is just in general everyday programming. Plus, you introducde me to The Big Snit. Yea!

I was just thinking about the number of programming examples I've seen where the author states "This is not production quality code". Hitler once said, if you repeat a lie often enough, people will believe it. My point is, we see lots of these 'quick and dirty' examples and after a while, it is easy to start believing that 'Production Quality Code' is a mythical thing. I know from experience that a lot of programmers do actually write very poor code and then put it into production. I don't really know where I'm going with this, except to say that, with the best of intentions, it is all too easy to set a bad example.

re: A nasality talisman for the sultana analyst

Joe Chung — Thu, 05 Feb 2009 16:41:43 GMT

File.ReadAllLines(dictionary) is a one-liner replacement for FileLines().

It's a pity that you can only use the join operator on equality comparisons, else we could have done this:

from word in File.ReadAllLines(dictionary)
let canonical = Canonicalize(word)
join rack in racks on rack.Contains(canonical)
orderby word
select word;

[[ ERIC: ReadAllLines is not a one-liner replacement. ReadAllLines reads the entire 2 meg dictionary into memory at once. My version reads one line at a time into memory. The next version of the framework will probably have a version of ReadAllLines that does it my way. ]]

re: A nasality talisman for the sultana analyst

Joe Chung — Thu, 05 Feb 2009 16:54:30 GMT

Actually, joining rack in racks on canonical equals rack would work just fine!

re: A nasality talisman for the sultana analyst

Aaron G — Thu, 05 Feb 2009 22:51:15 GMT

Is it cheating to pre-compute the canonical forms? I mean, clearly the bottleneck is having to iterate through the whole dictionary, not computing the 676 combinations of blanks in the rack, so you just need an index. Stuff the original word and canonical form into an MSDE database and you could do all those lookups, well, pretty much instantly.

I know, it's not clever, but why fuss over DAWGs and histograms and data structures when somebody has already done most of the work for you? Memory and disk space are cheap. The clever part, as Eric already pointed out, is turning the word from a sequence into a set; how you do the transformation seems like micro-optimization to me.

Would I fail the Microsoft interview for taking that approach? :-)

re: A nasality talisman for the sultana analyst

Eric Lippert — Thu, 05 Feb 2009 23:46:45 GMT

Of course it is not "cheating" because I haven't specified what the rules are. :-)

This is not the first time I've implemented this program; my earlier JScript version worked by writing two programs, one which transformed the dictionary into an index file, and one which did lookups in the index file. That version was quite fast.

That works great for the problem that I stated -- find all the words that exactly match a given rack. It might work much less well for harder problems, like "find the highest scoring word that can be made from any of the letters in this rack", or even harder still, like "find the highest scoring play for a given rack and board state". For those problems, a simple index might not be good enough. I don't know; I haven't tried.

re: A nasality talisman for the sultana analyst

Thomas — Fri, 06 Feb 2009 01:49:30 GMT

@Brad: You're right, a hashtable is a better solution (if the number of blanks is small). Neat.

re: A nasality talisman for the sultana analyst

Figment Engine — Fri, 06 Feb 2009 21:22:52 GMT

Nice post, I've written an extension method that makes Enumerable character ranges easier to work with.

So you can write:

foreach (char c in 'A'.To('Z'))
Console.WriteLine(c);
instead of:

foreach (char c in "ABCDEFGHIJKLMNOPQRSTUVWXYZ")
Console.WriteLine(c);

fe.

[[ ERIC: A nice example of fluent programming -- however I find it a little bizarre that on the one hand you feel that its justified to use a crazy nano-optimization like using xor to swap two chars (which is on modern architectures no faster than just using a temp like a sensible person), and yet at the same time using iterators and lambdas and closures which have IMMENSE runtime costs compared to the nanosecond it takes to swap two chars. I would write the code to be as clear as possible first, and then optimize it based on profile data later. ]]

re: A nasality talisman for the sultana analyst

leniel — Sat, 07 Feb 2009 10:05:15 GMT

Hi Eric,

I've just played with your code and noted that the extension method Join won't compile. It must be declared public instead of private.

Great exercise!

All the best,

Leniel Macaferi

Or make the class that holds all the methods a static class, which is what I did. -- Eric

re: A nasality talisman for the sultana analyst

Figment Engine — Sat, 07 Feb 2009 19:56:17 GMT

@Eric: you are quite right - the swap is better using a temp var, that will teach me for reusing over optimized array rotation code!

private static void Swap(ref char a, ref char b)
{
temp = a;
a = b;
b = a;
}

the previous version of the swap was more more effluent programming than fluent ;-)

re: A nasality talisman for the sultana analyst

J.D. — Wed, 18 Feb 2009 23:34:07 GMT

Figment Engine:

Um.. Check your code.

re: A nasality talisman for the sultana analyst

Diego — Thu, 19 Feb 2009 00:06:31 GMT

Interesante la lectura acerca de la "codificación" en especial los dibujitos.

re: A nasality talisman for the sultana analyst

Horza — Tue, 24 Feb 2009 19:29:03 GMT

@Figment Engine:

corrected code:

private static void Swap(ref char a, ref char b)

{

temp = a;

a = b;

b = temp;

}

re: A nasality talisman for the sultana analyst

zara — Sat, 28 Feb 2009 19:55:25 GMT

private static void Swap(ref char a, ref char b)

{

temp = a;

a = b;

b = temp;

}

ı know which is a swap.it s name is SWAP!I like it.

re: A nasality talisman for the sultana analyst

Malc Boczek — Mon, 02 Mar 2009 19:21:50 GMT

Amazingly timed relevant to current project.... thank you.

One potential addition to C# 5 (?) would allow access to the foreach root list/array;

e.g. foreach(object o on listroot in list).

IEnumerator ie = list.GetEnumerator()

while (ie.MoveNext())

{

// do something...

if (some condition) ie.Skip(n);

}

could then be written as,

foreach(object o on myie in list)

{

// do something...

if (some condition) myie.Skip(n);

}

The "on" target could also be a Typed Enumerator.

I know this doesn't add much functionality, but it does seem a little more readable (at least to me - I'd hate to start another code war like part 2 !!!)

Cheating at Scrabble with LINQ to Objects

Stuart Leeks — Fri, 06 Mar 2009 00:33:07 GMT

I read an interesting post on Eric Lippert’s blog recently where he was using LINQ to Objects to find

re: A nasality talisman for the sultana analyst

Paul Maddox — Tue, 17 Mar 2009 15:23:08 GMT

I think you're all missing the point - it's not about making the most efficient anagram finder, it's just a demonstration of LINQ.

re: A nasality talisman for the sultana analyst

mike — Sun, 29 Mar 2009 01:40:40 GMT

Please check out <a href="http://www.alpha-dream.com">Human pheromones, pheromone cologne by Alpha Dream</a>. Human pheromones help improve your sex life and dating success. Pheromones cause others to be more attracted to you, and help revamp your love life. Human pheromones are for men and women of all ages, and are provided in unscented sprays, or in cologne and perfume.

re: A nasality talisman for the sultana analyst

George Polevoy — Sun, 19 Apr 2009 18:18:12 GMT

Your code is total overkill both in terms of performance and disk space for the dictionary.

There is only as few as 2500 anagramms 1230 anagrammatic groups in the text of Tolstoy War and Peace.

Cheating at Scrabble with LINQ to Objects

UK Application Development Consulting — Fri, 19 Jun 2009 12:30:41 GMT

I read an interesting post on Eric Lippert’s blog recently where he was using LINQ to Objects to find

re: A nasality talisman for the sultana analyst

Frustrated — Thu, 19 Nov 2009 11:09:20 GMT

Is it possible to download the word list from somewhere? Maybe my Google skills suck but I just can't find it.