GameSalad

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Checking all possible solutions in a word game

fmakawafmakawa Posts: 559Member

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

  • SocksSocks London, UK.Posts: 12,822Member
    edited May 2016

    //

  • fmakawafmakawa Posts: 559Member

    @socks, not familiar with the short hand. That means?

    @Socks said:
    //

  • ArmellineArmelline Posts: 4,832Member, PRO

    @fmakawa said:
    @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?

  • fmakawafmakawa Posts: 559Member

    @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.

  • RThurmanRThurman Posts: 2,843Member, Sous Chef, PRO
  • tatiangtatiang Posts: 11,910Member, Sous Chef, PRO, Senior Sous-Chef

    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

  • fmakawafmakawa Posts: 559Member

    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!

    @tatiang said:
    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.

  • fmakawafmakawa Posts: 559Member

    @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.

  • RThurmanRThurman Posts: 2,843Member, Sous Chef, PRO

    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!

  • ArmellineArmelline Posts: 4,832Member, PRO

    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.

  • fmakawafmakawa Posts: 559Member

    @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!

  • ArmellineArmelline Posts: 4,832Member, PRO

    How many different letters is the grid populated with at any time?

  • fmakawafmakawa Posts: 559Member

    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?

    @Armelline said:
    How many different letters is the grid populated with at any time?

  • ArmellineArmelline Posts: 4,832Member, PRO

    There are two problems that you'll need to solve, and I'm not certain either can be solved effectively with GameSalad.

    1. 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.

    2. 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.

  • fmakawafmakawa Posts: 559Member

    @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.

  • ArmellineArmelline Posts: 4,832Member, PRO

    @fmakawa said:
    @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.

  • fmakawafmakawa Posts: 559Member

    @Armelline ahhhhh I see now said the blind fool!! Now I understand you clearly. Gotcha! I'll drop that function for now.

  • fmakawafmakawa Posts: 559Member

    @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?

  • zweg25zweg25 Posts: 738Member

    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.

  • RThurmanRThurman Posts: 2,843Member, Sous Chef, PRO

    @fmakawa said:
    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.

    That sounds interesting but will take quite a bit of time to go through all combinations/permutations.

    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?

    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.)

  • zweg25zweg25 Posts: 738Member

    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.

  • fmakawafmakawa Posts: 559Member

    @RThurman said:
    That sounds interesting but will take quite a bit of time to go through all combinations/permutations.

    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?

    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.)

    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.

  • fmakawafmakawa Posts: 559Member

    I PMed. Would be great!

    @zweg25 said:
    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.

Sign In or Register to comment.