Text Only | Text with Attachments

QB64.org Forum

Active Forums => Programs => Topic started by: Zeppelin on October 07, 2018, 03:56:15 am

Title: WordCracker
Post by: Zeppelin on October 07, 2018, 03:56:15 am
Hey,
I run into a issue with my program.
Im trying to make a program that will, when given a string of 9 letters and 1 key letter to print out all the possible words using these letters.
For example:
9 Letters: ABCDEFGHI
Key Letter: A
PRINTS:
BAD
CAB
DEAF
etc....

I am using a .txt database full of words from the Oxford dictionary and each time I run the program nothing is output. I cant find the issue.

Thanks,
Zeppelin

Ps. The program and wordlist are attached below.
Title: Re: WordCracker
Post by: SMcNeill on October 07, 2018, 07:37:00 am
http://qb64.freeforums.net/thread/42/scrabble-word-maker -- Sounds like what you're wanting is basically the same thing I've did here.  Give it a look and see if it helps.
Title: Re: WordCracker
Post by: bplus on October 07, 2018, 10:33:25 am
Code: QB64: [Select]
  1. 'SPLIT UP LETTERS
  2. FOR n = 1 TO 9
  3.     ltr$(n) = MID$(in$, n, 1)
  5. PRINT LEN(ltr$)  '>>>>>>>>>>>> 0 !!!
  7.  

Code: QB64: [Select]
  1.             FOR x = 1 TO LEN(in$)  '<<<<<<<<<<<<<<<<<<<<<<< change to this?
  2.                 IF ltr$(x) = templtr$ THEN
  3.                     ltr$(x) = ""
  4.                     count = count + 1
  5.                 END IF
  6.             NEXT x
  7.  

OH!!! This is screwing you up too!

Code: QB64: [Select]
  1.     FOR n = 1 TO 9
  2.         ltr$(n) = MID$(in$, n, 1)
  3.     NEXT n
You are using n for the word index from the file, and then changing n here when resetting ltr$() array!!!
Title: Re: WordCracker
Post by: bplus on October 07, 2018, 10:47:30 am
OK now get stuff printed in reasonable time!
Code: QB64: [Select]
  1.  
  2. DIM word$(84100)
  4. DIM SHARED ltr$(9)  '<<<<<<<<<<< shared to debug
  5.  
  6. 'SET KEY AND LETTERS
  7. key$ = "a"
  8. in$ = "abcdefghi"
  9. lenin = LEN(in$) '<<<<<<<<<<< for faster processing
  10.  
  11. 'SPLIT UP LETTERS
  12. FOR n = 1 TO 9
  13.     ltr$(n) = MID$(in$, n, 1)
  15.  
  16. 'LOAD ALL WORDS FROM .TXT FILE
  17. PRINT "LOADING...."
  18. OPEN "WordList.txt" FOR INPUT AS #1  '<<<<<<<<< moved to more appropriate place
  20.     filecount = filecount + 1
  21.     INPUT #1, line$
  22.     word$(filecount) = line$
  26.  
  27.  
  28. 'RUN THROUGH WORDS
  29. FOR n = 1 TO filecount
  30.     findkey = INSTR(word$(n), key$)
  31.  
  32.     IF findkey THEN
  33.         FOR i = 1 TO LEN(word$(n))
  34.             templtr$ = MID$(word$(n), i, 1)
  35.             FOR x = 1 TO lenin '<<<<<<<<<<<<<<<<< main fix #1
  36.                 IF ltr$(x) = templtr$ THEN
  37.                     ltr$(x) = ""
  38.                     count = count + 1
  39.                 END IF
  40.                 'debugging
  41.                 'PRINT "Update: file word = "; word$(n); " and here is current letters crossed off: "; letters$
  42.                 'INPUT "OK press enter... "; wate$
  43.             NEXT x
  44.         NEXT i
  45.  
  46.         IF count = LEN(word$(n)) THEN
  47.             PRINT word$(n)
  48.         END IF
  49.     END IF
  50.  
  51.     FOR m = 1 TO 9  'main fix #2 n's  to m's
  52.         ltr$(m) = MID$(in$, m, 1)
  53.     NEXT m
  54.     count = 0
  56.  
  57. PRINT "DONE..."
  58.  
  59. 'for debugging
  60. FUNCTION letters$ ()
  61.     FOR i = 1 TO 9
  62.         b$ = b$ + ltr$(i)
  63.     NEXT
  64.     letters$ = "*" + b$ + "*"
  66.  

DONE? Looks like the logic was OK, just the variable assignments needed fixing.
Title: Re: WordCracker
Post by: codeguy on October 07, 2018, 02:09:15 pm
Gives you every permutation of letters, numbers, etc. If parray() is ordered, so is the output.
Code: QB64: [Select]
  1. WIDTH 80, 43
  2. DIM parray(0 TO 3) AS LONG
  3. FOR i = 0 TO UBOUND(parray)
  4.     parray(i) = i
  8. PRINT "permutations"
  9. Permute parray(), 0, UBOUND(parray), np
  11.     x$ = INKEY$
  12. LOOP UNTIL x$ > ""
  14.  
  15. SUB DisplayResults (PArray() AS LONG, start, finish, np AS DOUBLE)
  17. PRINT USING "#,###,###,###,###"; np;
  18. FOR i = LBOUND(parray) TO UBOUND(parray)
  19.     PRINT PArray(i);
  23.  
  24. SUB Rotate (parray() AS LONG, Start AS LONG, finish AS LONG)
  26. ts = parray(Start)
  27. FOR i = Start TO finish - 1
  28.     SWAP parray(i), parray(i + 1)
  30. parray(finish) = ts
  32.  
  33. SUB Permute (parray() AS LONG, start AS LONG, finish AS LONG, np AS DOUBLE)
  34. np = np + 1
  35. DisplayResults parray(), LBOUND(parray), UBOUND(parray), np
  36. IF start < finish THEN
  37.     DIM i AS LONG
  38.     DIM j AS LONG
  39.     FOR i = finish - 1 TO start STEP -1
  40.         FOR j = i + 1 TO finish
  41.             SWAP parray(i), parray(j)
  42.             Permute parray(), i + 1, finish, np
  43.         NEXT
  44.         Rotate parray(), i, finish
  45.     NEXT
  48.  
Title: Re: WordCracker
Post by: bplus on October 07, 2018, 02:52:59 pm
Hi codeguy,

I thought about permutations and then thought nah! won't work with real words at varying lengths.

But I could be wrong, wouldn't be first time.

Wanna race? You modify your code for checking for real words and I will see if I can optimize Zeppellin's code some more.... post in 24 hours?


Title: Re: WordCracker
Post by: SMcNeill on October 07, 2018, 03:32:28 pm
Quote from: bplus on October 07, 2018, 02:52:59 pm
Hi codeguy,

I thought about permutations and then thought nah! won't work with real words at varying lengths.

But I could be wrong, wouldn't be first time.

Wanna race? You modify your code for checking for real words and I will see if I can optimize Zeppellin's code some more.... post in 24 hours?

Here's how I'd go, I think:

First, reduce the word list to exclude any words > 9 digits.  No need to search for impossible combinations.
Then count letters.  Save these in an array WordLetters(1 TO WordCount,1 TO 26).

Then count letters in the target word.
Compare.  If target count > word count then it's a match!

************************
The word list is going to be rather limited (less than 50k words I'd imagine), and most searches will terminate rather quickly.  (need an "A", don't have any?  Quit the search at this point.) 

