Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Crossword Solver by colinmcnicholl
from itertools import groupby
class Crossword_Puzzle:
"""Represents a fill-in type crossword that features a grid and a full list of
words from which words are chosen and entered in the empty cells in the grid.
There are no clues for where each word goes.
Attributes are:
crossword: A list of strings.
words: A list of words.
variables: A list of the variables in the grid (across and down
sequences of cells to be filled with words).
Example crossword:
0 1 2 3 4
+---+---+---+---+---+ Given the list of words:
0 | 1 | | 2 | | 3 | AFT LASER
+---+---+---+---+---+ ALE LEE
1 | # | # | | # | | EEL LINE
+---+---+---+---+---+ HEEL SAILS
2 | # | 4 | | 5 | | HIKE SHEET
+---+---+---+---+---+ HOSES STEER
3 | 6 | # | 7 | | | KEEL TIE
+---+---+---+---+---+ KNOT
4 | 8 | | | | |
+---+---+---+---+---+
5 | | # | # | | # | The numbers 1,2,3,4,5,6,7,8 in the crossword
+---+---+---+---+---+ puzzle correspond to the words
that will start at those locations.
"""
def __init__(self, crossword, words):
self.variables = []
self.crossword = crossword
self.get_variables(crossword)
self.get_variables(list(zip(*crossword)), True)
self.get_intersects(words)
def get_variables(self, crossword, rotate=False):
for row, seq in enumerate(crossword):
cell_groups = [(k, sum(1 for char in g)) for k,g in groupby(seq)]
col = 0
for k, num in cell_groups:
if k == '.' and num > 2:
if rotate:
self.variables.append(Variable(col, row, num, 1))
else:
self.variables.append(Variable(row, col, num, 0))
col += num
def get_intersects(self, words):
for var1 in self.variables:
for var2 in self.variables:
if var1.dir != var2.dir:
ndx_pair = get_intersect_index_pair(var1, var2)
if ndx_pair:
var1.append_intersect(ndx_pair[0], var2, ndx_pair[1])
def solve(self, seen = set()):
if len(self.variables) == len(seen):
solved = [['X' for col in self.crossword[0]] for row in self.crossword]
for var in self.variables:
for ndx in range(var.size):
(solved[var.row + ndx * var.dir]
[var.col + ndx * (1 - var.dir)]) = var.current[ndx]
return [''.join(row) for row in solved]
if not seen:
var = self.variables[0]
to_try = var.domain
else:
to_label = [var for var in self.variables
if all(tried != var for tried in seen)]
var = next((var for var in to_label
if any(var in tried.get_intersect_variables()
for tried in seen)), to_label[0])
to_try = [word for word in var.domain if all(tried.current != word for tried in seen)]
constrained_chars = var.get_constrained_characters()
to_try = [word for word in to_try if all(word[ndx] == char for ndx, char in constrained_chars)]
for word in to_try:
var.current = word
result = self.solve(seen | {var})
if result:
return result
return None
class Variable:
"""Represents a sequence of three or more empty cells in the crossword grid
to be filled in using a word from the given list of words. For example,
a variable may be referred to as 1 across, 2 down, etc..
The variable has the following attributes:
row: The row for the first character in the word, an integer.
col: The column for the first character in the word, an integer.
size: The number of empty cells (and thus # of characters).
dir: 0 for an across cells, 1 for a down cells.
intersects: A dictionary with:
keys:- are integers representing the index of the cell in
the sequence that is intersected by a sequence of empty
cells in the opposite direction.
values:- a 2-tuple containing a crossing variable and the
index of the crossining empty cell in the crossing variable.
domain: A list of words with the same number of characters as size.
current: A string representing the current value of the 'label'
or word selected to fill the empty cells of the variable.
For the example crossword puzzle shown in docstring of class Crossword_Puzzle
we have:
VARIABLE | STARTING CELL | DOMAIN
================================================
1ACROSS | 1 | {HOSES, LASER, SAILS, SHEET, STEER}
4ACROSS | 4 | {HEEL, HIKE, KEEL, KNOT, LINE}
7ACROSS | 7 | {AFT, ALE, EEL, LEE, TIE}
8ACROSS | 8 | {HOSES, LASER, SAILS, SHEET, STEER}
2DOWN | 2 | {HOSES, LASER, SAILS, SHEET, STEER}
3DOWN | 3 | {HOSES, LASER, SAILS, SHEET, STEER}
5DOWN | 5 | {HEEL, HIKE, KEEL, KNOT, LINE}
6DOWN | 6 | {AFT, ALE, EEL, LEE, TIE}
The binary constraints to be satisfied are:
1ACROSS[3] = 2DOWN[1] i.e. the third letter of 1ACROSS must be equal
to the first letter of 2DOWN
1ACROSS[5] = 3DOWN[1]
4ACROSS[2] = 2DOWN[3]
4ACROSS[3] = 5DOWN[1]
4ACROSS[4] = 3DOWN[3]
7ACROSS[1] = 2DOWN[4]
7ACROSS[2] = 5DOWN[2]
7ACROSS[3] = 3DOWN[4]
8ACROSS[1] = 6DOWN[2]
8ACROSS[3] = 2DOWN[5]
8ACROSS[4] = 5DOWN[3]
8ACROSS[5] = 3DOWN[5]
"""
def __init__(self, row, col, size, direction):
self.row = row
self.col = col
self.size = size
self.dir = direction
self.intersects = dict()
self.domain = domain_dict[size]
self.current = ''
def append_intersect(self, ndx1, var2, ndx2):
if ndx1 != None and ndx1 not in self.intersects.keys():
self.intersects[ndx1] = (var2, ndx2)
def get_intersect_variables(self):
return {v[0] for v in self.intersects.values()}
def get_constrained_characters(self):
constrained_ndx_char_tups = []
for ndx1 in self.intersects.keys():
var2, ndx2 = self.intersects[ndx1]
if var2.current:
constrained_ndx_char_tups.append((ndx1, var2.current[ndx2]))
return constrained_ndx_char_tups
def get_intersect_index_pair(variable, variable2):
cross_ndxs_1 = {(variable.row + ndx * variable.dir,
variable.col + ndx * (1 - variable.dir))
for ndx in range(variable.size)}
cross_ndxs_2 = {(variable2.row + ndx * variable2.dir,
variable2.col + ndx * (1 - variable2.dir))
for ndx in range(variable2.size)}
if cross_ndxs_1 & cross_ndxs_2:
r, c = list(cross_ndxs_1 & cross_ndxs_2)[0]
if variable.dir == 0:
ndx1 = c - variable.col
ndx2 = r - variable2.row
else:
ndx1 = r - variable.row
ndx2 = c - variable2.col
return (ndx1, ndx2)
return None
def solver(crossword, words):
global domain_dict
domain_dict = dict()
for word in words:
if len(word) not in domain_dict.keys():
domain_dict[len(word)] = [ word ]
else:
domain_dict[len(word)].append( word )
crossword_puzzle = Crossword_Puzzle(crossword, domain_dict)
return crossword_puzzle.solve()
if __name__ == '__main__':
#These "asserts" using only for self-checking and not necessary for auto-testing
import string
ERROR_TYPE = (False, "The result must be a list/tuple of strings")
ERROR_SIZE = (False, "The result must have the same size as input data")
ERROR_TEMPLATE = (False, "Your result is not look like the original crossword")
ERROR_UNFILLED = (False, "I see the empty cell in your result")
ERROR_TYPE_CELL = (False, "Cells should contains lowercase ascii letters or 'X'")
F_ERROR_REPEATED = lambda w: (False, "Found repeated words '{}'".format(w))
F_ERROR_UNKNOWN = lambda w: (False, "The word '{}' is not from the dictionary".format(w))
WORDS = ['act', 'age', 'air', 'arm', 'art', 'ask', 'bad', 'bag', 'bar', 'bat', 'bed', 'bet', 'bid', 'big', 'bit', 'box', 'boy', 'bug', 'bus', 'buy', 'can', 'cap', 'car', 'cat', 'cow', 'cry', 'cup', 'cut', 'dad', 'day', 'dig', 'dog', 'dot', 'due', 'ear', 'eat', 'egg', 'end', 'eye', 'fan', 'fat', 'fee', 'few', 'fix', 'fly', 'fun', 'gap', 'gas', 'god', 'guy', 'hat', 'hit', 'ice', 'job', 'key', 'kid', 'lab', 'law', 'lay', 'leg', 'let', 'lie', 'lip', 'log', 'low', 'man', 'map', 'mix', 'mom', 'mud', 'net', 'oil', 'one', 'pay', 'pen', 'pie', 'pin', 'pop', 'pot', 'put', 'raw', 'red', 'rip', 'row', 'rub', 'run', 'sad', 'sea', 'set', 'sex', 'she', 'sir', 'sky', 'son', 'sun', 'tap', 'tax', 'tea', 'tie', 'tip', 'toe', 'top', 'try', 'two', 'use', 'war', 'way', 'web', 'win', 'you', 'area', 'army', 'baby', 'back', 'bake', 'ball', 'band', 'bank', 'base', 'bath', 'bear', 'beat', 'beer', 'bell', 'belt', 'bend', 'bike', 'bill', 'bird', 'bite', 'blow', 'blue', 'boat', 'body', 'bone', 'book', 'boot', 'boss', 'bowl', 'burn', 'cake', 'call', 'calm', 'camp', 'card', 'care', 'case', 'cash', 'cell', 'chip', 'city', 'club', 'clue', 'coat', 'code', 'cold', 'cook', 'copy', 'cost', 'crew', 'dare', 'dark', 'data', 'date', 'dead', 'deal', 'dear', 'debt', 'deep', 'desk', 'diet', 'dirt', 'dish', 'disk', 'door', 'drag', 'draw', 'drop', 'dump', 'dust', 'duty', 'ease', 'east', 'edge', 'exam', 'exit', 'face', 'fact', 'fall', 'farm', 'fear', 'feed', 'feel', 'file', 'fill', 'film', 'fire', 'fish', 'flow', 'fold', 'food', 'foot', 'form', 'fuel', 'gain', 'game', 'gate', 'gear', 'gene', 'gift', 'girl', 'give', 'glad', 'goal', 'gold', 'golf', 'good', 'grab', 'hair', 'half', 'hall', 'hand', 'hang', 'harm', 'hate', 'head', 'heat', 'hell', 'help', 'hide', 'high', 'hire', 'hold', 'hole', 'home', 'hook', 'hope', 'host', 'hour', 'hunt', 'hurt', 'idea', 'iron', 'item', 'join', 'joke', 'jump', 'jury', 'keep', 'kick', 'kill', 'kind', 'king', 'kiss', 'knee', 'lack', 'lady', 'lake', 'land', 'lead', 'life', 'lift', 'line', 'link', 'list', 'load', 'loan', 'lock', 'long', 'look', 'loss', 'love', 'luck', 'mail', 'main', 'make', 'male', 'mall', 'many', 'mark', 'mate', 'math', 'meal', 'meat', 'meet', 'menu', 'mess', 'milk', 'mind', 'mine', 'miss', 'mode', 'mood', 'most', 'move', 'nail', 'name', 'neat', 'neck', 'news', 'nose', 'note', 'oven', 'pace', 'pack', 'page', 'pain', 'pair', 'park', 'part', 'pass', 'past', 'path', 'peak', 'pick', 'pipe', 'plan', 'play', 'poem', 'poet', 'pool', 'post', 'pull', 'push', 'quit', 'race', 'rain', 'rate', 'read', 'rent', 'rest', 'rice', 'rich', 'ride', 'ring', 'rise', 'risk', 'road', 'rock', 'role', 'roll', 'roof', 'room', 'rope', 'ruin', 'rule', 'rush', 'safe', 'sail', 'sale', 'salt', 'sand', 'save', 'seat', 'self', 'sell', 'ship', 'shoe', 'shop', 'shot', 'show', 'sick', 'side', 'sign', 'sing', 'sink', 'site', 'size', 'skin', 'slip', 'snow', 'sock', 'soft', 'soil', 'song', 'sort', 'soup', 'spot', 'star', 'stay', 'step', 'stop', 'suck', 'suit', 'swim', 'tale', 'talk', 'tank', 'task', 'team', 'tear', 'tell', 'term', 'test', 'text', 'till', 'time', 'tone', 'tool', 'tour', 'town', 'tree', 'trip', 'tune', 'turn', 'type', 'unit', 'user', 'vast', 'verb', 'verb', 'verb', 'view', 'wait', 'wake', 'walk', 'wall', 'wash', 'wave', 'wear', 'week', 'west', 'wife', 'will', 'wind', 'wine', 'wing', 'wish', 'wood', 'word', 'work', 'wrap', 'yard', 'year', 'zone', 'abuse', 'actor', 'adult', 'agent', 'alarm', 'anger', 'angle', 'apple', 'aside', 'award', 'basis', 'beach', 'being', 'bench', 'birth', 'black', 'blame', 'blank', 'blind', 'block', 'blood', 'board', 'bonus', 'brain', 'brave', 'bread', 'break', 'brick', 'brief', 'broad', 'brown', 'brush', 'buddy', 'bunch', 'buyer', 'cable', 'candy', 'carry', 'catch', 'cause', 'chain', 'chair', 'chart', 'check', 'cheek', 'chest', 'child', 'claim', 'class', 'clerk', 'click', 'clock', 'cloud', 'coach', 'coast', 'count', 'court', 'cover', 'crack', 'craft', 'crash', 'crazy', 'cream', 'cross', 'curve', 'cycle', 'dance', 'death', 'delay', 'depth', 'devil', 'doubt', 'draft', 'drama', 'dream', 'dress', 'drink', 'drive', 'drunk', 'earth', 'entry', 'equal', 'error', 'essay', 'event', 'fault', 'field', 'fight', 'final', 'floor', 'focus', 'force', 'frame', 'front', 'fruit', 'funny', 'glass', 'glove', 'grade', 'grand', 'grass', 'great', 'green', 'group', 'guard', 'guess', 'guest', 'guide', 'habit', 'heart', 'heavy', 'hello', 'honey', 'horse', 'hotel', 'house', 'human', 'hurry', 'ideal', 'image', 'issue', 'joint', 'judge', 'juice', 'knife', 'laugh', 'layer', 'leave', 'level', 'light', 'limit', 'local', 'lunch', 'major', 'march', 'match', 'maybe', 'media', 'metal', 'might', 'minor', 'model', 'money', 'month', 'motor', 'mouse', 'mouth', 'movie', 'music', 'nasty', 'nerve', 'night', 'noise', 'north', 'novel', 'nurse', 'offer', 'order', 'other', 'owner', 'paint', 'panic', 'paper', 'party', 'pause', 'peace', 'phase', 'phone', 'photo', 'piano', 'piece', 'pitch', 'pizza', 'place', 'plane', 'plant', 'plate', 'point', 'pound', 'power', 'press', 'price', 'pride', 'print', 'prior', 'prize', 'proof', 'punch', 'queen', 'quiet', 'quote', 'radio', 'raise', 'range', 'ratio', 'reach', 'reply', 'river', 'rough', 'round', 'royal', 'salad', 'scale', 'scene', 'score', 'screw', 'sense', 'serve', 'shake', 'shame', 'shape', 'share', 'shift', 'shine', 'shirt', 'shock', 'shoot', 'silly', 'skill', 'skirt', 'sleep', 'slice', 'slide', 'smile', 'smoke', 'solid', 'sound', 'south', 'space', 'spare', 'speed', 'spell', 'spend', 'spite', 'split', 'sport', 'spray', 'staff', 'stage', 'stand', 'start', 'state', 'steak', 'steal', 'stick', 'still', 'stock', 'store', 'storm', 'story', 'strip', 'study', 'stuff', 'style', 'sugar', 'sweet', 'swing', 'table', 'taste', 'teach', 'theme', 'thing', 'title', 'today', 'tooth', 'topic', 'total', 'touch', 'tough', 'towel', 'tower', 'track', 'trade', 'train', 'trash', 'treat', 'trick', 'truck', 'trust', 'truth', 'twist', 'uncle', 'union', 'upper', 'usual', 'value', 'video', 'virus', 'visit', 'voice', 'watch', 'water', 'weird', 'wheel', 'while', 'white', 'whole', 'woman', 'world', 'worry', 'worth', 'young', 'youth', 'abroad', 'access', 'action', 'active', 'advice', 'affair', 'affect', 'agency', 'amount', 'animal', 'annual', 'answer', 'appeal', 'aspect', 'assist', 'attack', 'author', 'basket', 'battle', 'beyond', 'bitter', 'border', 'boring', 'bother', 'bottle', 'bottom', 'branch', 'breast', 'breath', 'bridge', 'budget', 'button', 'camera', 'cancel', 'cancer', 'candle', 'career', 'carpet', 'chance', 'change', 'charge', 'choice', 'church', 'client', 'closet', 'coffee', 'collar', 'common', 'cookie', 'corner', 'county', 'couple', 'course', 'cousin', 'credit', 'damage', 'dealer', 'debate', 'degree', 'demand', 'design', 'desire', 'detail', 'device', 'dinner', 'divide', 'doctor', 'double', 'drawer', 'driver', 'editor', 'effect', 'effort', 'employ', 'energy', 'engine', 'escape', 'estate', 'excuse', 'expert', 'extent', 'factor', 'family', 'farmer', 'father', 'female', 'figure', 'finger', 'finish', 'flight', 'flower', 'formal', 'friend', 'future', 'garage', 'garden', 'gather', 'ground', 'growth', 'guitar', 'handle', 'health', 'height', 'horror', 'impact', 'income', 'injury', 'insect', 'inside', 'invite', 'island', 'jacket', 'junior', 'ladder', 'lawyer', 'leader', 'league', 'length', 'lesson', 'letter', 'listen', 'living', 'manner', 'market', 'master', 'matter', 'medium', 'member', 'memory', 'method', 'middle', 'minute', 'mirror', 'mobile', 'moment', 'mother', 'muscle', 'nation', 'native', 'nature', 'nobody', 'normal', 'notice', 'number', 'object', 'office', 'option', 'orange', 'parent', 'people', 'period', 'permit', 'person', 'phrase', 'player', 'plenty', 'poetry', 'police', 'policy', 'potato', 'priest', 'profit', 'prompt', 'public', 'purple', 'reason', 'recipe', 'record', 'refuse', 'region', 'regret', 'relief', 'remote', 'remove', 'repair', 'repeat', 'report', 'resist', 'resort', 'result', 'return', 'reveal', 'review', 'reward', 'safety', 'salary', 'sample', 'scheme', 'school', 'screen', 'script', 'search', 'season', 'second', 'secret', 'sector', 'senior', 'series', 'shower', 'signal', 'silver', 'simple', 'singer', 'single', 'sister', 'source', 'speech', 'spirit', 'spread', 'spring', 'square', 'stable', 'status', 'strain', 'street', 'stress', 'strike', 'string', 'stroke', 'studio', 'stupid', 'summer', 'survey', 'switch', 'system', 'tackle', 'target', 'tennis', 'thanks', 'theory', 'throat', 'ticket', 'tongue', 'travel', 'unique', 'visual', 'volume', 'wealth', 'weight', 'window', 'winner', 'winter', 'wonder', 'worker', 'writer', 'yellow', 'ability', 'account', 'address', 'advance', 'airline', 'airport', 'alcohol', 'analyst', 'anxiety', 'anybody', 'arrival', 'article', 'article', 'attempt', 'average', 'balance', 'bedroom', 'benefit', 'bicycle', 'brother', 'cabinet', 'capital', 'channel', 'chapter', 'charity', 'chicken', 'classic', 'climate', 'clothes', 'college', 'combine', 'comfort', 'command', 'comment', 'company', 'complex', 'concept', 'concern', 'concert', 'consist', 'contact', 'contest', 'context', 'control', 'convert', 'counter', 'country', 'courage', 'culture', 'current', 'deposit', 'diamond', 'disease', 'display', 'drawing', 'economy', 'emotion', 'evening', 'example', 'extreme', 'failure', 'feature', 'feeling', 'finance', 'finding', 'fishing', 'forever', 'fortune', 'freedom', 'funeral', 'garbage', 'general', 'grocery', 'hearing', 'highway', 'history', 'holiday', 'housing', 'husband', 'illegal', 'impress', 'initial', 'kitchen', 'leading', 'leather', 'lecture', 'library', 'machine', 'manager', 'maximum', 'meaning', 'meeting', 'mention', 'message', 'minimum', 'mission', 'mistake', 'mixture', 'monitor', 'morning', 'natural', 'network', 'nothing', 'officer', 'opening', 'opinion', 'outcome', 'outside', 'package', 'parking', 'partner', 'passage', 'passion', 'patient', 'pattern', 'payment', 'penalty', 'pension', 'physics', 'picture', 'plastic', 'present', 'primary', 'private', 'problem', 'process', 'produce', 'product', 'profile', 'program', 'project', 'promise', 'purpose', 'quality', 'quarter', 'reading', 'reality', 'recover', 'regular', 'release', 'request', 'reserve', 'resolve', 'respect', 'respond', 'revenue', 'routine', 'savings', 'science', 'scratch', 'section', 'service', 'session', 'setting', 'shelter', 'society', 'speaker', 'special', 'station', 'stomach', 'storage', 'stretch', 'student', 'subject', 'success', 'support', 'surgery', 'suspect', 'teacher', 'tension', 'thought', 'tonight', 'tourist', 'traffic', 'trainer', 'trouble', 'variety', 'vehicle', 'version', 'village', 'warning', 'weather', 'wedding', 'weekend', 'welcome', 'western', 'whereas', 'witness', 'working', 'writing', 'accident', 'activity', 'addition', 'ambition', 'analysis', 'anything', 'anywhere', 'argument', 'attitude', 'audience', 'baseball', 'bathroom', 'birthday', 'building', 'business', 'calendar', 'campaign', 'category', 'champion', 'chemical', 'computer', 'conflict', 'constant', 'contract', 'creative', 'currency', 'customer', 'database', 'daughter', 'decision', 'delivery', 'designer', 'director', 'disaster', 'discount', 'distance', 'district', 'document', 'election', 'elevator', 'emphasis', 'employee', 'employer', 'engineer', 'entrance', 'estimate', 'evidence', 'exchange', 'exercise', 'external', 'familiar', 'feedback', 'football', 'function', 'guidance', 'homework', 'hospital', 'incident', 'increase', 'industry', 'instance', 'interest', 'internal', 'internet', 'judgment', 'language', 'location', 'magazine', 'marriage', 'material', 'medicine', 'midnight', 'mortgage', 'mountain', 'national', 'negative', 'occasion', 'official', 'opposite', 'ordinary', 'original', 'painting', 'patience', 'personal', 'physical', 'platform', 'pleasure', 'politics', 'position', 'positive', 'possible', 'practice', 'presence', 'pressure', 'priority', 'progress', 'property', 'proposal', 'purchase', 'quantity', 'question', 'reaction', 'register', 'relation', 'relative', 'republic', 'research', 'resident', 'resource', 'response', 'sandwich', 'schedule', 'security', 'sentence', 'shopping', 'shoulder', 'software', 'solution', 'specific', 'standard', 'stranger', 'strategy', 'strength', 'struggle', 'surprise', 'surround', 'swimming', 'sympathy', 'teaching', 'tomorrow', 'training', 'upstairs', 'vacation', 'valuable', 'weakness', 'advantage', 'afternoon', 'agreement', 'apartment', 'assistant', 'associate', 'attention', 'awareness', 'beautiful', 'beginning', 'boyfriend', 'breakfast', 'brilliant', 'candidate', 'challenge', 'character', 'chemistry', 'childhood', 'chocolate', 'cigarette', 'classroom', 'committee', 'community', 'complaint', 'condition', 'confusion', 'criticism', 'departure', 'dependent', 'dimension', 'direction', 'economics', 'education', 'effective', 'emergency', 'equipment', 'extension', 'following', 'guarantee', 'highlight', 'historian', 'implement', 'inflation', 'influence', 'inspector', 'insurance', 'intention', 'interview', 'knowledge', 'landscape', 'marketing', 'necessary', 'newspaper', 'objective', 'operation', 'passenger', 'pollution', 'potential', 'president', 'principle', 'procedure', 'professor', 'promotion', 'reception', 'recording', 'reference', 'secretary', 'selection', 'sensitive', 'signature', 'situation', 'somewhere', 'spiritual', 'statement', 'structure', 'substance', 'telephone', 'temporary', 'tradition', 'variation', 'vegetable', 'yesterday', 'appearance', 'assignment', 'assistance', 'assumption', 'atmosphere', 'background', 'collection', 'commercial', 'commission', 'comparison', 'conclusion', 'conference', 'confidence', 'connection', 'definition', 'department', 'depression', 'difference', 'difficulty', 'discipline', 'discussion', 'efficiency', 'employment', 'enthusiasm', 'equivalent', 'excitement', 'experience', 'expression', 'foundation', 'friendship', 'girlfriend', 'government', 'importance', 'impression', 'indication', 'individual', 'inevitable', 'initiative', 'inspection', 'investment', 'leadership', 'literature', 'management', 'membership', 'obligation', 'particular', 'percentage', 'perception', 'permission', 'philosophy', 'population', 'possession', 'preference', 'profession', 'protection', 'psychology', 'reflection', 'reputation', 'resolution', 'restaurant', 'revolution', 'specialist', 'suggestion', 'technology', 'television', 'transition', 'university', 'advertising', 'alternative', 'application', 'appointment', 'association', 'celebration', 'combination', 'comfortable', 'competition', 'concentrate', 'consequence', 'description', 'development', 'engineering', 'environment', 'examination', 'explanation', 'grandfather', 'grandmother', 'imagination', 'improvement', 'independent', 'information', 'instruction', 'interaction', 'maintenance', 'measurement', 'negotiation', 'opportunity', 'performance', 'personality', 'perspective', 'possibility', 'preparation', 'recognition', 'replacement', 'requirement', 'supermarket', 'temperature', 'championship', 'construction', 'contribution', 'conversation', 'distribution', 'independence', 'introduction', 'manufacturer', 'organization', 'presentation', 'professional', 'refrigerator', 'relationship', 'satisfaction', 'significance', 'communication', 'consideration', 'entertainment', 'establishment', 'international', 'understanding', 'administration', 'recommendation', 'representative', 'responsibility', 'transportation']
def find_word(grid, row, col):
word = ""
while col < len(grid[row]) and grid[row][col] != "X":
word += grid[row][col]
col += 1
return word
def checker(func, template):
result = func(template, WORDS)
# types check
if not isinstance(result, (tuple, list)):
return ERROR_TYPE
if not all(isinstance(row, str) for row in result):
return ERROR_TYPE
# size check
if (len(result) != len(template) or
any(len(result[i]) != len(template[i]) for i in range(len(template)))):
return ERROR_SIZE
# template, letters and filled check
for i, row in enumerate(result):
for j, ch in enumerate(row):
if ch == "X":
if template[i][j] != "X":
return ERROR_TEMPLATE
elif ch == ".":
return ERROR_UNFILLED
elif ch in string.ascii_lowercase:
if template[i][j] != ".":
return ERROR_TEMPLATE
else:
return ERROR_TYPE_CELL
# words checking
used_words = set()
rotated_result = ["".join(row) for row in zip(*result)]
words = []
for k, row in enumerate(template):
for m, symb in enumerate(row):
if symb == "X":
continue
if (k == 0 or template[k - 1][m] == "X") and (k < len(template) - 1 and template[k + 1][m] == "."):
words.append(find_word(rotated_result, m, k))
if (m == 0 or template[k][m - 1] == "X") and (m < len(template[k]) - 1 and template[k][m + 1] == "."):
words.append(find_word(result, k, m))
for w in words:
if w in used_words:
return F_ERROR_REPEATED(w)
used_words.add(w)
if w not in WORDS:
return F_ERROR_UNKNOWN(w)
return True, "Great!"
result, message = checker(solver, ['.XXX.', '...X.', '.X.X.', '.....'])
assert result, "1st example. " + message
result, message = checker(solver, ['X.XX', '....', 'X.XX', 'X...', 'XXX.', '....', 'XXX.'],)
assert result, "2nd example. " + message
result, message = checker(solver, ['...XXXXXX', '.XXX.X...', '.....X.XX', 'XXXX.X...',
'XX...X.XX', 'XX.XXX.X.', 'X......X.', 'XX.X.XXX.', 'XXXX.....'],)
assert result, "3rd example. " + message
Jan. 25, 2020
Comments:
