This is a word game from a set of activity cards for children. Below the rules is code to find the best triplet using /usr/share/dict/words. I thought it was an interesting optimization problem, and am wondering if people can find improvements.
Rules
- Choose one letter from each of the sets below.
- Choose a word using the letters chosen (and any others).
- Score the word.
- Each letter from the chosen set gets the number shown with the set (repeats included).
AEIOU
count 0- All other letters are -2
- Repeat steps 1-3 above (no reusing letters in step 1) twice more.
- Final score is the sum of the three word scores.
Sets
(set 1 scores 1 point, set 2 scores 2 points, etc.)
- LTN
- RDS
- GBM
- CHP
- FWV
- YKJ
- QXZ
Code:
from itertools import permutations
import numpy as np
points = {'LTN' : 1,
'RDS' : 2,
'GBM' : 3,
'CHP' : 4,
'FWV' : 5,
'YKJ' : 6,
'QXZ' : 7}
def tonum(word):
word_array = np.zeros(26, dtype=np.int)
for l in word:
word_array[ord(l) - ord('A')] += 1
return word_array.reshape((26, 1))
def to_score_array(letters):
score_array = np.zeros(26, dtype=np.int) - 2
for v in 'AEIOU':
score_array[ord(v) - ord('A')] = 0
for idx, l in enumerate(letters):
score_array[ord(l) - ord('A')] = idx + 1
return np.matrix(score_array.reshape(1, 26))
def find_best_words():
wlist = [l.strip().upper() for l in open('/usr/share/dict/words') if l[0].lower() == l[0]]
wlist = [l for l in wlist if len(l) > 4]
orig = [l for l in wlist]
for rep in 'AEIOU':
wlist = [l.replace(rep, '') for l in wlist]
wlist = np.hstack([tonum(w) for w in wlist])
best = 0
ct = 0
bestwords = ()
for c1 in ['LTN']:
for c2 in permutations('RDS'):
for c3 in permutations('GBM'):
for c4 in permutations('CHP'):
for c5 in permutations('FWV'):
for c6 in permutations('YJK'):
for c7 in permutations('QZX'):
vals = [to_score_array(''.join(s)) for s in zip(c1, c2, c3, c4, c5, c6, c7)]
ct += 1
print ct, 6**6
scores1 = (vals[0] * wlist).A.flatten()
scores2 = (vals[1] * wlist).A.flatten()
scores3 = (vals[2] * wlist).A.flatten()
m1 = max(scores1)
m2 = max(scores2)
m3 = max(scores3)
if m1 + m2 + m3 > best:
print orig[scores1.argmax()], orig[scores2.argmax()], orig[scores3.argmax()], m1 + m2 + m3
best = m1 + m2 + m3
bestwords = (orig[scores1.argmax()], orig[scores2.argmax()], orig[scores3.argmax()])
return bestwords, best
if __name__ == '__main__':
import timeit
print timeit.timeit('print find_best_words()', 'from __main__ import find_best_words', number=1)
The matrix version is what I came up with after writing one in pure python (using dictionaries and scoring each word independently), and another in numpy but using indexing rather than matrix multiplication.
The next optimization would be to remove the vowels from the scoring entirely (and use a modified ord()
function), but I wonder if there are even faster approaches.
EDIT: added timeit.timeit code
EDIT: I'm adding a bounty, which I'll give to whichever improvement I most like (or possibly multiple answers, but I'll have to accrue some more reputation if that's the case).