Speed up a slow loop
J. Landman Gay
jacque at hyperactivesw.com
Wed Mar 9 14:37:40 EST 2022
I'm not sure I followed all that, but did you account for diagonals? It sounds like you'd need
to calculate all the possible polygons in a 5x5 grid, starting from anywhere, and sometimes
wrapping around itself.
I don't have the math skills to do that but when I get this thing presentable you could take a
look and see what you think.
On 3/8/22 8:32 PM, Quentin Long via use-livecode wrote:
> It occurs to me that any word which is valid in Boggle must consist of an uninterrupted run of letters which are *right next to each other* on the board. Hence, any digraph which *doesn't* consist of a pair of neighboring letters, *cannot* occur in any valid word.
> Since the "filter out all words with LettersNotOnTheBoard" idea worked, it may be that an analogous "filter out" operation can speed things up more. When setting up a new board...
> -- Construct a list of all 576 ( = 26x26 ) digraphs—"aa,ab,ac, … zx,zy,zz". Or, more likely, construct that list ahead of time, and store the list in a stack property.-- Remove all digraphs which contain at least one letter that's not on the board.-- Make a list of all pairs of neighboring letters on the board. Since you don't know which direction an arbitrary digraph is running in, you'll want to include ZA as well as AZ.-- Remove all the digraphs present on the board from the ListOfAllDigraphs.-- Replace all the "," in the ListOfAllDigraphs with "|". (i.e., replace commas with pipes)
> -- Put "[" & ListOfAllAbsentDigraphs & "]" into RegexPattern.-- Filter WordList without RegexPattern.-- ???-- Profit.
> Hmmm... since this starts out with a complete list of all 576 digraphs, there's no need to do a separate regex filter on individual letters; filtering out the full list of unused digraphs should encompass filtering out unused letters. Hence, just one regex filter should do the job. I think.
> On a 4x4 Boggle board, there are 72 neighboring pairs, hence a maximum of 144 valid digraphs; on a 5x5 board, there are 110 neighing pairs, hence a max of 220 digraphs. Hopefully, this won't add too much overhead to board setup.
> "Bewitched" + "Charlie's Angels" - Charlie = "At Arm's Length" Read the webcomic at [ http://www.atarmslength.net ]! If you like "At Arm's Length", support it at [ http://www.patreon.com/DarkwingDude ].
> use-livecode mailing list
> use-livecode at lists.runrev.com
> Please visit this url to subscribe, unsubscribe and manage your subscription preferences:
Jacqueline Landman Gay | jacque at hyperactivesw.com
HyperActive Software | http://www.hyperactivesw.com
More information about the use-livecode