I really don't think you'd need to worry about optimizing for speed any more than that, to be honest.
Title: Re: WordCracker
Post by: bplus on October 07, 2018, 03:44:47 pm
Quote from: SMcNeill on October 07, 2018, 03:32:28 pm
Quote from: bplus on October 07, 2018, 02:52:59 pm
Hi codeguy,

I thought about permutations and then thought nah! won't work with real words at varying lengths.

But I could be wrong, wouldn't be first time.

Wanna race? You modify your code for checking for real words and I will see if I can optimize Zeppellin's code some more.... post in 24 hours?

Here's how I'd go, I think:

First, reduce the word list to exclude any words > 9 digits.  No need to search for impossible combinations.
Then count letters.  Save these in an array WordLetters(1 TO WordCount,1 TO 26).

Then count letters in the target word.
Compare.  If target count > word count then it's a match!

************************
The word list is going to be rather limited (less than 50k words I'd imagine), and most searches will terminate rather quickly.  (need an "A", don't have any?  Quit the search at this point.) 

I really don't think you'd need to worry about optimizing for speed any more than that, to be honest.

Hmm... I think you are saying permutations is slower too?

I am thinking this part:
Code: QB64: [Select]
  1. 'SET KEY AND LETTERS
  2. key$ = "a"
  3. in$ = "abcdefghi"
  4. lenin = LEN(in$) '<<<<<<<<<<< for faster processing
  5.  

key$ and in$ might be input into the program at run time, so the letters might not be nine and in$ might be real words too not segments of the alphabet. That's how I would use this code for word games or word game solving. And the real words might have 2 or 3 of the same letters. I was planning on optimizing for such events.
Title: Re: WordCracker
Post by: SMcNeill on October 07, 2018, 04:28:46 pm
Here's an easy fix for you to optimize your code and run it faster.  (An increase of about 15x faster on my machine.) 

I'll post 2 routines here so you can run them and compare for speed differences:

YOURS (modified to loop and run for a set amount of time -- 5 seconds in this case):
Code: QB64: [Select]
  1. DIM word$(84100)
  3. DIM SHARED ltr$(9) '<<<<<<<<<<< shared to debug
  4.  
  5. 'SET KEY AND LETTERS
  6. key$ = "a"
  7. in$ = "abcdefghi"
  8. lenin = LEN(in$) '<<<<<<<<<<< for faster processing
  9.  
  10. 'SPLIT UP LETTERS
  11. FOR n = 1 TO 9
  12.     ltr$(n) = MID$(in$, n, 1)
  14.  
  15.  
  16.  
  17. 'LOAD ALL WORDS FROM .TXT FILE
  18. PRINT "LOADING...."
  19. OPEN "WordList.txt" FOR INPUT AS #1 '<<<<<<<<< moved to more appropriate place
  20. filecount = 0
  22.     filecount = filecount + 1
  23.     INPUT #1, line$
  24.     word$(filecount) = line$
  27.  
  28.  
  29. t# = TIMER
  30.  
  31. timelimit = 5
  32. DO UNTIL TIMER > t# + timelimit
  33.     CLS
  34.     loopsran = loopsran + 1
  35.  
  36.  
  37.  
  38.     'RUN THROUGH WORDS
  39.     FOR n = 1 TO filecount
  40.         findkey = INSTR(word$(n), key$)
  41.  
  42.         IF findkey THEN
  43.             FOR i = 1 TO LEN(word$(n))
  44.                 templtr$ = MID$(word$(n), i, 1)
  45.                 FOR x = 1 TO lenin '<<<<<<<<<<<<<<<<< main fix #1
  46.                     IF ltr$(x) = templtr$ THEN
  47.                         ltr$(x) = ""
  48.                         count = count + 1
  49.                     END IF
  50.                     'debugging
  51.                     'PRINT "Update: file word = "; word$(n); " and here is current letters crossed off: "; letters$
  52.                     'INPUT "OK press enter... "; wate$
  53.                 NEXT x
  54.             NEXT i
  55.  
  56.             IF count = LEN(word$(n)) THEN
  57.                 PRINT word$(n)
  58.             END IF
  59.         END IF
  60.  
  61.         FOR m = 1 TO 9 'main fix #2 n's  to m's
  62.             ltr$(m) = MID$(in$, m, 1)
  63.         NEXT m
  64.         count = 0
  65.     NEXT n
  66.  
  67.     PRINT "DONE..."
  69. PRINT USING "###,###,###,###,### loops ran in ##.# seconds"; loopsran, timelimit
  70.  
  71.  
  72. 'for debugging
  73. FUNCTION letters$ ()
  74.     FOR i = 1 TO 9
  75.         b$ = b$ + ltr$(i)
  76.     NEXT
  77.     letters$ = "*" + b$ + "*"

Modified:
Code: QB64: [Select]
  1. DEFLNG A-Z
  2. DIM word$(84100)
  4. DIM SHARED ltr(9) '<<<<<<<<<<< shared to debug
  5.  
  6. 'SET KEY AND LETTERS
  7. key$ = "a"
  8. in$ = "abcdefghi"
  9. lenin = LEN(in$) '<<<<<<<<<<< for faster processing
  10.  
  11. 'SPLIT UP LETTERS
  12. FOR n = 1 TO 9
  13.     ltr(n) = ASC(in$, n)
  15.  
  16.  
  17.  
  18.  
  19.  
  20. 'LOAD ALL WORDS FROM .TXT FILE
  21. PRINT "LOADING...."
  22. OPEN "WordList.txt" FOR BINARY AS #1 '<<<<<<<<< moved to more appropriate place
  23. filecount = 0
  25.     LINE INPUT #1, line$
  26.     IF LEN(line$) < 10 THEN
  27.         filecount = filecount + 1
  28.         word$(filecount) = line$
  29.     END IF
  32.  
  33.  
  34. t# = TIMER
  35. timelimit = 5
  36. DO UNTIL TIMER > t# + timelimit
  37.     CLS
  38.     loopsran = loopsran + 1
  39.  
  40.  
  41.     'RUN THROUGH WORDS
  42.     FOR n = 1 TO filecount
  43.         findkey = INSTR(word$(n), key$)
  44.  
  45.         IF findkey THEN
  46.             FOR i = 1 TO LEN(word$(n))
  47.                 templtr = ASC(word$(n), i)
  48.                 FOR x = 1 TO lenin '<<<<<<<<<<<<<<<<< main fix #1
  49.                     IF ltr(x) = templtr THEN
  50.                         ltr(x) = 0
  51.                         count = count + 1
  52.                     END IF
  53.                 NEXT x
  54.                 IF count <> i GOTO skipmore
  55.             NEXT i
  56.  
  57.             IF count = LEN(word$(n)) THEN
  58.                 PRINT word$(n),
  59.             END IF
  60.         END IF
  61.  
  62.         skipmore:
  63.         FOR m = 1 TO 9 'main fix #2 n's  to m's
  64.             ltr(m) = ASC(in$, m)
  65.         NEXT m
  66.         count = 0
  67.     NEXT n
  68.  
  69.     PRINT "DONE..."
  71. PRINT USING "###,###,###,###,### loops ran in ##.# seconds"; loopsran, timelimit
  72.  
  73. 'for debugging
  74. FUNCTION letters$ ()
  75.     FOR i = 1 TO 9
  76.         b$ = b$ + ltr$(i)
  77.     NEXT
  78.     letters$ = "*" + b$ + "*"

Yours will run 22 times in 5 seconds, mine 324 times...

The changes?

#1) STRINGS are gone.  Why do we need them?  Especially, WHY DO WE NEED MID$??

When going for speed routines, ASC outperforms MID$(x$,y,1) every time, hands down!  This is a major performance boost.

#2) The word list is limited to begin with.

    IF LEN(line$) < 10 THEN
        filecount = filecount + 1
        word$(filecount) = line$
    END IF

You're not going to find 10 letter word matches with only 9 letter words.

#3) (Not timed, but a huge speed boost): Changed file from INPUT to BINARY and changed INPUT # to LINE INPUT#.  This makes loading the word list a whole heck of a lot faster.  Even faster would be to load it all at once and then parse the words out of it, but who wants to go through the trouble for all of the few microseconds we'd save in this case?

Simple little things, but the affect the performance like crazy.
Title: Re: WordCracker
Post by: SMcNeill on October 07, 2018, 05:01:34 pm
And, if we create a letter index for our words (since we're going to do a limit by key$), we can almost double the performance.  (Probably more for certain letters which aren't going to be indexed as much as "a" is, in this case.)

Code: QB64: [Select]
  1. DEFLNG A-Z
  2. DIM word$(84100)
  4. DIM SHARED ltr(9) '<<<<<<<<<<< shared to debug
  5. DIM backup(9)
  6. DIM keycount(97 TO 122, 50000) 'letter/index
  7.  
  8. 'SET KEY AND LETTERS
  9. key$ = "a"
  10. in$ = "abcdefghi"
  11. lenin = LEN(in$) '<<<<<<<<<<< for faster processing
  12.  
  13. 'SPLIT UP LETTERS
  14. FOR n = 1 TO 9
  15.     ltr(n) = ASC(in$, n)
  16.     backup(n) = ltr(n)
  18.  
  19.  
  20.  
  21.  
  22.  
  23. 'LOAD ALL WORDS FROM .TXT FILE
  24. PRINT "LOADING...."
  25. OPEN "WordList.txt" FOR BINARY AS #1 '<<<<<<<<< moved to more appropriate place
  26. filecount = 0
  28.     LINE INPUT #1, line$
  29.     IF LEN(line$) < 10 THEN
  30.         filecount = filecount + 1
  31.         word$(filecount) = line$
  32.         FOR i = 97 TO 122
  33.             IF INSTR(line$, CHR$(i)) THEN
  34.                 keycount(i, 0) = keycount(i, 0) + 1 'record 0 tells us how many there are for that letter
  35.                 keycount(i, keycount(i, 0)) = filecount 'add the word number to the proper index
  36.             END IF
  37.         NEXT
  38.     END IF
  41.  
  42.  
  43. t# = TIMER
  44. timelimit = 5
  45. DO UNTIL TIMER > t# + timelimit
  46.     CLS
  47.     loopsran = loopsran + 1
  48.  
  49.  
  50.     'RUN THROUGH WORDS
  51.     findkey = ASC(key$)
  52.     FOR n = 1 TO keycount(findkey, 0)
  53.         w$ = word$(keycount(findkey, n))
  54.         l = LEN(w$)
  55.         FOR i = 1 TO l
  56.             templtr = ASC(w$, i)
  57.             FOR x = 1 TO lenin '<<<<<<<<<<<<<<<<< main fix #1
  58.                 IF ltr(x) = templtr THEN
  59.                     ltr(x) = 0
  60.                     count = count + 1
  61.                 END IF
  62.             NEXT x
  63.             IF count <> i GOTO skipmore
  64.         NEXT i
  65.  
  66.         IF count = l THEN PRINT w$,
  67.  
  68.         skipmore:
  69.         FOR m = 1 TO 9 'main fix #2 n's  to m's
  70.             ltr(m) = backup(m)
  71.         NEXT m
  72.         count = 0
  73.     NEXT n
  74.  
  75.     PRINT "DONE..."
  77. PRINT USING "###,###,###,###,### loops ran in ##.# seconds"; loopsran, timelimit
  78.  
  79. 'for debugging
  80. FUNCTION letters$ ()
  81.     FOR i = 1 TO 9
  82.         b$ = b$ + ltr$(i)
  83.     NEXT
  84.     letters$ = "*" + b$ + "*"
  86.  

No need to check each and every word for a letter, if we already have built an index to tell us which words contain those letters.  ;)

(Current run time is 488 loops in 5 seconds on my PC, if you're curious about the actual number to compare improvement.)
Title: Re: WordCracker
Post by: bplus on October 07, 2018, 05:01:54 pm
Here's what I had in mind:
Code: QB64: [Select]
  1. ' WordCrack mod 1.bas B+ 2018-10-07
  2.  
  3. INPUT "Enter a string to build words from "; in$
  4. 'load words
  5. OPEN "WordList.txt" FOR BINARY AS #1
  6. gulp& = LOF(1)
  7. buff$ = STRING$(gulp&, " ")
  8. GET #1, , buff$
  10. REDIM word$(0)
  11. Split buff$, CHR$(10), word$()
  12. filecount& = UBOUND(word$)
  13. 'RUN THROUGH WORDS
  14. FOR n& = 0 TO filecount&
  15.     c$ = in$
  16.     OK% = -1
  17.     FOR i% = 1 TO LEN(word$(n&))
  18.         p% = INSTR(c$, MID$(word$(n&), i%, 1))
  19.         IF p% = 0 THEN
  20.             OK% = 0: EXIT FOR
  21.         ELSE
  22.             MID$(c$, p%, 1) = "+"
  23.         END IF
  24.     NEXT
  25.     IF OK% THEN PRINT word$(n&); ", ";
  27. PRINT "DONE..."
  28.  
  29.  
  30. SUB Split (mystr AS STRING, delim AS STRING, arr() AS STRING)
  31.     ' bplus modifications of Galleon fix of Bulrush Split reply #13
  32.     ' http://www.[abandoned, outdated and now likely malicious qb64 dot net website - don’t go there]/forum/index.php?topic=1612.0
  33.     ' this sub further developed and tested here: \test\Strings\Split test.bas
  34.     DIM copy AS STRING, p AS LONG, curpos AS LONG, arrpos AS LONG, lc AS LONG, dpos AS LONG
  35.     copy = mystr 'make copy since we are messing with mystr
  36.     'special case if delim is space, probably want to remove all excess space
  37.     IF delim = " " THEN
  38.         copy = RTRIM$(LTRIM$(copy))
  39.         p = INSTR(copy, "  ")
  40.         WHILE p > 0
  41.             copy = MID$(copy, 1, p - 1) + MID$(copy, p + 1)
  42.             p = INSTR(copy, "  ")
  43.         WEND
  44.     END IF
  45.     curpos = 1
  46.     arrpos = 0
  47.     lc = LEN(copy)
  48.     dpos = INSTR(curpos, copy, delim)
  49.     DO UNTIL dpos = 0
  50.         arr(arrpos) = MID$(copy, curpos, dpos - curpos)
  51.         arrpos = arrpos + 1
  52.         REDIM _PRESERVE arr(arrpos + 1) AS STRING
  53.         curpos = dpos + LEN(delim)
  54.         dpos = INSTR(curpos, copy, delim)
  55.     LOOP
  56.     arr(arrpos) = MID$(copy, curpos)
  57.     REDIM _PRESERVE arr(arrpos) AS STRING
  59.  

Looks pretty simple to me.

Yes, Binary load most significant speed improvement! :)
Title: Re: WordCracker
Post by: SMcNeill on October 07, 2018, 05:26:23 pm
And another small modification of the original gives us another decent speed boost:

Code: QB64: [Select]
  1. DEFLNG A-Z
  2. DIM word$(84100)
  3. DIM keys
  4. DIM SHARED ltr(1 TO 9) '<<<<<<<<<<< shared to debug
  5. DIM backup(1 TO 9)
  6. DIM keycount(97 TO 122, 50000) 'letter/index
  7. DIM m1 AS _MEM, m2 AS _MEM 'just for quick array restoration
  8. m1 = _MEM(ltr()): m2 = _MEM(backup())
  9.  
  10. 'SET KEY AND LETTERS
  11. keys = ASC("a")
  12. in$ = "abcdefghi"
  13. lenin = LEN(in$) '<<<<<<<<<<< for faster processing
  14.  
  15. 'SPLIT UP LETTERS
  16. FOR n = 1 TO 9
  17.     ltr(n) = ASC(in$, n)
  19. _MEMPUT m2, m2.OFFSET, ltr()
  20.  
  21.  
  22. 'LOAD ALL WORDS FROM .TXT FILE
  23. PRINT "LOADING...."
  24. OPEN "WordList.txt" FOR BINARY AS #1 '<<<<<<<<< moved to more appropriate place
  25. filecount = 0
  27.     LINE INPUT #1, line$
  28.     IF LEN(line$) < 10 THEN
  29.         filecount = filecount + 1
  30.         word$(filecount) = line$
  31.         FOR i = 97 TO 122
  32.             IF INSTR(line$, CHR$(i)) THEN
  33.                 keycount(i, 0) = keycount(i, 0) + 1 'record 0 tells us how many there are for that letter
  34.                 keycount(i, keycount(i, 0)) = filecount 'add the word number to the proper index
  35.             END IF
  36.         NEXT
  37.     END IF
  40.  
  41.  
  42. t# = TIMER
  43. timelimit = 5
  44.  
  45.  
  46. DO UNTIL TIMER > t# + timelimit
  47.     CLS
  48.     loopsran = loopsran + 1
  49.  
  50.  
  51.     'RUN THROUGH WORDS
  52.     FOR n = 1 TO keycount(keys, 0)
  53.         w$ = word$(keycount(keys, n))
  54.         l = LEN(w$)
  55.         FOR i = 1 TO l
  56.             templtr = ASC(w$, i)
  57.             FOR x = 1 TO lenin '<<<<<<<<<<<<<<<<< main fix #1
  58.                 IF ltr(x) = templtr THEN
  59.                     ltr(x) = 0
  60.                     count = count + 1
  61.                     EXIT FOR
  62.                 END IF
  63.             NEXT x
  64.             IF count <> i GOTO skipmore
  65.         NEXT i
  66.  
  67.         PRINT w$,
  68.  
  69.         skipmore:
  70.         $CHECKING:OFF
  71.         _MEMPUT m1, m1.OFFSET, backup()
  72.         $CHECKING:ON
  73.         count = 0
  74.     NEXT n
  75.  
  76.     PRINT "DONE..."
  78. PRINT USING "###,###,###,###,### loops ran in ##.# seconds"; loopsran, timelimit
  79.  
  80. 'for debugging
  81. FUNCTION letters$ ()
  82.     FOR i = 1 TO 9
  83.         b$ = b$ + ltr$(i)
  84.     NEXT
  85.     letters$ = "*" + b$ + "*"
  87.  

Instead of a FOR...LOOP to reset the search list, I simply restored it with a backup array with _MEM.

From:

        FOR m = 1 TO 9 'main fix #2 n's  to m's
            ltr$(m) = MID$(in$, m, 1)
        NEXT m

To:

        $CHECKING:OFF
        _MEMPUT m1, m1.OFFSET, backup()
        $CHECKING:ON

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

I'm now getting ~900 runs in a short 5 second period.  I'd call that fast enough for just about anything I'd need to use it for.  (And a nice improvement from the original 22 runs in 5 seconds.)  ;)
Title: Re: WordCracker
Post by: bplus on October 07, 2018, 05:40:28 pm
I am getting 363 cycles for abcdefghi in 5 secs with Windows 10 Intel Core i5 processor without any preprocessing of the word$() array.
Title: Re: WordCracker
Post by: bplus on October 07, 2018, 07:24:40 pm
Steve your last code improvement is running 1067 or so loops on my machine.

Yeah OK, checking word length first does make sense and adds another 100 loops in 5 secs:
Code: QB64: [Select]
  1. ' WordCrack mod 1.bas B+ 2018-10-07
  2.  
  3. ' now with timer mod
  4.  
  5. 'INPUT "Enter a string to build words from "; in$
  6. in$ = "abcdefghi"
  7. in$ = LCASE$(in$)
  8. lenin = LEN(in$)
  9.  
  10. 'load words
  11. OPEN "WordList.txt" FOR BINARY AS #1
  12. gulp& = LOF(1)
  13. buff$ = STRING$(gulp&, " ")
  14. GET #1, , buff$
  16. REDIM word$(0)
  17. Split buff$, CHR$(10), word$()
  18. filecount& = UBOUND(word$)
  19. start! = TIMER
  20. WHILE TIMER - start! < 5
  21.     'RUN THROUGH WORDS
  22.     FOR n& = 0 TO filecount&
  23.         IF LEN(word$(n&)) <= lenin THEN
  24.             c$ = in$
  25.             OK% = -1
  26.             FOR i% = 1 TO LEN(word$(n&))
  27.                 p% = INSTR(c$, MID$(word$(n&), i%, 1))
  28.                 IF p% = 0 THEN
  29.                     OK% = 0: EXIT FOR
  30.                 ELSE
  31.                     MID$(c$, p%, 1) = "+"
  32.                 END IF
  33.             NEXT
  34.             IF OK% THEN PRINT word$(n&); ", ";
  35.         END IF
  36.     NEXT
  37.     counter = counter + 1
  39. PRINT "Loop count in 5 secs ="; counter
  41.  
  42. SUB Split (mystr AS STRING, delim AS STRING, arr() AS STRING)
  43.     ' bplus modifications of Galleon fix of Bulrush Split reply #13
  44.     ' http://www.[abandoned, outdated and now likely malicious qb64 dot net website - don’t go there]/forum/index.php?topic=1612.0
  45.     ' this sub further developed and tested here: \test\Strings\Split test.bas
  46.     DIM copy AS STRING, p AS LONG, curpos AS LONG, arrpos AS LONG, lc AS LONG, dpos AS LONG
  47.     copy = mystr 'make copy since we are messing with mystr
  48.     'special case if delim is space, probably want to remove all excess space
  49.     IF delim = " " THEN
  50.         copy = RTRIM$(LTRIM$(copy))
  51.         p = INSTR(copy, "  ")
  52.         WHILE p > 0
  53.             copy = MID$(copy, 1, p - 1) + MID$(copy, p + 1)
  54.             p = INSTR(copy, "  ")
  55.         WEND
  56.     END IF
  57.     curpos = 1
  58.     arrpos = 0
  59.     lc = LEN(copy)
  60.     dpos = INSTR(curpos, copy, delim)
  61.     DO UNTIL dpos = 0
  62.         arr(arrpos) = MID$(copy, curpos, dpos - curpos)
  63.         arrpos = arrpos + 1
  64.         REDIM _PRESERVE arr(arrpos + 1) AS STRING
  65.         curpos = dpos + LEN(delim)
  66.         dpos = INSTR(curpos, copy, delim)
  67.     LOOP
  68.     arr(arrpos) = MID$(copy, curpos)
  69.     REDIM _PRESERVE arr(arrpos) AS STRING
  71.  
Title: Re: WordCracker
Post by: codeguy on October 08, 2018, 12:23:37 am
generates strings and retrieves matches for permutations of letters creating words up to 8 characters long. in order too. On my humble machine, (39/64)s. Because permutations are generated in lexical order AND the wordlist is in lexical order (both ascending), this becomes nothing more than a simple merge/find algorithm, the same used for batch database updates. Quick? Judge for yourself. found 58 matches in 322560 variable-length permutations. I am uncertain how many loops/second this code executes, but I'm gonna say it's 322560/(39/64), roughly 529329 trials/second on my humble 2.16GHz machine. On my machine, this will also execute about 8 times, perhaps a wee bit more. I am uncertain how fast Steve's CPU is, but mine is no speed demon nor is it super slow. Mine is roughly 240,000 trials/GHz.
Code: QB64: [Select]
  1. WIDTH 80, 43
  2. DIM parray(0 TO 7) AS LONG '* checks words up to 8 characters long
  3. theword$ = "sequoias"
  4. FOR i = 0 TO UBOUND(parray)
  5.     parray(i) = ASC(theword$, i + 1)
  7. s& = LBOUND(parray)
  8. h& = UBOUND(parray)
  10.     an& = s& + 1
  11.     FOR q& = an& TO h&
  12.         IF parray(q&) < parray(s&) THEN
  13.             SWAP parray(q&), parray(s&)
  14.         END IF
  15.     NEXT
  16.     s& = an&
  17. LOOP WHILE s& <= h&
  20. Wlist% = FREEFILE
  21. OPEN ".\wordlist.txt" FOR BINARY AS Wlist%
  22. PRINT LOF(Wlist%)
  23. chunk$ = INPUT$(LOF(Wlist%), Wlist%)
  24. CLOSE Wlist%
  25. REDIM words$(0 TO 999999)
  26. Wct& = 0
  27. FOR u& = 1 TO LEN(chunk$)
  28.     IF ASC(chunk$, u&) = 10 OR u& > LEN(chunk$) THEN
  29.         IF LEN(w$) <= 8 THEN
  30.             words$(Wct&) = w$
  31.             PRINT w$; Wct&
  32.             Wct& = Wct& + 1
  33.         END IF
  34.         w$ = ""
  35.     ELSE
  36.         w$ = w$ + MID$(chunk$, u&, 1)
  37.     END IF
  39. chunk$ = ""
  40. WordsIndex& = 0
  41. nmatches& = 0
  42. '_DELAY 60
  43. t! = TIMER(.001)
  44. PRINT "permutations"
  45. Permute parray(), 0, UBOUND(parray), np#, words$(), WordIndex&, Wct&, nmatches&, npermtrials#
  46. f! = TIMER(.001)
  47. PRINT f! - t!; nmatches&; np#; npermtrials#
  49.     x$ = INKEY$
  50. LOOP UNTIL x$ > ""
  52.  
  53. SUB DisplayResults (PArray() AS LONG, start, finish, np AS DOUBLE)
  54.     DIM i AS LONG
  55.     PRINT USING "#,###,###,###,###"; np;
  56.     FOR i = LBOUND(parray) TO UBOUND(parray)
  57.         PRINT PArray(i);
  58.     NEXT
  59.     PRINT
  61.  
  62. SUB Rotate (parray() AS LONG, Start AS LONG, finish AS LONG)
  63.     DIM ts AS LONG
  64.     ts = parray(Start)
  65.     FOR i = Start TO finish - 1
  66.         SWAP parray(i), parray(i + 1)
  67.     NEXT
  68.     parray(finish) = ts
  70.  
  71. SUB Permute (parray() AS LONG, start AS LONG, finish AS LONG, np AS DOUBLE, words$(), index&, wct&, matchcount&, NPermsTried#)
  72.     np = np + 1
  73.     IF index& < wct& THEN
  74.         FOR a& = 0 TO UBOUND(parray)
  75.             v$ = array2word$(parray(), LBOUND(parray), LBOUND(parray) + a&)
  76.             DO
  77.                 IF words$(index&) < v$ THEN
  78.                     index& = index& + 1
  79.                 ELSE
  80.                     NPermsTried# = NPermsTried# + 1
  81.                     IF words$(index&) = v$ THEN
  82.                         matchcount& = matchcount& + 1
  83.                         PRINT v$; ":match:"; words$(index&); index&; matchcount&
  84.                     END IF
  85.                     EXIT DO
  86.                 END IF
  87.             LOOP
  88.         NEXT
  89.     ELSE
  90.         EXIT SUB
  91.     END IF
  92.     IF start < finish THEN
  93.         DIM i AS LONG
  94.         DIM j AS LONG
  95.         FOR i = finish - 1 TO start STEP -1
  96.             FOR j = i + 1 TO finish
  97.                 SWAP parray(i), parray(j)
  98.                 Permute parray(), i + 1, finish, np, words$(), index&, wct&, matchcount&, NPermsTried#
  99.             NEXT
  100.             Rotate parray(), i, finish
  101.         NEXT
  102.     END IF
  104.  
  105. FUNCTION array2word$ (parray() AS LONG, start AS LONG, finish AS LONG)
  106.     m$ = SPACE$(finish - start + 1)
  107.     POSITION& = 1
  108.     FOR z& = start TO finish
  109.         MID$(m$, POSITION&) = CHR$(parray(z&))
  110.         POSITION& = POSITION& + 1
  111.     NEXT
  112.     array2word$ = m$
  114.  
Title: Re: WordCracker
Post by: Zeppelin on October 08, 2018, 01:11:38 am
Wow. Thanks everyone for their responses. Thanks for the performance tips (It really helps. I still learning).
Its nice to see everyone trying to out-do each others programs.

I have to say SMcNeill..... what do you do with your life.

Just joking man. Unbelievably fast program by the way.

Thanks everyone,
Zeppelin
Title: Re: WordCracker
Post by: bplus on October 08, 2018, 10:10:05 am
Made some more improvements like getting rid of blank word and preprocessed file according to number of letters input to build words from. "abcdefghi" now runs around 518 loops in 5 secs and finds 351 words from "Steve McNeil" input. Steve's code crashes if "Steve McNeil" is input. ;-))
Code: QB64: [Select]
  1. _TITLE "WordCrack mod 2 with preprocessing.bas B+ 2018-10-08"
  2.  
  3. ' now with timer mod and preprocessing of word file to length of in$
  4.  
  5. 'INPUT "Enter a string to build words from "; inp$
  6. inp$ = "Steve McNeil"
  7. in$ = LCASE$(inp$)
  8. lenin = LEN(in$)
  9.  
  10. 'load words
  11. OPEN "WordList.txt" FOR BINARY AS #1
  12. gulp& = LOF(1)
  13. buff$ = STRING$(gulp&, " ")
  14. GET #1, , buff$
  16. REDIM longWords$(0)
  17. Split buff$, CHR$(10), longWords$()
  18.  
  19. 'preprocess word list, use only words <= the build words string
  20. DIM word$(84100)
  21. FOR i& = 0 TO UBOUND(longWords$)
  22.     IF LEN(longWords$(i&)) <= lenin THEN
  23.         IF LTRIM$(longWords$(i&)) <> "" THEN
  24.             IF ASC(longWords$(i&)) > 96 AND ASC(longWords$(i&)) < 123 THEN
  25.                 wi& = wi& + 1
  26.                 word$(wi&) = longWords$(i&)
  27.             END IF
  28.         END IF
  29.     END IF
  31.  
  32. 'NOW do the loop count, should add lots of loops checking one less thing per loop and looping less times
  33. start! = TIMER
  34. WHILE TIMER - start! < 5
  35.     'RUN THROUGH WORDS
  36.     foundWords% = 0
  37.     FOR n& = 0 TO wi&
  38.         c$ = in$
  39.         OK% = -1
  40.         FOR i% = 1 TO LEN(word$(n&))
  41.             p% = INSTR(c$, MID$(word$(n&), i%, 1))
  42.             IF p% = 0 THEN
  43.                 OK% = 0: EXIT FOR
  44.             ELSE
  45.                 MID$(c$, p%, 1) = "+"
  46.             END IF
  47.         NEXT
  48.         IF OK% THEN foundWords% = foundWords% + 1: PRINT word$(n&); ", ";
  49.     NEXT
  50.     counter% = counter% + 1
  52. PRINT: PRINT: PRINT "Found:"; foundWords%; "words in "; CHR$(34); inp$; CHR$(34); ","; counter%; "times in 5 secs."
  54.  
  55. SUB Split (mystr AS STRING, delim AS STRING, arr() AS STRING)
  56.     ' bplus modifications of Galleon fix of Bulrush Split reply #13
  57.     ' http://www.[abandoned, outdated and now likely malicious qb64 dot net website - don’t go there]/forum/index.php?topic=1612.0
  58.     ' this sub further developed and tested here: \test\Strings\Split test.bas
  59.     DIM copy AS STRING, p AS LONG, curpos AS LONG, arrpos AS LONG, lc AS LONG, dpos AS LONG
  60.     copy = mystr 'make copy since we are messing with mystr
  61.     'special case if delim is space, probably want to remove all excess space
  62.     IF delim = " " THEN
  63.         copy = RTRIM$(LTRIM$(copy))
  64.         p = INSTR(copy, "  ")
  65.         WHILE p > 0
  66.             copy = MID$(copy, 1, p - 1) + MID$(copy, p + 1)
  67.             p = INSTR(copy, "  ")
  68.         WEND
  69.     END IF
  70.     curpos = 1
  71.     arrpos = 0
  72.     lc = LEN(copy)
  73.     dpos = INSTR(curpos, copy, delim)
  74.     DO UNTIL dpos = 0
  75.         arr(arrpos) = MID$(copy, curpos, dpos - curpos)
  76.         arrpos = arrpos + 1
  77.         REDIM _PRESERVE arr(arrpos + 1) AS STRING
  78.         curpos = dpos + LEN(delim)
  79.         dpos = INSTR(curpos, copy, delim)
  80.     LOOP
  81.     arr(arrpos) = MID$(copy, curpos)
  82.     REDIM _PRESERVE arr(arrpos) AS STRING
  84.  

PS codeguy's code is going to crash also if only permutations up to 8 letters is allowed, without even checking I can see that.

Less than 4 hours to go. Will Steve fix his code in time? Stay tuned...  ;)
Title: Re: WordCracker
Post by: bplus on October 08, 2018, 10:23:45 am
Steve wins again! My name only has 271 words in it. :) (but none are vile)
Title: Re: WordCracker
Post by: SMcNeill on October 08, 2018, 11:27:46 am
Modified to run with any size string (even "Steve McNeil"; which, btw, is named WRONG.  /cry!!):

