Skip to content

Instantly share code, notes, and snippets.

@bobbydavid
Created July 31, 2016 19:24
Show Gist options
  • Save bobbydavid/0c9bd07cbf486d5f5a18d777b2cf496d to your computer and use it in GitHub Desktop.
Save bobbydavid/0c9bd07cbf486d5f5a18d777b2cf496d to your computer and use it in GitHub Desktop.
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment