very advanced string algorithm help required

1. Junior Member
Join Date
Dec 1969
Posts
4

## very advanced string algorithm help required

hi all,<BR><BR>i dont know if anyone has tried this before or not but here goes. We play a game in the uk whereby you are given n letters and you have to make as many words as possible or the longest word possible from these letters.<BR><BR>i am attempting to make an engine in ASP that does exactly the above. i have a database of around 35000 words ranging from 3 letters to 15 letters in length.<BR><BR>now i realize that i am going to have to step through each word in the table asking the question can this word be made by these letters. the problem is the easiest way to do this baring in mind that the source letters can and will be in any random order and they may be repeated ie. the letters could be aghheopp in this scenario the player could use the letters p and h twice as they appear twice.<BR><BR>any help on this matter would be absolutly great and very much appreciated.<BR><BR>thanks in advance<BR><BR>daniel.

2. Senior Member
Join Date
Dec 1969
Posts
11,247

## Bill do you remember

I think Bill and I discussed this about a year ago.<BR><BR>Conclusion was "Don&#039;t Even attempt this!" would take too much processing

3. Junior Member
Join Date
Dec 1969
Posts
4

## RE: Bill do you remember

ouch ..... ok i am gonna do this ... then when its done ... i am gonna post the solution !!! the gauntlet is down !<BR><BR>cheers<BR><BR>DG

4. Senior Member
Join Date
Dec 1969
Posts
96,118

## I think it can be done...

...but *NOT* using a database. It should be done in memory, only.<BR><BR>35,000 words at an average of (say) 10 characters each (and using Unicode characters even) is only 700KB of memory. Even with array overhead, that&#039;s no more than 1MB.<BR><BR>And then if you keep a *sorted* version of each word (e.g, "banana" is sorted to "aaabnn"), you double the space to 2MB but you probably speed up performance by 10 to 1 or more.<BR><BR>This is really not overly complicated, at all. But I&#039;d certainly never attempt it in *any* scripting language; certainly not VBScript.<BR><BR>

5. Senior Member
Join Date
Dec 1969
Posts
96,118

## Probably a 2-day project...

...or so, if you were to use VB.NET, say.<BR><BR>It&#039;s just not appropriate use of a DB, that&#039;s all.<BR><BR><BR><BR>

6. Senior Member
Join Date
Dec 1969
Posts
2,930

## speaking of inappropriate uses of a db

doug&#039;s got one for ya ;-)<BR><BR>but... wouldn&#039;t you use some kind of math for this? i&#039;m sure you can find some algorithm or some clever replacement scheme that would speed this up immensely<BR><BR>like a bitmask (26 letters fit in 32 bits!)<BR><BR>bad<BR>= 0002h & 0001h & 0004h<BR><BR>you know, instead of searching a string for a character<BR><BR>then for the letters in each word in memory, you&#039;d have... DOH!!! you can&#039;t tell if there are duplicate letters.<BR><BR>nevermind

7. Senior Member
Join Date
Dec 1969
Posts
2,930

## 0004h = 0008h

8. Senior Member
Join Date
Dec 1969
Posts
96,118

## EXCELLENT IDEA!

For a first level check, YES!<BR><BR>Sure, it doesn&#039;t find the duplicated letters in the word, but at least you&#039;d eliminate "apple" when your letters are "bana" real damned quick! You&#039;d still have to check "aaabnn" versus "aabn" to discover that there aren&#039;t enough letters to make the word, but it&#039;s a *GREAT* first test!<BR><BR>

9. Senior Member
Join Date
Dec 1969
Posts
2,930

## that'll be \$5

:-P<BR><BR>listen to my music!

10. Junior Member
Join Date
Dec 1969
Posts
4

## RE: that'll be \$5

ok ok ok, this is not good, i got as far as 10 letter searches taking less that 30 seconds BUT hey it dont work ... i am getting wacked out here ... its one of those stupid little ponderes that will drive me insane///<BR><BR>love the idea of converting words etc ... but at first thought i was working like this.<BR><BR>two loops<BR><BR>loop through the word you have checking each letter off against ones you need to have to make this word. if the letter doesnt exist (simple instr) then jump out to the next letter, if the letter does exist then remove it from the word and move on .... when you run out of letters then see if there are any left over (ie letters that you would still need to make said word but didnt have (len(tempword&#062;0)) then you aint matched it ... otherwise you have.....<BR><BR>thats the theory all i got to do is slot it ... i even got a regexp replace that only replaces the first instance of a letter so i can remove a single letter from the string ie cool remove &#039;o&#039; returns col not cl as it would with replace....<BR><BR>god i wish i had never entered into this one.!

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•