WordCracker

[codeguy]

No, mine does unconditional permutations. Which is why it may have detected 3 more words than other submissions. But it does generate matches in lexical (alphabetical) order, saving sorting. For 8 characters or less, the speed is VERY similar to Steve's algorithm, running 8+ times to completion in the 5 second limit. Mine in 8 character mode, runs about .60s or less using the complete wordlist.txt document.

[SMcNeill]

My entry into the field of long-arse string searches:

Code: QB64: [Select]

1. SCREEN _NEWIMAGE(800, 600, 32)
2. CONST In$ = "thequickbrownfoxjumpedoverthelazydogdreamingofcountingsheepthinkingofbrownfoxjumpingoverdogs"
3.  
4. InLen = LEN(in$)
5.  
6.  
7. OPEN "WordList.txt" FOR BINARY AS #1
8. DO UNTIL EOF(1)
9.     LINE INPUT #1, junk$
10.     WordCount = WordCount + 1
11.     IF LEN(junk$) > maxlength THEN maxlength = LEN(junk$)
12. LOOP
13. SEEK 1, 1
14.  
15. TYPE WordLetters
16.     letter AS _UNSIGNED _BYTE
17.     count AS _UNSIGNED _BYTE
18. END TYPE
19. DIM Words(WordCount) AS STRING, Match(WordCount) AS LONG
20. DIM WordLetters(WordCount, 26) AS WordLetters
21. DIM Letters(97 TO 122) AS _UNSIGNED _BYTE
22.  
23. FOR i = 1 TO WordCount 'Load and prepare our word list and wordsearch array
24.     LINE INPUT #1, Words(i)
25.     FOR j = 1 TO LEN(Words(i))
26.         a = ASC(Words(i), j)
27.         IF a > 96 AND a < 123 THEN
28.             afound = 0
29.             FOR k = 1 TO WordLetters(i, 0).count
30.                 IF a = WordLetters(i, k).letter THEN afound = k: EXIT FOR
31.             NEXT
32.             IF afound THEN
33.                 WordLetters(i, afound).count = WordLetters(i, afound).count + 1 'add to the count of an existing letter
34.             ELSE
35.                 WordLetters(i, 0).count = WordLetters(i, 0).count + 1 'increase the total count of letters
36.                 w = WordLetters(i, 0).count
37.                 WordLetters(i, w).letter = a 'save the letter
38.                 WordLetters(i, w).count = 1 'and count it 1 for the first time it appeared
39.             END IF
40.         ELSE
41.             WordLetters(i, 0).count = 0 'invalidate words with non A-Z letters
42.             EXIT FOR
43.         END IF
44.     NEXT
45. NEXT
46.  
47. FOR i = 1 TO InLen 'get the letters for the search string
48.     a = (ASC(in$, i) OR 32)
49.     Letters(a) = Letters(a) + 1
50. NEXT
51.  
52.  
53. t# = TIMER
54. DO UNTIL TIMER > t# + 5
55.     loopcount = loopcount + 1
56.     wordfound = 0 'reset our counter
57.  
58.     'THE MAIN SEARCH ROUTINE HERE
59.  
60.     FOR i = 1 TO WordCount 'now check every word for a match
61.         sl = WordLetters(i, 0).count 'search limit
62.         IF sl = 0 THEN GOTO invalid
63.         FOR j = 1 TO sl
64.             l = WordLetters(i, j).letter 'the letter in the word
65.             IF Letters(l) < WordLetters(i, j).count THEN GOTO invalid 'it's impossible
66.         NEXT
67.         wordfound = wordfound + 1
68.         Match(wordfound) = i
69.         invalid:
70.     NEXT
71.  
72.     'END OF THE MAIN SEARCH ROUTINE
73.  
74. LOOP
75.  
76. 'Print Results
77. FOR i = 1 TO wordfound
78.     PRINT Words(Match(i));
79.     IF i < wordfound THEN PRINT ","; ELSE PRINT
80. NEXT
81. PRINT
82. PRINT "DONE, with"; wordfound; "matches, with a speed of"; loopcount; "runs in 5 seconds."
83.  
84. END
85.  
86. 'And, if you want to see the secret behind this method, here's how we store and retrieve our data:
87.  
88. FOR i = 1 TO 10 'I think just showing how we track 10 words should be fine enough
89.     PRINT Words(i),
90.     FOR j = 1 TO WordLetters(i, 0).count
91.         PRINT CHR$(WordLetters(i, j).letter);
92.         PRINT WordLetters(i, j).count;
93.         PRINT ",";
94.     NEXT
95.     PRINT
96. NEXT
97.  
98. SLEEP
99.  
100. 'and here's the in$ and how its letter count holds up
101.  
102.  
103. PRINT in$
104. FOR i = 97 TO 122
105.     PRINT Letters(i);
106. NEXT
107. PRINT
108.  

