Mercurial > hg > config

annotate python/anagram.py @ 408:705dc5cfd68d

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
make this modular
author Jeff Hammel <jhammel@mozilla.com>
date Sun, 04 Aug 2013 10:31:11 -0700
parents 4096771c8b9f
children 83618049c2ff
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
0
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
1 #!/usr/bin/env python
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
2
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
3 import os
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
4
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
5 dictionary = []
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
6
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
7 def read_dictionary(f):
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
8 for name in f.readlines():
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
9 name = name.strip('\n')
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
10 word = ''.join(name.split()).lower()
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
11 dictionary.append(word)
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
12
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
13 def is_in(string1, string2):
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
14
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
15 string2 = list(string2)
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
16
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
17 try:
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
18 for i in string1:
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
19 string2.remove(i)
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
20 except ValueError:
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
21 return None
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
22
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
23 return ''.join(string2)
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
24
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
25 def anagramize(theword, wordlist, level=0):
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
26
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
27 if 0:
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
28 print '%s%s : %s' % ('-' * level, theword, wordlist)
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
29
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
30 anagrams = []
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
31
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
32 # start the search with a new word
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
33 for index in range(len(wordlist)):
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
34 word = wordlist[index]
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
35 subword = is_in(word, theword)
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
36 if subword == '':
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
37 anagrams.append(word)
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
38 continue
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
39
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
40 if subword is None:
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
41 continue
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
42
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
43
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
44 sublist = [ i for i in wordlist[index:]
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
45 if is_in(i, subword) is not None ]
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
46 subgram = anagramize(subword, sublist, level+1)
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
47
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
48 if subgram is not None:
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
49 anagrams += [ ' '.join((word, i)) for i in subgram ]
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
50
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
51 if 0:
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
52 print '%s%s returning %s' % ('-' * level, theword, anagrams)
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
53
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
54 if anagrams:
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
55 return anagrams
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
56 return None
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
57
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
58 if __name__ == '__main__':
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
59 import sys
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
60 from optparse import OptionParser
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
61
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
62 parser = OptionParser()
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
63 parser.add_option("-f", dest="filename", help="dictionary to read",
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
64 default='')
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
65 (options, args) = parser.parse_args()
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
66
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
67 if not os.path.exists(options.filename):
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
68
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
69 dicts = [ '/home/jhammel/docs/dict.txt',
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
70 '/usr/share/dict/cracklib-small',
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
71 '/usr/share/dict/american-english' ]
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
72
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
73 for i in dicts:
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
74 if os.path.exists(i):
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
75 options.filename = i
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
76 break
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
77 else:
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
78 print 'Dictionary not found'
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
79 parser.print_help()
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
80 sys.exit(1)
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
81
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
82 if not args:
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
83 print 'please provide an anagram'
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
84 sys.exit(0)
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
85
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
86 f = file(options.filename, 'r')
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
87 read_dictionary(f)
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
88
21
099a3bfa2852 fixes to anagram.py
k0s <k0scist@gmail.com>
parents: 0
diff changeset
89 # XXX could cleanup
0
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
90 anagram = ' '.join(args)
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
91 anagram = ''.join(anagram.split()).lower()
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
92
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
93 # don't use letter names
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
94 dictionary = [ i for i in dictionary if (len(i) > 1) or i in 'ai' ]
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
95
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
96 wordlist = [ i for i in dictionary
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
97 if i and is_in(i, anagram) is not None ]
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
98
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
99 anagrams = anagramize(anagram, wordlist)
145
4096771c8b9f protect from no anagrams case
Jeff Hammel <jhammel@mozilla.com>
parents: 21
diff changeset
100
4096771c8b9f protect from no anagrams case
Jeff Hammel <jhammel@mozilla.com>
parents: 21
diff changeset
101 if anagrams:
4096771c8b9f protect from no anagrams case
Jeff Hammel <jhammel@mozilla.com>
parents: 21
diff changeset
102 print '\n'.join(anagrams)