Code: QB64: [Select]
  1. WIDTH 80, 50
  2. DEFLNG A-Z
  3. 'SET KEY AND LETTERS
  4. keys = 0 ' ASC("S") OR &B00100000 '0 for no key limiter, otherwise use the ASC("letter") OR &B00100000 to force lowercase value
  5. in$ = LCASE$("SteveMcNeil")
  6. lenin = LEN(in$) '<<<<<<<<<<< for faster processing
  7.  
  8.  
  9. DIM word$(84100)
  10. DIM SHARED ltr(1 TO lenin) '<<<<<<<<<<< shared to debug
  11. DIM backup(1 TO lenin)
  12. DIM keycount(97 TO 122, 60000) 'letter/index
  13. DIM m1 AS _MEM, m2 AS _MEM 'just for quick array restoration
  14. m1 = _MEM(ltr()): m2 = _MEM(backup())
  15.  
  16.  
  17. 'SPLIT UP LETTERS
  18. FOR n = 1 TO lenin
  19.     ltr(n) = ASC(in$, n) OR &B00100000
  21. _MEMPUT m2, m2.OFFSET, ltr()
  22.  
  23.  
  24. 'LOAD ALL WORDS FROM .TXT FILE
  25. PRINT "LOADING...."
  26. OPEN "WordList.txt" FOR BINARY AS #1 '<<<<<<<<< moved to more appropriate place
  27. filecount = 0
  29.     LINE INPUT #1, line$
  30.     IF LEN(line$) <= lenin THEN
  31.         filecount = filecount + 1
  32.         word$(filecount) = line$
  33.         FOR i = 97 TO 122
  34.             IF INSTR(line$, CHR$(i)) THEN
  35.                 keycount(i, 0) = keycount(i, 0) + 1 'record 0 tells us how many there are for that letter
  36.                 keycount(i, keycount(i, 0)) = filecount 'add the word number to the proper index
  37.             END IF
  38.         NEXT
  39.     END IF
  42.  
  43.  
  44. t# = TIMER
  45. timelimit = 5
  46.  
  47.  
  48. DO UNTIL TIMER > t# + timelimit
  49.     CLS
  50.     loopsran = loopsran + 1
  51.     totalcount = 0
  52.  
  53.  
  54.     'RUN THROUGH WORDS
  55.     IF keys = 0 THEN k = filecount ELSE k = keycount(keys, 0)
  56.     FOR n = 1 TO k
  57.         w$ = word$(n)
  58.         FOR i = 1 TO LEN(w$)
  59.             templtr = ASC(w$, i)
  60.             FOR x = 1 TO lenin
  61.                 IF ltr(x) = templtr THEN ltr(x) = 0: GOTO stillvalid
  62.             NEXT x
  63.             GOTO skipmore
  64.             stillvalid:
  65.         NEXT i
  66.  
  67.         totalcount = totalcount + 1
  68.         PRINT w$,
  69.  
  70.         skipmore:
  71.         $CHECKING:OFF
  72.         _MEMPUT m1, m1.OFFSET, backup()
  73.         $CHECKING:ON
  74.         count = 0
  75.     NEXT n
  76.  
  77.     PRINT "DONE..."
  79. PRINT USING "###,###,###,###,### loops ran in ##.# seconds"; loopsran, timelimit
  80. PRINT totalcount; "matches found for "; in$

About 300 loops in 5 seconds with the longer name giving us more letters to check against.  Oddly enough, my list is only counting 350 words for us, and not 351 as Bplus says his is generating.  Is this a glitch in my counting method?  His?  Or is somebody leaving a word out, or including a false positive?   

I dunno!

Some digging will be required to see where that extra word comes from, and what the heck it is!  :P
Title: Re: WordCracker
Post by: SMcNeill on October 08, 2018, 11:41:33 am
Testing shows that Bplus is wrong.   :D