Instead of 32-37 runs in 5 seconds, this does about 150 on my machine.   

If you're curious how it does it, remove the END statement and then let it run.  It'll show you how we basically break down our words so we never have to check the letters in them any more times than is absolutely necessary to make a match.  ;)

[SMcNeill]

And, a slight tweak to do some pre-sorting based on In$ size and non-A-Z characters, and to add a key$ to make certain that the words all contain a valid letter we designate, as per the original post's requirements:

Code: QB64: [Select]

1. SCREEN _NEWIMAGE(800, 600, 32)
2. CONST In$ = "thequickbrownfoxjumpedoverthelazydogdreamingofcountingsheepthinkingofbrownfoxjumpingoverdogs"
3. 'CONST In$ = "abcdefghi"
4. 'key$ = "a" 'make "" or remark this line out completely to do a search without a required key, as per the original post
5. InLen = LEN(In$)
6.  
7.  
8. OPEN "WordList.txt" FOR BINARY AS #1
9. DO UNTIL EOF(1)
10.     LINE INPUT #1, junk$
11.     WordCount = WordCount + 1
12.     IF LEN(junk$) > maxlength THEN maxlength = LEN(junk$)
13. LOOP
14. SEEK 1, 1
15.  
16. TYPE WordLetters
17.     letter AS _UNSIGNED _BYTE
18.     count AS _UNSIGNED _BYTE
19. END TYPE
20. DIM Words(WordCount) AS STRING, Match(WordCount) AS LONG
21. DIM WordLetters(WordCount, 17) AS WordLetters
22. DIM Letters(97 TO 122) AS _UNSIGNED _BYTE
23.  
24.  
25. FOR i = 1 TO WordCount
26.     wc = wc + 1
27.     LINE INPUT #1, Words(wc)
28.     IF LEN(Words(wc)) > InLen THEN 'remove words too long to fit
29.         wc = wc - 1
30.     ELSE
31.         FOR j = 1 TO LEN(Words(wc)) 'remove non A-Z words as we're only searching for words with those letters
32.             IF ASC(Words(wc), j) < 97 OR ASC(Words(wc), j) > 122 THEN wc = wc - 1: EXIT FOR
33.         NEXT
34.     END IF
35. NEXT
36. WordCount = wc
37.  
38. FOR i = 1 TO WordCount 'Load and prepare our word list and wordsearch array
39.     FOR j = 1 TO LEN(Words(i))
40.         a = ASC(Words(i), j)
41.         afound = 0
42.         FOR k = 1 TO WordLetters(i, 0).count
43.             IF a = WordLetters(i, k).letter THEN afound = k: EXIT FOR
44.         NEXT
45.         IF afound THEN
46.             WordLetters(i, afound).count = WordLetters(i, afound).count + 1 'add to the count of an existing letter
47.         ELSE
48.             WordLetters(i, 0).count = WordLetters(i, 0).count + 1 'increase the total count of letters
49.             w = WordLetters(i, 0).count
50.             WordLetters(i, w).letter = a 'save the letter
51.             WordLetters(i, w).count = 1 'and count it 1 for the first time it appeared
52.         END IF
53.     NEXT
54. NEXT
55.  
56. FOR i = 1 TO InLen 'get the letters for the search string
57.     a = (ASC(In$, i) OR 32)
58.     Letters(a) = Letters(a) + 1
59. NEXT
60.  
61.  
62. t# = TIMER
63. DO UNTIL TIMER > t# + 5
64.     loopcount = loopcount + 1
65.     wordfound = 0 'reset our counter
66.  
67.     'THE MAIN SEARCH ROUTINE HERE
68.  
69.     FOR i = 1 TO WordCount 'now check every word for a match
70.         sl = WordLetters(i, 0).count 'search limit
71.         FOR j = 1 TO sl
72.             l = WordLetters(i, j).letter 'the letter in the word
73.             IF Letters(l) < WordLetters(i, j).count THEN GOTO invalid 'it's impossible
74.         NEXT
75.         IF key$ = "" THEN
76.             wordfound = wordfound + 1
77.             Match(wordfound) = i
78.         ELSEIF INSTR(Words(i), key$) <> 0 THEN
79.             wordfound = wordfound + 1
80.             Match(wordfound) = i
81.         END IF
82.         invalid:
83.     NEXT
84.  
85.     'END OF THE MAIN SEARCH ROUTINE
86.  
87. LOOP
88.  
89.  
90. 'Print Results
91. FOR i = 1 TO wordfound
92.     PRINT Words(Match(i));
93.     IF i < wordfound THEN PRINT ","; ELSE PRINT
94. NEXT
95. PRINT
96. PRINT "DONE, with"; wordfound; "matches, with a speed of"; loopcount; "runs in 5 seconds."
97.  
98. SLEEP
99. CLS
100.  
101.  
102.  
103.  
104. 'And, if you want to see the secret behind this method, here's how we store and retrieve our data:
105.  
106. FOR i = 1 TO 10 'I think just showing how we track 10 words should be fine enough
107.     PRINT Words(i),
108.     FOR j = 1 TO WordLetters(i, 0).count
109.         PRINT CHR$(WordLetters(i, j).letter);
110.         PRINT WordLetters(i, j).count;
111.         PRINT ",",
112.     NEXT
113.     PRINT
114. NEXT
115.  
116. SLEEP
117.  
118. 'and here's the in$ and how its letter count holds up
119.  
120.  
121. PRINT In$
122. FOR i = 97 TO 122
123.     PRINT CHR$(i); LTRIM$(RTRIM$(STR$(Letters(i))));
124.     IF i < 122 THEN PRINT ", "; ELSE PRINT
125. NEXT
126. PRINT

