polygon.py

#!/usr/bin/env python3.2

"""
polygon: moo.com polygon puzzle solver

moo.com business cards might have a polygon puzzler on a promotional card in
the pack.  This tool finds the words.
"""

__author__ = '[email protected] (Phil Pennock)'

import argparse
import sys
import itertools

DEFAULT_WORDFILE = '/usr/share/dict/words'

class Polygon(object):
  def __init__(self, letters=None, wordfile=DEFAULT_WORDFILE):
    self.wordfile = wordfile
    if letters is not None:
      self.new_letters(letters)

  def new_letters(self, letters):
    # works for string or other iter:
    self.rawletters = [x.lower() for x in letters]
    return self

  def loaddict(self, dictfile):
    self._wordlist = set(x.strip().lower() for x in open(dictfile).readlines())

  def dictwords(self):
    if not hasattr(self, '_wordlist'):
      self.loaddict(self.wordfile)
    return self._wordlist

  wordlist = property(
      fget=lambda self: self.dictwords(),
      fset=lambda self, v: self.loaddict(v),
      )

  def words_of_len(self, n):
    return self.wordlist.intersection(set(''.join(x) for x in itertools.permutations(self.rawletters, n)))

  def words_of_at_least_len(self, n):
    all = set()
    for i in range(n, len(self.rawletters)+1):
      all.update(self.words_of_len(i))
    return all

def _main(args, argv0):
  parser = argparse.ArgumentParser()
  parser.add_argument('-w', '--wordfile',
                      default=DEFAULT_WORDFILE, help='dictionary wordfile')
  parser.add_argument('-m', '--minlength',
                      default=4, type=int, help='minimum letters needed')
  parser.add_argument('letters', nargs='+', help='polygon letters')
  options = parser.parse_args(args=args)

  poly = Polygon(wordfile=options.wordfile)
  for letters_item in options.letters:
    available = poly.new_letters(letters_item).words_of_at_least_len(options.minlength)
    msg = '{comboletters}: {wordcount} words of at least length {minlength}'.format(
        comboletters = ''.join(x for x in letters_item),
        wordcount = len(available),
        minlength = options.minlength,
        )
    print('{0}\n{1}\n'.format(msg, '-'*len(msg)), end='')
    print(' '.join(sorted(available)))
    print()

if __name__ == '__main__':
  argv0 = sys.argv[0].rsplit('/')[-1]
  rv = _main(sys.argv[1:], argv0=argv0)
  sys.exit(rv)

# vim: set ft=python sw=2 expandtab :

Note that this works for letter lists of length 9, but not so well as the length ramps up. This was fast to write and fast to solve the supplied puzzles, but is not fast in the general case.

Given:

import math

class F(object):
  def __init__(self):
    self.fmap = {}
  def factorial(self, i):
    if i not in self.fmap:
      self.fmap[i] = math.factorial(i)
    return self.fmap[i]
  def permutations(self, n, k):
    nf = self.factorial(n)
    nkf = self.factorial(n-k)
    return nf // nkf
  def letters_for_words(self, letters_len, min_word_len):
    count = 0
    print('Given {0} letters'.format(letters_len))
    for i in range(min_word_len, letters_len+1):
      p = self.permutations(letters_len, i)
      print('Permutations length {0}: {1}'.format(i, p))
      count += p
    print('Total possible words in set: {0}'.format(count))

We get (after f = F()):

>>> f.letters_for_words(9, 4)
Given 9 letters
Permutations length 4: 3024
Permutations length 5: 15120
Permutations length 6: 60480
Permutations length 7: 181440
Permutations length 8: 362880
Permutations length 9: 362880
Total possible words in set: 985824
>>> f.letters_for_words(13, 4)
Given 13 letters
Permutations length 4: 17160
Permutations length 5: 154440
Permutations length 6: 1235520
Permutations length 7: 8648640
Permutations length 8: 51891840
Permutations length 9: 259459200
Permutations length 10: 1037836800
Permutations length 11: 3113510400
Permutations length 12: 6227020800
Permutations length 13: 6227020800
Total possible words in set: 16926795600

Google Interview Question: how would you optimise this? ;)