Skip to content

Instantly share code, notes, and snippets.

@smithcommajoseph
Created August 4, 2022 20:40
Show Gist options
  • Save smithcommajoseph/532281e226191d4620cd8b3c2786d788 to your computer and use it in GitHub Desktop.
Save smithcommajoseph/532281e226191d4620cd8b3c2786d788 to your computer and use it in GitHub Desktop.
Display the source blob
Display the rendered blob
Raw
{
"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