Jimmy and the coconuts

This blog is about transformations, and random internet walks. Earlier today I was searching for "Jimmy and the coconuts" because I heard Ryan Adams refer to himself and the Cardinals by that moniker at a recent show.

There weren't very many hits for the search, but among the unrelated hits was a site from Waterloo's math pages. http://www.math.uwaterloo.ca/navigation/ideas/Zeno/zenologic.shtml#. The phrase isn't in that page, but some of the puzzles on that page are sort of fun.

There is a puzzle about word transformation, and I thought it related nicely to the irrelevance of following random web links. I was too lazy to think about how to transform the word [snow] into [rain] by one letter word transformations (see the page), with the sequence giving valid words. Instead, I cooked up a quick python script that uses a shell command to test the validness of the words, and does a breadth-first search to find the transformation (sure, a-star would be faster to run, but this only took a couple minutes to write). Anyway, I have no idea who is reading this, or how you got here, maybe it was from searching for Jimmy and the coconuts. Either way, on initial inspection this page is guaranteed to be irrelevant, and because of that it actually is relevant.

The transformation from the listed program gives: ['snow', 'snot', 'soot', 'loot', 'loon', 'loin', 'lain', 'rain']. Based on "spell"'s dictionary.

#!/usr/bin/python
import os, sys, struct, string

# Prune out the words that are not in the dictionary.  Uses spell. replace with your own
# if you want to use.  
def remove_invalid(cands):
    f = file('/tmp/cands.txt', 'w')
    for cand in cands : f.write('%s\n'%cand)
    f.close()
    f = os.popen('spell < /tmp/cands.txt', 'r')
    lines = f.readlines()
    lines = [l.strip() for l in lines]
    for c in lines: cands.remove(c)
    return cands

# Yeah, I was in a hurry, I'm sure there is a better way to get the ascii chars out
# of a string, instead of using the interpreter and the doc strings to find something that worked
def word_neighbors(str):
    cands = [];
    asc = string.ascii_letters
    for i in xrange(0, len(str)):
        for j in xrange(1, 26):
            b = struct.unpack('b', str[i])
            b = (b[0] + j - 97) % 26
            cands = cands + [str[0:i] + asc[b] + str[(i+1):]]
    return cands

if len(sys.argv)<=2:
    print 'Need two strings of the same length'
    sys.exit(1)
if (len(sys.argv[1])!=len(sys.argv[2])):
    print 'Strings arent same length'

w1 = sys.argv[1].lower()
w2 = sys.argv[2].lower()

q = remove_invalid(word_neighbors(w1))

neighs = word_neighbors(w1)
remove_invalid(neighs)

Q = neighs
vis = {}
parent = {}
for n in neighs: parent[n] = w1

while len(Q):
    e = Q.pop()
    if e == w2:
        break
    vis[e] = 1
    neighs = remove_invalid(word_neighbors(e))
    for n in neighs:
        if (n not in vis) & (n not in Q):
            parent[n] = e
            Q = [n] + Q

if e == w2:
    print 'Found transformation:'
    tform = []
    while e != w1:
        tform = [e] + tform
        e = parent[e]
    tform = [w1] + tform
    print tform
    sys.exit(0)
else:
    print 'Did not find a transformation'
    sys.exit(1)