Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
ChainMap & Counter solution in Clear category for Crossword Solver by gyahun_dash
from collections import ChainMap, Counter
from functools import reduce
from itertools import chain, groupby
from operator import mul
def solver(crossword, vocab):
grid = [[(i, j) for j in range(len(r))] for i, r in enumerate(crossword)]
table = dict(zip(chain(*grid), chain(*crossword)))
segs = (groupby(line, key=table.get) for line in chain(grid, zip(*grid)))
spaces = (tuple(s) for k, s in chain(*segs) if k == '.')
blanks = [s for s in spaces if len(s) > 1]
cross = {x for x, c in Counter(chain(*blanks)).items() if c == 2}
wsets = {k: set(g) for k, g in groupby(sorted(vocab, key=len), key=len)}
links = []
connect = lambda b: [len(set(b) & set(s)) for s in (chain(*links), cross)]
while blanks:
links.append(blanks.pop(blanks.index(max(blanks, key=connect))))
def search(blanks, words=ChainMap(wsets), letters=ChainMap()):
blank, *rest = blanks
length = len(blank)
def getletters(x):
if x in letters: return Counter(letters[x])
link = next(b for b in rest if x in b)
return Counter(word[link.index(x)] for word in words[len(link)])
stats = {blank.index(x): getletters(x) for x in cross & set(blank)}
estimate = lambda w: reduce(mul, (stats[i][w[i]] for i in stats))
scores = Counter({w: estimate(w) for w in words[length]})
for word in sorted(+scores, key=scores.get, reverse=True):
newletters = letters.new_child(dict(zip(blank, word)))
if not rest: return newletters
newwords = words.new_child({length: words[length] - {word}})
result = search(rest, newwords, newletters)
if result is not None: return result
letters = search(links)
return [''.join(letters.get(c, 'X') for c in row) for row in grid]
April 12, 2016
Comments: