bg11
April 16th, 2008, 07:28 PM
Partly due to the enthusiasm shown here for python, I decided to have a go at learning it. I'm going through Downey's Python book from the green tea site. But I'm stuck on an exercise involving reading in a word list, searching for pairs of words which are shifts or "rotations" of each other, e.g. melon shifted by -10 is cubed.
I've written some code, which seems to work, but it takes a very long time to finish the whole word list (see attachment, filename=brit-a-z). I'm sure there's some reasonably simple way of optimising it. Advice, tips, hints?
Here's the code:
dord = {}
def list_rotations(file):
fin = open(file)
nlines = 0
for line in fin:
word = line.strip()
i = 0
if len(word) < 4: ### for testing ###
ord_list = []
while i < len(word):
if word[i] in dord: o = dord[word[i]]
else:
o = ord(word[i])
ord_list.append(o)
i += 1
dord[word] = ord_list
nlines += 1
for k1 in dord:
for k2 in dord:
if k1 != k2 and len(k1) == len(k2):
are_rotated(k1, k2)
def are_rotated(word1, word2):
shift = [0]*len(word1)
i = 0
for o in dord[word1]:
lord = dord[word2]
if o == lord[i]: rotated = False
shift[i] = o - lord[i]
if shift[i] < 0: shift[i] += 26
if i>0:
if shift[i] != shift[i-1]: return False
i += 1
print word1, word2, shift[0]
list_rotations('brit-a-z.txt')
I've written some code, which seems to work, but it takes a very long time to finish the whole word list (see attachment, filename=brit-a-z). I'm sure there's some reasonably simple way of optimising it. Advice, tips, hints?
Here's the code:
dord = {}
def list_rotations(file):
fin = open(file)
nlines = 0
for line in fin:
word = line.strip()
i = 0
if len(word) < 4: ### for testing ###
ord_list = []
while i < len(word):
if word[i] in dord: o = dord[word[i]]
else:
o = ord(word[i])
ord_list.append(o)
i += 1
dord[word] = ord_list
nlines += 1
for k1 in dord:
for k2 in dord:
if k1 != k2 and len(k1) == len(k2):
are_rotated(k1, k2)
def are_rotated(word1, word2):
shift = [0]*len(word1)
i = 0
for o in dord[word1]:
lord = dord[word2]
if o == lord[i]: rotated = False
shift[i] = o - lord[i]
if shift[i] < 0: shift[i] += 26
if i>0:
if shift[i] != shift[i-1]: return False
i += 1
print word1, word2, shift[0]
list_rotations('brit-a-z.txt')