Checking all possible solutions in a word game
fmakawa
Member Posts: 565
Hi Folks,
I hit a stumbling block. I am creating a suite of word games and in some you get a number of letters which you then rearrange into words. That's working fine. I'm stuck however on trying to create a list of all the possible words I could have made with the available letters. As in after I finish the round and I only made lets say 20 words, I move to a scene/pop up that shows me all the words that were possible, lets say 60 of them. Anyone with an idea how I can work this?
Comments
//
@socks, not familiar with the short hand. That means?
It means he wrote something then changed his mind about it.
What you're asking is going to be tricky. Are you using random letters for levels, or pre-picked ones?
Contact me for custom work - Expert GS developer with 15 years of GS experience - Skype: armelline.support
@Armelline the letters are random. For instance in one, I used 100 options for the letters, partitioned to match a regular English Scrabble set. The letters are then mixed at random and presented in a grid of 5x5. Each piece having generated its own random Letter. So its possible to have a whole board of just 'A'. (I suppose I should adjust that so that all take from a diminishing pool to prevent such an occurrence). So the grid is unique and solutions which are recognised depend on the game form- word search would just take the 8 cardinal points, boggle would take pretty much any connecting boxes etc. Currently working on the word search one since its solutions are simpler than the boggle one but baffled.
Maybe something like this?
http://forums.gamesalad.com/discussion/comment/406303/#Comment_406303
You can find English letter frequency statistics online. I recommend using the percentage occurrences for each letter when choosing "random" letters to fill the grid, or at least use that as a starting point.
New to GameSalad? (FAQs) | Tutorials | Templates | Greenleaf Games | Educator & Certified GameSalad User
I did that, much like @tshirtbooth did ages ago but the problem was that when you used his method derived from that you ended up with a skewed board. So I decided to follow a scrabble board, having come to the conclusion that they must be widely versed on the distribution of letters for a decent word game. Its worked great so far, no complaints here!
@RThurman That's great stuff. But I hit a snag whilst looking through. The demo requires a string being put in of 10 letters and then check for words going left to right and this could be reversed for the other way around. The snags come when I add something that isn't linear such as boggle game where aren't following a linear path. ie
So Whilst I could regurgitate the process in the demo to do all the cardinal directions (left, right. up, down and diagonals) it would be able to read the rest that don't follow this format. hmmmm. tricky.
Oh -- I see.
In order to check all possible combinations of a 5X5 grid, that would be 25! (read that as 25 factorial). I believe that 25 factorial would be 15,511,210,043,330,985,984,000,000 separate combinations. Thats a lot of calculating!
Sounds like you need an anagram dictionary. This would be an interesting one in GameSalad. I may have a stab at it if I get time.
Contact me for custom work - Expert GS developer with 15 years of GS experience - Skype: armelline.support
@RThurman much less since they have to be connecting but yeah, still its a lot and the logic is going to be crazy (if managed)
@Armelline that would be amazing!
I'm going to keep at it though!
How many different letters is the grid populated with at any time?
Contact me for custom work - Expert GS developer with 15 years of GS experience - Skype: armelline.support
I didn't set a limit as to how many unique letters per board so theoretically you could have a-y or z-b, which cell having a unique letter and equally all 25 could turn out to be C. Or did I misunderstand the question?
There are two problems that you'll need to solve, and I'm not certain either can be solved effectively with GameSalad.
You need to work out every possible combination of letters and check them against a dictionary. This is doable, though difficult - except for the problem 2 provides.
The second is the problem. To work out every possible combination of letters, you need to work out every "path" through the letters that can conceivably be words. As @RThurman mentioned, this is a daunting task. It's almost certainly impossible with GameSalad, and making the word list needed in one relies upon it.
If you have a smaller list of letters - say 7 different letters in the grid, then you can build a word list fairly simply, and then check if they can be found in the grid. But with 25 letters, that's pretty much the entire dictionary.
As it stands, your task is almost certainly impossible using GameSalad.
Contact me for custom work - Expert GS developer with 15 years of GS experience - Skype: armelline.support
@Armelline, hmmm. The word list I already have. The whole dictionary, Merriam Webster minus words of 1-2 letters. tabled and everything.
Its the path part it seems where I have hit a wall. ah well. I suppose I can try game the function a bit so I dont give all the combinations but give some solutions.
I think you misunderstand what I mean by word list - I mean the possible words that can be made using the letters in the grid.
Giving some possible words probably wouldn't be that hard. It's giving all possible words that will be really difficult.
Contact me for custom work - Expert GS developer with 15 years of GS experience - Skype: armelline.support
@Armelline ahhhhh I see now said the blind fool!! Now I understand you clearly. Gotcha! I'll drop that function for now.
@Armelline @RThurman Hi Folks, So I thought of this some more, couldn't help it! How about I create an array of all the possible permutations and create a 'solver' that follows the array? If it finds words it adds them to a list but if the combination no longer matches anything it stops the search for that string and then moves to the next one.
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
like
1-2-3-4-5-10-9-8 etc
1-2-3-4-9-8-7-6-5 etc
Or perhaps have each tile have its set paths and have it have a solver which follows the paths and finding words, and stopping when a path becomes redundant?
Here was my attempt at an anagram finder for words of length 5.
https://www.dropbox.com/s/clsdq6huk89rfvf/anagramFinder.mov?dl=0
I used one of the GS templates to check if the word is a valid word and then compared it with a local site. It isn't the most efficient, but it can solve it in about 5-10 seconds. Could probably make it faster by adding more actors to solve at a time. If you are interested let me know.
That sounds interesting but will take quite a bit of time to go through all combinations/permutations.
Yes thats the beginning part! But then you need to build in the AI for the solver. There are examples and prototypes out there on the interwebs (in other languages/SDKs) that might help you as you figure it out. (And I bet plenty of Master's degree theses have been written on this subject.)
I successfully made an anagram solver, maybe it can help you out. But it only works for 6 letter words and under. Truthfully it works best for 5 words and under, got it to work in about half a second, but once you go over five words the time it takes slows a good amount. But if you can limit it to only certain combinations and now every possible combination it may be useful.
If you are still interested PM me and I'll show you.
I'm not worried about time that much since its meant to run as a background process. And when the round ends, after 2 minutes, you get the set of solutions. I figure an process however slow should be able to handle it in 2 minutes, no?
Its funny cause I can now build one in html but utterly failing here on GS. Been looking through a few of them, the trick is finding a way to translate processes in other languages to similar or complimentary GS functions and attributes.
I PMed. Would be great!