Compare the 2 file dumps (the first is mine, the second is Bplus's), and it's immediately obvious what the issue is, right at the very top of the file -- a BLANK word.  There's 350 words, with an extra "" at the top of his list.   

Steve wins again!  ;D
Title: Re: WordCracker
Post by: bplus on October 08, 2018, 12:09:55 pm
Cra...

Sorry about your name Steve, my eyes are going bad.

Wait,  , isn't a word? ;-))  (where the heck did that come from?)

Thanks for heads up!

Title: Re: WordCracker
Post by: SMcNeill on October 08, 2018, 12:44:28 pm
Quote from: bplus on October 08, 2018, 12:09:55 pm
Cra...

Sorry about your name Steve, my eyes are going bad.

No worries; it's the story of my life...  My family has lived here since forever, so when it was time to name the roads, the powers that be named the road here after my family...

And, spelt it wrong!

No kidding!!

You can find me on McNeil Hill Rd, still laughing at the irony of being immortalized incorrectly.

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

And funniest thing?? 

The local government says we can change the name, as long as WE are willing to pay the $$$$$ to change the road signs.

Two little signs, only needing an extra "l" in them, and yet to comply to state standards, they cost over $2600 each!

It's no damn wonder our government is broke, trying to hit such costs just to stay within regulation.  On a low traveled, rural as heck road like mine, a $2.00 slab of wood, $1 can of white paint, and $1 can of black paint for lettering, would be more than sufficient to serve the needs of the community...

And yet...  The sign has to be a certain gauge steel, painted X coats of reflective green, with Y coats of Z-size white paint, mixed with XX percent reflective beads....

(And, just in case you want to see how nutty regulations are for government stuff, here's the regs on signs:  http://www.vdot.virginia.gov/business/resources/TED/final_MUTCD/2013_sup/Revision_1_Part_2_Signs.pdf --- Well, it's the BASIC regulations.  There are 14 supplements, with 5 supplements to supplement the supplements also...l)
Title: Re: WordCracker
Post by: Cobalt on October 08, 2018, 01:04:32 pm
Quote from: SMcNeill on October 08, 2018, 12:44:28 pm
And funniest thing?? 

The local government says we can change the name, as long as WE are willing to pay the $$$$$ to change the road signs.

Two little signs, only needing an extra "l" in them, and yet to comply to state standards, they cost over $2600 each!

It's no damn wonder our government is broke, trying to hit such costs just to stay within regulation.  On a low traveled, rural as heck road like mine, a $2.00 slab of wood, $1 can of white paint, and $1 can of black paint for lettering, would be more than sufficient to serve the needs of the community...

And yet...  The sign has to be a certain gauge steel, painted X coats of reflective green, with Y coats of Z-size white paint, mixed with XX percent reflective beads....

(And, just in case you want to see how nutty regulations are for government stuff, here's the regs on signs:  http://www.vdot.virginia.gov/business/resources/TED/final_MUTCD/2013_sup/Revision_1_Part_2_Signs.pdf --- Well, it's the BASIC regulations.  There are 14 supplements, with 5 supplements to supplement the supplements also...l)

just do what the kids do, take some paint and add your own extra 'l', find some spray paint thats lying around it costs you nothing! unless you get caught and fined. or go the extra mile with some masking tape so it looks better!
175 pages, does that meet novel requirements too?
Title: Re: WordCracker
Post by: bplus on October 08, 2018, 03:29:34 pm
Yep, for shorter strings Steve's loop count is a winner!

But for longer strings this current version is a winner.
Code: QB64: [Select]
  1. WIDTH 80, 50
  2. _TITLE "WordCrack mod 2 with preprocessing.bas B+ 2018-10-08"
  3.  
  4. ' now with timer mod and preprocessing of word file to length of in$
  5.  
  6. ' fix the extra "" word being printed   12:28 PM
  7. ' use same print method as Steve's code, change type for wordsFound
  8.  
  9. 'INPUT "Enter a string to build words from "; inp$
  10. inp$ = "thequickbrownfoxjumpedoverthelazydog"
  11. 'inp$ = "thequickbrownfoxjumpedoverthelazydogdreamingofcountingsheep"
  12. 'inp$ = "thequickbrownfoxjumpedoverthelazydogdreamingofcountingsheepthinkingofbrownfoxjumpingoverdogs"
  13. in$ = LCASE$(inp$)
  14. lenin = LEN(in$)
  15.  
  16. 'load words
  17. OPEN "WordList.txt" FOR BINARY AS #1
  18. gulp& = LOF(1)
  19. buff$ = STRING$(gulp&, " ")
  20. GET #1, , buff$
  22. REDIM longWords$(0)
  23. Split buff$, CHR$(10), longWords$()
  24.  
  25. 'preprocess word list, use only words <= the build words string
  26. DIM word$(84100)
  27. FOR i& = 0 TO UBOUND(longWords$)
  28.     IF LEN(longWords$(i&)) <= lenin THEN
  29.         IF LTRIM$(longWords$(i&)) <> "" THEN
  30.             IF ASC(longWords$(i&)) > 96 AND ASC(longWords$(i&)) < 123 THEN
  31.                 wi& = wi& + 1
  32.                 word$(wi&) = longWords$(i&)
  33.             END IF
  34.         END IF
  35.     END IF
  37.  
  38. 'NOW do the loop count, should add lots of loops checking one less thing per loop and looping less times
  39. start! = TIMER
  40. WHILE TIMER - start! < 5
  41.     'RUN THROUGH WORDS
  42.     foundWords& = 0
  43.     FOR n& = 1 TO wi& '<<<<<<<<<<<<<<<<<<<  fixed from 0 to 1
  44.         c$ = in$
  45.         OK% = -1
  46.         FOR i% = 1 TO LEN(word$(n&))
  47.             p% = INSTR(c$, MID$(word$(n&), i%, 1))
  48.             IF p% = 0 THEN
  49.                 OK% = 0: EXIT FOR
  50.             ELSE
  51.                 MID$(c$, p%, 1) = "+"
  52.             END IF
  53.         NEXT
  54.         IF OK% THEN foundWords& = foundWords& + 1: PRINT word$(n&),
  55.     NEXT
  56.     counter& = counter& + 1
  58. PRINT: PRINT: PRINT "Found:"; foundWords&; "words in "; CHR$(34); inp$; CHR$(34); ","; counter&; "times in 5 secs."
  60.  
  61. SUB Split (mystr AS STRING, delim AS STRING, arr() AS STRING)
  62.     ' bplus modifications of Galleon fix of Bulrush Split reply #13
  63.     ' http://www.[abandoned, outdated and now likely malicious qb64 dot net website - don’t go there]/forum/index.php?topic=1612.0
  64.     ' this sub further developed and tested here: \test\Strings\Split test.bas
  65.     DIM copy AS STRING, p AS LONG, curpos AS LONG, arrpos AS LONG, lc AS LONG, dpos AS LONG
  66.     copy = mystr 'make copy since we are messing with mystr
  67.     'special case if delim is space, probably want to remove all excess space
  68.     IF delim = " " THEN
  69.         copy = RTRIM$(LTRIM$(copy))
  70.         p = INSTR(copy, "  ")
  71.         WHILE p > 0
  72.             copy = MID$(copy, 1, p - 1) + MID$(copy, p + 1)
  73.             p = INSTR(copy, "  ")
  74.         WEND
  75.     END IF
  76.     curpos = 1
  77.     arrpos = 0
  78.     lc = LEN(copy)
  79.     dpos = INSTR(curpos, copy, delim)
  80.     DO UNTIL dpos = 0
  81.         arr(arrpos) = MID$(copy, curpos, dpos - curpos)
  82.         arrpos = arrpos + 1
  83.         REDIM _PRESERVE arr(arrpos + 1) AS STRING
  84.         curpos = dpos + LEN(delim)
  85.         dpos = INSTR(curpos, copy, delim)
  86.     LOOP
  87.     arr(arrpos) = MID$(copy, curpos)
  88.     REDIM _PRESERVE arr(arrpos) AS STRING
  90.  
  91.  

inp$ = "thequickbrownfoxjumpedoverthelazydog" > 74 loops versus 65 Steve's
'inp$ = "thequickbrownfoxjumpedoverthelazydogdreamingofcountingsheep" > 41 versus 36-37 Steve's
'inp$ = "thequickbrownfoxjumpedoverthelazydogdreamingofcountingsheepthinkingofbrownfoxjumpingoverdogs" > 37 versus 32-33 Steve's
Title: Re: WordCracker
Post by: SMcNeill on October 08, 2018, 03:40:47 pm
Quote
Yep, for shorter strings Steve's loop count is a winner!

But for longer strings this current version is a winner.

When dealing with such long strings, I'd definitely go a different route.  Read letters.  Preset an array.   Just compare letter counts.  I imagine it'd be a ton faster than how we're currently doing it, but that's because the program needs would be much different than originally stated.

I'll play around with it some and see just how quick a routine I can whip up for those longer words/phrases.  :)
Title: Re: WordCracker
Post by: codeguy on October 08, 2018, 03:58:27 pm
I got 361 words matching stevemcneill using the wordlist.txt as included in an attachment for this post. Somewhere, someone is wrong. Mine was modified to accommodate the added characters. Yes, it took a while as I did no optimizations for eliminating impossible prefixes and suffixes.
Title: Re: WordCracker
Post by: bplus on October 08, 2018, 04:22:34 pm
Hi codeguy,

For stevemcneill, 2 l's on end, I am getting 392 words with Steve's code and my version.

I don't know about just a letter? is t a word? I know I is. ;)
Title: Re: WordCracker
Post by: SMcNeill on October 08, 2018, 04:27:12 pm
Quote from: bplus on October 08, 2018, 04:22:34 pm
Hi codeguy,

For stevemcneill, 2 l's on end, I am getting 392 words with Steve's code and my version.

I don't know about just a letter? is t a word? I know I is. ;)

Large dictionaries list each letter as a single-letter word. Each such word is defined as a noun, denoting the letter with which it is spelled.

"Psychology" starts with a p.

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

What if Q from Star Trek took the L train to the T intersection of C and D streets because he had a map where an X marked that spot? Would he get an A for following directions?
Title: Re: WordCracker
Post by: codeguy on October 08, 2018, 04:41:19 pm
You ARE using the original wordlist.txt from the original thread post https://www.qb64.org/forum/index.php?action=dlattach;topic=679.0;attach=1619 (https://www.qb64.org/forum/index.php?action=dlattach;topic=679.0;attach=1619), right? I got 361 unique matches using "stevemcneill" as the original string on my modified code, which was considerably slower BUT it does EXHAUSTIVE permutations of every letter, leading to quite large numbers, in fact the size of the job increases as a factorial.
Title: Re: WordCracker
Post by: bplus on October 08, 2018, 04:52:37 pm
Hi codeguy,

Is your code geared to handle the triple e and double l in stevemcneill? This is why I thought "nah!" for permutations.

Hi Steve,

You sure know how to drive home a point, N, S, E and W! ;)
Title: Re: WordCracker
Post by: codeguy on October 08, 2018, 05:23:50 pm
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.
Title: Re: WordCracker
Post by: SMcNeill on October 08, 2018, 06:50:09 pm
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
  9.     LINE INPUT #1, junk$
  10.     WordCount = WordCount + 1
  11.     IF LEN(junk$) > maxlength THEN maxlength = LEN(junk$)
  13. SEEK 1, 1
  14.  
  15. TYPE WordLetters
  16.     letter AS _UNSIGNED _BYTE
  17.     count AS _UNSIGNED _BYTE
  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
  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
  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.  
  75.  
  76. 'Print Results
  77. FOR i = 1 TO wordfound
  78.     PRINT Words(Match(i));
  79.     IF i < wordfound THEN PRINT ","; ELSE PRINT
  82. PRINT "DONE, with"; wordfound; "matches, with a speed of"; loopcount; "runs in 5 seconds."
  83.  
  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
  97.  
  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);
  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.  ;)
