wordpuzzle.py

import copy
import itertools

from collections import defaultdict

print 'Starting.'

key_words = ['PONIES', 'ACCEPT', 'SEARED', 'CAVIAR']

#wordfile = "/usr/share/dict/words"
wordfile = "words.txt"


def makepartial():
  global partial, words
  print 'Making dictionary...'
  words = set()
  partial = defaultdict(set)
  value_count = 0
  with open(wordfile) as f:
    for line in f.read().splitlines():
      if len(line) == 6:
        line = line.upper()
        words.add(line)
        for i in range(2 ** 6):
          part = list(line)
          for j in range(6):
            mask = 1 << j
            if i & mask:
              part[j] = '*'
          partial[''.join(part)].add(line)
          value_count += 1

  print 'Dictionary created.'
  print 'Word size:', len(words)
  print 'Partial key size:', len(partial)
  print 'Partial value size:', value_count
  print '****** size:', len(partial['******'])

makepartial()

def show(grid):
  assert len(grid) == 12
  square = [['*' for i in range(6)] for j in range(6)]
  for i in range(6):
    if grid[i] is None:
      continue
    for j in range(6):
      if square[i][j] == '*':
        square[i][j] = grid[i][j]
      elif square[i][j] != grid[i][j]:
        raise Exception(str(grid))
  for i in range(6):
    if grid[i + 6] is None:
      continue
    for j in range(6):
      if square[j][i] == '*':
        square[j][i] = grid[i + 6][j]
      elif square[j][i] != grid[i + 6][j]:
        raise Exception(str(grid))
  for i in range(6):
    print ' '.join(square[i])
  print ''



#   6 7 8 9 a b
# 0 * * * * * * 
# 1 * * * * * * 
# 2 * * * * * * 
# 3 * * * * * * 
# 4 * * * * * * 
# 5 * * * * * * 
def fits(grid, word, index):
  if index < 6:
    for i in range(6):
      if grid[index][i] == '*':
        grid[index][i] = word[i]
      elif grid[index][i] != word[i]:
        return False
  else:
    index -= 6
    for i in range(6):
      if grid[i][index] == '*':
        grid[i][index] = word[i]
      elif grid[i][index] != word[i]:
        return False
  return True

def cur(grid, index):
  if index < 6:
    return grid[index]
  index -= 6
  return ''.join([grid[i][index] for i in range(6)])


consider_count = 0


def makeCrossPartial(grid, index):
  if index < 6:
    letters = []
    for i in range(6):
      if grid[6 + i] is None:
        letters.append('*')
      else:
        letters.append(grid[6 + i][index])
  else:
    letters = []
    for i in range(6):
      if grid[i] is None:
        letters.append('*')
      else:
        letters.append(grid[i][index - 6])
  return ''.join(letters)

def gridfits(grid, word, index):
  assert len(grid) == 12
  for i in range(12):
    if grid[i] is not None and type(grid[i]) is not str:
      print type(grid[i])
      print grid
      assert False

  if grid[index]:
    return False
  if index < 6:
    offset = 6
    j = index
  else:
    offset = 0
    j = index - 6
  for i in range(6):
    crossword = grid[offset + i]
    if crossword is not None and crossword[j] != word[i]:
      return False
  return True

def addInitialWords(grid, initial):
  for i in range(4):
    cross = makeCrossPartial(grid, initial[i])
    if key_words[i] not in partial[cross]:
      return False
    grid[initial[i]] = key_words[i]
  return True


def recurse(grid):
  global minnone, bestgrid, messages

  nonecount = 0
  options = None
  impossible = None
  for i in range(12):
    if grid[i] is None:
      nonecount += 1
      cross = makeCrossPartial(grid, i)
      if len(partial[cross]) == 0:
        impossible = cross
        break
      if options is None or len(options) > len(partial[cross]):
        options = partial[cross]
        index = i

  if nonecount < minnone:
    messages.append('state: ' + str(nonecount) + ': ' + str(grid))
    best = True
    bestgrid = copy.copy(grid)
    minnone = nonecount
  else:
    best = False

  if nonecount == 0:
    assert impossible is None
    assert options is None
    messages.append('SOLVED!!!')
    return True

  if impossible is not None:
    if best:
      messages.append('Stopping at impossible: ' + impossible)
    return False

  if best:
    msg = 'Options to try: ' + str(len(options))
    if len(options) < 10:
      msg += ': ' + ','.join(options)
    messages.append(msg)

  for option in options:
    if best:
      messages.append('Trying: ' + option + ' at ' + str(index))
    if gridfits(grid, option, index):
      grid[index] = option
      if recurse(grid):
        return True
      elif best:
        messages.append('(pop)')
      grid[index] = None

  if best:
    messages.append('All options exhausted.')
  return False


working_permutations = 0
permutations_considered = 0
for initial in itertools.permutations(range(12), r=4):
  permutations_considered += 1
  grid = [None for i in range(12)]
  if not addInitialWords(grid, initial):
    continue
  else:
    working_permutations += 1
    origgrid = copy.copy(grid)

  minnone = 12
  bestgrid = copy.copy(grid)
  messages = []
  success = recurse(grid)

  if success:
    print '===================='
    print 'Initial:'
    show(origgrid)
    print 'Messages:'
    for message in messages:
      print '>> ' + message
    print 'Best depth:',minnone
    print 'Grid:'
    show(bestgrid)

print 'Permutations considered:', permutations_considered
print 'Working permutations:', working_permutations