Jamie's Blog

I used jQuery for the UI. I am a recent convert to jQuery, having mostly used Prototype + Scriptaculous.

The word list is embedded into the page script as a javascript array. On document ready, html is generated, which writes the first and last word to the page, and creates blank input boxes for the intermediate words.

There is a keyup event bound on each input box, which will determine if the word is correct. If it is, a css class will be added which shows a green underline underneath the box. Otherwise, a red underline will be shown.

Finally, there are buttons on the page which are created dynamically and provides hints or reveal all of the answers.

Word Jumble Filled

Search

The problem of generating the chain of clues is a simple search problem. In this case, depth-first search was used, because the algorithm would attempt path depth-wise and only explore another branch if the generated chain was not long enough.

Another tactic would have been to use a breadth first search. To use breadth-first search, we could have modified the regex pattern to find all words that differed from the base word by just one letter.

Using water as the base word, that regular expression looks something like: /([^w]ater|w[^a]ter|wa[^t]er|wat[^e]r|wate[^r])/. This would find all words in the dictionary that differed by one word (let’s call this word set B).

If we were using breadth-first search, we would then repeat the process with all of the words we just found (word set B).

If you were to visualize the difference between breadth-first and depth-first search, breadth-first would look like a tree with wide but shallow roots. Depth-first search would look like a tree with few but deep roots.

Query Params

The flexibility of the puzzle is enhanced by optional query parameters that may be applied. The word param allows specification of the starting or seed word. The length param specifies the maximum length of the puzzle.

Recursion

The program uses recursion to perform the search. This almost goes without saying, for it is difficult to do general search without recursion (although you could do so with macros and similar programming constructs). Search may be done using loop control structures but I can’t imagine an elegant solution using loops.

The pseudocode for the recursion is basically:

function build(baseWord, chainWords, maxLength)

    regex = generateRandomRegex(baseWord)
    wordSetB = getPossibleWords(regex, notIn=chainWords)
    for(word in wordSetB)

        chain = build(word, chainWords+word, maxLength)
        if Length(chain) >= maxLength

            break

    return chain

I’m posting this because I always spend half-an-hour trying to find this information. To set up virtual mappings or virtual directories (what I call them) for ColdFusion on JRun on OSX, edit the jrun-web.xml file in (this is where mine was, you may have to look elsewhere):

/Applications/JRun4/servers/cfusion/cfusion-ear/cfusion-war/WEB-INF/jrun-web.xml

Add an entry to the jrun-web-app xml element like this…

<jrun-web-app>
<!-- ... -->

  <virtual-mapping>
    <resource-path>/virtualdir/*</resource-path>
    <system-path>/physical/path/</system-path>
  </virtual-mapping>

<!-- ... -->
</jrun-web-app>

The first thing I did was made sure that the word list would be cached on application start. This was as simple as creating an Application.cfc cfcomponent and implementing the onApplicationStart function.  This function reads the dictionary in (described in the last entry) and caches the word list in a ColdFusion array. There are other options for storing this data, but this had the best mix of speed and function considering the method of search I wanted to use against it.

Although the dictionary was only 52K, this caching probably helped performance a great deal.

To generate the word list, I decided on the following algorithm:

1. Choose an initial starting word (at random, or via user entry)
2. Use the word to generate a regular expression.
   Replace a random single letter with the Regex pattern [^L] (where L is the letter you have replaced).

   Example:

   word: water
   regex: w[^a]ter

3. Next, iterate through all of the words, testing each word against the regular expression. Store all matches.
4. With each match, one-by-one, repeat Step 2 until we get a chain of N words. (Where N is the maximum length of the chain.)
5. Obviously, if we have no more matches, we stop. If we have at least a 3-word chain, we can use it.

There are a few considerations not discussed above in generating the puzzle:

• If we match a word that is already in the chain, we should ignore that word to avoid duplicates.
• Not implemented: we should not replace a letter in the same position twice. For example, if we replace the “w” in water, don’t replace the “h” hater (if hater is the 2nd word).
• Depth-first versus Breadth-first searching…to be discussed

In my last entry, I described the concept behind the Word Jumble game. In this entry, I will describe initial steps in creating the game.

Firstly, I needed some dictionary of words. The Unix flavors have built-in dictionaries, and I develop on OSX, so I Googled the location of its dictionary:

/usr/share/dict/words

I knew I wanted to do puzzles of only 5-letter words, so I used the

grep

command to create a file of just these words.

grep ^.....$ /usr/share/dict/words > dictionary-5letterwords.txt

Notice the regular expression I used. I wanted to demonstrate an actual use of regular expressions for this project. The regular expression

/^.....$/

says to match a line of just 5 characters. The period means to match any character. I made the assumption that there would be no words in the dictionary with a space or other punctuation–although that was, perhaps, a faulty assumption.

Next, I started working on the code. Since we use mostly ColdFusion at Wharton, that’s what I wrote the app in.

Word Jumble Filled

For a recent Regular Expressions Tech Talk at Wharton, I wrote a Word Jumble game.  I will be describing the game and some of the key concepts used in making the game.

Game Screenshot

The premise of the game is to transform one word into another by replacing a single letter in the starting word to form a new word and repeating until you match the last word.

So, let’s say we have the word baked, which we want to transform into the word water. We do this by changing one letter in the word baked and forming a new word, repeating the single-letter replacement until we have the word water.

• baked <- start
• bated
• batea
• bater
• water <- end

The rules are:

• You are only given a starting word and ending word
• Change only one letter to form a new word
• The new word must be a real word (in some dictionary)
• The same word cannot appear twice
• Each word must be the same length

Based on these rules, I sat down one evening and spit out an implementation of the game which has the following features:

• randomly generates a puzzle of 5-letter words
• generates a puzzle of max length n, where n is the number of words in the puzzle
• accepts an initial starting word
• accepts user guesses for the intermediate words

Someone asked me about Date Validation the other day. Here are two simple approaches for use in your CF apps.

Assume that the strDate variable contains your date. On the server-side, you may use IsDate(strDate). On the client side, !isNaN(new Date(strDate)). I don’t know for sure if the client-side code is the best way to do it. There are RE-based techniques, but these are the most concise.

CFML:

    <cfoutput>
      <cfset strDate1 = "2001 Fazuary 1"/>
      <cfset strDate2 = "2001 Feb 1" />

        #IsDate(strDate1)#<br>
        #isDate(strDate2)#

    </cfoutput>

    <!---

    Outputs:

    NO
    YES

    --->

Client-side Javascript:

    <script>
    // This creates a function to test the string.
    // What is this function doing? It takes the
    // strDate string and attempts to convert it into
    // a Date object using the Date constructor.
    // When the Date constructor cannot convert the
    // string, it returns NaN (not a number).
    // So, we wind up testing for NOT NaN using
    // !isNaN. Don't ask me why the Date constructor
    // returns NaN and not NaD (not a date)! =D
    function isDate(strDate) { return !isNaN(new Date(strDate)); }

    var strDate1 = "2001 Fazuary 1",
        strDate2 = "2001 Feb 1";

    alert(
        isDate(strDate1) + '\n' +
        isDate(strDate2)
    );

    //
    // Brings up an alert window that says:
    //
    // false
    // true

    </script>

This is the start of a ColdFusion Cheatsheet. It contains mask options for DateFormat and TimeFormat. I plan to add to it as I find the need.

ColdFusion Cheatsheet v0.001