Jamie's Blog

My wife loves PopCap’s game Alchemy. It’s a dominoes-like game, where you match up alchemic symbols and various colors. The object of the game is to turn each board-square from lead to gold. I have been wanting to try out the limejs game library, which is based on Google’s Closure compiler, so I decided to write a quick implementation of the game. You can find the source on Github.

You can try out the game online. To play, place pieces adjacent to other pieces which match in symbol or color. A placed piece must match all the pieces adjacent to it. A wild card piece, denoted with the ‘*’ symbol, matches all pieces. Filling a row or column with pieces will mark the corresponding spaces as cleared. The object of the game is to get each space marked as cleared.

Edit (20100214 11:00 PM): Added win condition and box showing how many spaces cleared.
Edit (20100215 11:00 PM): Added leveling. The board starts small with few pieces and keeps getting bigger with each round.

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

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

I wanted to try out some canvas element functionality, given that I have a feeling it will steal a lot of Flash’s thunder. I whipped up a bubble-breaker game (the mechanic should be very familiar to you) in a few hours. Enjoy the demo! I may do a quick write up at a later point.

I’ve only tested it in Firefox 3.6. I do not know whether it will work in other browsers.

Demo
Project site

bubble breaker 13x13

bubble breaker 30x30