another Python sol'n to expert qotw #22
Andrew Dalke <dalke-DxsMES/F/[email protected]>
| Newsgroups | gmane.comp.lang.perl.qotw.discuss |
|---|---|
| Message-ID | <[email protected]> |
Here's another Python solution to the qotw #22. Unlike Dan
Schmidt's, this one builds up an adjacency graph then
uses the shortest path algorithm to find the ladder. Like
his code, I normalize to lowercase.
My timings have my code as being about the same speed as Dan's
% /usr/bin/time python wordladder.py algae zesty Web2 | wc
1.55 real 1.20 user 0.15 sys
15 15 90
% /usr/bin/time python schmidt_wordladder.py algae zesty Web2 | wc
1.53 real 1.31 user 0.08 sys
15 15 90
% /usr/bin/time python wordladder.py octavo herpes Web2 | wc
2.94 real 2.42 user 0.20 sys
32 32 224
% /usr/bin/time python schmidt_wordladder.py octavo herpes Web2 | wc
3.12 real 2.71 user 0.15 sys
32 32 224
Most of my time is spent setting up the graph data structure.
For Web2 the times break down into:
1.3s - load the data into a table of "subwords"
(eg, "love" -> ["\000ove", "l\000ve", "lo\000e", "lov\000e"])
1.0s - make the adjacency graph
0.1s - do the search
I found one difference so far between our two algorithms.
Looking at the ladder, it appears mine gives a correct, shorter
ladder than his.
% python schmidt_wordladder.py zounds peltry Web2 | wc
56 56 392
% python wordladder.py zounds peltry Web2 | wc
55 55 385
Mine Dan's
====== ======
1. zounds zounds
2. wounds wounds
3. woundy woundy
4. roundy roundy
5. rouncy rouncy
6. rounce rounce
7. jounce jounce
8. jaunce jaunce
9. launce launce
10. launch launch
11. caunch caunch
12. clunch clunch
13. clutch clutch
14. clitch clitch
15. slitch slitch
16. stitch stitch
17. stetch stetch
18. stench stench
19. stanch stanch
20. starch starch
21. sparch sparch
22. sparth sparth
23. swarth swarth
24. swarty swarty
25. ------ swarry
26. starty != starry
27. starvy starvy
28. starve starve
29. staree staree
30. starer starer
31. soarer soarer
32. soaper soaper
33. souper souper
34. couper couper
35. coupee coupee
36. couple couple
37. copple copple
38. popple popple
39. popply popply
40. popely popely
41. popery popery
42. ropery ropery
43. rosery rosery
44. rosary rosary
45. rotary rotary
46. notary notary
47. nonary nonary
48. donary donary
49. denary denary
50. senary senary
51. sentry sentry
52. gentry gentry
53. gantry gantry
54. pantry pantry
55. paltry paltry
56. peltry peltry
I also did a brute search for longest shortest paths. Here
are the ones I found in Web2. I haven't seen other messages
with this info.
word
length size ladder
------ ---- ------
2 5 ['ge', 'ae', 'as', 'us', 'up']
3 10 ['edh', 'edo', 'ido', 'ida', 'ila', 'sla', 'sia',
'pia', 'pya', 'mya']
4 18 ['idol', 'idyl', 'odyl', 'odal', 'oral', 'orad',
'brad', 'bead', 'beak', 'beck', 'back', 'bach',
'each', 'etch', 'utch', 'utah', 'utas', 'upas']
5 38 ['alure', 'azure', 'azury', 'anury', 'anura',
'abura', 'abuta', 'aluta', 'alula', 'amula',
'amala', 'amara', 'arara', 'araca', 'braca',
'brava', 'breva', 'breve', 'beeve', 'belve',
'belee', 'besee', 'resee', 'resex', 'remex',
'remix', 'remit', 'demit', 'dimit', 'digit',
'dight', 'wight', 'wicht', 'wecht', 'pecht',
'pacht', 'yacht', 'yasht']
6 55 ['zounds', 'wounds', 'woundy', 'roundy', 'rouncy',
'rounce', 'jounce', 'jaunce', 'launce', 'launch',
'caunch', 'clunch', 'clutch', 'clitch', 'slitch',
'stitch', 'stetch', 'stench', 'stanch', 'starch',
'sparch', 'sparth', 'swarth', 'swarty', 'starty',
'starvy', 'starve', 'staree', 'starer', 'soarer',
'soaper', 'souper', 'couper', 'coupee', 'couple',
'copple', 'popple', 'popply', 'popely', 'popery',
'ropery', 'rosery', 'rosary', 'rotary', 'notary',
'nonary', 'donary', 'denary', 'senary', 'sentry',
'gentry', 'gantry', 'pantry', 'paltry', 'peltry']
7 41 ['turfite', 'turgite', 'tergite', 'termite', 'termine',
'terrine', 'terrane', 'terrage', 'serrage', 'servage',
'selvage', 'sylvage', 'sylvate', 'solvate', 'volvate',
'valvate', 'vallate', 'villate', 'village', 'pillage',
'pellage', 'pellate', 'mellate', 'mellite', 'millite',
'milline', 'milling', 'willing', 'welling', 'welding',
'wedding', 'wedging', 'sedging', 'serging', 'serving',
'nerving', 'nervine', 'cervine', 'corvine', 'corvina',
'cortina']
8 38 ['deafness', 'dearness', 'nearness', 'neatness',
'featness', 'feltness', 'fellness', 'wellness',
'willness', 'wildness', 'mildness', 'milkness',
'silkness', 'sickness', 'sickless', 'sackless',
'tackless', 'tankless', 'tangless', 'pangless',
'paneless', 'waneless', 'wareless', 'wardless',
'wordless', 'fordless', 'foodless', 'footless',
'sootless', 'shotless', 'showless', 'thowless',
'thewless', 'thewness', 'thenness', 'thinness',
'thisness', 'thusness']
9 23 ['unpausing', 'unpassing', 'unpasting', 'unwasting',
'unwaiting', 'unwailing', 'unfailing', 'unfalling',
'unfilling', 'untilling', 'untelling', 'unselling',
'unsealing', 'unhealing', 'unhearing', 'unwearing',
'unweaving', 'unreaving', 'unreeving', 'unreeling',
'unfeeling', 'unfeeding', 'unheeding']
10 14 ['unsinkable', 'unsingable', 'unwingable',
'unwindable', 'unbindable', 'unbendable',
'unvendable', 'unventable', 'unrentable',
'unrestable', 'untestable', 'untastable',
'unwastable', 'unwashable']
11 13 ['buckishness', 'puckishness', 'peckishness',
'peakishness', 'weakishness', 'wearishness',
'bearishness', 'boarishness', 'boorishness',
'moorishness', 'moodishness', 'goodishness',
'goosishness']
12 8 ['modification', 'codification', 'conification',
'sonification', 'sinification', 'vinification',
'vilification', 'bilification']
13 5 ['infectiveness', 'invectiveness', 'inventiveness',
'intentiveness', 'intensiveness']
14 6 ['inventibleness', 'invendibleness',
'unvendibleness', 'unvendableness',
'unbendableness', 'unbondableness']
15 3 ['integripalliate', 'integropalliate',
'integropalliata']
16 4 ['incontrovertibly', 'uncontrovertibly',
'uncontrovertible', 'uncontrovertable']
17 3 ['disproportionally', 'disproportionably',
'disproportionable']
18 3 ['chlorophylligenous', 'chlorophylligerous',
'chlorophylliferous']
19 2 ['representationalism', 'representationalist']
20 3 ['uncontrovertableness', 'uncontrovertibleness',
'incontrovertibleness']
21 2 ['undistinguishableness', 'indistinguishableness']
22 0
23 2 ['pseudolamellibranchiate', 'pseudolamellibranchiata']
24 0
Andrew
dalke-DxsMES/F/[email protected]
# A Python solution to the Perl Expert quiz of the week #22
import sys, time
# From Jeff Epler, 2004-06-05 on comp.lang.python
def shortest_path(start, end, adj):
seen = {start: None} # XXX use sets here instead
queue = [[start]] # XXX use collections.deque here instead
while queue:
partial = queue.pop(0) # XXX this is O(|queue|)
tail = partial[-1]
for edge in adj[tail]:
if edge in seen: continue
seen[edge] = None
next_partial = partial + [edge]
if edge == end:
return next_partial
queue.append(next_partial)
def main(argv):
if not (3 <= len(argv) <= 4):
raise SystemExit("Usage: %s from_word to_word [words_filename]"
%
sys.argv[0])
_, from_word, to_word, filename = (argv +
["/usr/share/dict/words"])[:4]
if len(from_word) != len(to_word):
raise SystemExit("the words must have the same length")
from_word = from_word.lower()
to_word = to_word.lower()
n = len(from_word)
if n == 0:
return
subword_parents = {}
graph = {}
range_n = range(n)
for line in open(filename, "U"):
if len(line) != n+1:
continue
word = line[:-1].lower()
for i in range_n:
subword = word[:i] + "\000" + word[i+1:]
# Slightly faster on my machine than
# subword_parents.setdefault(subword, []).append(word)
if subword in subword_parents:
subword_parents[subword].append(word)
else:
subword_parents[subword] = [word]
graph[word] = []
for words in subword_parents.itervalues():
for i in range(len(words)):
graph[words[i]].extend(words[0:i] + words[i+1:])
if from_word not in graph:
raise SystemExit("%r is not in the dictionary" % (from_word,))
if to_word not in graph:
raise SystemExit("%r is not in the dictionary" % (to_word,))
result = shortest_path(from_word, to_word, graph)
if result is None:
raise SystemExit("no path found")
else:
print "\n".join(result)
if __name__ == "__main__":
main(sys.argv)