Thursday, December 31, 2009

Craziest

Craziest - a dictionary for Scrabble and other word games.

It works on the premise that you have some assortment of letters, and aybe a blank or two (which can be used as any letter in the alphabet) and you want to find out what words can you make out of those letters. And that's what this script is for.

For instance, you have the letters: GZXATA and a blank tile, so you go:

craziest.py GZXATA?

(the question mark represents a single blank) and the script will print out a list of words and their value in points, e.g.:

14   ZAP
14 GAZE
13 ZETA
13 WAX
13 FAX
13 ADZ
12 ZIT

By default, the program uses the master aspell dictionary, but you can force it to use any list of words (the -D switch) or any command that produces it (the -d switch).

Also, it's possible to specify what length the word should be by manipulating the maximum and minimum number of letters (-M and -m switches, respectively) - the default values are 7 and 2.

You can also choose to provide your own alphabet, or letter scores, using an alphabet file (switch -a) where each line would contain a single letter and its score, separated by whitespace.

Oh, and as a rule, the entire script is case insensitive, except for when the dictionary is read in, where the words that start with a capital letter are filtered out.

Also, the name craziest is a reference to the triple-triple that is the highest achievable single word score in Scrabble (that I know of). Here, it's all explained here in this vidlit.

And finally, ladies and gentlemen, the code:
 