We now run nice and fast for both short and long strings.  We can use a preset qualifier key if we want to, but we don't have to.  Run times are ~900 loops for "abcdefghi" with a key of "a", and ~200 times with the long entry Bplus used in his test routine earlier.

[bplus]

Yah Steve, 140 loops on my machine fabulous. Poor Peter, you robbed him to pay Paul. ;-))
(Steve, this comment based on your previous code post, you posted another while I was getting list ready for codeguy.)

Hi code guy,

Here is my list of 392 words from stevemcneill from the given WordList.txt file posted earlier in thread.
Hope this helps you find differences in lists.

PS what is unconditional permutation?

[bplus]

Some time ago, I built a Word Search Solver and had thought about making a Word Search Puzzle Builder.

With this Word Crack code review, I am rethinking building a Word Search Puzzle Builder based on a longish quote. Hmm... a few more details to work out... but have good word list generator now and if you throw in allot of extra of the same letters, could be a quite a challenge, like getting a puzzle where all the pieces look the same.

[SMcNeill]

And for those who are having trouble understanding how my last 2 examples work, the secret is in the letter counter.

Take APPLE as an example...  Instead of searching to see if the In$ has those 5 letters, we instead count the letters first, when we load the dictionary.  1 A, 2 P, 1 L, 1 E...    All we have to check is a maximum of 4 times, instead of 5; we just check to make certain In$ has 2 Ps in it once, rather than checking twice...

