I can't imagine why I was invited to contribute to this newsletter. My programs never look anything like those of you Run Rev pros. I never deal with error checking; error checking is for sissies. And I never bother much with the nomenclature to distinguish different variable types. And comments are for those who feel the world will not end tomorrow, as I do.

Part of my style, such as it is, is a consequence of my upbringing as a physicist. I have never been trained in the fine art of programming. You see, we learn programming the way we learned the facts of life--on the street. It is not a pretty sight. And, more significantly, we program only for our own needs.

But here I am writing for an audience and so I have made some concessions. Nevertheless, I caution, caveat lector .

Recently Laura Grinton showed us her splendid Scrabble utility. I'm not much of a Scrabble player. Can't spell for one thing; I take after the idol of all physicists, Albert, who got the "i" before "e" rule wrong twice in his own name. But there are three puzzle games included in our local paper: Jumble, Cryptoquote and Sudoku. Jumble is a game of anagrams, Cryptoquote is a cryptography game and I'm sure you know of Sudoku. I will consider only anagrams and cryptography but not Sudoku. (But see http://www.jamesphurley.com/Sudoku.htm if Sudoku interests you.) In these two games, two tools are useful: Finding permutations and pattern matching.

(By the way, for you scrabble fans, you should take a look at the front page of the Sunday NY Times--March 2, 2008. Or do a search for "Scrabble" on the NY Times archives for the article titled "Online Scrabble Craze Leaves Game Sellers at Loss for Words." It discusses some the problems a couple of Indian programmers are having with Mattel over "Scrabulous", their on-line version of Scrabble to be found on Facebook. On their site you can play Scrabble with your more distant friends.)

For Jumble one needs a permutation function somewhat different from that offered by Laura in her Scrabble article. For Scrabble, given the two characters "ab" one needs all combinations of these letters: a, b, ab, and ba. For Jumble one need only the permutations ab and ba.

Algorithms for finding permutations is a storied subject in the programming literature. I will only scratch the surface (for I have navigated only the surface) and do only what we need for unscrambling anagrams. Some of you will find this old-hat and some even naïve--I'm not a mathematician. But some will find it interesting. Among the multitude of methods, I will consider just two, two that I picked up on the street--a hot dog vendor outside a Starbucks. The first is a simple recursive algorithm (because it is fun) and an iterative algorithm (because it is faster.)

Recursive programs can be a problem in that they eat up computer memory; firstly it is necessary to store multiple recursive layers in memory and it may run out before it gets to the answer. (Generally this is not a big problem in modern computers.) And secondly, recursive programs can be a nightmare to debug--you don't get to really look at the answer until you get to the end of the recursion. But I find there is great beauty in this method. It is magical.   We might also call it The Leap of Faith Method.

Our function is called "allPerms." It takes a string as input and returns a list of strings, a list of all permutations of the string.

function allPerms tString
put the number of chars in tString into tNum
if tNum is 1 then return tString
repeat with i = 1 to the length of tString

put char i of tString into tFirstChar
--Here is the magic. We don't know what the list of
all permutations is.
--But let's go nuts and give it a name: allPerms
--We will determine that list recursively, much as one does in constructing a recursive
algorithm for the factorial function.
--For the factorial is n times the factorial of n-1.
--Similarly, we know the list of permutations of just one character
--and we know the permutations of all the characters are the list of
--each character, taken one at a time, with the list of permutation of all
--the remaining characters but that first character.
--So we write:
repeat for each line tLine in allPerms (allCharsBut(tString,i))
put tFirstChar & tLine & cr after results
end repeat
end repeat
return results
end theListofAllPerms

Say what? "each line tLine in allPerms?" But allPerms is exactly what we are trying to find. We have presumed that the function definition "allPerms" will somehow know how to deal with allPerms when it calls itself later in the function.

Notice the repeat loop in theListOfAllPerms:

repeat for each line tLine in allPerms(allButChar(tCharList,i))
put tFirstChar & tLine & cr after results
end repeat

This is where we actually state our intention: Concatenate each character in the string with all the permutations of all the other characters. To understand how this works it is best to take an example. Consider the problem of finding all of the permutations of the characters abc. We try the following. We will attempt to find the permutations of each character separately together with each of the other 2 characters, .i.e.