1 #!/usr/bin/python
2 #
3 # Craziest
4 #
5 # A script to find all legal Scrabble words that can be made using some list
6 # of letters and a dictionary of all legal words, and sort the output by the
7 # total score of each word.
8 #
9 # Parameters:
10 # -m, --min-length= Specify the minimum length of a word.
11 # -M, --max-length= Specify the maximum length of a word.
12 # -d, --dictionary-command= Provide a command that gives the list
13 # of correct words.
14 # -D, --dictionary-file= Provide a file with the list of correct words.
15 # -a, --alphabet= Specify available letters and their weights.
16 # -n, --no-scores Do not display word scores.
17 # -b, --blank-symbol= Define the symbol used to represent a blank.
18 # -h, --usage Command usage information.
19 #
20 # Author:
21 # Konrad Siek
22 #
23 # License
24 # Copyright 2009 Konrad Siek
25 #
26 # This program is free software: you can redistribute it and/or modify
27 # it under the terms of the GNU General Public License as published by
28 # the Free Software Foundation, either version 3 of the License, or
29 # (at your option) any later version.
30 #
31 # This program is distributed in the hope that it will be useful,
32 # but WITHOUT ANY WARRANTY; without even the implied warranty of
33 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
34 # GNU General Public License for more details.
35 #
36 # You should have received a copy of the GNU General Public License
37 # along with this program. If not, see <http://www.gnu.org/licenses/>.
38
39 SCORES = {
40 'A': 1, 'B': 3, 'C': 3, 'D': 2, 'E': 1, 'F': 4, 'G': 2, 'H': 4,
41 'I': 1, 'J': 8, 'K': 5, 'L': 1, 'M': 3, 'N': 1, 'O': 1, 'P': 3,
42 'Q': 10, 'R': 1, 'S': 1, 'T': 1, 'U': 1, 'V': 4, 'W': 4, 'X': 8,
43 'Y': 4, 'Z': 10,
44 }
45
46 def usage(program):
47 """ Print the usage information."""
48 print """Usage: %s [OPTIONS] LETTERS [, ...]'
49 OPTIONS
50 -m, --min-length= Specify the minimum length of a word.
51 -M, --max-length= Specify the maximum length of a word.
52 -d, --dictionary-command= Provide a command that gives the list
53 of correct words.
54 -D, --dictionary-file= Provide a file with the list of correct words.
55 -a, --alphabet= Specify available letters and their weights.
56 -n, --no-scores Do not display word scores.
57 -b, --blank-symbol= Define the symbol used to represent a blank.
58 -h, --usage Command usage information.
59 """ % program
60
61 class AspellDictionary:
62 def __init__(self, command='aspell dump master', keep_capitals = False):
63 """ Create an instance of the dictionary using a command."""
64 import commands
65 self.words = set([])
66 for word in commands.getoutput(command).split():
67 if len(word) > 0 and word[0].islower():
68 self.words.add(word.upper())
69
70 class FileDictionary:
71 def __init__(self, path, keep_capitals = False):
72 """ Create a dictionary from a file."""
73 self.words = set([])
74 for line in file(path).readlines():
75 for word in line.split():
76 if len(word) > 0 and word[0].islower():
77 self.words.add(word.upper())
78
79 def read_scores(path):
80 """ Read a list of available letters and their scores from a file."""
81 score = {}
82 for line in file(path).readlines():
83 letter, value = line.split(None, 1)
84 score[letter.upper()] = int(value)
85 return score
86
87 def create_words(letters, dictionary, min_length=2, max_length=8):
88 """ Create a list of all possible words that can be created from the given
89 list of letters. All the words will be correct according to the provided
90 dictionary.
91 """
92 from itertools import permutations
93 possible_words = set([])
94 for length in range(min_length, max_length + 1):
95 for permutation in permutations(letters, length):
96 possible_words.add("".join(permutation).upper())
97 return dictionary.words.intersection(possible_words)
98
99 def weigh_word(word, scores):
100 """ Add the score of each letter to produce the score of the word."""
101 sum = 0
102 for letter in word:
103 sum += scores[letter]
104 return sum
105
106 def expand_blanks(word, blank_symbol = '?', letters = SCORES.keys()):
107 """ Expand the symbol representing a blank into all possible letters."""
108 if word.find(blank_symbol) < 0:
109 return [word]
110 from itertools import permutations
111 words = []
112 template = word.replace(blank_symbol, "%s")
113 for tuple in permutations(letters, word.count(blank_symbol)):
114 words.append(template % tuple)
115 return words
116
117 def generate(argument, dictionary, min_length, max_length, blank, scores):
118 """ Generate a list of possible words."""
119 words = set([])
120 for expanded_set in expand_blanks(argument, blank, scores.keys()):
121 word_list = create_words(expanded_set, dictionary, min_length, max_length)
122 word_set = set(word_list)
123 words = words.union(word_set)
124 return words
125
126 def weigh(words, scores = SCORES):
127 """ Add scores to the words in the list."""
128 weighed_words = []
129 for word in words:
130 weighed_words.append((weigh_word(word, scores), word))
131 weighed_words.sort(None, None, True)
132 return weighed_words
133
134 def printout(weighed_words, show_weights = True):
135 """ Print out the list of words."""
136 if show_weights:
137 for pair in weighed_words:
138 print "%-4s\t%s" % pair
139 else:
140 for _, word in weighed_words:
141 print word
142
143 if __name__ == '__main__':
144 import sys
145 from getopt import getopt
146
147 # Default values for parameters.
148 dictionary = AspellDictionary()
149 min_length, max_length = (2, 7)
150 blank_symbol = '?'
151 show_scores = True
152 scores = SCORES
153
154 # Definitions of switches.
155 shorts = [ 'm:', 'M:', 'd:', 'D:', 'h', 'n', 'b:', 'a:']
156 longs = [
157 'min-length=', 'max-length=', 'dictionary-command=',
158 'dicionary-file=', 'usage', 'no-scores', 'blank-symbol=',
159 'alphabet='
160 ]
161
162 # Process user-supplied commandline parameters.
163 opts, args = getopt(sys.argv[1:], ''.join(shorts), longs)
164 for opt in opts:
165 if opt[0] in ['-m', '--min-length']:
166 min_length = int(opt[1])
167 elif opt[0] in ['-M', '--max-length']:
168 max_length = int(opt[1])
169 elif opt[0] in ['-d', '--dictionary-command']:
170 dictionary = AspellDicionary(opt[1])
171 elif opt[0] in ['-D', '--dictionary-file']:
172 dictionary = FileDictionary(opt[1])
173 elif opt[0] in ['-a', '--alphabet']:
174 scores = read_scores(opt[1])
175 elif opt[0] in ['-b', '--blank-symbol']:
176 blank_symbol = opt[1]
177 elif opt[0] in ['-n', '--no-scores']:
178 show_scores = False
179 elif opt[0] in ['-h', '--usage']:
180 usage(sys.argv[0])
181 sys.exit(0)
182 else:
183 usage(sys.argv[0])
184 sys.exit(1)
185
186 # Process each of the aguments.
187 for argument in args:
188 words = generate(
189 argument, dictionary, min_length, max_length, blank_symbol, scores
190 )
191 weighed_words = weigh(words, scores)
192 printout(weighed_words, show_scores)
193


The code is also available at GitHub as python/craziest.py.