Python algorithm - Jumble solver

Unscrambling Words: A Python Jumble Solver Algorithm

Learn how to build an efficient Python algorithm to solve word jumbles using combinatorics, dictionary lookups, and optimization techniques.

Word jumbles are a classic puzzle where letters of a word are scrambled, and the goal is to rearrange them to form the original word. While simple for humans with small words, solving them programmatically for longer words or large sets of jumbled letters requires a systematic approach. This article will guide you through creating a Python-based jumble solver, exploring different algorithmic strategies, and optimizing performance.

The Core Idea: Permutations and Dictionary Lookup

At its heart, a jumble solver works by generating all possible arrangements (permutations) of the given jumbled letters and then checking each arrangement against a known dictionary of valid words. If a generated permutation exists in the dictionary, it's a potential solution. This brute-force approach is conceptually straightforward but can become computationally expensive very quickly as the length of the jumbled word increases.

flowchart TD
    A[Start with Jumbled Letters] --> B{Generate All Permutations}
    B --> C{For Each Permutation}
    C --> D{Is Permutation in Dictionary?}
    D -- Yes --> E[Add to Solutions]
    D -- No --> C
    E --> F[End]
    C -- All Permutations Checked --> F

Basic Jumble Solver Workflow

import itertools

def solve_jumble_basic(jumbled_word, dictionary):
    solutions = set()
    for perm in itertools.permutations(jumbled_word):
        candidate = "".join(perm)
        if candidate in dictionary:
            solutions.add(candidate)
    return sorted(list(solutions))

# Example Usage:
# dictionary = {"apple", "banana", "orange", "pleap"}
# jumbled = "pleap"
# print(solve_jumble_basic(jumbled, dictionary))
# Output: ['apple', 'pleap']

Basic Jumble Solver using itertools.permutations

Optimization: Pre-processing the Dictionary

The basic approach is inefficient because it generates many permutations that are clearly not valid words. A significant optimization involves pre-processing the dictionary. Instead of checking permutations against raw words, we can group dictionary words by their 'canonical form' – a sorted string of their letters. For example, 'apple' and 'pleap' both have the canonical form 'aelpp'.

When solving a jumble, we first find the canonical form of the jumbled letters. Then, we only need to look up this canonical form in our pre-processed dictionary to find all matching words. This drastically reduces the search space.

from collections import defaultdict

def preprocess_dictionary(word_list):
    canonical_map = defaultdict(list)
    for word in word_list:
        canonical_form = "".join(sorted(word.lower()))
        canonical_map[canonical_form].append(word.lower())
    return canonical_map

def solve_jumble_optimized(jumbled_word, canonical_map):
    jumbled_canonical = "".join(sorted(jumbled_word.lower()))
    return sorted(list(set(canonical_map.get(jumbled_canonical, []))))

# Example Usage:
# raw_dictionary = ["apple", "banana", "orange", "pleap", "apelp"]
# preprocessed_dict = preprocess_dictionary(raw_dictionary)
# print(preprocessed_dict)
# # Output: defaultdict(<class 'list'>, {'aelpp': ['apple', 'pleap', 'apelp'], 'aaabnn': ['banana'], 'aegnor': ['orange']})

# jumbled = "pleap"
# print(solve_jumble_optimized(jumbled, preprocessed_dict))
# # Output: ['apelp', 'apple', 'pleap']

Optimized Jumble Solver with Pre-processed Dictionary

Handling Sub-Anagrams and Length Constraints

Sometimes, a jumble might contain letters that can form multiple words of different lengths (e.g., 'listen' could form 'silent', 'lint', 'tens'). The optimized approach above only finds words that use all the jumbled letters. To find sub-anagrams, we need to generate canonical forms for all possible subsets of the jumbled letters.

This can be done by iterating through all possible lengths from a minimum (e.g., 3 letters) up to the length of the jumbled word, and for each length, generating combinations of letters, then their canonical forms.

import itertools
from collections import defaultdict

def preprocess_dictionary_sub_anagrams(word_list):
    canonical_map = defaultdict(list)
    for word in word_list:
        canonical_form = "".join(sorted(word.lower()))
        canonical_map[canonical_form].append(word.lower())
    return canonical_map

def solve_jumble_sub_anagrams(jumbled_word, canonical_map, min_length=3):
    solutions = set()
    jumbled_letters = sorted(jumbled_word.lower())

    for length in range(min_length, len(jumbled_letters) + 1):
        for combo in itertools.combinations(jumbled_letters, length):
            sub_canonical = "".join(sorted(combo))
            if sub_canonical in canonical_map:
                for word in canonical_map[sub_canonical]:
                    solutions.add(word)
    return sorted(list(solutions))

# Example Usage:
# raw_dictionary = ["listen", "silent", "lint", "tens", "nest", "net"]
# preprocessed_dict = preprocess_dictionary_sub_anagrams(raw_dictionary)
# jumbled = "listen"
# print(solve_jumble_sub_anagrams(jumbled, preprocessed_dict))
# # Output: ['lint', 'listen', 'nest', 'net', 'silent', 'tens']

Jumble Solver for Sub-Anagrams

flowchart TD
    A[Start with Jumbled Letters] --> B{Generate Canonical Map from Dictionary}
    B --> C{For Each Possible Word Length (min to max)}
    C --> D{Generate Combinations of Jumbled Letters for Current Length}
    D --> E{For Each Combination}
    E --> F{Calculate Canonical Form of Combination}
    F --> G{Lookup Canonical Form in Map}
    G -- Found --> H[Add Matching Words to Solutions]
    G -- Not Found --> E
    H --> E
    E -- All Combinations Checked --> C
    C -- All Lengths Checked --> I[Return Solutions]

Sub-Anagram Jumble Solver Workflow

This sub-anagram approach is more comprehensive but also more computationally intensive than the exact match. The choice between the two depends on the specific requirements of your jumble solver.

1. Prepare Your Dictionary

Obtain a list of words (e.g., a text file with one word per line). Common sources include /usr/share/dict/words on Unix-like systems or online word lists. Ensure it's clean and contains only valid words.

2. Pre-process the Dictionary

Run the preprocess_dictionary or preprocess_dictionary_sub_anagrams function once with your word list to create the canonical map. Store this map if you plan to run the solver multiple times.

3. Solve the Jumble

Call solve_jumble_optimized or solve_jumble_sub_anagrams with your jumbled word and the pre-processed dictionary map. The function will return a list of possible solutions.