In some cases, this reduces a ton of letter checks.   MISSISSIPPI.  Instead of 11 letters, we check 4...   (1 M, 4 I, 4 S, 2 P).

Minimal conditional checking makes for maximum performance.  ;)

[bplus]

And for those who are having trouble understanding how my last 2 examples work, the secret is in the letter counter.

Take APPLE as an example...  Instead of searching to see if the In$ has those 5 letters, we instead count the letters first, when we load the dictionary.  1 A, 2 P, 1 L, 1 E...    All we have to check is a maximum of 4 times, instead of 5; we just check to make certain In$ has 2 Ps in it once, rather than checking twice...

In some cases, this reduces a ton of letter checks.   MISSISSIPPI.  Instead of 11 letters, we check 4...   (1 M, 4 I, 4 S, 2 P).

Minimal conditional checking makes for maximum performance.  ;)

PLUS, if you want to save even more time, save the processed Word List back into a new Data File, once and forever preprocessed!

Peter smiles, he ain't feel'in so broke no more.

[codeguy]

Unconditional permutation means I perform no checking as to whether the next generated permutation actually fits the pattern of the language. In essence, it will check for permutations of words beginning with rx or some other beginning consonant pair that does not appear in standard language. This is handy for finding abbreviations like RPM or GPS or even TLDR, which are not words in the standard sense, but is included in the English language as shorthand for Revolutions Per Minute Global Positioning System and Too Late Didn't READ. Even stuff like RTFM, whose translation I will leave to the reader. While my method is slow for very large strings, it is absolutely thorough and can work for languages that are not English too. Slow? Yes, it is slow, but it will not skip any possible permutations that could lead to missing words in a word list. This is why it's considered an exhaustive algorithm. Also, my method eliminates any chance for repetitions of words found. BTW, my name has 871 exactly matching words that are in wordlist.txt, among them. Sanhedrin, Idaho and ordinals. Weird, huh? But for words of 8 characters or less, using the permutation method and my searching algorithm is competitive to Steve's work. This word list does not contain axolotl, a kind of salamander (301 words in wordlist.txt), but 32 words contained in axolotl were found. With my algorithm, if it's in there, this will find it AND give results in sorted order.

[bplus]

Thanks codeguy,

As the man said, "Minimal conditional checking makes for maximum performance.  ;)  "

Oh hey, I've got try this with my middle name too, 1106! including roman, sagamen.

[SMcNeill]

And for those who are having trouble understanding how my last 2 examples work, the secret is in the letter counter.

Take APPLE as an example...  Instead of searching to see if the In$ has those 5 letters, we instead count the letters first, when we load the dictionary.  1 A, 2 P, 1 L, 1 E...    All we have to check is a maximum of 4 times, instead of 5; we just check to make certain In$ has 2 Ps in it once, rather than checking twice...

In some cases, this reduces a ton of letter checks.   MISSISSIPPI.  Instead of 11 letters, we check 4...   (1 M, 4 I, 4 S, 2 P).

Minimal conditional checking makes for maximum performance.  ;)

PLUS, if you want to save even more time, save the processed Word List back into a new Data File, once and forever preprocessed!

Peter smiles, he ain't feel'in so broke no more.

If I were to save it as a processed list, I'd sort it first to put maximum letters first.

Apple has 2Ps and only one of every other letter.  Since double letters are rarer than single letters, if we check for the PP first, we're more likely to be able to skip the rest of the checks.

So, instead of 1A2P1L1E, I'd store it as 2P1A1E1L....

Take ELEVEN for a perfect example.  It's rare to see 4 Es in a word, but not so rare to find a single L, V, or N.  Check it first and chances are you can skip all the other letters completely.

***************

Edit: Scrabble letter values would actually be a good criteria for sorting order.  Z, X, Q at the front of the search list, A, E, I, O, U, S, T, and such as the last things compared.