The permutations of abc are equivalent to:

a & all permutations of bc
b & all permutations of ac
c & all permutations of ab

Notice that we haven't determined the permutation of bc, ac or ab. But suppose we iterate the process. Consider next:

The permutations of bc are equivalent to:

b & all permutations of c
c & all permutations of b

But we know what the permutation of a single character is; it's just the character itself. Voila. We have a workable algorithm!

The one missing ingredient in the above definition of the permutation function is a definition of the auxiliary function that returns the string, but with the i'th character deleted. And that is:

function allButChar tWord, j
delete char j of tWord
return tWord
end allButChar

It remains only to add some facility for removing duplicates, in case there are duplicate letters. Among the permutations of the letters in "dad" there will be "dad" and, interchanging the "dees," "dad." This function will do that fairly efficiently.

function removeDuplicates tList
--Rather than check each element in the list
--to see if it appears elsewhere,
--it is a bit faster to sort the list and
--then, doing a "repeat for each" loop to see if two
--or more successive elements are the same same same
--and capture only the first occurrence.
sort tList
put empty into tPreviousWord
repeat for each line tWord in tList
if tWord is not tPreviousWord then put tWord & cr after tReturn
put tWord into tPreviousWord
end repeat
return tReturn
end removeDuplicates

The Iterative Function

Well, that's all nifty as hell, but not as practical as an iterative approach. (I believe there is a theorem that for every recursive algorithm there is an iterative counter part, but not vice-versa.) The simplest iterative algorithm may be the "interweave."

Say you wanted to find all the permutations of the characters 123. Let's start with a "seed," with the character 1. Now interweave the 2 to obtain:

21
12

Next interweave the 3. The first line above (21) becomes:

321
231
213

Notice the 3 on the diagonal.

And now interweaving the 3 in the line 12 becomes:

312
231
213

Again, notice the 3 on the diagonal.

The function that accomplishes this in the general case is:

function allPermsInterweave tWord
put the length of tWord into numChars
put char 1 of tWord into tSeed
repeat with i = 2 to numChars
put interWeave(char i of tWord,tSeed) into tSeed
end repeat
return tSeed
end allPermsInterweave

function interWeave tChar, tList
repeat for each line tLine in tList
put the length of tLine into m
put tLine into temp
repeat with i = 0 to m # or "m down to 0"
--Note that "after char 0" is the same
--as "before char 1."
put tChar after char i of temp
put temp & cr after results
put tLine into temp
end repeat
end repeat
return results
end interWeave

(Click here to download.)

Here is a screen shot of the card that allows you to compare the two methods in operation:

And here is a screen shot showing the interweave in action.

It is shown at the stage where the 1, 2, and 3 have already been interwoven. If you hit the "Now interweave the no. 4" button it will do as it says, and the button name will change to "Now interweave the no. 5." The last word in the button name becomes a parameter in the button function. Now is that slick or what?

With these tools it is easy to construct a little anagram game:

Select the number of characters to be permuted and hit "New Anagram." There is no need here to use all the machinery for finding all possible permutations. We simply select all words from the dictionary with the required number of characters, and then randomly choose a single word from this list. We then anagram the word by randomly choosing a sequence of its letters.   Some care must be exercised in choosing this randomization to be sure that the original word is not chosen by accident. If this happens, the seed for the random number generator must be reset.

on mouseUp

put decompress(the compressed of this stack) into tWordList
put field "charNum" into tCharNum
--Pick all the tCharNum words from the dictionary
repeat for each word tWord in tWordList
if the number of chars in tWord = tCharNum then
put tWord & cr after tNewList
end if
end repeat
--Pick a word at random from this list
put the number of words in tNewList into tNum
put word random(tNum) of tNewList into tWord
put "to" into tWord
--Scramble the letters to create the puzzle.
--But first save a copy of the word to compare
--with the scrambled word, just to be sure the
--scrambled word is not, by accident, the same as
--the unscrambled word.
put tWord into tSavedWord
put tCharNum into tSavedNum

