Computron's Tabulations

A coworker was cleaning up some HTML and wanted to remove unnecessary css styles from article markup. Specifically, he wanted to remove font styles from the markup, but retain other styles. CSS styles appear in HTML in the form: <tag style="style1: value; style2: value;">content</tag> There is a bit of variation possible in the style definition. Whitespace is ignored, and the ending semi-colon is optional. If a style appeared like this: style="font-family: arial; color: #000; font-size: x-large" He wanted to strip the font styles so that the new style definition would look like: style="color: #000; " First, he tried a regular expression like: /(font-(face|size|family): *.+(;|"|'))/i

Which consumed too much:

Then we tried to modify the expression to consume less: /(font-(face|size|family): *[^;"]+(;|"|'))/i

The problem was that the ending quote of a style attribute was being captured. We changed the regex to avoid this: /(font-(face|size|family): *[^;"']+;?)("|')?/i

A final modification, the addition of a ?: modifier at the beginning of the capturing parentheses, will avoid unnecessary captures.

/(font-(?:face|size|family): *[^;"']+;?)(?:"|')?/i

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.

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:

func 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