next »

[Zaid Crouch]

Morning all! 

After a brief hiatus, I'm going back to a word game project I've been doing a bit of work on, for the iPhone (there seems to be a shortage of them, methinks ). Anyways, my actual question: do people have any suggestions on the best way to implement word validation? And more specifically, fast word validation.

I'd been thinking along the lines of using a set of valid words, and then just checking for membership, which should be reasonably fast. It is complicated somewhat by the fact that my master list will probably need to consist of word objects, not just strings (the game will require certain other word-specific data), so I was thinking that a dictionary, using the actual strings as keys would probably be my best option.

I feel like a bit of an idiot asking, but I figure there're gotta be a few people with more experience regarding word games and/or collections than I. Thanks in advance for responses!

[mcc]

I guess isn't this the exact situation the trie was invented for?

I'm not sure what you mean by "word objects".

[Zaid Crouch]

Thanks, mcc, that looks like exactly what I was after – it's not a structure I was familiar with previously. 

"Word objects" was just referring to the particular objects I'll be using to story the words and their associated details, as opposed to just using strings.

[mcc]

it's not a structure I was familiar with previously. 

Yeah, it's a little bit obscure.

[raigan]

It depends how the dictionary is implemented, but if it's something like a hash map then that should be fine. AFAIK in C# the Dictionary object is hash-based.

You could also probably get away with an array of strings in alphabetical order and a binary search.

If you want auto-complete or other "neighborhood" type functionality then tries would seem to offer that, but if you just need "does this word exist, and if so can I have the object associated with it" then whatever's supported natively by the language is probably fine.

Then again, I'm quite lazy

(A quick Google turned this up, it might be useful: http://www.codeproject.com/KB/game/Anagrams2.aspx )

[Zaid Crouch]

I'm thinking I'm gonna give tries a shot. It will be a little more work, setting it up and porting all the info in. That said, the other extra benefits could be useful for my project.

Plus at the end, I'd like to be able to compare the two, and see how much extra (or little) benefit I got for the extra work.

Thanks for the link too, I'll check it out properly soon

[Zaratustra]

For Alphabox I stored the dictionary in a kind of janky but fast way (since Flash isn't very quick for mass processing of data): I indexed words first by size, then by first letter, then just as a unordered array inside each of those. So you find a word by doing this:

if (dictionary[word.length][word[0]].contains(word)) { blah }

[st33d]

I actually parsed massive quantities of instructions with regex on the fly in FatCat in Flash.

A lot of the scripting language for the monsters was broken up with brackets holding sub-programs.

Dunno if you get regex on iphone though.

[Titch]

For Alphabox I stored the dictionary in a kind of janky but fast way (since Flash isn't very quick for mass processing of data): I indexed words first by size, then by first letter, then just as a unordered array inside each of those. So you find a word by doing this:

if (dictionary[word.length][word[0]].contains(word)) { blah }

I did something like this. Only I created a separate array for each word length and used switch/case to select the relevant one as Flash tended to freak out with very long arrays. Then I used a binary search pattern using the build in string comparison to try and match it. It worked surprisingly well. Since players entered letters one at a time I could have probably made it more efficient sorting the dictionary by letter indexes and then memorising the last index searched from but...meh. If it ain't broke.