{ "cells": [ { "cell_type": "markdown", "source": [ "# trying to create a better grid builging algorithm" ], "metadata": {} }, { "cell_type": "code", "execution_count": 1, "source": [ "# load stuff\n", "import json\n", "import random\n", "import numpy as np\n", "from string import digits, ascii_lowercase\n", "import pathlib\n", "import logging\n", "import copy" ], "outputs": [], "metadata": {} }, { "cell_type": "code", "execution_count": 2, "source": [ "def get_difficulty_threshold(lang: str, difficulty: int):\n", " return get_difficulty_threshold.thresholds[lang][difficulty]\n", "\n", "\n", "get_difficulty_threshold.thresholds = {\n", " 'de': {\n", " 0: 12,\n", " 1: 6,\n", " 2: 0\n", " },\n", " 'en': {\n", " 0: 200,\n", " 1: 100,\n", " 2: 10\n", " }\n", "}\n", "\n", "\n", "def get_database(lang: str = \"en\") -> dict:\n", " if lang not in get_database._dbs:\n", " try:\n", " file = __file__\n", " except:\n", " file = \"./.tmp\"\n", " current_folder = pathlib.Path(file).parents[0]\n", " db_file = str(current_folder / f\"{lang}.json\")\n", "\n", " logging.info(\"loading database: %s\", lang)\n", "\n", " with open(db_file, \"r\") as f:\n", " db = json.load(f)\n", " get_database._dbs[lang] = db\n", "\n", " logging.info(\"database loaded\")\n", "\n", " return get_database._dbs[lang]\n", "\n", "\n", "get_database._dbs = {}\n", "\n", "def build_inverted_index(db):\n", "\n", " inverted_db = {}\n", "\n", " inverted_db['#'] = {}\n", " number_db = inverted_db['#']\n", "\n", " for letter in ascii_lowercase:\n", " inverted_db[letter] = {}\n", "\n", " for key, item in db.items():\n", " try:\n", " word = item['word']\n", " norm_word = normalize_word(word)\n", "\n", " n = len(norm_word)\n", "\n", " if norm_word.isalnum():\n", "\n", " for i, letter in enumerate(norm_word):\n", " letter_db = inverted_db[letter]\n", " if i not in letter_db:\n", " letter_db[i] = {}\n", " letter_db_i = letter_db[i]\n", " if n not in letter_db_i:\n", " letter_db_i[n] = []\n", " if n not in number_db:\n", " number_db[n] = []\n", " \n", " letter_db_i[n].append(key)\n", " number_db[n].append(key)\n", " except:\n", " pass\n", " #print(\"error processing \" + word)\n", " \n", " return inverted_db\n", "\n", "def get_inverted_database(lang: str) -> dict:\n", " if lang not in get_inverted_database._dbs:\n", " get_inverted_database._dbs[lang] = build_inverted_index(get_database(lang))\n", " return get_inverted_database._dbs[lang]\n", "\n", "get_inverted_database._dbs = {}\n", " \n", "\n", "remove_digits = str.maketrans('', '', digits)\n", "\n", "def normalize_word(word: str):\n", " word = word.translate(remove_digits)\n", " return word.lower()\n", "\n", "def find_suitable_words(constraints: list, db: dict, inverted_db: dict):\n", " sets = []\n", "\n", " n = len(constraints)\n", " for i,letter in enumerate(constraints):\n", " if letter == ' ':\n", " continue\n", " \n", " letter_db = inverted_db[letter]\n", " if i in letter_db:\n", " i_list = letter_db[i]\n", " \n", " if not n in i_list:\n", " return set()\n", " \n", " sets.append(set(i_list[n]))\n", " \n", " else:\n", " return set()\n", " \n", " # at least one constraint must be set\n", " if len(sets) == 0:\n", " \n", " # set first letter random and try again\n", " if n in inverted_db['#']:\n", " return inverted_db['#'][n]\n", " return set()\n", " \n", " return set.intersection(*sets)\n", " \n", "\n" ], "outputs": [], "metadata": {} }, { "cell_type": "code", "execution_count": 3, "source": [ "find_suitable_words(list(\" \"), get_database(\"de\"), get_inverted_database(\"de\"))" ], "outputs": [ { "output_type": "execute_result", "data": { "text/plain": [ "['du',\n", " 'du',\n", " 'er',\n", " 'er',\n", " 'hi',\n", " 'hi',\n", " 'bp',\n", " 'bp',\n", " 'ol',\n", " 'ol',\n", " 'ei',\n", " 'ei',\n", " 'iq',\n", " 'iq',\n", " 'we',\n", " 'we',\n", " 'cd',\n", " 'cd',\n", " 'am',\n", " 'am',\n", " 'ha',\n", " 'ha',\n", " 'ei0',\n", " 'ei0',\n", " 'hi0',\n", " 'hi0',\n", " 'hi1',\n", " 'hi1',\n", " 'es',\n", " 'es',\n", " 'ai',\n", " 'ai',\n", " 'aa',\n", " 'aa',\n", " 'ag',\n", " 'ag',\n", " 'ag0',\n", " 'ag0',\n", " 'db',\n", " 'db',\n", " 'fc',\n", " 'fc',\n", " 'ab',\n", " 'ab',\n", " 'ab0',\n", " 'ab0',\n", " 'hp',\n", " 'hp',\n", " 'ms',\n", " 'ms',\n", " 'pa',\n", " 'pa',\n", " 'eh',\n", " 'eh',\n", " 'eh1',\n", " 'eh1',\n", " 'fs',\n", " 'fs',\n", " 'it',\n", " 'it',\n", " 'ki',\n", " 'ki',\n", " 'pc',\n", " 'pc',\n", " 'pc0',\n", " 'pc0',\n", " 'um',\n", " 'um',\n", " 'um0',\n", " 'um0',\n", " 'hr',\n", " 'hr',\n", " 'in',\n", " 'in',\n", " 'im',\n", " 'im',\n", " 'ir',\n", " 'ir',\n", " 'hf',\n", " 'hf',\n", " 'cu',\n", " 'cu',\n", " 'ja',\n", " 'ja',\n", " 'ja0',\n", " 'ja0',\n", " 'ja1',\n", " 'ja1',\n", " 'aa0',\n", " 'aa0',\n", " 'aa2',\n", " 'aa2',\n", " 'dm',\n", " 'dm',\n", " 'zu',\n", " 'zu',\n", " 'zu1',\n", " 'zu1',\n", " 'zu2',\n", " 'zu2',\n", " 'zu3',\n", " 'zu3',\n", " 'zu4',\n", " 'zu4',\n", " 'an',\n", " 'an',\n", " 'an0',\n", " 'an0',\n", " 'so',\n", " 'so',\n", " 'so0',\n", " 'so0',\n", " 'so1',\n", " 'so1',\n", " 'so3',\n", " 'so3',\n", " 'af',\n", " 'af',\n", " 'lg',\n", " 'lg',\n", " 'nf',\n", " 'nf',\n", " 'nl',\n", " 'nl',\n", " 'da1',\n", " 'da1',\n", " 'wo',\n", " 'wo',\n", " 'wo0',\n", " 'wo0',\n", " 'wo1',\n", " 'wo1',\n", " 'ab1',\n", " 'ab1',\n", " 'ai0',\n", " 'ai0',\n", " 'dj',\n", " 'dj',\n", " 'on0',\n", " 'on0',\n", " 'ob0',\n", " 'ob0',\n", " 'am1',\n", " 'am1',\n", " 'ta',\n", " 'ta',\n", " 'to',\n", " 'to',\n", " 'kw',\n", " 'kw',\n", " 'dv',\n", " 'dv',\n", " 'dv0',\n", " 'dv0',\n", " 'mr',\n", " 'mr',\n", " 'zv',\n", " 'zv',\n", " 'kg',\n", " 'kg',\n", " 'ap',\n", " 'ap',\n", " 'ao',\n", " 'ao',\n", " 'av',\n", " 'av',\n", " 'ba',\n", " 'ba',\n", " 'bg',\n", " 'bg',\n", " 'bk',\n", " 'bk',\n", " 'br',\n", " 'br',\n", " 'bt',\n", " 'bt',\n", " 'eg0',\n", " 'eg0',\n", " 'eg1',\n", " 'eg1',\n", " 'fg0',\n", " 'fg0',\n", " 'fm0',\n", " 'fm0',\n", " 'pd',\n", " 'pd',\n", " 'fw',\n", " 'fw',\n", " 'ra',\n", " 'ra',\n", " 'qm0',\n", " 'qm0',\n", " 'rg',\n", " 'rg',\n", " 'wm',\n", " 'wm',\n", " 'sg',\n", " 'sg',\n", " 'va',\n", " 'va',\n", " 'vg',\n", " 'vg',\n", " 'vz',\n", " 'vz',\n", " 'wd',\n", " 'wd',\n", " 'wp',\n", " 'wp',\n", " 'zh',\n", " 'zh',\n", " 'ct',\n", " 'ct',\n", " 'dg',\n", " 'dg',\n", " 'dh',\n", " 'dh',\n", " 'dt',\n", " 'dt',\n", " 'ep',\n", " 'ep',\n", " 'hk',\n", " 'hk',\n", " 'km',\n", " 'km',\n", " 'kp',\n", " 'kp',\n", " 'mk',\n", " 'mk',\n", " 'mm',\n", " 'mm',\n", " 'og',\n", " 'og',\n", " 'ot',\n", " 'ot',\n", " 'rh',\n", " 'rh',\n", " 'as0',\n", " 'as0',\n", " 'as1',\n", " 'as1',\n", " 'be',\n", " 'be',\n", " 'es2',\n", " 'es2',\n", " 'fr',\n", " 'fr',\n", " 'mo',\n", " 'mo',\n", " 'os',\n", " 'os',\n", " 'os0',\n", " 'os0',\n", " 'po',\n", " 'po',\n", " 'po0',\n", " 'po0',\n", " 'ra0',\n", " 'ra0',\n", " 're0',\n", " 're0',\n", " 'tb',\n", " 'tb',\n", " 'np',\n", " 'np',\n", " 'ps',\n", " 'ps',\n", " 'sv',\n", " 'sv',\n", " 'xl',\n", " 'xl',\n", " 'bw',\n", " 'bw',\n", " 'bh',\n", " 'bh',\n", " 'ss',\n", " 'ss',\n", " 'sw',\n", " 'sw',\n", " 'ac',\n", " 'ac',\n", " 'ak',\n", " 'ak',\n", " 'aw',\n", " 'aw',\n", " 'az',\n", " 'az',\n", " 'bb',\n", " 'bb',\n", " 'bl',\n", " 'bl',\n", " 'bm',\n", " 'bm',\n", " 'bs',\n", " 'bs',\n", " 'bz',\n", " 'bz',\n", " 'cb',\n", " 'cb',\n", " 'ww',\n", " 'ww',\n", " 'di',\n", " 'di',\n", " 'do0',\n", " 'do0',\n", " 'rg0',\n", " 'rg0',\n", " 'ho0',\n", " 'ho0',\n", " 'tv',\n", " 'tv',\n", " 'oh',\n", " 'oh',\n", " 'nt',\n", " 'nt',\n", " 'wc',\n", " 'wc',\n", " 'mp',\n", " 'mp',\n", " 'na',\n", " 'na',\n", " 'pk',\n", " 'pk',\n", " 'op',\n", " 'op',\n", " 'sp',\n", " 'sp',\n", " 'ka',\n", " 'ka',\n", " 'kp0',\n", " 'kp0',\n", " 'rm',\n", " 'rm',\n", " 'lw',\n", " 'lw',\n", " 'mw',\n", " 'mw',\n", " 'pp',\n", " 'pp',\n", " 'sb',\n", " 'sb',\n", " 'nu1',\n", " 'nu1',\n", " 'gz',\n", " 'gz',\n", " 'ae0',\n", " 'ae0',\n", " 'at',\n", " 'at',\n", " 'be0',\n", " 'be0',\n", " 'pi',\n", " 'pi',\n", " 'vn',\n", " 'vn',\n", " 'ss0',\n", " 'ss0',\n", " 'ss1',\n", " 'ss1',\n", " 'kp1',\n", " 'kp1',\n", " 'sz',\n", " 'sz',\n", " 'hm',\n", " 'hm',\n", " 'ld',\n", " 'ld',\n", " 'wu',\n", " 'wu',\n", " 'kv',\n", " 'kv',\n", " 'vu',\n", " 'vu',\n", " 'za',\n", " 'za',\n", " 'wg',\n", " 'wg',\n", " 'tg',\n", " 'tg',\n", " 'ja2',\n", " 'ja2',\n", " 'mc',\n", " 'mc',\n", " 'ur',\n", " 'ur',\n", " 'id',\n", " 'id',\n", " 'my',\n", " 'my',\n", " 'kl',\n", " 'kl',\n", " 'sd',\n", " 'sd',\n", " 'md',\n", " 'md',\n", " 'im0',\n", " 'im0',\n", " 'dw',\n", " 'dw',\n", " 'ny',\n", " 'ny',\n", " 'nv',\n", " 'nv',\n", " 'dz0',\n", " 'dz0',\n", " 'et',\n", " 'et',\n", " 'nn',\n", " 'nn',\n", " 'ff',\n", " 'ff',\n", " 'ff0',\n", " 'ff0',\n", " 'vv',\n", " 'vv',\n", " 'gr',\n", " 'gr',\n", " 'ig',\n", " 'ig',\n", " 'vp',\n", " 'vp',\n", " 'do1',\n", " 'do1',\n", " 'da2',\n", " 'da2',\n", " 'dk',\n", " 'dk',\n", " 'dp',\n", " 'dp',\n", " 'de',\n", " 'de',\n", " 'ec',\n", " 'ec',\n", " 'er2',\n", " 'er2',\n", " 'ga',\n", " 'ga',\n", " 'gd',\n", " 'gd',\n", " 'ug',\n", " 'ug',\n", " 'mg0',\n", " 'mg0',\n", " 'ic',\n", " 'ic',\n", " 'rb',\n", " 'rb',\n", " 'gb',\n", " 'gb',\n", " 'zr',\n", " 'zr',\n", " 'ns',\n", " 'ns',\n", " 'kr',\n", " 'kr',\n", " 'hz',\n", " 'hz',\n", " 'nf0',\n", " 'nf0',\n", " 'sm0',\n", " 'sm0',\n", " 'en',\n", " 'en',\n", " 'qi',\n", " 'qi',\n", " 'gv',\n", " 'gv',\n", " 'uz0',\n", " 'uz0',\n", " 'kh',\n", " 'kh',\n", " 'gf',\n", " 'gf',\n", " 'tk',\n", " 'tk',\n", " 'hc',\n", " 'hc',\n", " 'zk',\n", " 'zk',\n", " 'lb',\n", " 'lb',\n", " 'wr',\n", " 'wr',\n", " 'st',\n", " 'st',\n", " 'te',\n", " 'te',\n", " 'hb',\n", " 'hb',\n", " 'vj',\n", " 'vj',\n", " 'us',\n", " 'us',\n", " 'on1',\n", " 'on1',\n", " 'on2',\n", " 'on2',\n", " 'vr',\n", " 'vr']" ] }, "metadata": {}, "execution_count": 3 } ], "metadata": {} }, { "cell_type": "code", "execution_count": 4, "source": [ "class NoDataException(Exception):\n", " pass\n", "\n", "\n", "class WordInfo(object):\n", " def __init__(self, word: str, y: int, x: int, is_vertical: bool, database: dict, opposite_prefix: str = \"opposite of\", synonym_prefix: str = \"other word for\"):\n", " self._dictionary_database = database\n", " self._y = y\n", " self._x = x\n", " self._word = word\n", " self._hint = None\n", " self._is_vertical = is_vertical\n", "\n", " self.opposite_prefix = opposite_prefix\n", " self.synonym_prefix = synonym_prefix\n", "\n", " self.choose_info()\n", "\n", " def get_attribute(self, attr: str):\n", " attr = self._dictionary_database[self._word][attr]\n", " if attr is None or len(attr) == 0:\n", " raise NoDataException\n", " return attr\n", "\n", " def get_best_antonym(self) -> str:\n", " antonyms = self.get_attribute(\"antonyms\")\n", " return random.choice(antonyms)\n", "\n", " def get_best_synonym(self) -> str:\n", " synonyms = self.get_attribute(\"synonyms\")\n", " return random.choice(synonyms)\n", "\n", " def get_best_sense(self) -> str:\n", " senses = self.get_attribute(\"senses\")\n", " return random.choice(senses)\n", "\n", " def choose_info(self, n: int = 1):\n", " assert n <= 4\n", " # first choose antonyms, then synonyms, then senses\n", "\n", " hints = []\n", "\n", " try:\n", " antonyms = self.get_attribute(\"antonyms\")\n", " antonyms = [f\"{self.opposite_prefix} {w}\" for w in antonyms]\n", " hints = hints + antonyms\n", " except NoDataException:\n", " pass\n", "\n", " try:\n", " synonyms = self.get_attribute(\"synonyms\")\n", " synonyms = [f\"{self.synonym_prefix} {w}\" for w in synonyms]\n", "\n", " hints = hints + synonyms\n", " except NoDataException:\n", " pass\n", "\n", " try:\n", " senses = self.get_attribute(\"senses\")\n", " hints = hints + senses\n", " except NoDataException:\n", " pass\n", "\n", " final_hints = []\n", " for i in range(n):\n", " choice = random.choice(hints)\n", " hints.remove(choice)\n", " final_hints.append(choice)\n", "\n", " if n == 1:\n", " self._hint = final_hints[0]\n", " return\n", "\n", " hint_symbols = ['a)', 'b)', 'c)', 'd)']\n", "\n", " self._hint = \"\"\n", " for i in range(n):\n", " self._hint += hint_symbols[i] + \" \" + final_hints[i] + \". \"\n", "\n", " def get_hint(self) -> str:\n", " return self._hint\n", "\n", " def get_hint_location(self):\n", " x = self._x if self._is_vertical else self._x - 1\n", " y = self._y - 1 if self._is_vertical else self._y\n", " return (y, x)\n", "\n", " def is_vertical(self):\n", " return self._is_vertical\n" ], "outputs": [], "metadata": {} }, { "cell_type": "code", "execution_count": 64, "source": [ "def create_base_grid(n:int, min_word_length: int = 4, max_word_length: int = 15, filter_length: int = 2):\n", " w = n\n", " h = n\n", " horizontal_grid = np.full(shape=(h,w), dtype=np.bool, fill_value=False)\n", " vertical_grid = np.full(shape=(h,w), dtype=np.bool, fill_value=False)\n", "\n", "\n", " for y in range(h):\n", " x = 0\n", " while x < w:\n", " rand_max = random.randint(min_word_length, max_word_length)\n", " rand_length = random.randint(min_word_length, rand_max)#\n", "\n", " x_next = min(x + rand_length, w)\n", " horizontal_grid[y,x:x_next] = True\n", " x = x_next + 1\n", " \n", " for x in range(w):\n", " y = 0\n", " while y < h:\n", " rand_max = random.randint(min_word_length, max_word_length)\n", " rand_length = random.randint(min_word_length, rand_max)\n", " y_next = min(y + rand_length, h)\n", " vertical_grid[y:y_next, x] = True\n", " y = y_next + 1\n", " \n", "\n", " \n", " for y in range(0,h,2):\n", " horizontal_grid[y,0] = False\n", " horizontal_grid[y,-1] = False\n", "\n", " \n", " \n", " for x in range(2,w,2):\n", " vertical_grid[0,x] = False\n", " vertical_grid[-1,x] = False\n", "\n", " for y in range(2,h,2):\n", " for x in range(2,w,2):\n", " if random.randint(0,3) == 0:\n", " horizontal_grid[y,x] = False\n", "\n", "\n", "\n", " combined = np.logical_and(horizontal_grid, vertical_grid)\n", "\n", " #combined = np.logical_and(horizontal_grid, horizontal_grid.transpose())\n", " \n", "\n", "\n", " # clean up areas that are to small\n", " old_combined = combined.copy()\n", " first_try = True\n", "\n", " while np.sum(old_combined.astype(int)) != np.sum(combined.astype(int)) or first_try:\n", "\n", " first_try = False\n", "\n", " count_x = np.full(shape=(h,w), dtype=np.int, fill_value=0)\n", " count_y = np.full(shape=(h,w), dtype=np.int, fill_value=0)\n", "\n", " for x in range(w):\n", " last_y = 0\n", " for y in range(h):\n", " if not combined[y,x] and last_y != y: \n", " count_y[last_y:y,x] = y - last_y\n", " last_y = y + 1\n", " \n", " if last_y < h:\n", " count_y[last_y:h,x] = h - last_y\n", " \n", " for y in range(h):\n", " last_x = 0\n", " for x in range(w):\n", " if not combined[y,x] and last_x != x: \n", " count_x[y,last_x:x] = x - last_x\n", " last_x = x + 1\n", " \n", " if last_x < w:\n", " count_x[y, last_x:w] = w - last_x\n", "\n", " count_mask = np.logical_and(count_x < filter_length, count_y < filter_length)\n", " old_combined = combined.copy()\n", " combined[count_mask] = False\n", "\n", "\n", " # clean up areas that are too small\n", "\n", " reachable = np.full(shape=(h,w), dtype=np.bool, fill_value=False)\n", "\n", " old_reachable = reachable.copy()\n", "\n", " reachable[1,0] = True\n", " reachable[0,1] = True\n", "\n", " \n", " i = 0\n", " while np.sum(old_reachable.astype(int)) != np.sum(reachable.astype(int)):\n", " old_reachable = reachable.copy()\n", " i += 1\n", " for y in range(h):\n", " for x in range(w):\n", " if x > 0 and (reachable[y,x-1] and combined[y,x-1]) or x < w-1 and (reachable[y,x+1] and combined[y,x+1]):\n", " reachable[y,x] = True\n", " continue\n", " if y > 0 and (reachable[y-1,x] and combined[y-1,x]) or y < h-1 and (reachable[y+1,x] and combined[y+1,x]):\n", " reachable[y,x] = True\n", " \n", " #print(\"flooded after \" + str(i) + \" iterations\")\n", " \n", " combined = np.logical_and(combined, reachable)\n", "\n", " return combined\n" ], "outputs": [], "metadata": {} }, { "cell_type": "code", "execution_count": 6, "source": [ "def create_base_grid(n: int):\n", " grid = np.full(shape=(n,n), dtype=np.bool, fill_value=True)\n", " for y in range(n):\n", " for x in range(n):\n", " if y % 2 == 1 and x % 2 == 1 and not random.randint(0,8) == 0:\n", " grid[y,x] = False\n", " \n", " else:\n", " if y % 2 != x % 2:\n", " if random.randint(0,3) == 0:\n", " grid[y,x] = False\n", " else:\n", " if random.randint(0,8) == 0:\n", " pass\n", " #grid[y,x] = False\n", "\n", " return grid\n", " #return np.logical_and(grid, grid.transpose())\n", "\n", " " ], "outputs": [], "metadata": {} }, { "cell_type": "code", "execution_count": 65, "source": [ "%%prun\n", "import matplotlib.pyplot as plt\n", "\n", "base_grid = create_base_grid(20)" ], "outputs": [ { "output_type": "stream", "name": "stdout", "text": [ " " ] }, { "output_type": "stream", "name": "stdout", "text": [ " 2317 function calls in 0.008 seconds\n", "\n", " Ordered by: internal time\n", "\n", " ncalls tottime percall cumtime percall filename:lineno(function)\n", " 1 0.006 0.006 0.008 0.008 :1(create_base_grid)\n", " 18 0.001 0.000 0.001 0.000 {method 'copy' of 'numpy.ndarray' objects}\n", " 311 0.000 0.000 0.001 0.000 random.py:291(randrange)\n", " 311 0.000 0.000 0.000 0.000 random.py:238(_randbelow_with_getrandbits)\n", " 36 0.000 0.000 0.000 0.000 {method 'astype' of 'numpy.ndarray' objects}\n", " 36 0.000 0.000 0.000 0.000 {method 'reduce' of 'numpy.ufunc' objects}\n", " 311 0.000 0.000 0.001 0.000 random.py:335(randint)\n", " 36 0.000 0.000 0.000 0.000 fromnumeric.py:70(_wrapreduction)\n", " 1 0.000 0.000 0.008 0.008 {built-in method builtins.exec}\n", " 36 0.000 0.000 0.000 0.000 fromnumeric.py:2105(sum)\n", " 43 0.000 0.000 0.001 0.000 {built-in method numpy.core._multiarray_umath.implement_array_function}\n", " 541 0.000 0.000 0.000 0.000 {method 'getrandbits' of '_random.Random' objects}\n", " 36 0.000 0.000 0.001 0.000 <__array_function__ internals>:2(sum)\n", " 115 0.000 0.000 0.000 0.000 {built-in method builtins.min}\n", " 311 0.000 0.000 0.000 0.000 {method 'bit_length' of 'int' objects}\n", " 36 0.000 0.000 0.000 0.000 fromnumeric.py:71()\n", " 7 0.000 0.000 0.000 0.000 numeric.py:268(full)\n", " 7 0.000 0.000 0.000 0.000 {built-in method numpy.empty}\n", " 7 0.000 0.000 0.000 0.000 <__array_function__ internals>:2(copyto)\n", " 1 0.000 0.000 0.008 0.008 :1()\n", " 36 0.000 0.000 0.000 0.000 {built-in method builtins.isinstance}\n", " 36 0.000 0.000 0.000 0.000 fromnumeric.py:2100(_sum_dispatcher)\n", " 36 0.000 0.000 0.000 0.000 {method 'items' of 'dict' objects}\n", " 7 0.000 0.000 0.000 0.000 multiarray.py:1043(copyto)\n", " 1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}" ] } ], "metadata": {} }, { "cell_type": "code", "execution_count": 66, "source": [ "\n", "\n", "\n", "plt.imshow(base_grid)\n", "plt.colorbar()\n", "plt.show()\n" ], "outputs": [ { "output_type": "display_data", "data": { "text/plain": [ "
" ], "image/svg+xml": "\n\n\n\n \n \n \n \n 2021-08-23T14:04:57.641931\n image/svg+xml\n \n \n Matplotlib v3.3.4, https://matplotlib.org/\n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n\n", "image/png": "iVBORw0KGgoAAAANSUhEUgAAATcAAAD8CAYAAAASeuPxAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuNCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8QVMy6AAAACXBIWXMAAAsTAAALEwEAmpwYAAAXqUlEQVR4nO3df7BcZX3H8feHC5iCoYgRDCFoxgl0GCekNiY61BakQMhQox1bEx1FinPFMZ06U2eM7Yw64z92HGt1QOJVM4EZDToVNK0pF8q0RUeQBCaEhB/hNiJcQomBlh9GfuTeb/8459Jls3v37Nk92WdPPq+ZM9k959nnPLsXvnOe85zv8ygiMDOrm2MG3QAzsyo4uJlZLTm4mVktObiZWS05uJlZLTm4mVktObiZ2cBJ2ihpv6RdbY5L0tclTUjaKeltnep0cDOzFGwCVs5y/FJgcb6NAtd2qtDBzcwGLiJuB56epchq4PrI3AmcLGn+bHUe288G9svxek3M4cRCZc9acrBwvXt2nlC4bBX1VtXWYeO/2eD/W3iB3/BSvKhe6rjkghPjqaenCpW9e+eLu4EXGnaNRcRYF6dbADzW8H4y3/dEuw8kGdzmcCIrdGGhsuPjOwrXe8npSwuXraLeqto6bPw3G/x/C7+I23qu46mnp7hr/MxCZUfmP/xCRCzr4XStAvGsuaNJBjczS18A00wfqdNNAgsb3p8B7JvtAz3dc5O0UtJD+QjG+hbHux7hMLPhEAQvx1ShrQ+2AB/JY8o7gGciom2XFHq4cpM0AlwDXEQWVbdJ2hIR9zcUaxzhWEE2wrGi7DnNLC39unKTtBk4H5gnaRL4PHAcQERsALYCq4AJ4CBwRac6e+mWLgcmImJv3rgbyEY0GoPbKyMcwJ2STpY0v1PENbP0BcFUn6ZMi4i1HY4H8Mlu6uylW9pu9KLbMgBIGpW0XdL2l3mxh2aZ2ZEyTRTaBqGXK7cioxeFRzjyYeExgJN0imfQNEtcAFMDClxF9BLcioxedD3CYWbDY1BXZUX00i3dBiyWtEjS8cAashGNRl2PcJjZcAjg5YhC2yCUvnKLiEOS1gHjwAiwMSJ2S7oqP15qhMPMhkMQSXdLleICMcvOnRN3jS/sXNCALp+M37ejsnbY8Fh+yWNsv/eFntKvliw5LrZsnVeo7KKF/313jxkKXXOGgpmVkmUopMvBzcxKElMtH4hIg4ObmZWSDSg4uJlZzWTPuTm4mVkNTfvKzczqxlduZlZLgZhKeKUCBzczK83dUjOrnUC8FCODbkZbDm5mVkr2EK+7pV3Zs/OE4gt4dJFONOg0parOn0JK1aB/224N039fVSwQsyee6ks9HlAws9qJEFPhKzczq6FpX7mZWd1kAwrphpB0W2ZmSfOAgpnV1pSfczOzunGGgpnV1nTCo6WlWyZpoaR/l/SApN2S/rpFmfMlPSNpR759rrfmmlkqssT5Ywptg9DLldsh4G8i4h5Jc4G7Jd0aEfc3lftpRFzWw3nMLEGBeLmO6Vf5En1P5K+fk/QA2WryzcHNzGoogvo/xCvpzcDvA79ocfidku4lW4z50xGxu00do8AowJkLjmV8+45+NO1Vqkr7qSKVZ9gM+rfttg1VtLeq36CKepdfcrAPtajeD/FKei3wQ+BTEfFs0+F7gDdFxPOSVgE/Aha3qicixoAxyJb267VdZlatIO0rt55aJuk4ssD23Yi4sfl4RDwbEc/nr7cCx0kqttChmSWvlgMKkgR8B3ggIv6hTZk3Ak9GREhaThZM+zMdgZkNVKDaTlZ5HvBh4D5JO/J9fwucCRARG4D3A5+QdAj4LbAmUlzi3sy6li3tl+6jsr2Mlv4MZr+bGBFXA1eXPYeZpcyLMptZDQVpZyg4uJlZaSlfuaUbds0saRFiOo4ptHUiaaWkhyRNSFrf4vjvSvpnSffm6Z5XdKrTV25mVko2oNB7+pWkEeAa4CJgEtgmaUtTKucngfsj4k8lvQF4SNJ3I+KldvU6uJlZSX1bQ2E5MBERewEk3QCs5tWpnAHMzR9Bey3wNFl+e1tJBrdhW/2qaNlhWyGqG3X9blWsPAX1WP0qG1AofM9tnqTtDe/H8qwkyHLSH2s4NgmsaPr81cAWsjTOucAHImJ6thMmGdzMbDh0kX1wICKWtTnWKkI2Pw97CbADeDfwFuBWST9tkfL5Cg8omFkpMxkKRbYOJoGFDe/PILtCa3QFcGNkJoBfAr83W6UObmZW2jTHFNo62AYslrRI0vHAGrIuaKNHgQsBJJ0GnA3sna1Sd0vNrJQIeHm69+ujiDgkaR0wDowAGyNit6Sr8uMbgC8CmyTdR9aN/UxEHJitXgc3Mysl65b2p/OXzxq0tWnfhobX+4CLu6nTwc3MSks5Q8HBzcxK6fJRkCPOwc3MSupft7QKDm5mVlqt11CowllLDjI+vqPv9Q76yfgUsimqUtfvNuhMgm7bUFQ/FojJRktruLSfmR3d6jzNuJkd5WrbLZX0CPAcMAUcas4dyzP4vwasAg4CH42Ie3o5p5ml4WgYLb1glieFLyVbp3QxWZb/tRye7W9mQ+poHi1dDVyfr3h1p6STJc2PiCcqPq+ZVSxCHEo4uPXasgBukXS3pNEWx1vN07SgVUWSRiVtl7T9109N9dgsMzsS+jQrSCV6vXI7LyL2STqVbH6lByPi9objReZpynZmE9eNASw7d47XNjVLXOr33Hq6csuTWYmI/cBNZNMFNyoyT5OZDamUr9xKBzdJJ0qaO/OaLGN/V1OxLcBHlHkH8Izvt5nVQx8nq6xEL93S04Cbsqc9OBb4XkTc3DQH01ayx0AmyB4F6bgcl5kNj1o+55avVHNui/2NczAF2ZJcXelmgZhuVJXKU8ViNnVNZ6pSHf+bqUpfFogJONSHySqr4gwFMyst5QEFBzczK8W5pWZWW+HgZmZ1VMsBBTM7ukX4npuZ1ZKY8mipmdWR77mZWe2knlvq4GZm5UR23y1VDm5mVppHSyuUQjpR0TZUlSaVwm+QQgrYoH+HFFbKOpLCAwpmVlfulppZLXm01MxqJ8LBzcxqyo+CmFkt+Z6bmdVOIKY9WmpmdZTwhVtPC8ScLWlHw/aspE81lTlf0jMNZT7Xc4vNLA35gEKRrRNJKyU9JGlC0vo2Zc7P48huSf/Zqc5e1lB4CFian3QEeJxseb9mP42Iy8qex8wS1odLtzx+XANcRLYc6DZJWyLi/oYyJwPfAFZGxKP5Wsmz6leH+ULgvyLiV32qz8yGQJ+u3JYDExGxNyJeAm4AVjeV+SBwY0Q8mp039neqtF/33NYAm9sce6eke8kWY/50ROxuVUjSKDAKMIcT+tSstAw6PQjqnQLWjSpWLKtDSlU3ApieLvwoyDxJ2xvej0XEWP56AfBYw7FJYEXT588CjpP0H8Bc4GsRcf1sJ+w5uEk6HngP8NkWh+8B3hQRz0taBfwIWNyqnvyLjgGcpFNSvk9pZpBFt+LPuR2IiGVtjrWqpDkGHAv8AVkv8XeAOyTdGRF72p2wH93SS4F7IuLJw1oX8WxEPJ+/3koWeef14ZxmloCIYlsHk8DChvdnkPX0msvcHBG/iYgDwO20WDe5UT+C21radEklvVH5kvSSlufn6301WDNLQxTcZrcNWCxpUd4TXANsaSrzY+Bdko6VdAJZt/WB2SrtqVuan+Qi4OMN+66CV1aefz/wCUmHgN8Ca/JV6M1s6BV7zKOTiDgkaR0wDowAGyNid2MsiYgHJN0M7ASmgW9HxK7Z6u0puEXEQeD1Tfs2NLy+Gri6l3OYWcL6dKmS37ba2rRvQ9P7LwNfLlqnMxTMrJyAKD5aesQ5uJlZDxzczKyOEr6D7uBmZuU5uJlZ7XT3EO8Rl2RwO2vJQcbHdwy0DVWk0qSQopRCG1IwTL9DFW1dfsnBvtST8oNdSQY3MxsSHi01szqSr9zMrHaKpVYNjIObmZUkDyiYWU35ys3Maml60A1oz8HNzMrxc25mVlceLTWzeko4uKW7XLSZWQ+SvHLbs/OESlYn6kYV9aawOtIwpR1VqYr/vlL4bYt+rz3Rn9n+3S01s/oJkk6/6tgtlbRR0n5Juxr2nSLpVkkP5/++rs1nV0p6SNKEpPX9bLiZJaA/C8RUosg9t03AyqZ964HbImIxcFv+/lUkjQDXkC39dw6wVtI5PbXWzJKiKLYNQsfgFhG3A0837V4NXJe/vg54b4uPLgcmImJvRLwE3JB/zszqYsiv3Fo5LSKeAMj/PbVFmQXAYw3vJ/N9ZlYXCQe3KgcUWt1pbPs1JY0CowBzOKGqNplZnwyyy1lE2Su3JyXNB8j/3d+izCSwsOH9GcC+dhVGxFhELIuIZcfxmpLNMrMjalrFtgEoG9y2AJfnry8nW+q+2TZgsaRFko4H1uSfM7OaGOoBBUmbgTuAsyVNSroS+BJwkaSHgYvy90g6XdJWgIg4BKwDxoEHgB9ExO5qvoaZDcQw33OLiLVtDl3Youw+YFXD+63A1tKtM7N0JX7PLckMhRRWv6pCN+k5VaVqVVVvValH3bR32FKlasHBzczqSAlPVulZQcyslnzlZmbluVtqZrXjAQUzqy0HNzOrJQc3M6sb4dFSM6ujgqlXRe7LFZ3YVtLbJU1Jen+nOh3czKy8PqRfFZ3YNi/392QpnR05uJlZef3JLS06se1fAT+k9SxEh0nynltVq19VlcozTCt1Dfo3qFIVbUghTSuF37adLh4FmSdpe8P7sYgYy1+3mth2xavOIy0A3ge8G3h7kRMmGdzMbEgUD24HImJZm2NFJrb9R+AzETElFZsfzsHNzMqJvo2WFpnYdhlwQx7Y5gGrJB2KiB+1q9TBzczK689zbq9MbAs8Tjax7QdfdZqIRTOvJW0C/mW2wAYObmbWg36kX0XEIUkzE9uOABsjYrekq/LjG8rU6+BmZuX1KUOh1cS27YJaRHy0SJ0ObmZWzgCnEC/Cwc3MShFpzwpSZIGYjZL2S9rVsO/Lkh6UtFPSTZJObvPZRyTdJ2lH0zMuZlYDQ736FbAJWNm071bgrRGxBNgDfHaWz18QEUtnecbFzIZVwqtfdQxuEXE78HTTvlvypfsA7iR7LsXMjjYJB7d+3HP7S+D7bY4FcIukAL7ZkG5xGEmjwCjAHE4ofPKq0om6UbTeYWprlfWm8DsMWsopVYXVeSZeSX8HHAK+26bIeRGxT9KpwK2SHsyvBA+TB74xgJN0SsI/mZm9IuH/U0vPCiLpcuAy4EMR0fIr5os0ExH7gZvIsv/NrCY0XWwbhFLBTdJK4DPAeyLiYJsyJ0qaO/MauBjY1aqsmQ2noR4tlbQZuAM4W9KkpCuBq4G5ZF3NHZI25GVPlzTzlPFpwM8k3QvcBfwkIm6u5FuY2ZFXdDAh1QGFiFjbYvd32pTdB6zKX+8Fzu2pdWaWtoTvuTlDwcxKST1DwcHNzErTdLrRzcHNzMpx4ryZ1ZW7pWZWTw5u1UkhPWeYVupKQQrtHaa/WcqpWr5yM7N6cnAzs9rp3+pXlXBwM7NS/JybmdVX6zkzkuDgZmal+crNzOrHD/GaWV15QMHMasnBzczqJ/CAQrfOWnKQ8fEdfa+3qifIU3jivgrOkhh8nVXVu/ySlhNod80DCmZWTw5uZlY3qT/EW2QNhY2S9kva1bDvC5Iez9dP2CFpVZvPrpT0kKQJSev72XAzG7AINF1sG4Qiq19tAla22P/ViFiab1ubD0oaAa4BLgXOAdZKOqeXxppZYhJeIKZjcMsXUX66RN3LgYmI2BsRLwE3AKtL1GNmiRrqpf1msU7Szrzb+roWxxcAjzW8n8z3tSRpVNJ2Sdt//dRUD80ysyMigOkotg1A2eB2LfAWYCnwBPCVFmXUYl/bbxkRYxGxLCKWveH1IyWbZWZH1DB3S1uJiCcjYioipoFvkXVBm00CCxvenwHsK3M+M0tTv7qlnQYfJX0o7ynulPRzSR3XRC4V3CTNb3j7PmBXi2LbgMWSFkk6HlgDbClzPjNLUz9GSwsOPv4S+OOIWAJ8ERjr1LaOz7lJ2gycD8yTNAl8Hjhf0lKyC85HgI/nZU8Hvh0RqyLikKR1wDgwAmyMiN2dzmdmQ6J/Xc5XBh8BJM0MPt7/yqkift5Q/k6ynuCsOga3iFjbYvd32pTdB6xqeL8VOOwxkU727DyhkgU8Bp0ilMJCH8OWUjXo3yyF36AbRX+vPfFUz+fKHuItHN3mSdre8H4sImauvloNPq6Ypa4rgX/tdEJnKJhZecVnBTkQEcvaHCs8+CjpArLg9oedTujgZmaldXHlNptCg4+SlgDfBi6N6Hzp2ctzbmZ2NCv6GEjn+Ndx8FHSmcCNwIcjYk+R5vnKzcxK6k/eaLvBR0lX5cc3AJ8DXg98QxLAoVm6uYCDm5n1ok+TVbYafMyD2szrjwEf66ZOBzczK8eLMptZbXmacTOrpXRjm4ObmZWn6XT7pQ5uZlZO0M1DvEdcksGtqtWvulFF2k8KqTwptKEb3bS3itSyFNLVBp2C1o6Ifj3EW4kkg5uZDQkHNzOrJQc3M6sd33Mzs7ryaKmZ1VC4W2pmNRQ4uJlZTaXbKy20hsJG4DJgf0S8Nd/3feDsvMjJwP9GxNIWn30EeA6YosAUJWY2XIb9ObdNwNXA9TM7IuIDM68lfQV4ZpbPXxARB8o20MwSNszBLSJul/TmVseUzRr3F8C7+9wuM0tdBEyl2y/t9Z7bu4AnI+LhNscDuEVSAN9sWO3mMJJGgVGAOVSz+lUKqTRVqOv36lYV3y2F/76qakNfDPOVWwdrgc2zHD8vIvZJOhW4VdKDEXF7q4J54BsDOEmnpPuLmdn/Szi4lV4gRtKxwJ8B329XJl/HlIjYD9xEtviqmdVBANNRbBuAXla/+hPgwYiYbHVQ0omS5s68Bi4GdvVwPjNLSkBMF9sGoGNwk7QZuAM4W9KkpCvzQ2to6pJKOl3SzCIPpwE/k3QvcBfwk4i4uX9NN7OBCrIBhSLbABQZLV3bZv9HW+zbB6zKX+8Fzu2xfWaWsoTvuTlDwczKc3Azs/px4ryZ1VEAnvLIzGrJV25mVj/1Tr+qRAqrX3Vj0Kli3agqRSiFeqtwtK1o1ZWAGNAzbEUkGdzMbEgMKPugCAc3MyvP99zMrHYiPFpqZjXlKzczq58gpqYG3Yi2HNzMrJyZKY8S5eBmZuUl/ChIL/O5mdlRLICYjkJbJ5JWSnpI0oSk9S2OS9LX8+M7Jb2tU50ObmZWTvRnskpJI8A1wKXAOcBaSec0FbsUWJxvo8C1nZrn4GZmpcXUVKGtg+XARETsjYiXgBuA1U1lVgPXR+ZO4GRJ82erNMl7bnfvfPHAyPyJXzXtngf0uP7pROGSI7P+bOXqbVNnm+9VvK1V6cNv0PK7VfHbVmXY/mZdeFOvFTzH/4z/W/zTvILF50ja3vB+rGE1vAXAYw3HJoEVTZ9vVWYB8ES7EyYZ3CLiDc37JG2v44r1df1eUN/vVtfv1a2IWNmnqtSq+hJlXsXdUjMbtElgYcP7M4B9Jcq8ioObmQ3aNmCxpEWSjidbfGpLU5ktwEfyUdN3AM9ERNsuKSTaLW2j7Wr1Q66u3wvq+93q+r0GIiIOSVoHjAMjwMaI2C3pqvz4BmAr2eJTE8BB4IpO9SoSzg0zMyvL3VIzqyUHNzOrpeSDW6e0jGEm6RFJ90na0fQM0FCRtFHSfkm7GvadIulWSQ/n/75ukG0sq813+4Kkx/O/2w5JqwbZRmst6eBWMC1j2F0QEUuH/LmpTUDzM0/rgdsiYjFwW/5+GG3i8O8G8NX877Y0IrYe4TZZAUkHN4qlZdiARcTtwNNNu1cD1+WvrwPeeyTb1C9tvpsNgdSDW7uUi7oI4BZJd0saHXRj+uy0meeQ8n9PHXB7+m1dPjvFxmHtctdd6sGt65SLIXNeRLyNrNv9SUl/NOgGWSHXAm8BlpLlNn5loK2xllIPbl2nXAyTiNiX/7sfuImsG14XT87M2pD/u3/A7embiHgyIqYiW7TzW9Tr71YbqQe3ImkZQ0nSiZLmzrwGLgZ2zf6pobIFuDx/fTnw4wG2pa+aptp5H/X6u9VG0ulX7dIyBtysfjkNuEkSZH+H70XEzYNtUjmSNgPnA/MkTQKfB74E/EDSlcCjwJ8ProXltflu50taSnaL5BHg44Nqn7Xn9Cszq6XUu6VmZqU4uJlZLTm4mVktObiZWS05uJlZLTm4mVktObiZWS39H56KiJNVeAU7AAAAAElFTkSuQmCC" }, "metadata": { "needs_background": "light" } } ], "metadata": {} }, { "cell_type": "code", "execution_count": 112, "source": [ "class GridWord(object):\n", "\n", " @classmethod\n", " def from_base_grid(cls, base_grid: np.ndarray, min_word_length = 2) -> list:\n", "\n", " grid_words = []\n", " # a word starts after each non-letter field, and at the beginning if there is\n", " # a letter field at the beginning of a row/column\n", " h, w = base_grid.shape\n", "\n", " # first get all horizontal words\n", " for y in range(h):\n", " word_start = 0\n", " for x in range(w):\n", " if not base_grid[y, x]:\n", " if word_start < x:\n", " word = GridWord(\n", " y=y,\n", " x=word_start,\n", " is_vertical=False,\n", " length=x - word_start\n", " )\n", " if word.length >= min_word_length:\n", " grid_words.append(word)\n", " \n", " word_start = x + 1\n", "\n", " if word_start < w:\n", " word = GridWord(\n", " y=y,\n", " x=word_start,\n", " is_vertical=False,\n", " length=w - word_start\n", " )\n", " if word.length >= min_word_length:\n", " grid_words.append(word)\n", " \n", " # then get all vertical word slots\n", " for x in range(w):\n", " word_start = 0\n", " for y in range(h):\n", " if not base_grid[y, x]:\n", " if word_start < y:\n", " word = GridWord(\n", " y=word_start,\n", " x=x,\n", " is_vertical=True,\n", " length=y - word_start\n", " )\n", "\n", " if word.length >= min_word_length:\n", " grid_words.append(word)\n", " \n", " word_start = y + 1\n", "\n", " if word_start < h:\n", " word = GridWord(\n", " y=word_start,\n", " x=x,\n", " is_vertical=True,\n", " length=h - word_start\n", " )\n", " if word.length >= min_word_length:\n", " grid_words.append(word)\n", " \n", " for i in range(len(grid_words)):\n", " grid_words[i].id = i\n", " for j in range(i):\n", " word_a = grid_words[i]\n", " word_b = grid_words[j]\n", "\n", " if word_a.check_connected(word_b):\n", " word_a.connect_word(word_b)\n", " word_b.connect_word(word_a)\n", "\n", " return grid_words\n", "\n", " def __init__(self, y: int, x: int, is_vertical: bool, length: int, id: int = None) -> None:\n", " self.x = x\n", " self.y = y\n", " self.is_vertical = is_vertical\n", " self.length = length\n", " self.word_key = None\n", " self.connected_words = []\n", " self.id = id\n", "\n", " self.candidate_cache = []\n", " self.candidate_cache_key = \"\"\n", " \n", " \n", " def get_letters(self, letter_grid: np.ndarray) -> list:\n", " if self.is_vertical:\n", " return letter_grid[self.y:self.y+self.length, self.x].flatten()\n", " return letter_grid[self.y, self.x: self.x + self.length].flatten()\n", " \n", " def set_letters(self, letters, letter_grid: np.ndarray):\n", " if self.is_vertical:\n", " letter_grid[self.y:self.y + self.length, self.x] = letters\n", " else:\n", " letter_grid[self.y, self.x: self.x + self.length] = letters\n", " \n", " def set_word_key(self, word_key:str):\n", " self.word_key = word_key\n", " \n", " def connect_word(self, grid_word):\n", " self.connected_words.append(grid_word)\n", " \n", " \n", " \n", " def check_connected(self, grid_word):\n", " if self.is_vertical == grid_word.is_vertical:\n", " return False\n", " \n", " if self.is_vertical:\n", " if self.y > grid_word.y:\n", " return False\n", " if self.y + self.length <= grid_word.y:\n", " return False\n", " \n", " if self.x >= grid_word.x + grid_word.length:\n", " return False\n", " \n", " if self.x < grid_word.x:\n", " return False\n", " \n", " else:\n", " if self.x > grid_word.x:\n", " return False\n", " if self.x + self.length <= grid_word.x:\n", " return False\n", " if self.y >= grid_word.y + grid_word.length:\n", " return False\n", " if self.y < grid_word.y:\n", " return False\n", " \n", " return True\n", " \n", " def get_candidates(self, letter_grid, db, inverted_db):\n", " letters = self.get_letters(letter_grid)\n", " word = \"\".join(letters) \n", " if word == self.candidate_cache_key:\n", " return self.candidate_cache\n", " self.candidate_cache = find_suitable_words(letters, db, inverted_db)\n", " self.candidate_cache_key = word\n", " return self.candidate_cache\n", " \n", " def get_connected_words(self):\n", " return self.connected_words\n", "\n", " \n", "\n", "\n", "class GridCreationState(object):\n", " def __init__(self, base_grid, db, inverted_db, letter_grid = None, grid_words = None, final_grid_words = None, used_ids = None) -> None:\n", " self.base_grid = base_grid\n", " self.shape = base_grid.shape\n", " self.db = db\n", " self.inverted_db = inverted_db\n", " \n", "\n", " if letter_grid is None:\n", " self.letter_grid = np.full(shape = self.shape, fill_value=' ', dtype=np.unicode)\n", " else:\n", " self.letter_grid = letter_grid\n", " \n", " if grid_words is None:\n", " self.grid_words = GridWord.from_base_grid(base_grid=base_grid)\n", " else:\n", " self.grid_words = grid_words\n", "\n", " \n", " if final_grid_words is None:\n", " self.final_grid_words = []\n", " else:\n", " self.final_grid_words = final_grid_words\n", " \n", " if used_ids is None:\n", " self.used_ids = [[False]] * len(self.grid_words)\n", " else:\n", " self.used_ids = used_ids\n", " \n", "\n", "\n", " def copy(self):\n", " return GridCreationState(self.base_grid, self.db, self.inverted_db, self.letter_grid.copy(), self.grid_words.copy(), self.final_grid_words.copy(), self.used_ids.copy())\n", " \n", "\n", " def set_random_word(self, last_word = None, n_retries = 1, max_preselected = 10):\n", " # choose random word\n", "\n", " preselected_id = None\n", " preselected_candidates = []\n", "\n", " for word in self.final_grid_words:\n", " connected_words = word.get_connected_words()\n", " #random.shuffle(connected_words)\n", " for connected_word in connected_words:\n", " if not self.used_ids[connected_word.id]:\n", " preselected_id = connected_word.id\n", " for i in range(preselected_id):\n", " if self.used_ids[i]:\n", " preselected_id -= 1\n", " preselected_candidates.append(preselected_id)\n", " \n", " \n", " if len(preselected_candidates) > 0:\n", " random.shuffle(preselected_candidates)\n", " break\n", " \n", " \n", "\n", "\n", " n_tries = 1\n", " if preselected_id is not None:\n", " n_tries = min(len(preselected_candidates), max_preselected)\n", " else:\n", " random_index = random.randint(0, len(self.grid_words) - 1)\n", " \n", " for i in range(n_tries):\n", " if preselected_id is not None:\n", " random_index = preselected_candidates[i]\n", " grid_word = self.grid_words[random_index]\n", " \n", " candidates_raw = list(grid_word.get_candidates(self.letter_grid, self.db, self.inverted_db))\n", " \n", " \n", " if len(candidates_raw) > 0:\n", " for j in range(min(n_retries, len(candidates_raw))):\n", " word_key = candidates_raw[j]\n", " word = normalize_word(self.db[word_key]['word'])\n", "\n", " new_grid = self.letter_grid.copy()\n", "\n", " grid_word.set_letters(list(word), new_grid)\n", "\n", " for word in grid_word.get_connected_words():\n", " if word.id not in self.used_ids:\n", " n_cands = len(word.get_candidates(new_grid, self.db, self.inverted_db))\n", " if n_cands == 0:\n", " return None\n", "\n", "\n", " self.letter_grid = new_grid\n", " grid_word.set_word_key(word_key)\n", " self.used_ids[grid_word.id] = True\n", " self.final_grid_words.append(grid_word)\n", " del(self.grid_words[random_index])\n", "\n", " return grid_word\n", " \n", " return None\n", " \n", " \n", " def fill(self, depth = 0, last_word = None):\n", " if depth % 5 == 0:\n", " print(\"depth\", depth)\n", "\n", " n_retries = 100 if depth == 0 else 2\n", " if len(self.grid_words) == 0:\n", " return self\n", "\n", "\n", " \n", " state_copy = self.copy()\n", " grid_word = None\n", " for _ in range(n_retries):\n", " \n", " \n", " grid_word = state_copy.set_random_word(last_word = last_word, n_retries=20, max_preselected = 2)\n", " if grid_word is not None:\n", " \n", " final_state = state_copy.fill(\n", " depth = depth + 1,\n", " last_word = grid_word)\n", " if final_state is not None:\n", " return final_state\n", " return None\n", "\n", " \n", " \n", "\n", "\n", "\n", " \n" ], "outputs": [], "metadata": {} }, { "cell_type": "code", "execution_count": 114, "source": [ "%%prun\n", "base_grid = create_base_grid(14, min_word_length=3, max_word_length=12)\n", "\n", "db = get_database(\"de\")\n", "inverted_db = get_inverted_database(\"de\")\n", "\n", "grid_state = GridCreationState(base_grid, db, inverted_db)\n", "\n", "final_state = grid_state.fill()\n", "\n", "print(final_state is not None)" ], "outputs": [ { "output_type": "stream", "name": "stdout", "text": [ "depth 0\n", "True\n", " " ] }, { "output_type": "stream", "name": "stdout", "text": [ " 1490 function calls (1488 primitive calls) in 0.004 seconds\n", "\n", " Ordered by: internal time\n", "\n", " ncalls tottime percall cumtime percall filename:lineno(function)\n", " 1 0.002 0.002 0.003 0.003 :1(create_base_grid)\n", " 14 0.000 0.000 0.000 0.000 {method 'astype' of 'numpy.ndarray' objects}\n", " 14 0.000 0.000 0.000 0.000 {method 'reduce' of 'numpy.ufunc' objects}\n", " 1 0.000 0.000 0.000 0.000 :3(from_base_grid)\n", " 184 0.000 0.000 0.000 0.000 random.py:238(_randbelow_with_getrandbits)\n", " 184 0.000 0.000 0.000 0.000 random.py:291(randrange)\n", " 2 0.000 0.000 0.000 0.000 :188(set_random_word)\n", " 2 0.000 0.000 0.000 0.000 :92(find_suitable_words)\n", " 1 0.000 0.000 0.004 0.004 {built-in method builtins.exec}\n", " 7 0.000 0.000 0.000 0.000 socket.py:438(send)\n", " 11 0.000 0.000 0.000 0.000 {method 'copy' of 'numpy.ndarray' objects}\n", " 3/1 0.000 0.000 0.001 0.001 :254(fill)\n", " 184 0.000 0.000 0.000 0.000 random.py:335(randint)\n", " 22 0.000 0.000 0.000 0.000 {built-in method numpy.core._multiarray_umath.implement_array_function}\n", " 14 0.000 0.000 0.000 0.000 fromnumeric.py:70(_wrapreduction)\n", " 14 0.000 0.000 0.000 0.000 fromnumeric.py:2105(sum)\n", " 3 0.000 0.000 0.000 0.000 {method 'join' of 'str' objects}\n", " 315 0.000 0.000 0.000 0.000 {method 'getrandbits' of '_random.Random' objects}\n", " 7 0.000 0.000 0.000 0.000 iostream.py:195(schedule)\n", " 14 0.000 0.000 0.000 0.000 <__array_function__ internals>:2(sum)\n", " 1 0.000 0.000 0.004 0.004 :1()\n", " 6 0.000 0.000 0.000 0.000 iostream.py:384(write)\n", " 75 0.000 0.000 0.000 0.000 {built-in method builtins.min}\n", " 3 0.000 0.000 0.000 0.000 :154(__init__)\n", " 3 0.000 0.000 0.000 0.000 :138(get_candidates)\n", " 8 0.000 0.000 0.000 0.000 numeric.py:268(full)\n", " 8 0.000 0.000 0.000 0.000 {built-in method numpy.empty}\n", " 1 0.000 0.000 0.000 0.000 {method 'intersection' of 'set' objects}\n", " 184 0.000 0.000 0.000 0.000 {method 'bit_length' of 'int' objects}\n", " 8 0.000 0.000 0.000 0.000 <__array_function__ internals>:2(copyto)\n", " 3 0.000 0.000 0.000 0.000 {method 'flatten' of 'numpy.ndarray' objects}\n", " 2 0.000 0.000 0.000 0.000 :96(set_letters)\n", " 2 0.000 0.000 0.000 0.000 {built-in method builtins.print}\n", " 14 0.000 0.000 0.000 0.000 fromnumeric.py:71()\n", " 3 0.000 0.000 0.000 0.000 :91(get_letters)\n", " 7 0.000 0.000 0.000 0.000 :78(__init__)\n", " 7 0.000 0.000 0.000 0.000 threading.py:1093(is_alive)\n", " 2 0.000 0.000 0.000 0.000 :184(copy)\n", " 6 0.000 0.000 0.000 0.000 iostream.py:308(_is_master_process)\n", " 20 0.000 0.000 0.000 0.000 {built-in method builtins.isinstance}\n", " 7 0.000 0.000 0.000 0.000 iostream.py:91(_event_pipe)\n", " 7 0.000 0.000 0.000 0.000 threading.py:1039(_wait_for_tstate_lock)\n", " 2 0.000 0.000 0.000 0.000 :88(normalize_word)\n", " 7 0.000 0.000 0.000 0.000 {method 'acquire' of '_thread.lock' objects}\n", " 14 0.000 0.000 0.000 0.000 fromnumeric.py:2100(_sum_dispatcher)\n", " 1 0.000 0.000 0.000 0.000 :19(get_database)\n", " 2 0.000 0.000 0.000 0.000 {method 'translate' of 'str' objects}\n", " 6 0.000 0.000 0.000 0.000 {built-in method posix.getpid}\n", " 17 0.000 0.000 0.000 0.000 {built-in method builtins.len}\n", " 14 0.000 0.000 0.000 0.000 {method 'items' of 'dict' objects}\n", " 6 0.000 0.000 0.000 0.000 iostream.py:321(_schedule_flush)\n", " 8 0.000 0.000 0.000 0.000 multiarray.py:1043(copyto)\n", " 7 0.000 0.000 0.000 0.000 {method 'append' of 'list' objects}\n", " 6 0.000 0.000 0.000 0.000 {method 'copy' of 'list' objects}\n", " 7 0.000 0.000 0.000 0.000 threading.py:529(is_set)\n", " 1 0.000 0.000 0.000 0.000 :78(get_inverted_database)\n", " 2 0.000 0.000 0.000 0.000 :105(connect_word)\n", " 3 0.000 0.000 0.000 0.000 :147(get_connected_words)\n", " 1 0.000 0.000 0.000 0.000 :110(check_connected)\n", " 2 0.000 0.000 0.000 0.000 {method 'lower' of 'str' objects}\n", " 7 0.000 0.000 0.000 0.000 {method 'append' of 'collections.deque' objects}\n", " 2 0.000 0.000 0.000 0.000 :102(set_word_key)\n", " 1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}" ] } ], "metadata": {} }, { "cell_type": "code", "execution_count": 115, "source": [ "\n", "plt.imshow(base_grid)\n", "plt.show()\n", "print(final_state.letter_grid)\n", "for grid_word in final_state.final_grid_words:\n", " connected = []\n", " for word in grid_word.connected_words:\n", " connected.append(word.word_key)\n", " print(grid_word.word_key, connected)" ], "outputs": [ { "output_type": "display_data", "data": { "text/plain": [ "
" ], "image/svg+xml": "\n\n\n\n \n \n \n \n 2021-08-23T14:20:12.832599\n image/svg+xml\n \n \n Matplotlib v3.3.4, https://matplotlib.org/\n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n\n", "image/png": "iVBORw0KGgoAAAANSUhEUgAAAPsAAAD4CAYAAAAq5pAIAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuNCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8QVMy6AAAACXBIWXMAAAsTAAALEwEAmpwYAAALLUlEQVR4nO3df6zddX3H8edrLVBbJcA2jbRkYMLYCEExjUNd3GI1q0iof+wPyFi6adJ/tonGRCH8YfbfEo3RZEZDECWTwB+IkxAVmqoxJrOzQNMBRWDooFItC5kYyCiN7/1xD0m5a6k53+/59sj7+Uhuzu/7/tybPnN+3HP6SVUh6dXvd072AiRNw9ilJoxdasLYpSaMXWpi7ZTDTs1ptY4Nc9/+Dy9+fu7bPrJv/dy3lX5b/C/PcbheyLEumzT2dWzgT7Jl7tvffffeuW/7F2e/Ze7bSr8tdteu417mw3ipCWOXmjB2qYlBsSfZmuTHSR5Lcu1Yi5I0vrljT7IG+DzwPuBC4KokF461MEnjGnLP/jbgsap6vKoOA7cB28ZZlqSxDYl9I/DkUacPzM57mSQ7kuxJsudFXhgwTtIQQ2I/1h/u/9/nZavqhqraXFWbT+G0AeMkDTEk9gPAOUed3gQ8NWw5khZlSOw/As5Pcl6SU4ErgTvHWZaksc39dtmqOpLk74G7gTXATVX14GgrkzSqQe+Nr6pvAt8caS2SFsh30ElNGLvURKb832U3v3ld/fvd55z4iq8yfrxWU9ldu3i2njnm59m9Z5eaMHapCWOXmjB2qQljl5owdqkJY5eaMHapCWOXmjB2qQljl5owdqkJY5eaMHapiUl3cX1k3/pBH/e8+6m9c9/Wj5mqO+/ZpSaMXWrC2KUmjF1qYsguruck+W6S/UkeTHLNmAuTNK4hr8YfAT5WVfcleR1wb5KdVfXQSGuTNKK579mr6mBV3Tc7/itgP8fYxVXSchjl7+xJzgUuAXYf47IdwA6AdawfY5ykOQx+gS7Ja4GvAR+pqmdXX+6WzdJyGBR7klNYCf2WqrpjnCVJWoQhr8YH+BKwv6o+M96SJC3CkHv2dwJ/Dbw7yd7Z12UjrUvSyIbsz/4D4Jh7SklaPr6DTmrC2KUmJv08+1B+Jl2an/fsUhPGLjVh7FITxi41YexSE8YuNWHsUhPGLjVh7FITxi41YexSE8YuNWHsUhPGLjVh7FITxi41YexSE8YuNWHsUhNjbP+0Jsn9Se4aY0GSFmOMe/ZrWNnBVdISG7rX2ybg/cCN4yxH0qIMvWf/LPBx4NfHu0KSHUn2JNnzIi8MHCdpXkM2drwcOFRV977S9dyyWVoOQzd2vCLJT4HbWNng8aujrErS6OaOvaquq6pNVXUucCXwnaq6erSVSRqVf2eXmhhlr7eq+h7wvTG+l6TF8J5dasLYpSaMXWrC2KUmjF1qwtilJoxdasLYpSaMXWrC2KUmjF1qwtilJoxdasLYpSaMXWrC2KUmjF1qwtilJoxdasLYpSaMXWrC2KUmhm7seEaS25M8nGR/krePtTBJ4xr6/8Z/Dvh2Vf1lklOB9SOsSdICzB17ktOBdwF/A1BVh4HD4yxL0tiGPIx/E/A08OUk9ye5McmG1Vdyy2ZpOQyJfS3wVuALVXUJ8Bxw7eoruWWztByGxH4AOFBVu2enb2clfklLaMiWzT8HnkxyweysLcBDo6xK0uiGvhr/D8Ats1fiHwf+dviSJC3CoNirai+weZylSFok30EnNWHsUhPGLjVh7FITxi41YexSE8YuNWHsUhPGLjVh7FITxi41YexSE8YuNWHsUhPGLjVh7FITxi41YexSE8YuNWHsUhPGLjVh7FITQ7ds/miSB5M8kOTWJOvGWpikcc0de5KNwIeBzVV1EbAGuHKshUka19CH8WuB1yRZy8re7E8NX5KkRRiy19vPgE8DTwAHgV9W1T2rr+eWzdJyGPIw/kxgG3AecDawIcnVq6/nls3SchjyMP49wE+q6umqehG4A3jHOMuSNLYhsT8BXJpkfZKwsmXz/nGWJWlsQ56z7wZuB+4D/mP2vW4YaV2SRjZ0y+ZPAp8caS2SFsh30ElNGLvUhLFLTRi71ISxS00Yu9SEsUtNGLvUhLFLTRi71ISxS00Yu9SEsUtNGLvUhLFLTRi71ISxS00Yu9SEsUtNGLvUhLFLTRi71MQJY09yU5JDSR446ryzkuxM8ujs8MzFLlPSUL/JPftXgK2rzrsW2FVV5wO7ZqclLbETxl5V3weeWXX2NuDm2fGbgQ+MuyxJY5v3OfsbquogwOzw9ce7ols2S8th4S/QuWWztBzmjf0XSd4IMDs8NN6SJC3CvLHfCWyfHd8OfGOc5UhalN/kT2+3Av8GXJDkQJIPAf8EvDfJo8B7Z6clLbETbtlcVVcd56ItI69F0gL5DjqpCWOXmjB2qQljl5owdqkJY5eaMHapCWOXmjB2qQljl5owdqkJY5eaMHapCWOXmjB2qQljl5owdqkJY5eaMHapCWOXmjB2qQljl5qYd8vmTyV5OMm+JF9PcsZCVylpsHm3bN4JXFRVFwOPANeNvC5JI5try+aquqeqjsxO/hDYtIC1SRrRGM/ZPwh8a4TvI2mBTrj90ytJcj1wBLjlFa6zA9gBsI71Q8ZJGmDu2JNsBy4HtlRVHe96VXUDcAPA6TnruNeTtFhzxZ5kK/AJ4M+q6vlxlyRpEebdsvmfgdcBO5PsTfLFBa9T0kDzbtn8pQWsRdIC+Q46qQljl5owdqkJY5eaMHapCWOXmjB2qQljl5owdqkJY5eaMHapCWOXmjB2qQljl5owdqkJY5eaMHapCWOXmsgr/Mew4w9Lngb+6xWu8nvAf0+0HGc7+9U4+w+q6vePdcGksZ9Ikj1VtdnZznb2+HwYLzVh7FITyxb7Dc52trMXY6mes0tanGW7Z5e0IMYuNbEUsSfZmuTHSR5Lcu2Ec89J8t0k+5M8mOSaqWYftYY1Se5PctfEc89IcnuSh2c//9snnP3R2e/7gSS3Jlm34Hk3JTmU5IGjzjsryc4kj84Oz5xw9qdmv/d9Sb6e5IxFzF7tpMeeZA3weeB9wIXAVUkunGj8EeBjVfXHwKXA3004+yXXAPsnngnwOeDbVfVHwJunWkOSjcCHgc1VdRGwBrhywWO/Amxddd61wK6qOh/YNTs91eydwEVVdTHwCHDdgma/zEmPHXgb8FhVPV5Vh4HbgG1TDK6qg1V13+z4r1j5B79xitkASTYB7wdunGrmbO7pwLuYbdBZVYer6n8mXMJa4DVJ1gLrgacWOayqvg88s+rsbcDNs+M3Ax+YanZV3VNVR2YnfwhsWsTs1ZYh9o3Ak0edPsCEwb0kybnAJcDuCcd+Fvg48OsJZwK8CXga+PLsKcSNSTZMMbiqfgZ8GngCOAj8sqrumWL2Km+oqoOzNR0EXn8S1gDwQeBbUwxahthzjPMm/XtgktcCXwM+UlXPTjTzcuBQVd07xbxV1gJvBb5QVZcAz7G4h7EvM3tuvA04Dzgb2JDk6ilmL5sk17PyVPKWKeYtQ+wHgHOOOr2JBT+sO1qSU1gJ/ZaqumOqucA7gSuS/JSVpy7vTvLViWYfAA5U1UuPYm5nJf4pvAf4SVU9XVUvAncA75ho9tF+keSNALPDQ1MOT7IduBz4q5rozS7LEPuPgPOTnJfkVFZerLlzisFJwsrz1v1V9ZkpZr6kqq6rqk1VdS4rP/N3qmqSe7iq+jnwZJILZmdtAR6aYjYrD98vTbJ+9vvfwsl5gfJOYPvs+HbgG1MNTrIV+ARwRVU9P9VcquqkfwGXsfKq5H8C1084909ZecqwD9g7+7rsJPz8fw7cNfHMtwB7Zj/7vwJnTjj7H4GHgQeAfwFOW/C8W1l5feBFVh7VfAj4XVZehX90dnjWhLMfY+V1qpf+zX1xit+7b5eVmliGh/GSJmDsUhPGLjVh7FITxi41YexSE8YuNfF/ksZAGJKKktsAAAAASUVORK5CYII=" }, "metadata": { "needs_background": "light" } }, { "output_type": "stream", "name": "stdout", "text": [ "[[' ' 'm' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ']\n", " ['a' 'a' 'c' 'h' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ']\n", " [' ' 'i' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ']\n", " [' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ']\n", " [' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ']\n", " [' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ']\n", " [' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ']\n", " [' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ']\n", " [' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ']\n", " [' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ']\n", " [' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ']\n", " [' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ']\n", " [' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ']\n", " [' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ']]\n", "mai ['aach0']\n", "aach0 ['mai']\n" ] } ], "metadata": {} }, { "cell_type": "code", "execution_count": null, "source": [ "grid_word" ], "outputs": [], "metadata": {} }, { "cell_type": "code", "execution_count": 292, "source": [ "def create_word_grid(w: int, h: int, lang_code: str = \"en\", target_density: float = 0.5, difficulty: int = 0):\n", " np.full()\n", "\n" ], "outputs": [], "metadata": {} }, { "cell_type": "code", "execution_count": 85, "source": [ "w = 5\n", "h = 5\n", "\n", "hh_index = np.zeros(shape=(h,w), dtype = int)\n", "vv_index = np.zeros(shape=(w,h), dtype = int)\n", "\n", "\n", "h_index = w - np.arange(w)\n", "v_index = h - np.arange(h)\n", "\n", "hh_index[:] = h_index\n", "vv_index[:] = v_index\n", "vv_index = vv_index.transpose()\n", "\n", "\n", "horizontal_starting_points = np.full(shape=(h, w), dtype=int, fill_value=-1)\n", "horizontal_starting_points[::2,::2] = 0\n", "horizontal_starting_points[horizontal_starting_points == 0] = hh_index[horizontal_starting_points == 0]\n", "\n", "vertical_starting_points = np.full(shape=(h, w), dtype=int, fill_value=-1)\n", "vertical_starting_points[::2,::2] = 0\n", "vertical_starting_points[vertical_starting_points == 0] = vv_index[vertical_starting_points == 0]\n", "\n", "vertical_starting_points" ], "outputs": [ { "output_type": "execute_result", "data": { "text/plain": [ "array([[ 5, -1, 5, -1, 5],\n", " [-1, -1, -1, -1, -1],\n", " [ 3, -1, 3, -1, 3],\n", " [-1, -1, -1, -1, -1],\n", " [ 1, -1, 1, -1, 1]])" ] }, "metadata": {}, "execution_count": 85 } ], "metadata": {} }, { "cell_type": "code", "execution_count": null, "source": [], "outputs": [], "metadata": {} }, { "cell_type": "code", "execution_count": 82, "source": [ "w = 10\n", "h = 5\n", "\n", "hh_index = np.zeros(shape=(h,w), dtype = int)\n", "vv_index = np.zeros(shape=(w,h), dtype = int)\n", "\n", "\n", "h_index = w - 1 - np.arange(w)\n", "v_index = h - 1 - np.arange(h)\n", "\n", "hh_index[:] = h_index\n", "vv_index[:] = v_index\n", "vv_index = vv_index.transpose()\n", "\n", "hh_index\n" ], "outputs": [ { "output_type": "execute_result", "data": { "text/plain": [ "array([[9, 8, 7, 6, 5, 4, 3, 2, 1, 0],\n", " [9, 8, 7, 6, 5, 4, 3, 2, 1, 0],\n", " [9, 8, 7, 6, 5, 4, 3, 2, 1, 0],\n", " [9, 8, 7, 6, 5, 4, 3, 2, 1, 0],\n", " [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]])" ] }, "metadata": {}, "execution_count": 82 } ], "metadata": {} }, { "cell_type": "code", "execution_count": 87, "source": [ "l = [[1,2],[2,3]]\n", "\n", "[1,3] in l" ], "outputs": [ { "output_type": "execute_result", "data": { "text/plain": [ "False" ] }, "metadata": {}, "execution_count": 87 } ], "metadata": {} }, { "cell_type": "code", "execution_count": 53, "source": [ "import pprint\n", "\n", "grid, hints, solution = create_word_grid(10,20)\n", "\n", "pprint.pprint(grid)" ], "outputs": [ { "output_type": "stream", "name": "stdout", "text": [ "100\n", "200\n", "300\n", "400\n", "500\n", "600\n", "700\n", "800\n", "900\n", "1000\n", "1100\n", "1200\n" ] }, { "output_type": "error", "ename": "RecursionError", "evalue": "maximum recursion depth exceeded while calling a Python object", "traceback": [ "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[0;31mRecursionError\u001b[0m Traceback (most recent call last)", "\u001b[0;32m\u001b[0m in \u001b[0;36m\u001b[0;34m\u001b[0m\n\u001b[1;32m 1\u001b[0m \u001b[0;32mimport\u001b[0m \u001b[0mpprint\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 2\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 3\u001b[0;31m \u001b[0mgrid\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mhints\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0msolution\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mcreate_word_grid\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m10\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m20\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 4\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 5\u001b[0m \u001b[0mpprint\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mpprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mgrid\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;32m\u001b[0m in \u001b[0;36mcreate_word_grid\u001b[0;34m(w, h, lang_code, target_density, difficulty)\u001b[0m\n\u001b[1;32m 279\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 280\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 281\u001b[0;31m \u001b[0msolution_word_locations\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mget_solution_word\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 282\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 283\u001b[0m \u001b[0mlogging\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0minfo\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"crossword generation done after %s iterations\"\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mstr\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mi\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;32m\u001b[0m in \u001b[0;36mget_solution_word\u001b[0;34m(min_length, max_length)\u001b[0m\n\u001b[1;32m 173\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0mchar\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mlocations_cpy\u001b[0m \u001b[0;32mor\u001b[0m \u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mlocations_cpy\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mchar\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 174\u001b[0m \u001b[0;31m# next try:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 175\u001b[0;31m \u001b[0;32mreturn\u001b[0m \u001b[0mget_solution_word\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mmin_length\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0mmin_length\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mmax_length\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0mmax_length\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 176\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 177\u001b[0m \u001b[0mlocation_candidates\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mlocations_cpy\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mchar\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "... last 1 frames repeated, from the frame below ...\n", "\u001b[0;32m\u001b[0m in \u001b[0;36mget_solution_word\u001b[0;34m(min_length, max_length)\u001b[0m\n\u001b[1;32m 173\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0mchar\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mlocations_cpy\u001b[0m \u001b[0;32mor\u001b[0m \u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mlocations_cpy\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mchar\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 174\u001b[0m \u001b[0;31m# next try:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 175\u001b[0;31m \u001b[0;32mreturn\u001b[0m \u001b[0mget_solution_word\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mmin_length\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0mmin_length\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mmax_length\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0mmax_length\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 176\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 177\u001b[0m \u001b[0mlocation_candidates\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mlocations_cpy\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mchar\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;31mRecursionError\u001b[0m: maximum recursion depth exceeded while calling a Python object" ] } ], "metadata": {} } ], "metadata": { "orig_nbformat": 4, "language_info": { "name": "python", "version": "3.9.5", "mimetype": "text/x-python", "codemirror_mode": { "name": "ipython", "version": 3 }, "pygments_lexer": "ipython3", "nbconvert_exporter": "python", "file_extension": ".py" }, "kernelspec": { "name": "python3", "display_name": "Python 3.9.5 64-bit" }, "interpreter": { "hash": "916dbcbb3f70747c44a77c7bcd40155683ae19c65e1c03b4aa3499c5328201f1" } }, "nbformat": 4, "nbformat_minor": 2 }