Created
August 4, 2022 20:40
-
-
Save smithcommajoseph/532281e226191d4620cd8b3c2786d788 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
{ | |
"cells": [ | |
{ | |
"cell_type": "markdown", | |
"metadata": {}, | |
"source": [ | |
"Below is a solution for [exercise 4.1](http://artint.info/2e/html/ArtInt2e.Ch4.S12.html#Ch4.F14). I have added comments to explain my thought process and approach. \n", | |
"\n", | |
"I utilized something akin to the first representation (represent the word positions (1-across, 4-across, etc.) as variables, with the set of words as possible values) - reducing the search space at each step via word filtering and board validation, the latter of which ensures domain consistency (I believe this fulfills part a).\n", | |
"\n", | |
"First we create a `Crossword_Solver` class." | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 89, | |
"metadata": {}, | |
"outputs": [], | |
"source": [ | |
"class Crossword_Solver():\n", | |
"\n", | |
" WIDTH = None\n", | |
" HEIGHT = None\n", | |
" words = None\n", | |
" board = None\n", | |
" is_valid = False\n", | |
" logging = False\n", | |
" \n", | |
" # on init add wordlist, width, height and logging props\n", | |
" def __init__(self, words, width=3, height=3, logging=False):\n", | |
" self.words = words\n", | |
" self.WIDTH = width\n", | |
" self.HEIGHT = height\n", | |
" self.logging = logging\n", | |
"\n", | |
" if self.logging:\n", | |
" print('Logging is set to True\\n')\n", | |
"\n", | |
" # print the incoming message, but only if logging is active\n", | |
" def print_log(self, msg, indent=0):\n", | |
" if self.logging:\n", | |
" print(f'{\" \" * indent}{msg}')\n", | |
"\n", | |
" # print the board and validity\n", | |
" def print_results(self):\n", | |
" txt_frag = 'VALID' if self.is_valid else 'INVALID'\n", | |
" print(f'Board is {txt_frag}\\n')\n", | |
" for r in self.board:\n", | |
" print(r)\n", | |
"\n", | |
" # creates and returns a board object that is self.WIDTH x self.HEIGHT\n", | |
" def get_board(self):\n", | |
" return [[' ' for x in range(self.WIDTH)] for y in range(self.HEIGHT)] \n", | |
"\n", | |
" # adds the incoming word to the board at the given position. \n", | |
" # if axis == x, the word is added horizontally\n", | |
" # if axis == y, the word is added vertically\n", | |
" def enter_word_at(self, board, word, pos, axis):\n", | |
" if axis == 'x':\n", | |
" for i in range(3):\n", | |
" board[pos][i] = word[i]\n", | |
" if axis == 'y':\n", | |
" for i in range(3):\n", | |
" board[i][pos] = word[i]\n", | |
"\n", | |
" # evaluates the board at the given depth. word fragments are evaluated \n", | |
" # vertically, as all words are added horizontally (with one initial exception)\n", | |
" # from the provided wordlist and are therefore already assumed to be valid\n", | |
" def validate_board(self, board, depth):\n", | |
" is_valid = True\n", | |
" frag = ''\n", | |
" for i in range(3):\n", | |
" frag = ''\n", | |
" for y in range(depth):\n", | |
" frag += board[y][i] \n", | |
" \n", | |
" filtered_words = [w for w in self.words if w[0] == frag[0]]\n", | |
" for idx, f in enumerate(frag):\n", | |
" filtered_words = [w for w in filtered_words if w[idx] == f[0]]\n", | |
" \n", | |
" if len(filtered_words) == 0: \n", | |
" self.print_log('...VALIDATION FAILED!!', depth + 2)\n", | |
" return False\n", | |
"\n", | |
" return is_valid\n", | |
"\n", | |
" # operates recursively, trying words that were filtered in previous operations\n", | |
" # (search space pruning) and checking the validity of each move.\n", | |
" # if a given move is invalid, it is not reset, but chars will be overwritten\n", | |
" # by subsequent operations.\n", | |
" def explore(self, board, root, words, filtered_words, pos):\n", | |
" self.print_log(f'possible choices {filtered_words}', (pos + 1) * 2) \n", | |
" tmp_words = words[:]\n", | |
" is_valid = False\n", | |
" filtered_inner = []\n", | |
" \n", | |
" for f in filtered_words:\n", | |
" # bail if the current filtered word is not in the wordlist, that means\n", | |
" # it's already in use \n", | |
" if f not in tmp_words: continue \n", | |
" tmp_words.remove(f)\n", | |
" self.print_log(f'Trying {f} horizontally at position 0,{pos}', (pos + 1) * 2) \n", | |
" self.enter_word_at(board, f, pos, 'x')\n", | |
"\n", | |
" # check if the board appears valid \n", | |
" # (words horizontally and vertically are in the words list)\n", | |
" if not self.validate_board(board, pos + 1): \n", | |
" continue \n", | |
" else: \n", | |
" is_valid = True \n", | |
" \n", | |
" # recurse\n", | |
" if pos < WIDTH - 1:\n", | |
" filtered_inner = [w for w in tmp_words if w[0] == root[pos + 1]]\n", | |
" self.explore(board, root, tmp_words, filtered_inner, pos+1) \n", | |
"\n", | |
" return (is_valid, board, tmp_words, filtered_inner)\n", | |
" \n", | |
" # try_word does the following\n", | |
" # 1. places the given word horizontally at 0,0\n", | |
" # 2. looks for words valid words (words with the same start char) to place \n", | |
" # vertically at 0,0 \n", | |
" # 3. uses self.explore to recursively fill and test the remaining values\n", | |
" # 4. returns the validity and board resulting from the above operations\n", | |
" def try_word(self, word):\n", | |
" self.print_log(f'Trying {word} horizontally at position 0,0')\n", | |
"\n", | |
" board = self.get_board()\n", | |
" is_valid = False\n", | |
"\n", | |
" tmp_words = self.words[:]\n", | |
" tmp_words.remove(word)\n", | |
"\n", | |
" self.enter_word_at(board, word, 0, 'x')\n", | |
"\n", | |
" filtered_words = [w for w in tmp_words if w[0] == word[0]]\n", | |
" if len(filtered_words) == 0: return self.get_board()\n", | |
"\n", | |
" # add y at 0\n", | |
" for fw in filtered_words:\n", | |
" tmp_words = self.words[:]\n", | |
" tmp_words.remove(word)\n", | |
" # bail if the current filtered word is not in the wordlist, that means\n", | |
" # it's already in use\n", | |
" if fw not in tmp_words: continue\n", | |
" tmp_words.remove(fw)\n", | |
" self.print_log(f'Trying {fw} vertically at position 0,0', 2)\n", | |
" self.enter_word_at(board, fw, 0, 'y')\n", | |
" r2_filtered_words = [w for w in tmp_words if w[0] == fw[1]]\n", | |
" if len(r2_filtered_words) == 0: \n", | |
" self.print_log('...FAILED!! NO VALID FILTERED WORDS', 2) \n", | |
" continue\n", | |
"\n", | |
" is_valid, board, tmp_words, filtered_words = self.explore(board, fw, tmp_words, r2_filtered_words, 1)\n", | |
"\n", | |
" return (is_valid, board)\n", | |
" \n", | |
" # iterates through the provided wordlist, placing each word horizontally at\n", | |
" # 0,0 to determine if the crossword may be solved.\n", | |
" # returns self for chaining purposes\n", | |
" def solve(self):\n", | |
" for word in self.words:\n", | |
" is_valid, board = self.try_word(word)\n", | |
" if is_valid:\n", | |
" self.is_valid = is_valid\n", | |
" self.board = board\n", | |
" break\n", | |
"\n", | |
" print('\\nCOMPLETE!!!\\n')\n", | |
"\n", | |
" return self\n", | |
" " | |
] | |
}, | |
{ | |
"cell_type": "markdown", | |
"metadata": {}, | |
"source": [ | |
"Now, we're ready to define our dimensions and wordlist. After which, we create an instance of Crossword_Solver that solves the thing and prints the results. \n", | |
"\n", | |
"*Note: the final arg to Crossword_Solver can be omitted if one wants to run this sans logging.*" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 90, | |
"metadata": {}, | |
"outputs": [ | |
{ | |
"name": "stdout", | |
"output_type": "stream", | |
"text": [ | |
"Logging is set to True\n", | |
"\n", | |
"Trying add horizontally at position 0,0\n", | |
" Trying age vertically at position 0,0\n", | |
" ...FAILED!! NO VALID FILTERED WORDS\n", | |
" Trying aid vertically at position 0,0\n", | |
" ...FAILED!! NO VALID FILTERED WORDS\n", | |
" Trying aim vertically at position 0,0\n", | |
" ...FAILED!! NO VALID FILTERED WORDS\n", | |
" Trying air vertically at position 0,0\n", | |
" ...FAILED!! NO VALID FILTERED WORDS\n", | |
" Trying are vertically at position 0,0\n", | |
" ...FAILED!! NO VALID FILTERED WORDS\n", | |
" Trying arm vertically at position 0,0\n", | |
" ...FAILED!! NO VALID FILTERED WORDS\n", | |
" Trying art vertically at position 0,0\n", | |
" ...FAILED!! NO VALID FILTERED WORDS\n", | |
"Trying age horizontally at position 0,0\n", | |
" Trying add vertically at position 0,0\n", | |
" possible choices ['dim']\n", | |
" Trying dim horizontally at position 0,1\n", | |
" ...VALIDATION FAILED!!\n", | |
" Trying aid vertically at position 0,0\n", | |
" ...FAILED!! NO VALID FILTERED WORDS\n", | |
" Trying aim vertically at position 0,0\n", | |
" ...FAILED!! NO VALID FILTERED WORDS\n", | |
" Trying air vertically at position 0,0\n", | |
" ...FAILED!! NO VALID FILTERED WORDS\n", | |
" Trying are vertically at position 0,0\n", | |
" ...FAILED!! NO VALID FILTERED WORDS\n", | |
" Trying arm vertically at position 0,0\n", | |
" ...FAILED!! NO VALID FILTERED WORDS\n", | |
" Trying art vertically at position 0,0\n", | |
" ...FAILED!! NO VALID FILTERED WORDS\n", | |
"Trying aid horizontally at position 0,0\n", | |
" Trying add vertically at position 0,0\n", | |
" possible choices ['dim']\n", | |
" Trying dim horizontally at position 0,1\n", | |
" ...VALIDATION FAILED!!\n", | |
" Trying age vertically at position 0,0\n", | |
" ...FAILED!! NO VALID FILTERED WORDS\n", | |
" Trying aim vertically at position 0,0\n", | |
" ...FAILED!! NO VALID FILTERED WORDS\n", | |
" Trying air vertically at position 0,0\n", | |
" ...FAILED!! NO VALID FILTERED WORDS\n", | |
" Trying are vertically at position 0,0\n", | |
" ...FAILED!! NO VALID FILTERED WORDS\n", | |
" Trying arm vertically at position 0,0\n", | |
" ...FAILED!! NO VALID FILTERED WORDS\n", | |
" Trying art vertically at position 0,0\n", | |
" ...FAILED!! NO VALID FILTERED WORDS\n", | |
"Trying aim horizontally at position 0,0\n", | |
" Trying add vertically at position 0,0\n", | |
" possible choices ['dim']\n", | |
" Trying dim horizontally at position 0,1\n", | |
" ...VALIDATION FAILED!!\n", | |
" Trying age vertically at position 0,0\n", | |
" ...FAILED!! NO VALID FILTERED WORDS\n", | |
" Trying aid vertically at position 0,0\n", | |
" ...FAILED!! NO VALID FILTERED WORDS\n", | |
" Trying air vertically at position 0,0\n", | |
" ...FAILED!! NO VALID FILTERED WORDS\n", | |
" Trying are vertically at position 0,0\n", | |
" ...FAILED!! NO VALID FILTERED WORDS\n", | |
" Trying arm vertically at position 0,0\n", | |
" ...FAILED!! NO VALID FILTERED WORDS\n", | |
" Trying art vertically at position 0,0\n", | |
" ...FAILED!! NO VALID FILTERED WORDS\n", | |
"Trying air horizontally at position 0,0\n", | |
" Trying add vertically at position 0,0\n", | |
" possible choices ['dim']\n", | |
" Trying dim horizontally at position 0,1\n", | |
" ...VALIDATION FAILED!!\n", | |
" Trying age vertically at position 0,0\n", | |
" ...FAILED!! NO VALID FILTERED WORDS\n", | |
" Trying aid vertically at position 0,0\n", | |
" ...FAILED!! NO VALID FILTERED WORDS\n", | |
" Trying aim vertically at position 0,0\n", | |
" ...FAILED!! NO VALID FILTERED WORDS\n", | |
" Trying are vertically at position 0,0\n", | |
" ...FAILED!! NO VALID FILTERED WORDS\n", | |
" Trying arm vertically at position 0,0\n", | |
" ...FAILED!! NO VALID FILTERED WORDS\n", | |
" Trying art vertically at position 0,0\n", | |
" ...FAILED!! NO VALID FILTERED WORDS\n", | |
"Trying are horizontally at position 0,0\n", | |
" Trying add vertically at position 0,0\n", | |
" possible choices ['dim']\n", | |
" Trying dim horizontally at position 0,1\n", | |
" ...VALIDATION FAILED!!\n", | |
" Trying age vertically at position 0,0\n", | |
" ...FAILED!! NO VALID FILTERED WORDS\n", | |
" Trying aid vertically at position 0,0\n", | |
" ...FAILED!! NO VALID FILTERED WORDS\n", | |
" Trying aim vertically at position 0,0\n", | |
" ...FAILED!! NO VALID FILTERED WORDS\n", | |
" Trying air vertically at position 0,0\n", | |
" ...FAILED!! NO VALID FILTERED WORDS\n", | |
" Trying arm vertically at position 0,0\n", | |
" ...FAILED!! NO VALID FILTERED WORDS\n", | |
" Trying art vertically at position 0,0\n", | |
" ...FAILED!! NO VALID FILTERED WORDS\n", | |
"Trying arm horizontally at position 0,0\n", | |
" Trying add vertically at position 0,0\n", | |
" possible choices ['dim']\n", | |
" Trying dim horizontally at position 0,1\n", | |
" ...VALIDATION FAILED!!\n", | |
" Trying age vertically at position 0,0\n", | |
" ...FAILED!! NO VALID FILTERED WORDS\n", | |
" Trying aid vertically at position 0,0\n", | |
" ...FAILED!! NO VALID FILTERED WORDS\n", | |
" Trying aim vertically at position 0,0\n", | |
" ...FAILED!! NO VALID FILTERED WORDS\n", | |
" Trying air vertically at position 0,0\n", | |
" ...FAILED!! NO VALID FILTERED WORDS\n", | |
" Trying are vertically at position 0,0\n", | |
" ...FAILED!! NO VALID FILTERED WORDS\n", | |
" Trying art vertically at position 0,0\n", | |
" ...FAILED!! NO VALID FILTERED WORDS\n", | |
"Trying art horizontally at position 0,0\n", | |
" Trying add vertically at position 0,0\n", | |
" possible choices ['dim']\n", | |
" Trying dim horizontally at position 0,1\n", | |
" ...VALIDATION FAILED!!\n", | |
" Trying age vertically at position 0,0\n", | |
" ...FAILED!! NO VALID FILTERED WORDS\n", | |
" Trying aid vertically at position 0,0\n", | |
" ...FAILED!! NO VALID FILTERED WORDS\n", | |
" Trying aim vertically at position 0,0\n", | |
" ...FAILED!! NO VALID FILTERED WORDS\n", | |
" Trying air vertically at position 0,0\n", | |
" ...FAILED!! NO VALID FILTERED WORDS\n", | |
" Trying are vertically at position 0,0\n", | |
" ...FAILED!! NO VALID FILTERED WORDS\n", | |
" Trying arm vertically at position 0,0\n", | |
" ...FAILED!! NO VALID FILTERED WORDS\n", | |
"Trying bad horizontally at position 0,0\n", | |
" Trying bat vertically at position 0,0\n", | |
" possible choices ['add', 'age', 'aid', 'aim', 'air', 'are', 'arm', 'art']\n", | |
" Trying add horizontally at position 0,1\n", | |
" ...VALIDATION FAILED!!\n", | |
" Trying age horizontally at position 0,1\n", | |
" ...VALIDATION FAILED!!\n", | |
" Trying aid horizontally at position 0,1\n", | |
" ...VALIDATION FAILED!!\n", | |
" Trying aim horizontally at position 0,1\n", | |
" ...VALIDATION FAILED!!\n", | |
" Trying air horizontally at position 0,1\n", | |
" ...VALIDATION FAILED!!\n", | |
" Trying are horizontally at position 0,1\n", | |
" ...VALIDATION FAILED!!\n", | |
" Trying arm horizontally at position 0,1\n", | |
" ...VALIDATION FAILED!!\n", | |
" Trying art horizontally at position 0,1\n", | |
" ...VALIDATION FAILED!!\n", | |
" Trying bee vertically at position 0,0\n", | |
" possible choices ['ear', 'eel', 'eft']\n", | |
" Trying ear horizontally at position 0,1\n", | |
" ...VALIDATION FAILED!!\n", | |
" Trying eel horizontally at position 0,1\n", | |
" ...VALIDATION FAILED!!\n", | |
" Trying eft horizontally at position 0,1\n", | |
" ...VALIDATION FAILED!!\n", | |
" Trying boa vertically at position 0,0\n", | |
" possible choices ['oaf']\n", | |
" Trying oaf horizontally at position 0,1\n", | |
" ...VALIDATION FAILED!!\n", | |
"Trying bat horizontally at position 0,0\n", | |
" Trying bad vertically at position 0,0\n", | |
" possible choices ['add', 'age', 'aid', 'aim', 'air', 'are', 'arm', 'art']\n", | |
" Trying add horizontally at position 0,1\n", | |
" ...VALIDATION FAILED!!\n", | |
" Trying age horizontally at position 0,1\n", | |
" ...VALIDATION FAILED!!\n", | |
" Trying aid horizontally at position 0,1\n", | |
" ...VALIDATION FAILED!!\n", | |
" Trying aim horizontally at position 0,1\n", | |
" ...VALIDATION FAILED!!\n", | |
" Trying air horizontally at position 0,1\n", | |
" ...VALIDATION FAILED!!\n", | |
" Trying are horizontally at position 0,1\n", | |
" ...VALIDATION FAILED!!\n", | |
" Trying arm horizontally at position 0,1\n", | |
" ...VALIDATION FAILED!!\n", | |
" Trying art horizontally at position 0,1\n", | |
" ...VALIDATION FAILED!!\n", | |
" Trying bee vertically at position 0,0\n", | |
" possible choices ['ear', 'eel', 'eft']\n", | |
" Trying ear horizontally at position 0,1\n", | |
" ...VALIDATION FAILED!!\n", | |
" Trying eel horizontally at position 0,1\n", | |
" ...VALIDATION FAILED!!\n", | |
" Trying eft horizontally at position 0,1\n", | |
" ...VALIDATION FAILED!!\n", | |
" Trying boa vertically at position 0,0\n", | |
" possible choices ['oaf']\n", | |
" Trying oaf horizontally at position 0,1\n", | |
" ...VALIDATION FAILED!!\n", | |
"Trying bee horizontally at position 0,0\n", | |
" Trying bad vertically at position 0,0\n", | |
" possible choices ['add', 'age', 'aid', 'aim', 'air', 'are', 'arm', 'art']\n", | |
" Trying add horizontally at position 0,1\n", | |
" ...VALIDATION FAILED!!\n", | |
" Trying age horizontally at position 0,1\n", | |
" ...VALIDATION FAILED!!\n", | |
" Trying aid horizontally at position 0,1\n", | |
" ...VALIDATION FAILED!!\n", | |
" Trying aim horizontally at position 0,1\n", | |
" ...VALIDATION FAILED!!\n", | |
" Trying air horizontally at position 0,1\n", | |
" ...VALIDATION FAILED!!\n", | |
" Trying are horizontally at position 0,1\n", | |
" ...VALIDATION FAILED!!\n", | |
" Trying arm horizontally at position 0,1\n", | |
" ...VALIDATION FAILED!!\n", | |
" Trying art horizontally at position 0,1\n", | |
" ...VALIDATION FAILED!!\n", | |
" Trying bat vertically at position 0,0\n", | |
" possible choices ['add', 'age', 'aid', 'aim', 'air', 'are', 'arm', 'art']\n", | |
" Trying add horizontally at position 0,1\n", | |
" ...VALIDATION FAILED!!\n", | |
" Trying age horizontally at position 0,1\n", | |
" ...VALIDATION FAILED!!\n", | |
" Trying aid horizontally at position 0,1\n", | |
" ...VALIDATION FAILED!!\n", | |
" Trying aim horizontally at position 0,1\n", | |
" ...VALIDATION FAILED!!\n", | |
" Trying air horizontally at position 0,1\n", | |
" ...VALIDATION FAILED!!\n", | |
" Trying are horizontally at position 0,1\n", | |
" ...VALIDATION FAILED!!\n", | |
" Trying arm horizontally at position 0,1\n", | |
" ...VALIDATION FAILED!!\n", | |
" Trying art horizontally at position 0,1\n", | |
" ...VALIDATION FAILED!!\n", | |
" Trying boa vertically at position 0,0\n", | |
" possible choices ['oaf']\n", | |
" Trying oaf horizontally at position 0,1\n", | |
" possible choices ['add', 'age', 'aid', 'aim', 'air', 'are', 'arm', 'art']\n", | |
" Trying add horizontally at position 0,2\n", | |
" ...VALIDATION FAILED!!\n", | |
" Trying age horizontally at position 0,2\n", | |
" ...VALIDATION FAILED!!\n", | |
" Trying aid horizontally at position 0,2\n", | |
" ...VALIDATION FAILED!!\n", | |
" Trying aim horizontally at position 0,2\n", | |
" ...VALIDATION FAILED!!\n", | |
" Trying air horizontally at position 0,2\n", | |
" ...VALIDATION FAILED!!\n", | |
" Trying are horizontally at position 0,2\n", | |
" ...VALIDATION FAILED!!\n", | |
" Trying arm horizontally at position 0,2\n", | |
" ...VALIDATION FAILED!!\n", | |
" Trying art horizontally at position 0,2\n", | |
"\n", | |
"COMPLETE!!!\n", | |
"\n", | |
"Board is VALID\n", | |
"\n", | |
"['b', 'e', 'e']\n", | |
"['o', 'a', 'f']\n", | |
"['a', 'r', 't']\n" | |
] | |
} | |
], | |
"source": [ | |
"WIDTH = 3\n", | |
"HEIGHT = 3\n", | |
"\n", | |
"words = [\n", | |
" 'add', 'age', 'aid', 'aim', 'air', 'are', 'arm', 'art', 'bad', 'bat', 'bee', \n", | |
" 'boa', 'dim', 'ear', 'eel', 'eft', 'lee', 'oaf'\n", | |
"]\n", | |
"\n", | |
"cws = Crossword_Solver(words, WIDTH, HEIGHT, True)\n", | |
"cws.solve().print_results()" | |
] | |
}, | |
{ | |
"cell_type": "markdown", | |
"metadata": {}, | |
"source": [ | |
"While the above is a brute-force approach, it does the job. Ideally, we'd modify this to gracefully handle more complex board types (like a real crossword layout, for example), but this increases the scope significantly and is not the goal of this exercise. " | |
] | |
} | |
], | |
"metadata": { | |
"kernelspec": { | |
"display_name": "Python 3.9.12 64-bit", | |
"language": "python", | |
"name": "python3" | |
}, | |
"language_info": { | |
"codemirror_mode": { | |
"name": "ipython", | |
"version": 3 | |
}, | |
"file_extension": ".py", | |
"mimetype": "text/x-python", | |
"name": "python", | |
"nbconvert_exporter": "python", | |
"pygments_lexer": "ipython3", | |
"version": "3.9.12" | |
}, | |
"orig_nbformat": 4, | |
"vscode": { | |
"interpreter": { | |
"hash": "b0fa6594d8f4cbf19f97940f81e996739fb7646882a419484c72d19e05852a7e" | |
} | |
} | |
}, | |
"nbformat": 4, | |
"nbformat_minor": 2 | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment