Using Arrays in a Word Finder App

You can download the stack in this lesson here: https://tinyurl.com/y9he5c7b

In this lesson we will see how to use LiveCode to build a small Word Finder application. This application was originally developed by one of the Development Team to 'assist' him in his Scrabble playing, it's handy but perhaps not strictly within the rules of the game.

The LiveCode Word Finder has two options; an Anagram Finder and a Scrabble Solver. The Anagram Finder takes a list of letters and returns all the valid anagrams which can be created using them relative to a fixed list of words. Each anagram is checked for validity against the SOWPODS word list which is the word list used in current International Scrabble Tournaments.

The Scrabble Solver extends the functionality of the Anagram Finder by filtering its results to find only the anagrams which match the user entered pattern. This pattern represents an opening on the Scrabble board where, for example, the pattern 'b??' means find all three letter words starting with 'b'. Question marks must be used to represent wildcards. Only anagrams which contain the same number of characters as those in the pattern will be returned.

Interface

Firstly we need to create our interface, we need options for what task we want to perform(1), fields to enter the pattern to match(2) and available letters(3), a search button(4) and a results field (5).

We group the radio buttons for Anagram Finder and Scrabble Solver, this means only one can be selected at a time without you having to implement that behavior manually.

Implementing the Anagram Finder - Stage 1 Finding all Possible Permutations

The Word Finder is implemented using one recursive function, which makes up the backbone of the application, and a handful of smaller, simpler functions which perform various checks and preparation work.

We begin by generating a list of all possible permutations using the letters which were entered in the Available Letters field. This is done using a recursive function which continually splits the string of available letters down into smaller substrings, and calls itself again with a substring as the parameter. The recursion stops when the parameter string contains only one character and therefore can't be split any further. As the recursion is taking place lists of permutations are generated by placing the characters which have been taken off the start of the parameter string, in turn, between each of the remaining characters of the string. More details can be found by looking at the permuteSequence function in the card script. You can view the card script at the end of this lesson.

 

 

Implementing the Anagram Finder - Stage 2 Checking against the Dictionary

Once a list of permutations has been found they are checked to see if they are valid words (relative to our dictionary). As the dictionary is quite large, we store it compressed (using the built-in compress function) in the custom property uAllWords of the stack. To check if a permutation is valid we could have used

tString is among the lines of sDictionary

but the time required for this check would be dependent on the size of the dictionary. As a result the dictionary is instead placed into an array using the code below

repeat for each line tWord in tWords
	put true into sDictionary[tWord]
end repeat

This allows us to use the check

sDictionary[tString]

This will be true if tString is within the word list, and empty (i.e. false) otherwise. This check is much more efficient than checking the lines of the custom property as it can be carried out in constant time. Any permutations which are contained within the dictionary are added to a list of valid words. The final piece of processing needed is to remove any duplicates from this list of words. A duplicate can occur if there are multiple instances of a given letter in the Available Letters field since each letter is treated uniquely in terms of producing permutations.

ABC Example

Given the letters a,b,c the possible permutations are

abc,bac,bca,acb,cab,cba,ab,ba,ac,ca,a,bc,cb,b,c,

but the only valid words are

ab, ba, bac, cab

At this point the remaining words will be returned if the Anagram Finder option has been selected.

Scrabble Solver

If you selected the Scrabble Solver option one more step is needed before returning the results. This step further filters the list of anagrams to cut out any which do not match the pattern which the user entered. It is implemented using the filter command and takes the contents of the Pattern field to use as the regular expression.

Question marks must be used to represent wildcards, for example the pattern 'a?' returns all valid 2 letter words starting with a. In the example above this is aa and ab. This is the list of valid 2 letter words beginning with a which can be made with the given letters, in this case aa is possible because we assume that the a given in the pattern is already on the board and the second a comes from the list of tiles we have in our hand.

Using the Anagram Finder

Using the Anagram Finder

If you are using the Anagram Finder at least one character must be placed in the available letters field. The returned anagrams will contain only the characters which you enter. Clicking Search will start the application and cause any results to appear in the field below the button.

Using the Scrabble Solver

Using the Scrabble Solver

When using the Scrabble Solver both a pattern and list of available characters are required. The characters represent the tiles you currently hold and the pattern an opening on the board( i.e. t *blank slot* *blank slot* *blank slot*). Blank slots (i.e. wildcards) must be entered as question marks and will be interpreted as spaces which need to be filled by one of your tiles. Once you have entered both a pattern and your tiles click Search to retrieve word suggestions. An example of a valid search is shown in the screenshot.

The Card Script in Full

local sDictionary
on preOpenCard
  -- Fetch the compressed list of words and decompress it
  local tWords
  put decompress(the uAllWords of this stack) into tWords
  
  -- Use an array to allow fast checking of validity of
  -- our dictionary words:
  --   A word is in the dictionary if sDictionary[tWord]
  --   is true.
  repeat for each line tWord in tWords
    put true into sDictionary[tWord]
 end repeat
 
 -- Reset the display
 put empty into field "Pattern"
 put empty into field "AvailableLetters"
 put empty into field "Results"
end preOpenCard
#
#  Generate all anagrams possible with the available letters
#  and return only those present in the dictionary. 
#
function generateAnagrams pLetterList
  -- Convert list of letters into sequence of letters
  -- (remove commas, make lower-case)
  local tLetters
  put pLetterList into tLetters
  replace comma with empty in tLetters
  put toLower(tLetters) into tLetters
  
  -- Generate the list of permuations of our letters
  local tPermutations
  put generatePermutations(tLetters) into tPermutations
  
  -- Now iterate through all permutations and determine which
  -- ones are valid dictionary words
  local tAnagrams
  repeat for each item tPermutation in tPermutations
    if sDictionary[tPermutation] then
      put tPermutation & comma after tAnagrams
    end if
  end repeat
  delete char -1 of tAnagrams
  
  -- Remove any duplicate entries in our anagram list and
  -- format appropriately.
  local tUniqueAnagrams
  put removeDuplicates(tAnagrams) into tUniqueAnagrams
  
  return tUniqueAnagrams
end generateAnagrams
function solveScrabble pPattern, pAvailableLetters
  local tAnagrams
  put generateAnagrams(pAvailableLetters) into tAnagrams
  
  -- Anagrams are returned as a comma separated list, with some formatting
  -- (additional space after each comma) so turn this into a return-separated list
  replace comma & space with return in tAnagrams
  
  -- Filter out any words that do not match the pattern.
  local tMatchedWords
  put tAnagrams into tMatchedWords
  filter tMatchedWords with pPattern
  
  -- Reapply the formatting as a comma (and space) separated list
  replace return with comma & space in tMatchedWords
  
  return tMatchedWords
end solveScrabble
 
#
#  Delete any duplicates from the list and sort the resulting
#  items by word length, formatting appropriately.
#
function removeDuplicates pList
  local tHead, tRest, tSingleInstance
  put pList into tRest
  repeat with x=1 to the number of items of tRest
    put item 1 of tRest into tHead
    delete item 1 of tRest
    if tHead is not among the items of tRest then
      put tHead & "," after tSingleInstance
    end if
  end repeat
  delete char -1 of tSingleInstance
  sort items of tSingleInstance ascending numeric by the length of each
  replace comma with ", " in tSingleInstance
  return tSingleInstance
end removeDuplicates
 
#
#  Get a list of all possible permutations.
#
function generatePermutations pAvailableLetters
  return permuteSequence(pAvailableLetters)
end generatePermutations
#  The main part of the recursive function - we make this private as it speed up
#  execution slightly.
#
private function permuteSequence pAvailableLetters
  -- Terminate the recursion if we reach a single letter as there is only
  -- one permutation of one letter (obviously!).
  if the number of chars in pAvailableLetters is 1 then
    --  If theres only one character there is only one way to write it.
    return pAvailableLetters & comma
  end if
  
  -- We have more than one letter, so recurse to form a list of all
  -- permutations
  local tPermutations
  repeat with j = 1 to the length of pAvailableLetters
    local tCurrentLetter
     
    -- Split the list of letters into first letter (tCurrentLetter),
    -- and remaining letters (pAvailableLetters)
    put char 1 of pAvailableLetters into tCurrentLetter
    delete char 1 of pAvailableLetters
     
    --  Compute the permutations of the remaining letters
    local tSmallerPermutations
    put permuteSequence(pAvailableLetters) into tSmallerPermutations
     
    -- Loop through all permutations not including the first letter (tCurrentLetter)
    -- and insert the first letter in every possible place. e.g. given a permutation
    --   foo and first letter b
    -- we get:
    --   bfoo, fboo, fobo, foob
    local tCurrentWord
    put comma after tSmallerPermutations
    repeat for each item tCurrentWord in tSmallerPermutations
      -- Iterate over the characters within the current string.
      repeat with y=0 to the number of chars in tCurrentWord
        local tStartString, tEndString
         
        -- Get a substring to make up the start of the permutation.
        put char 1 to y of tCurrentWord into tStartString
         
        -- Get a substring to make up the end of the permutation.
        put char y+1 to -1 of tCurrentWord into tEndString
         
        -- Put the first character between the substrings.
        put tStartString & tCurrentLetter & tEndString & "," after tPermutations
      end repeat
    end repeat
  end repeat
  
  -- Return the list of permutations
  return tPermutations
end permuteSequence

3 Comments

bogs

There appears to be an issue with decompressing the custom property "uAllWords" in the stack. Anyone using a Mac appears to have no problem doing so, where as Windows and Linux users get an error. This is being discussed in this thread on the forums -
http://forums.livecode.com/viewtopic.php?f=7&t=31413&start=30

Elanor Buchanan

Hi bogs,

Thanks for bringing this to our attention. I have updated the attached stack with a uAllWords property compressed within LiveCode and that seems to resolve the issue. Please let us know if the updated stack still can't decompress the data on Windows and Linux.

Kind regards

Elanor

bogs

As far as I can tell, everything appears to work correctly now. Thank you for fixing the issue so quickly!

Add your comment

E-Mail me when someone replies to this comment