Monday, November 12, 2012

Dirty Letterpress

My friend Andy introduced me to an iphone game called letterpress. The concept is pretty simple and the game is easy to learn - you have a board full of letters and you can create words out of any number of them. You get points for ever letter used, subject to some nuances about how they are defended and such.
iPhone Screenshot 1
(The picture is from the appstore link above)

Andy beat me a couple of times quite handily. Which got me thinking about how this was a rather simple string search problem that I was failing at. Enter python.

#!/usr/bin/python
import sys

board = sorted(sys.argv[1].lower())

d = open('/usr/share/dict/words')
for w in d:
s = sorted(w.strip().lower())
if len(s) < 9: continue
i = 0; j = 0
while i < len(s) and j < len(board):
if s[i] == board[j]:
i = i+1
j = j+1
elif s[i] > board[j]:
j = j+1
else:
j = len(board)
if i == len(s):
print len(s), " ", w.strip()


And the expected results:

letterpress > ./letterpress.py evkrvtzahfcyxvgatiwigoezy | sort -nr
12   vociferative
12   overactivity
12   excogitative
11   viaggiatory
11   theatricize
11   rhyotaxitic
11   overagitate
11   heterotaxic
11   heterotaxia
11   gravitative
11   fevertwitch
11   exhortative
10   whitterick
10   vociferize
10   vociferate
10   victoriate
10   verificate
10   twitchfire
10   thieftaker

Needless to say Andy caught on quite quick that something was amiss :) I resigned.