Groups Home - Yahoo! - Help

Welcome, Guest Register - Sign In 
wordgame-programmers · A list for programmers of word games. Ve [ Join This Group! ]
* Messages  
  owner = Owner 
  moderator = Moderator 
  online = Online 
 Messages Messages Help
Reply | Forward | View Source | Unwrap Lines
  Message 487 of 487  |  Previous | Next  [ Up Thread ] Message Index
 Msg #
From:  Eric House <fixin@p...>
Date:  Sun Sep 22, 2002  6:17 am
Subject:  Re: [wgp] Boggle dictionary algorithm

> Yes, otherwise the tree would be larger than the word list... I've
> put the source at It
> exploits the fact that the words come in in alphabetical order. I
> think that is also a known technique... I hope the source is
> understandable, if not, feel free to ask.

Some years ago when I started coding A&J's algorithm for Crosswords
(my PalmOS scrabble-like game) I had a conversation with one of the
authors (Jacobsen, I think) that resulted in my getting some
dawg-building code that was nearly instantaneous, but also
incomprehensible (to me). I stuck with the stuff I'd already written,
though it was maybe 100x slower.

Falk's algorighm is pretty much the same, but somehow now I can follow
it. I've recoded the compression part in perl, and while it's slower
than the C++ that inspired it it's still *much* faster (at least 20x)
and much less resource-hungry than my version. It's certainly fast
enough to use for an online dictionary-builder -- and so I'm on my
way. Thanks for sharing the code!

I'm posting my version here:

It's not a complete replacement for Falk's app. There's no lookup
facility. More importantly, it doesn't yet output a binary
representation of the trie array. But that's a trivial change. I'm
posting now because the changes I make down the line will be in the
direction of Crossword's (and PalmOS's) requirements. I think it'll
be more useful to others while still in this form.



* From the desktop of: Eric House, fixin@p... *
* Crosswords 4.0 for PalmOS is out!: <> *

  Message 487 of 487  |  Previous | Next  [ Up Thread ] Message Index
 Msg #
Reply | Forward | View Source | Unwrap Lines

Copyright 2002 Yahoo! Inc. All rights reserved.
Privacy Policy - Terms of Service - Guidelines - Help