Solve the Jumble!
Ah yes. The weighty problem of solving the Jumble in the daily paper. This is usually an easy puzzle to solve, although when your mind gets "jumble-blocked", it can tend to stay that way for a while.
In the "Jumble" puzzles (copyrighted by David L. Hoyt) the challenge is to unscramble a set of words. The individual words are usually 5 to 8 characters long. In the official puzzle, selected letters from the individual answers are unscramble to provide the punchline to a horrific pun.
How to Solve It
The human brain seems to be particularly gifted at doing this. Many solvers have had the experience of having the unscrambled answer for each word pop right into their head after a quick glance. This is followed by a short burst of intellectual smugness and fantasies about accepting the Nobel Prize for Extreme Cleverness.
And yet, sometimes the unscrambling process stumbles and the letters just stare back at you, defiantly scrambled. At that point any number of tricks to jump-start the puzzle-solving process might work. Simple tactics like reversing the scrambled letters and giving your brain another go, or heuristics like looking for common groupings of letters ('th', 'ing', etc.) in order to simplify the number of combinations to consider.
This is a fun Comp Sci 101 exercise because of how inventive people can be at finding difficult solutions. On the other hand, if you identify the elegant, simplifying hack (or, well, have it explained to you ... I'm not proud) it can take your own personal smugness to all new levels. In this case, the clever hack is described by Jon Bentley in the "Aha! Algorithms" essay from his book "Programming Pearls".
To unscramble the individual words, the essay describes this central trick: sort the letters of the scrambled word into alphabetical order. Then compare this sorted arrangement of letters with a dictionary of words processed the same way (an alphabetical list of words each paired with a version of itself with its letters sorted alphabetically).
For example, say that one of our scrambled puzzle words is "lorac". We sort the letters into alphabetical order to obtain "aclor". We then search our dictionary for any five-letter words that also sorted to the pattern "aclor". (I used a list of about 100,000 words and found four solutions: "calor", "carlo", "carol", and "coral")
The final script used in this page is written in PHP and is fairly short and simple:
As mentioned, that worked, but it wasn't very fast the first time I wrote it because of the time needed to load the word list (100,000 lines long). And then I had a linear search through the list, etc. Not efficient.
I replaced the list with a call to a MySQL table of dictionary words and their corresponding 'signed' versions, and that made for a simpler and much faster script.