word shifts

[Peter Otten]

dave wrote:

> I made a function that takes a word list (one word per line, text file) 
> and searches for all the words in the list that are 'shifts' of 
> eachother.  'abc' shifted 1 is 'bcd'
> 
> Please take a look and tell me if this is a viable solution.
> 
>  def shift(word, amt):
>         ans = ''
>         for letter in word:
>                 ans = ans + chr((ord(letter) - ord('a') + amt) % 26 +
ord('a'))
>         return ans
> 
> def fileshift(x):
>         fin = open(x)
>         d = {}
>         for line in fin:
>                 d[line.strip()] = [1]
>                 for i in range(1, 26):
>                         ite = shift(line.strip(), i)
>                         if ite in d:
>                                 print ite
> 
> 
> Any tips/suggestions/critiques greatly appreciated.. I'm trying to 
> teach myself Python (and still beginning) and would love any helpful 
> info.

My ideas: 

Move the open() call out of fileshift() and have it working with arbitrary
iterables. 
Store a normalized version of the word in the dictionary. if every word in
the dict is guaranteed to start with an "a" you can reduce the number of
tests to one.
If you have many words you can build a fast shift() function based on
str.translate().

Invoke the following script both with and without a filename argument:

from string import ascii_lowercase as chars, maketrans

tables = [maketrans(chars, chars[i:] + chars[:i]) for i in range(26)]

def shift(word, n):
    return word.translate(tables[n%26])

def normalize(word):
    a = word[0]
    return shift(word, ord("a") - ord(a))

def findshifted(words):
    d = {}
    for word in words:
        d.setdefault(normalize(word), []).append(word)
    return d


if __name__ == "__main__":
    import sys
    args = sys.argv[1:]
    if args:
        words = (line.strip() for line in open(args[0]))
    else:
        import random
        sample = """\
        alpha
        beta
        gamma
        delta
        """.split()

        words = sample + [shift(random.choice(sample), random.randrange(26))
for _ in range(10)]

    items = findshifted(words).items()
    items.sort()
    for k, v in items:
        print k, "-->", v

Peter