I imagine you could eek out a considerable performance boost with minimal effort, implementing such a method.

[codeguy]

Steve, I was really impressed with your speedy performance, so I took the liberty of modifying it for exact same results and significantly faster performance.

Code: QB64: [Select]

1.  
2. SCREEN _NEWIMAGE(800, 600, 32)
3. CONST In$ = "thequickbrownfoxjumpedoverthelazydogdreamingofcountingsheepthinkingofbrownfoxjumpingoverdogs"
4. DIM wordcount AS LONG: wordcount = 0
5. DIM maxlength AS LONG: maxlength = 0
6. InLen = LEN(In$)
7.  
8.  
9. OPEN "WordList.txt" FOR BINARY AS #1
10. DO UNTIL EOF(1)
11.     LINE INPUT #1, junk$
12.     wordcount = wordcount + 1
13.     IF LEN(junk$) > maxlength THEN maxlength = LEN(junk$)
14. LOOP
15. SEEK 1, 1
16.  
17. TYPE WordLetters
18.     letter AS _UNSIGNED _BYTE
19.     count AS _UNSIGNED _BYTE
20. END TYPE
21. DIM Words(wordcount) AS STRING, Match(wordcount) AS LONG
22. DIM WordLetters(wordcount, 26) AS WordLetters
23. DIM Letters(97 TO 122) AS _UNSIGNED _BYTE
24. DIM ascii AS _UNSIGNED _BYTE
25. DIM KIterWordLettersCount AS LONG
26. DIM afound AS LONG: afound = 0
27. DIM w AS LONG
28. DIM i AS LONG
29. DIM j AS LONG
30. FOR i = 1 TO wordcount 'Load and prepare our word list and wordsearch array
31.     LINE INPUT #1, Words(i)
32.     FOR j = 1 TO LEN(Words(i))
33.         ascii = ASC(Words(i), j)
34.         SELECT CASE ascii
35.             CASE 97 TO 122
36.                 FOR KIterWordLettersCount = 1 TO WordLetters(i, 0).count
37.                     IF ascii = WordLetters(i, KIterWordLettersCount).letter THEN afound = KIterWordLettersCount: EXIT FOR
38.                 NEXT
39.                 IF afound THEN
40.                     WordLetters(i, afound).count = WordLetters(i, afound).count + 1 'add to the count of an existing letter
41.                     afound = 0
42.                 ELSE
43.                     WordLetters(i, 0).count = WordLetters(i, 0).count + 1 'increase the total count of letters
44.                     w = WordLetters(i, 0).count
45.                     WordLetters(i, w).letter = ascii 'save the letter
46.                     WordLetters(i, w).count = 1 'and count it 1 for the first time it appeared
47.                 END IF
48.             CASE ELSE
49.                 WordLetters(i, 0).count = 0 'invalidate words with non A-Z letters
50.                 EXIT FOR
51.         END SELECT
52.     NEXT
53. NEXT
54.  
55. FOR i = 1 TO InLen 'get the letters for the search string
56.     ascii = (ASC(In$, i) OR 32)
57.     Letters(ascii) = Letters(ascii) + 1
58. NEXT
59.  
60. DIM sl AS LONG
61. DIM wordfound AS LONG
62. t# = TIMER(.001)
63. DO UNTIL TIMER > t# + 5
64.     loopcount = loopcount + 1
65.     wordfound = 0 'reset our counter
66.  
67.     'THE MAIN SEARCH ROUTINE HERE
68.  
69.     FOR i = 1 TO wordcount 'now check every word for a match
70.         sl = WordLetters(i, 0).count 'search limit
71.         IF sl THEN
72.             FOR j = 1 TO sl
73.                 l = WordLetters(i, j).letter 'the letter in the word
74.                 IF Letters(l) < WordLetters(i, j).count THEN GOTO invalid 'it's impossible
75.             NEXT
76.             wordfound = wordfound + 1
77.             Match(wordfound) = i
78.         END IF
79.         invalid:
80.     NEXT
81.  
82.     'END OF THE MAIN SEARCH ROUTINE
83.  
84. LOOP
85.  
86. 'Print Results
87. FOR i = 1 TO wordfound
88.     PRINT Words(Match(i));
89.     IF i < wordfound THEN PRINT ","; ELSE PRINT
90. NEXT
91. PRINT
92. PRINT "DONE, with"; wordfound; "matches, with a speed of"; loopcount; "runs in 5 seconds."
93.  
94. END
95.  
96. 'And, if you want to see the secret behind this method, here's how we store and retrieve our data:
97.  
98. FOR i = 1 TO 10 'I think just showing how we track 10 words should be fine enough
99.     PRINT Words(i),
100.     FOR j = 1 TO WordLetters(i, 0).count
101.         PRINT CHR$(WordLetters(i, j).letter);
102.         PRINT WordLetters(i, j).count;
103.         PRINT ",";
104.     NEXT
105.     PRINT
106. NEXT
107.  
108. SLEEP
109.  
110. 'and here's the in$ and how its letter count holds up
111.  
112.  
113. PRINT In$
114. FOR i = 97 TO 122
115.     PRINT Letters(i);
116. NEXT
117. PRINT
118.  
119.  

