Solving the Daily Jumble…

I frequently do the crossword puzzle in my local paper. On the same page, usually on the left side it, the daily Jumble innocently exists. Its purpose is to torment the weak and waste a lot of time for the clever. I have to admit that I have been frustrated by it many times before.

To reduce my frustrations, I decided to make a small program that helps one to solve Jumbles. The program does not necessarily solve Jumbles, rather it reports various possible solutions since many times multiple answers are feasible. Using these answers, it would be possible to find an answer that best fits the puzzle’s clue/question.

Note that the solution looks up solutions in a dictionary file. In certain cases it is possible to not have a solution; these include:

  • Proper names of people, tv shows, companies
  • Slang; that is not real words
  • WordPlay; after solving a few of these puzzles, wordplay happens too often and I believe that the Jumble’s creator has a pretty bad sense of humour.

Core Idea…

The hash table is the main idea required to solve this problem. Using a premade set of words, a hash table is created where the keys are sets of letters and the values are list of possible words that can be created with those letters (as seen in the image below). Therefore solutions can simply be looked up from a properly created hash table.

\begin{aligned} \mathsf{key}_1 &\rightarrow \mathsf{word\ or\ set\ of\ words} \\ \mathsf{key}_2 &\rightarrow \mathsf{another\ word\ or\ set\ of\ words} \\ \ \vdots & \quad \vdots \quad \vdots\quad \vdots\quad \vdots \\ \mathsf{key}_i &\rightarrow \mathsf{yet\ another\ word\ or\ set\ of\ words} \\ \end{aligned}

The key is determined by alphabetically sorting the letters of word, and the value is the regular unsorted sort. Since the same set of letters can be rearranged to form multiple words, then the key needs to refer to a list of values. Note that the majority of cases usually contain one unscrambled word instead of a list of words. An example of some of the entries used by our program are listed below:

\begin{aligned} \mathsf{ACDEN} &\rightarrow \mathsf{ACNED,\ CANED,\ DANCE} \\ \mathsf{ACDEIQTTU} &\rightarrow \mathsf{ACQUITTED} \\ \mathsf{ACDER} &\rightarrow \mathsf{ACRED,\ ARCED,\ CADRE,\ CARED,\ CEDAR,\ RACED} \\ \mathsf{AABCORT} &\rightarrow \mathsf{ACROBAT} \\ \mathsf{AIILNPST} &\rightarrow \mathsf{ALPINIST,\ ANTISLIP,\ PINTAILS,\ TAILSPIN} \\ \end{aligned}

Main Algorithm

The following steps are the main steps in solving the Jumble:

  1. Create a hash table from all the words in the dictionary. Note that it is possible to get a text file of all english words freely online.
  2. Next we lookup each puzzle word to get the unscrambled version(s).
  3. Then we create all the possible combinations from the set of unscrambled words. If we one had one unscrambled word for each word, then only one combination exists. Note that this can be done using a set of nested for loops or the itertools.product function.
  4. After that for each particular unscrambled word combination, the necessary circled/selected letters are extracted.
  5. Now using the extracted letters from the previous step, all combinations are generated based on the length of the required words in the final clue. If the final clue has multiple words, a combination is made for the first word and then this is process is done recursively with the remaining letters for the next words. Note that all combinations can be generated using the itertools.combinations function
  6. For each the letter combinations found in step 5, is looked up in the hash table to check to see if it has solutions. If word exist for all the letters, that particular set of words is then printed out.
  7. Finally, the user looks through the list to find the solution that best fits the context of the puzzle

Example Output

Some examples of the program output (note that the program is a command line version for right now). First for the Jumble pictured above, the output results show an ideal one solution case…

> python JumbleSolver.py JumblePuzzle_01_23.txt 
Loading Puzzle...
Loading dictionary file...
  GILCO --> LOGIC  
  SHRUE --> USHER  
  LIEPCS --> SPLICE  
  NRHGAA --> HANGAR  

Solution Words:  LOGIC  USHER  SPLICE  HANGAR  
Final Letters:  L  G  U  S  S  I  H  G  
Final solution(s): 
  SLUGGISH

Next for the following puzzle, it results in a few combinations with the final solutions. Note that in the used dictionary contains some words that may or may not be to common (such as QI… I guess that is quite interesting).

The code produces the following solution, and the user would have to get the final answer from the list of candidate solutions.

> python JumbleSolver.py JumblePuzzle_06_24.txt 
Loading Puzzle...
Loading dictionary file...
  WAQUKS --> SQUAWK  
  FUMNIF --> MUFFIN  
  DGUTEB --> BUDGET  
  SNITIS --> INSIST  
  QUTAEE --> EQUATE  
  IGLGEG --> GIGGLE  

Solution Words:  SQUAWK  MUFFIN  BUDGET  INSIST  EQUATE  GIGGLE  
Final Letters:  Q  U  M  N  B  G  I  I  T  E  U  G  G  
Final solution(s): 
  QUIT  MUGGING  BE  
  QUIT  BEGGING  MU  
  QUIT  BEGGING  UM  
  QUIT  BUGGING  EM  
  QUIT  BUGGING  ME  
  MUTE  BUGGING  QI  
  BUTE  MUGGING  QI  
  TUBE  MUGGING  QI

Code

The code (written in Python) along with a dictionary file and some test puzzles is available here.

 

No Comments

Add your comment