Solving Jumble with Python and Bash

In order to solve jumble, we first write a Python script that outputs all character permutations of a given string. The script demonstrates a cool little recursive algorithm. To compute all permutations of a string of length n, we pick off the character at each index in the string, and compute the permutations of the remaining n-1 characters. The function substring constructs this n-1 character string. When we have a list of the permutations of these n-1 characters, we use the list comprehension

[first + i for i in perms(others)]

to prepend the character that we initially picked off onto each string in the list.

permutations.py

---

#!/usr/bin/env python

import sys 

def substring(s, i): 
    if i == (len(s) - 1): 
        return s[:i]
    elif i == 0:
        return s[1:]
    else:
        return s[0:i] + s[i+1:]

def perm(s):
    p = []
    length = len(s)
    if length <= 1:
        p.append(s)
    else:
        for i in range(length):
            first = s[i]
            others = substring(s, i)
            p.extend([first + i for i in perm(others)])
    return p

if __name__ == '__main__':
    if len(sys.argv) != 2:
        print('usage: %s word' % sys.argv[0])
        sys.exit(1)
    perms = perm(sys.argv[1])
    for i in perms:
        print(i)
    sys.exit(0)

Let's try out the script by having it display all permutations of the string 'one'.

$ ./permutations.py one
one
oen
noe
neo
eon
eno

Now all we have to do to solve jumble is loop over each string in the output and see if that string appears in a dictionary. To do this, we'll write a short Bash script that greps for each word against a dictionary file. On my computer a flat text dictionary is located at /usr/share/dict/words. Feel free to change the assignment of the variable DICT to some other dictionary file that is found on your machine.

jumble.sh

---

#!/bin/bash

DICT=/usr/share/dict/words

if [ $# -ne 1 ]; then
    echo "usage: $0 jumble-word"
    exit 1
fi

cnt=1
for i in `./permutations.py $1`; do
    grep -q "^$i$" $DICT 
    if [ $? -eq 0 ]; then
        printf "%6d: %s ... [YES]\n" "$cnt" "$i"
        exit 0
    fi  
    printf "%6d: %s ... [NO]\n" "$cnt" "$i"
    let cnt=cnt+1
done

exit 1

Let's try out our program on an example taken from jumble.com.

$ ./jumble.sh tecot
     1: tecot ... [NO]
     2: tecto ... [NO]
     3: teoct ... [NO]
     4: teotc ... [NO]
     5: tetco ... [NO]
     6: tetoc ... [NO]
     7: tceot ... [NO]
     8: tceto ... [NO]
     9: tcoet ... [NO]
    10: tcote ... [NO]
    11: tcteo ... [NO]
    12: tctoe ... [NO]
    13: toect ... [NO]
    14: toetc ... [NO]
    15: tocet ... [NO]
    16: tocte ... [NO]
    17: totec ... [NO]
    18: totce ... [NO]
    19: tteco ... [NO]
    20: tteoc ... [NO]
    21: ttceo ... [NO]
    22: ttcoe ... [NO]
    23: ttoec ... [NO]
    24: ttoce ... [NO]
    25: etcot ... [NO]
    26: etcto ... [NO]
    27: etoct ... [NO]
    28: etotc ... [NO]
    29: ettco ... [NO]
    30: ettoc ... [NO]
    31: ectot ... [NO]
    32: ectto ... [NO]
    33: ecott ... [NO]
    34: ecott ... [NO]
    35: ectto ... [NO]
    36: ectot ... [NO]
    37: eotct ... [NO]
    38: eottc ... [NO]
    39: eoctt ... [NO]
    40: eoctt ... [NO]
    41: eottc ... [NO]
    42: eotct ... [NO]
    43: ettco ... [NO]
    44: ettoc ... [NO]
    45: etcto ... [NO]
    46: etcot ... [NO]
    47: etotc ... [NO]
    48: etoct ... [NO]
    49: cteot ... [NO]
    50: cteto ... [NO]
    51: ctoet ... [NO]
    52: ctote ... [NO]
    53: ctteo ... [NO]
    54: cttoe ... [NO]
    55: cetot ... [NO]
    56: cetto ... [NO]
    57: ceott ... [NO]
    58: ceott ... [NO]
    59: cetto ... [NO]
    60: cetot ... [NO]
    61: cotet ... [NO]
    62: cotte ... [YES]