Mercurial > hg > config

annotate python/anagram.py @ 3:a7188391b4ce

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
autojoin socialplanning
author k0s <k0scist@gmail.com>
date Wed, 28 Oct 2009 12:49:24 -0400
parents f3ab51c79813
children 099a3bfa2852
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 # import pdb; pdb.set_trace()
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
49 if subgram is not None:
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
50 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
51
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
52 if 0:
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
53 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
54
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
55 if anagrams:
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
56 return anagrams
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
57 return None
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
58
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
59 if __name__ == '__main__':
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
60 import sys
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
61 from optparse import OptionParser
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
62
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
63 parser = OptionParser()
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
64 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
65 default='')
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
66 (options, args) = parser.parse_args()
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
67
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
68 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
69
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
70 dicts = [ '/home/jhammel/docs/dict.txt',
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
71 '/usr/share/dict/cracklib-small',
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
72 '/usr/share/dict/american-english' ]
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
73
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
74 for i in dicts:
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
75 if os.path.exists(i):
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
76 options.filename = i
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
77 break
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
78 else:
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
79 print 'Dictionary not found'
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
80 parser.print_help()
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
81 sys.exit(1)
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
82
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
83 if not args:
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
84 print 'please provide an anagram'
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
85 sys.exit(0)
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
86
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
87 f = file(options.filename, 'r')
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
88 read_dictionary(f)
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
89
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
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
92 print anagram
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
93 print '-' * len(anagram)
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
94
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
95 anagram = ''.join(anagram.split()).lower()
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
96
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
97 # don't use letter names
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
98 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
99
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
100 wordlist = [ i for i in dictionary
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
101 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
102
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
103 anagrams = anagramize(anagram, wordlist)
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
104
f3ab51c79813 adding configuration from https://svn.openplans.org/svn/config_jhammel/
k0s <k0scist@gmail.com>
parents:
diff changeset
105 print '\n'.join(anagrams)