Sanchek

I've been playing online Scrabble against this linguistics major who absolutely kicks my ass. After losing a half dozen times in a row, I figured if they can bring their specialized education to the table, I should bring mine too.

So, I wrote an application to generate anagrams from a set of letters and check them against the TWL Scrabble dictionary. I decided to go ahead and host it where others can use it too. If you play Scrabble, it might be of use.

Enjoy.

Sanchek

Also, it's the weirdest thing. A large, large majority of the traffic to that site is from Canada. Is Scrabble the national pastime of Canada or something?

Kelraz Bladesinger

Haha thats crazy clever. Kudos.

Palarran

Hmm, I think something is wrong.

I was curious whether words longer than 8 letters were included, since it is normally difficult to form words more than 8 letters long in Scrabble. I tried entering "unbecoming" (the first word that came to mind, for some reason). It did return the 9 letter word "mucinogen" but not "unbecoming".

Yet "unbecoming" should be on the list:
http://www.scrabulous.com/dictionary...coming&dic=twl

Next I tried "optionally". This time it worked; the top result was "optionally".

Edit: I tried some more words with the prefix "un" to see if that was the issue. "Uninspired" and "uncommitted" worked. "Unoriginal" and "unforgiven" didn't.

Edit 2: "Onomatopoeia" worked but it took close to a minute to return results. "Alphabetically" resulted in a timeout. You may need to either cut off the number of letters considered or use a more efficient algorithm.

Sanchek

I'll take a look at that. Mainly, it's focused towards the 7 letter combinations that you can make in a normal Scrabble game (though, it does have the entire TWL word list to check against).

Sanchek

It's fixed now. Thanks for finding that for me.

To improve performance, I have lists of valid 2-5 letter word prefixes. If a branch of the tree is going down a path that's impossible to make a word from, it preemptively stops that branch short. Somehow, I managed to be missing about 6% of those from the five letter list, including UNBEC. Oops.

As for performance, yeah it kinda blows for a lot of letters. I'm just using a recursive algorithm, with that prefix based pruning. So, when you get to 12 letters, it's running nearly a half billion permutations. Ouch.

I've read about a more efficient algorithm, using a directed graph, but I doubt I'll ever feel like implementing it.

edit: Oh, and unforgiven isn't a valid TWL word, so that's why that one failed.

Palarran

Aha, you're right! With "unforgiven" I got lazy and just checked google ("define:unforgiven") instead of the TWL dictionary, since I had already closed the scrabulous.com page.

I was trying to think of how I would do it if I wanted to optimize for execution speed rather than ease of coding or anything else. (If I wanted a quick-and-dirty solution I'd probably have taken a similar approach to yours.)

I'd probably create a tree structure where each node (except the root node) represented a letter, and contained a set of child nodes representing letters _after_ that letter. Each word on the TWL list would be attached as a leaf node to the series of nodes representing the unique letters in the word sorted alphabetically. For example "banana" would be attached to (root)->A->B->N. Then if my search string was "ABCABCN" I would see that it has 2 A's, 2 B's, 2 C's, and one N, and iterate through the words in these lists, checking their letter counts against those of the search string:
A ("aa")
A->B ("abba", "baba", "aba", "baa", "ab", "ba")
A->B->C ("bacca", "abaca", "cab")
A->B->C->N ("cabana")
A->B->N ("banana", "ban", "nab")
A->C ("caca")
A->C->N ("cancan", "canna", "can")
A->N ("anna", "naan", "nana", "ana", "nan", "an", "na")
B (empty)
B->C (empty)
B->C->N (empty)
B->N (empty)
C (empty)
C->N (empty)
N (empty)

Of course I don't feel like implementing it either. I just like the problem solving part.

Fandros

Palarran, I'm a mere vessel now....

Sanchek

That's basically the same as the directed graph approach. I'm just worried that the memory footprint would be a lot larger than using a flat word list, which will cause me trouble at that shared host.

Oipunx the High Elf Cleri

One of my best friends has memorized every two letter and three letter word in the english language.

He loves scrabble!

__________________