Title: Re: WordCracker
Post by: SMcNeill on October 08, 2018, 07:30:11 pm
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
  10.     LINE INPUT #1, junk$
  11.     WordCount = WordCount + 1
  12.     IF LEN(junk$) > maxlength THEN maxlength = LEN(junk$)
  14. SEEK 1, 1
  15.  
  16. TYPE WordLetters
  17.     letter AS _UNSIGNED _BYTE
  18.     count AS _UNSIGNED _BYTE
  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
  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
  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
  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.  
  88.  
  89.  
  90. 'Print Results
  91. FOR i = 1 TO wordfound
  92.     PRINT Words(Match(i));
  93.     IF i < wordfound THEN PRINT ","; ELSE PRINT
  96. PRINT "DONE, with"; wordfound; "matches, with a speed of"; loopcount; "runs in 5 seconds."
  97.  
  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
  115.  
  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

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.
Title: Re: WordCracker
Post by: bplus on October 08, 2018, 07:34:55 pm
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?

Title: Re: WordCracker
Post by: bplus on October 08, 2018, 07:59:49 pm
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.
Title: Re: WordCracker
Post by: SMcNeill on October 08, 2018, 08:19:52 pm
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.  ;)
Title: Re: WordCracker
Post by: bplus on October 08, 2018, 08:32:47 pm
Quote from: SMcNeill on October 08, 2018, 08:19:52 pm
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.
Title: Re: WordCracker
Post by: codeguy on October 08, 2018, 08:49:01 pm
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.
Title: Re: WordCracker
Post by: bplus on October 08, 2018, 09:05:36 pm
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.
Title: Re: WordCracker
Post by: SMcNeill on October 08, 2018, 09:33:10 pm
Quote from: bplus on October 08, 2018, 08:32:47 pm
Quote from: SMcNeill on October 08, 2018, 08:19:52 pm
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.
Title: Re: WordCracker
Post by: codeguy on October 08, 2018, 11:10:34 pm
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
  11.     LINE INPUT #1, junk$
  12.     wordcount = wordcount + 1
  13.     IF LEN(junk$) > maxlength THEN maxlength = LEN(junk$)
  15. SEEK 1, 1
  16.  
  17. TYPE WordLetters
  18.     letter AS _UNSIGNED _BYTE
  19.     count AS _UNSIGNED _BYTE
  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
  25. DIM KIterWordLettersCount AS LONG
  26. DIM afound AS LONG: afound = 0
  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
  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
  59.  
  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.  
  85.  
  86. 'Print Results
  87. FOR i = 1 TO wordfound
  88.     PRINT Words(Match(i));
  89.     IF i < wordfound THEN PRINT ","; ELSE PRINT
  92. PRINT "DONE, with"; wordfound; "matches, with a speed of"; loopcount; "runs in 5 seconds."
  93.  
  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
  107.  
  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);
  118.  
  119.  
On my humble machine, this represents a 45 loops/5s to 80+ loops/5s. Awesome work, Steve.
Title: Re: WordCracker
Post by: SMcNeill on October 09, 2018, 12:13:36 am
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.)
Title: Re: WordCracker
Post by: bplus on October 10, 2018, 01:39:23 pm
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.
Text Only | Text with Attachments