Cheating with friends

cheat.md

#Cheating at 'scramble with friends'

Just to prove a point, horrible python but hacked together so excusable. Scored 800 points in a test round.

(ENV)λ  Python git:(master) ✗ time python scramble.py
Please enter line 1 delimited by spaces:
o e s e
Please enter line 2 delimited by spaces:
y s r u
Please enter line 3 delimited by spaces:
r a e d
Please enter line 4 delimited by spaces:
z b t e
Search size: 16
Search size: 84
Search size: 408
Search size: 1764
Search size: 6712
Search size: 22062
Search size: 64826
Search size: 169524
Search size: 392142
['essayer', 'debases', 'berated', 'teasers', 'assured', 'rebated', 'russet', 'yessed', 'rebate', 'debate', 'assure', 'deters', 'debars', 'erased', 'erases', 'dressy', 'reseed', 'dreary', 'teaser', 'teases', 'debase', 'raters', 'duress', 'sabers', 'seated', 'berate', 'reuses', 'essay', 'tares', 'arsed', 'sears', 'erase', 'dress', 'users', 'braes', 'dears', 'rated', 'based', 'bares', 'deary', 'debar', 'baser', 'drays', 'terse', 'sated', 'bases', 'rates', 'rater', 'teary', 'tared', 'brays', 'beard', 'rared', 'tears', 'reuse', 'saber', 'deter', 'bared', 'rares', 'brass', 'reset', 'drear', 'bates', 'tease', 'resat', 'bears', 'bated', 'betas', 'suede', 'ruses', 'rears', 'eases']
python scramble.py  4.67s user 0.63s system 52% cpu 10.138 total

scramble.py

import re
import enchant
import string
from collections import defaultdict

d = enchant.Dict("en_US")

checked = {}

whitespace_regex = re.compile('\s')
width = 4
height = 4
charmap = [[0] * height for column in xrange(width)]

for x in xrange(0, height):
  line_input = raw_input("Please enter line " + str(x + 1) + " delimited by spaces: \n")
  chars = whitespace_regex.split(line_input)
  if len(chars) > width: raise Exception("Too many characters in line " + str(x + 1) + "!")
  if len(chars) < width: raise Exception("Too few characters in line " + str(x + 1) + "!")
  for y, char in enumerate(chars): charmap[x][y] = char

frontier = []
results = set()

vowels = re.compile('[aeiouy]')
for x, y in ((x, y) for x in xrange(width) for y in xrange(height)):
  start = (x, y)
  past = set([start])
  seed_tuple = (start, past, charmap[x][y])
  frontier.append(seed_tuple)

def valid_moves(position, past):
  x, y = position
  le_b = max(x-1, 0)
  ri_b = min(x+1, width-1)
  to_b = max(y-1, 0)
  lo_b = min(y+1, height-1)

  return (move for move in ((x, y) for x in xrange(le_b, ri_b+1) for y in xrange(to_b, lo_b+1)) if move != position and not move in past)

_add_result = results.add
_check_word = d.check
_has_vowels = vowels.search
_join = string.join
while len(frontier) > 0:
  print("Search size: " + str(len(frontier)))

  def consider_word(t):
    _, _, word = t
    if len(word) <= 4:
      return True
    else:
      if not(len(word) < 9 and _has_vowels(word[-4:])): return False
      try:
        is_word = checked[word]
      except KeyError:
        is_word = _check_word(word)
        checked[word] = is_word
      if is_word: _add_result(word)
      return True

  old_frontier = frontier
  frontier = []
  _extend = frontier.extend

  for (pos, past, word, moves) in ((pos, past, word, valid_moves(pos, past))for (pos, past, word) in filter(consider_word, old_frontier)):
    _extend(((x, y), past | set([(x, y)]), _join([word, charmap[x][y]], '')) for x, y in moves)


sortedlist=sorted(list(results), key=lambda w: len(w), reverse=True)
print(sortedlist)