--This is where the characters in tWord are randomized.
repeat
if tCharNum is 0 then
--Check to be sure the original word has not
--been chosen by accident.
if tScrambledWord <> tSavedWord then exit repeat
else
put tSavedNum into tCharNum
--The seed for the random number generator
--must be reset or the same sequence of random
--numbers will be chosen all over again.
set the randomseed to 3141590
end if
end if
put random(tCharNum) into tChosenCharNum
put char tChosenCharNum of tWord after tScrambledWord
delete char tChosenCharNum of tWord
subtract 1 from tCharNum
end repeat

put toLower(tScrambledWord) into field "Scramble"
end mouseUp

The program having chosen the anagram it is then your task to find the word that may be obtained by rearranging the given letters.   If you fail, or you wish to check to see if there are other possible words, you hit the "Reveal solution(s)" button, which will reveal all anagrams to the puzzle. That script follows below. The sequence of steps in this button is:

on mouseUp
put "" into field "results"
put field "scramble" into tScrambledWord
put the number of chars in tScrambledWord into tCharNum
put decompress(the compressed of this stack) into tWordList

--Get all words from the dictionary of tCharNum length.
repeat for each word tWord in tWordList
if the length of tWord is tCharNum then
put true into tDict[tWord]
end if
end repeat

--Get all permutations of the scrambled word
put allPermsInterweave(tScrambledWord) into tPermutations
--If a given char appears more than once in a
--word there will be duplicates
put removeDuplicates(tPermutations) into tPermutations

--Check each permutation to see if it is in the dictionary.
repeat for each line tPermutation in tPermutations
if tDict[tPermutation] then
put tPermutation & cr after tAnagrams
end if
end repeat

--And display these possible solutions to the puzzle.
put tAnagrams into field "results"
end mouseUP

Cryptograms:

And now to my favorite word puzzle game, Cryptoquote. There is a screen shot of the game below. You see the quotation   encoded in red, ready for you to decipher. The code is a simple letter substitution. The quotations come from "The quotes of the day" on "The Quotations Page" web site. That page is parsed for the four daily quotes and then encoded.

Your job is to drag the black letters to their proper red letters. When you do, all the red letters of the same character will change throughout the sentence. In this example you might start with something like: the coded "s" is probably "a" in the solution. The double "f;" suggests that "q" might be a vowel and, since it appears frequently, and at the end of a couple of words, it is probably the letter "e."   I leave the rest to your decoding pleasure.

There are some options open to you under the File menu:

In dragging the black letters in the alphabet, Run Rev's "Grab me" command is used. No need for MouseMove handler. When the letter is dropped, the MouseUp handler catches the letter the mouse is over when it is released. It also checks the color of that letter to be sure that only the red letters are changed. If you make a mistake, simply double click the letter in error.

The actual programming is rather grubby and I was somewhat of a novice when I did it, so it may not be very enlightening. In any event, you are welcome to rummage around.

There is also a utility for decoding words that is similar to that Laura developed for Scrabble. My utility looks like this:

Where the instructions read:

Instructions

In decoding a cryptogram one might know certain letters and the fact that some letters are the same. For example suppose the coded word was: ABCCAD. You know then that the 3'rd and 4'th letters are the same, as well as the 1'st and 5'th. Suppose you also know that the last character is an "E". You would then try:1*221E, were the asterisks signify an unknown letter and the digits signify an unknown that appears elsewhere. In this case the 1'st and 5'th letters are the same, as well as the 3'rd and 4'th. The last letter is and "E". Plugging this in to the decoder field and hit the return button reveals that there is only one compatible word: LITTLE.

Try H*11***22 and you find the compatible words to be: hamminess, happiness, and huffiness. (MS Word does not recognize "hamminess.")

To cut the search short a bit, the dictionary is first gone through to find all those words of the right length. These words are then searched to see if they match the given criteria.

There is a great deal more one could build into this, a la Run Rev's regular expressions, but if pursued too far, the computer has taken over, and we wouldn't want that, would we?

At this point it is customary to just say, "enjoy," and go away. I have grown to hate that word. Some time ago, while eating at a fine restaurant, the waitress would punctuate every visit to our table with "enjoy." I told her that I would double her tip if she would refrain from using that word on future visits. I was not enjoying the endless repetition, and I felt the word had lost all meaning for her. I suggested "knock yourselves out" as a alternative.

So, to punctuate this article, let me just say "knock yourselves out" and go away.

Jim Hurley