On my humble machine, this represents a 45 loops/5s to 80+ loops/5s. Awesome work, Steve.

[SMcNeill]

Thanks for the kind words, Codeguy.  ;)

I've worked with datasets like this thousands of times in the past, so I've learned a few tricks for making them run efficiently.  The above was "speedy enough" for most needs, but there's methods quite a bit faster we could employ -- if we wanted to put forth the effort and alter our data somewhat.

Absolute fastest method I can imagine is by dividing our data into a tree structure....

For example, let's start with this tree:

A
AA
AAA

The first 3 entries on our list are those three.  By "treeing" our data, we say, "If I don't have A in the search phrase, then I can't have anything below A"

Eliminate "A" and we eliminate EVERYTHING with an A.  Our search list just dropped 50k words.

If we have A, but not AA, we've eliminated all words with AA from our search list...

It's a "cascading elimination" scheme and it's efficient, and fast, as heck!

The main issue with it is generating the lookup table to begin with...  Your data would need to be stored in a similar manner to this:
A (the word), 52154 (number of words with this eliminator), 2,3,4,5,6.... (Word list)
AA (next word), 2154 (number of words with this eliminator), 3,44,67,87,... (Word list)

**********************

It would bloat our data file considerably, depending on how many "eliminators" we want to use (why use anything more than 2 digits?  Longer words get more unique, the longer they become.), but it'd reduce our list of possible words to check by huge chunks at a time...

Fastest method I can think of, at the moment anyway.  ;)

(And if you look at my previous code, you can see where I was already generating lists which we could use for elimination purposes for single letters back with the original code in message #18.)

[bplus]

This letter count number formula thing lends itself obviously to anagrams, so yesterday I started modifying the file with BFormulas  a 26 chr$() string of counts for a, b, c... and all day long as I proceeded through with code tests, I had strongest feeling of Deja Vu  that I had done this before, that we, Steve too, had worked through this before, probably at Walter's forum. I check through old code posts 3 times and do not find anything on Anagrams... so I keep going reluctantly because it becomes more and more clear we had done this before.

Finally late last night, I do find the old code posted under Rosetta Folder! Yes, that's right because it started from a challenge from Rosetta stuff we were doing. Dang! I failed to remember the biggest hint of all, to sort by the BFormula$ key. Man what a time saver it is doing it that way, like a blink of the eye!

So if you find a word in your name or you are word building from a string, every anagram of it is automatically included. So along with filing the WordList with the BFormula key at start for saving allot of time, some more time saving could be made by listing all the anagrams that come with such a BFormula! WordList was reduced by 6,500+ lines by listing anagrams. Can't wait to try timed tests for generating words lists.