 |
Author |
|
|
|
Poo Bear
Pod Team
Joined: 14 Oct 2002
Posts: 4107
Location: Sheffield, UK
|
 Posted: Mon Jul 14, 2008 11:09 pm Post subject: |
 |
|
| Yes, that's very fast, nice one. I'm doing a whole mess of other gubbins to do with ranking words, unicode, special case phrases like 'qu' in english - but allegedly there are others in other languages so it handles it generically, pirate words, etc. So I got it going fast enough and then moved on, but this shows what can be done. |
|
|
|
Back to top |
|
|
 |
|
colinvella
Joined: 15 Sep 2006
Posts: 82
|
| Posted: Tue Jul 15, 2008 12:17 pm Post subject: |
|
|
[quote="Slyh"] | colinvella wrote: |
Yes. This algorithm is fine for relatively short words. For 8 letter words you'd already have to create 46,232 permutations, for 10 letters 4,037,912. I doubt that this would be fast enough, even when a Trie is used.
For short words/bad AI your algorithm is definitely faster. Using a Hash Map to store all valid words would probably be faster than using a Trie, though. Tries are more useful to save memory than for performance reasons. (At least if you have a complete word and want to find the exact word in a huge set of words.) |
There might be a way of pruning out the combos by doing the trie searches simultaneously with the combo construction.
For example:
---
You choose a first letter and check if the trie map root has a child node for that letter (trivially true for the 1st letter as you can find words starting with all the letters in the alphabet, given a comprehensive dictionary)
Repeat the process by selecting the next letter from the remaining valid letters and check if the trie tree can be navigated with the current combo. If not, stop working with this combo and start with a new one.
---
I would agree with you on the performance of hash maps, were it not for the fact that the hashing function for the strings is itself typically of Order(N). So even assuming no bin conflicts (usually not an issue since good hash map implementations grow automatically to counter this), a trie map should more or less perform better. Bear also in mind that some trie implementations actually collapse degenerate sections of their branches so that given a word of M letters, you don't necessarily have to traverse M nodes. Also, you can exit early from the search as soon as it is clear that the word is not in the dictionary given the current initial sub-string. For example, with a word like "xzfoopy", the search algo will terminate as soon as it tests the letter "z" because there are no valid words starting with "xz" (again my assumption!) |
|
|
|
Back to top |
|
|
|
|
rincebrain
Joined: 17 May 2007
Posts: 12
|
| Posted: Mon Sep 21, 2009 12:23 pm Post subject: |
|
|
| Poo Bear wrote: | That kind of thing, but a bit different. We've got another story by our friend Enzo (who did the one in MrRobot) and a ship to upgrade (not a space ship though  ) and a map and missions and special powers and stats and different enemies to fight and ...
Anyway, you'll see soon. |
"Soon", eh? |
|
|
|
Back to top |
|
|
|
|
Poo Bear
Pod Team
Joined: 14 Oct 2002
Posts: 4107
Location: Sheffield, UK
|
| Posted: Mon Sep 21, 2009 1:16 pm Post subject: |
|
|
Haha - yes, we end up doing contract work on boring "normal" type projects which drags us away from this stuff. Still, I'm working on it right now as a matter of fact <gasp>.
So it should be ready soon  |
|
|
|
Back to top |
|
|
|
|
Konedima
Grammar Police
Joined: 25 Oct 2003
Posts: 1068
Location: Sydney, Land of Censorship
|
|
|
|
Back to top |
|
|
|
|
Poo Bear
Pod Team
Joined: 14 Oct 2002
Posts: 4107
Location: Sheffield, UK
|
| Posted: Tue Sep 22, 2009 8:09 am Post subject: |
|
|
Probably Blizzard's definition
I was working fulltime on boring web based gaming stuff (gambling) for another company and not getting much time to do anything. There is a big recession in the UK though currently and it's turned into more of a part time contract now so I've got some free time. Not sure how long that will last though. |
|
|
|
Back to top |
|
|
|
|
Konedima
Grammar Police
Joined: 25 Oct 2003
Posts: 1068
Location: Sydney, Land of Censorship
|
| Posted: Tue Sep 22, 2009 8:30 am Post subject: |
|
|
| Relax, you're not the only ones who operate on Valve Time. |
|
|
|
Back to top |
|
|
|
|
|
|
|
|
|
