crosswords/data/better_grid_building2.ipynb

1423 lines
138 KiB
Plaintext
Raw Permalink Normal View History

2021-08-31 13:56:29 +02:00
{
"cells": [
{
"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",
"\n",
"import matplotlib.pyplot as plt\n",
"from IPython.display import display"
],
"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: 10,\n",
" 1: 6,\n",
" 2: 0\n",
" },\n",
" 'en': {\n",
" 0: 150,\n",
" 1: 100,\n",
" 2: 10\n",
" }\n",
"}\n",
"\n",
"\n",
"def get_database(lang: str = \"en\", difficulty: int = -1) -> 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] = {}\n",
" get_database._dbs[lang][-1] = db\n",
"\n",
" logging.info(\"database loaded\")\n",
" \n",
" if difficulty not in get_database._dbs[lang]:\n",
" t = get_difficulty_threshold(lang, difficulty)\n",
" logging.info(\"generate sub database for lang %s with difficulty %s\", lang, str(difficulty))\n",
" db = get_database._dbs[lang][-1]\n",
" new_db = {}\n",
" for word_key, item in db.items():\n",
" num_translations = item['num_translations']\n",
" if num_translations >= t:\n",
" new_db[word_key] = item\n",
" \n",
" get_database._dbs[lang][difficulty] = new_db\n",
"\n",
" return get_database._dbs[lang][difficulty]\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, difficulty: int = -1) -> dict:\n",
" if lang not in get_inverted_database._dbs:\n",
" get_inverted_database._dbs[lang] = {}\n",
" if difficulty not in get_inverted_database._dbs[lang]:\n",
" get_inverted_database._dbs[lang][difficulty] = build_inverted_index(get_database(lang, difficulty))\n",
" return get_inverted_database._dbs[lang][difficulty]\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": [
"%%prun\n",
"\n",
"print(len(find_suitable_words(list(\" \"), get_database(\n",
" \"de\", difficulty=0), get_inverted_database(\"de\", difficulty=0))))\n"
],
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"40\n",
" "
]
},
{
"output_type": "stream",
"name": "stdout",
"text": [
" 325711 function calls (325710 primitive calls) in 0.776 seconds\n",
"\n",
" Ordered by: internal time\n",
"\n",
" ncalls tottime percall cumtime percall filename:lineno(function)\n",
" 1 0.533 0.533 0.533 0.533 decoder.py:343(raw_decode)\n",
" 1 0.118 0.118 0.183 0.183 <ipython-input-2-3db35396d80b>:54(build_inverted_index)\n",
" 1 0.029 0.029 0.044 0.044 {method 'read' of '_io.TextIOWrapper' objects}\n",
" 250884 0.028 0.000 0.028 0.000 {method 'append' of 'list' objects}\n",
" 14931 0.019 0.000 0.019 0.000 {method 'translate' of 'str' objects}\n",
" 1 0.015 0.015 0.015 0.015 {built-in method _codecs.utf_8_decode}\n",
" 2 0.014 0.007 0.593 0.296 <ipython-input-2-3db35396d80b>:19(get_database)\n",
" 14931 0.009 0.000 0.031 0.000 <ipython-input-2-3db35396d80b>:103(normalize_word)\n",
" 14931 0.003 0.000 0.003 0.000 {method 'isalnum' of 'str' objects}\n",
" 14931 0.003 0.000 0.003 0.000 {method 'lower' of 'str' objects}\n",
"14941/14940 0.002 0.000 0.002 0.000 {built-in method builtins.len}\n",
" 1 0.001 0.001 0.578 0.578 __init__.py:274(load)\n",
" 1 0.000 0.000 0.000 0.000 {built-in method io.open}\n",
" 1 0.000 0.000 0.776 0.776 {built-in method builtins.exec}\n",
" 3 0.000 0.000 0.000 0.000 socket.py:438(send)\n",
" 1 0.000 0.000 0.775 0.775 <string>:1(<module>)\n",
" 1 0.000 0.000 0.000 0.000 __init__.py:1908(basicConfig)\n",
" 2 0.000 0.000 0.000 0.000 pathlib.py:64(parse_parts)\n",
" 2 0.000 0.000 0.000 0.000 pathlib.py:672(_parse_args)\n",
" 1 0.000 0.000 0.533 0.533 __init__.py:299(loads)\n",
" 1 0.000 0.000 0.533 0.533 decoder.py:332(decode)\n",
" 3 0.000 0.000 0.000 0.000 iostream.py:195(schedule)\n",
" 1 0.000 0.000 0.016 0.016 codecs.py:319(decode)\n",
" 3 0.000 0.000 0.000 0.000 __init__.py:2089(info)\n",
" 1 0.000 0.000 0.000 0.000 {method '__exit__' of '_io._IOBase' objects}\n",
" 1 0.000 0.000 0.000 0.000 pathlib.py:692(_from_parts)\n",
" 2 0.000 0.000 0.000 0.000 iostream.py:384(write)\n",
" 2 0.000 0.000 0.000 0.000 {method 'match' of 're.Pattern' objects}\n",
" 3 0.000 0.000 0.000 0.000 __init__.py:1689(isEnabledFor)\n",
" 1 0.000 0.000 0.000 0.000 {built-in method builtins.print}\n",
" 5 0.000 0.000 0.000 0.000 __init__.py:218(_acquireLock)\n",
" 1 0.000 0.000 0.000 0.000 __init__.py:857(__init__)\n",
" 1 0.000 0.000 0.000 0.000 pathlib.py:633(__getitem__)\n",
" 1 0.000 0.000 0.000 0.000 pathlib.py:1069(__new__)\n",
" 1 0.000 0.000 0.000 0.000 _bootlocale.py:33(getpreferredencoding)\n",
" 1 0.000 0.000 0.183 0.183 <ipython-input-2-3db35396d80b>:91(get_inverted_database)\n",
" 3 0.000 0.000 0.000 0.000 threading.py:1093(is_alive)\n",
" 1 0.000 0.000 0.000 0.000 __init__.py:553(__init__)\n",
" 2 0.000 0.000 0.000 0.000 iostream.py:308(_is_master_process)\n",
" 1 0.000 0.000 0.000 0.000 pathlib.py:732(__str__)\n",
" 3 0.000 0.000 0.000 0.000 threading.py:1039(_wait_for_tstate_lock)\n",
" 5 0.000 0.000 0.000 0.000 __init__.py:227(_releaseLock)\n",
" 1 0.000 0.000 0.000 0.000 {method 'search' of 're.Pattern' objects}\n",
" 1 0.000 0.000 0.000 0.000 _weakrefset.py:82(add)\n",
" 3 0.000 0.000 0.000 0.000 __init__.py:1436(info)\n",
" 1 0.000 0.000 0.000 0.000 pathlib.py:726(_make_child)\n",
" 3 0.000 0.000 0.000 0.000 {method 'acquire' of '_thread.lock' objects}\n",
" 1 0.000 0.000 0.000 0.000 {built-in method _locale.nl_langinfo}\n",
" 1 0.000 0.000 0.000 0.000 __init__.py:838(_addHandlerRef)\n",
" 2 0.000 0.000 0.000 0.000 pathlib.py:293(splitroot)\n",
" 2 0.000 0.000 0.000 0.000 pathlib.py:705(_from_parsed_parts)\n",
" 1 0.000 0.000 0.000 0.000 __init__.py:886(createLock)\n",
" 1 0.000 0.000 0.000 0.000 __init__.py:424(validate)\n",
" 8 0.000 0.000 0.000 0.000 {built-in method builtins.isinstance}\n",
" 1 0.000 0.000 0.000 0.000 __init__.py:1049(__init__)\n",
" 5 0.000 0.000 0.000 0.000 {method 'acquire' of '_thread.RLock' objects}\n",
" 1 0.000 0.000 0.000 0.000 <ipython-input-2-3db35396d80b>:107(find_suitable_words)\n",
" 3 0.000 0.000 0.000 0.000 iostream.py:91(_event_pipe)\n",
" 1 0.000 0.000 0.000 0.000 __init__.py:246(_register_at_fork_reinit_lock)\n",
" 1 0.000 0.000 0.000 0.000 {method 'startswith' of 'str' objects}\n",
" 1 0.000 0.000 0.000 0.000 pathlib.py:715(_format_parsed_parts)\n",
" 1 0.000 0.000 0.000 0.000 __init__.py:1601(addHandler)\n",
" 2 0.000 0.000 0.000 0.000 iostream.py:321(_schedule_flush)\n",
" 1 0.000 0.000 0.000 0.000 pathlib.py:620(__init__)\n",
" 1 0.000 0.000 0.000 0.000 codecs.py:309(__init__)\n",
" 1 0.000 0.000 0.000 0.000 threading.py:82(RLock)\n",
" 11 0.000 0.000 0.000 0.000 {method 'pop' of 'dict' objects}\n",
" 1 0.000 0.000 0.000 0.000 pathlib.py:986(parents)\n",
" 3 0.000 0.000 0.000 0.000 {built-in method __new__ of type object at 0x90efa0}\n",
" 3 0.000 0.000 0.000 0.000 pathlib.py:1079(_init)\n",
" 2 0.000 0.000 0.000 0.000 {built-in method sys.intern}\n",
" 5 0.000 0.000 0.000 0.000 {method 'release' of '_thread.RLock' objects}\n",
" 2 0.000 0.000 0.000 0.000 {method 'end' of 're.Match' objects}\n",
" 1 0.000 0.000 0.000 0.000 pathlib.py:964(__truediv__)\n",
" 2 0.000 0.000 0.000 0.000 {built-in method posix.getpid}\n",
" 1 0.000 0.000 0.000 0.000 __init__.py:771(__init__)\n",
" 1 0.000 0.000 0.000 0.000 <ipython-input-2-3db35396d80b>:1(get_difficulty_threshold)\n",
" 1 0.000 0.000 0.000 0.000 codecs.py:260(__init__)\n",
" 1 0.000 0.000 0.000 0.000 __init__.py:418(__init__)\n",
" 1 0.000 0.000 0.000 0.000 __init__.py:193(_checkLevel)\n",
" 1 0.000 0.000 0.000 0.000 __init__.py:1675(getEffectiveLevel)\n",
" 1 0.000 0.000 0.000 0.000 pathlib.py:627(__len__)\n",
" 3 0.000 0.000 0.000 0.000 {method 'append' of 'collections.deque' objects}\n",
" 1 0.000 0.000 0.000 0.000 pathlib.py:102(join_parsed_parts)\n",
" 3 0.000 0.000 0.000 0.000 threading.py:529(is_set)\n",
" 1 0.000 0.000 0.000 0.000 __init__.py:1276(disable)\n",
" 2 0.000 0.000 0.000 0.000 {method 'items' of 'dict' objects}\n",
" 1 0.000 0.000 0.000 0.000 {method 'split' of 'str' objects}\n",
" 1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}\n",
" 1 0.000 0.000 0.000 0.000 {method 'add' of 'set' objects}\n",
" 2 0.000 0.000 0.000 0.000 {built-in method posix.fspath}\n",
" 1 0.000 0.000 0.000 0.000 __init__.py:957(setFormatter)\n",
" 2 0.000 0.000 0.000 0.000 {method 'reverse' of 'list' objects}\n",
" 1 0.000 0.000 0.000 0.000 {method 'join' of 'str' objects}"
]
}
],
"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": 5,
"source": [
"TYPE_EMPTY = -1\n",
"TYPE_NEIGHBOR = -2\n",
"TYPE_BLOCKED = -3\n",
"\n",
"\n",
"class GridCreationWord(object):\n",
" def __init__(self, y: int, x: int, length: int, is_vertical: bool, id: int) -> None:\n",
" self.y = y\n",
" self.x = x\n",
" self.length = length\n",
" self.is_vertical = is_vertical\n",
" self.id = id\n",
"\n",
" self.word_key = None\n",
" self.connected_words = []\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 write(self, word: str, letter_grid: np.ndarray, x_grid: np.ndarray, y_grid: np.ndarray):\n",
" letters = list(word)\n",
" if self.is_vertical:\n",
"\n",
" xmin = max(self.x - 1, 0)\n",
" xmax = min(self.x + 2, letter_grid.shape[1])\n",
" ymin = self.y\n",
" ymax = self.y + self.length\n",
"\n",
" letter_grid[ymin:ymax, self.x] = letters\n",
"\n",
" conflicts = np.argwhere(\n",
" x_grid[ymin:ymax, self.x] == TYPE_NEIGHBOR\n",
" )\n",
" if len(conflicts) > 0:\n",
" corrected_conflicts = np.zeros(\n",
" shape=(len(conflicts), 2), dtype=np.int)\n",
" corrected_conflicts[:, 0] = ymin + conflicts.flatten()\n",
" corrected_conflicts[:, 1] = self.x\n",
" conflicts = corrected_conflicts\n",
"\n",
" x_neighbors = x_grid[ymin:ymax, xmin:xmax]\n",
" x_neighbors[x_neighbors == TYPE_EMPTY] = TYPE_NEIGHBOR\n",
" x_grid[ymin:ymax, xmin:xmax] = x_neighbors\n",
"\n",
" x_grid[ymin:ymax, self.x] = self.id\n",
"\n",
" fields_to_block = y_grid[ymin:ymax, self.x]\n",
" fields_to_block[fields_to_block < 0] = TYPE_BLOCKED\n",
" y_grid[ymin:ymax, self.x] = fields_to_block\n",
"\n",
" if ymin > 0:\n",
" x_grid[ymin - 1, self.x] = TYPE_BLOCKED\n",
" y_grid[ymin - 1, self.x] = TYPE_BLOCKED\n",
"\n",
" if ymax < letter_grid.shape[0]:\n",
"\n",
" x_grid[ymax, self.x] = TYPE_BLOCKED\n",
" y_grid[ymax, self.x] = TYPE_BLOCKED\n",
"\n",
" else:\n",
"\n",
" xmin = self.x\n",
" xmax = self.x + self.length\n",
" ymin = max(self.y - 1, 0)\n",
" ymax = min(self.y + 2, letter_grid.shape[0])\n",
"\n",
" letter_grid[self.y, xmin:xmax] = letters\n",
"\n",
" conflicts = np.argwhere(\n",
" y_grid[self.y, xmin:xmax] == TYPE_NEIGHBOR,\n",
" )\n",
" if len(conflicts) > 0:\n",
" corrected_conflicts = np.zeros(\n",
" shape=(len(conflicts), 2), dtype=np.int)\n",
" corrected_conflicts[:, 1] = xmin + conflicts.flatten()\n",
" corrected_conflicts[:, 0] = self.y\n",
" conflicts = corrected_conflicts\n",
"\n",
" y_neighbors = y_grid[ymin:ymax, xmin:xmax]\n",
" y_neighbors[y_neighbors == TYPE_EMPTY] = TYPE_NEIGHBOR\n",
" y_grid[ymin:ymax, xmin:xmax] = y_neighbors\n",
"\n",
" fields_to_block = x_grid[self.y, xmin:xmax]\n",
" fields_to_block[fields_to_block < 0] = TYPE_BLOCKED\n",
" x_grid[self.y, xmin:xmax] = fields_to_block\n",
"\n",
" y_grid[self.y, xmin:xmax] = self.id\n",
"\n",
" if xmin > 0:\n",
" x_grid[self.y, xmin - 1] = TYPE_BLOCKED\n",
" y_grid[self.y, xmin - 1] = TYPE_BLOCKED\n",
"\n",
" if xmax < letter_grid.shape[1]:\n",
"\n",
" x_grid[self.y, xmax] = TYPE_BLOCKED\n",
" y_grid[self.y, xmax] = TYPE_BLOCKED\n",
"\n",
" return conflicts\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",
" def get_connected_words(self):\n",
" return self.connected_words\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",
"\n",
"class GridCreationState(object):\n",
" def __init__(self, h: int, w: int, db, inverted_db, old_state=None) -> None:\n",
" if old_state is not None:\n",
" self.h = h\n",
" self.w = w\n",
" self.db = db\n",
" self.inverted_db = inverted_db\n",
" self.x_grid = old_state.x_grid.copy()\n",
" self.y_grid = old_state.y_grid.copy()\n",
" self.letter_grid = old_state.letter_grid.copy()\n",
" self.placed_words = old_state.placed_words.copy()\n",
" self.used_word_keys = old_state.used_word_keys.copy()\n",
"\n",
" return\n",
"\n",
" self.h = h\n",
" self.w = w\n",
" self.x_grid = np.full(shape=(h, w), dtype=np.int,\n",
" fill_value=TYPE_EMPTY)\n",
" self.y_grid = np.full(shape=(h, w), dtype=np.int,\n",
" fill_value=TYPE_EMPTY)\n",
"\n",
" self.letter_grid = np.full(\n",
" shape=(h, w), dtype=np.unicode, fill_value=' ')\n",
"\n",
" self.placed_words = []\n",
" self.used_word_keys = set()\n",
"\n",
" self.db = db\n",
" self.inverted_db = inverted_db\n",
"\n",
" def write_word(self, word_key: str, y: int, x: int, is_vertical: bool):\n",
" id = len(self.placed_words)\n",
"\n",
" word_raw = self.db[word_key]['word']\n",
" word_normalized = normalize_word(word_raw)\n",
"\n",
" grid_word = GridCreationWord(y=y,\n",
" x=x,\n",
" length=len(word_normalized),\n",
" is_vertical=is_vertical, id=id)\n",
"\n",
" grid_word.set_word_key(word_key=word_key)\n",
"\n",
" conflicts = grid_word.write(word=word_normalized,\n",
" letter_grid=self.letter_grid,\n",
" x_grid=self.x_grid,\n",
" y_grid=self.y_grid)\n",
"\n",
" self.placed_words.append(grid_word)\n",
" self.used_word_keys.add(word_key)\n",
"\n",
" return conflicts\n",
"\n",
" def copy(self):\n",
" return GridCreationState(self.h, self.w, self.db, self.inverted_db, self)\n",
"\n",
" def get_density(self):\n",
"\n",
" blocked_fields_x = np.logical_or(\n",
" self.x_grid >= 0, self.x_grid == TYPE_BLOCKED)\n",
" blocked_fields_y = np.logical_or(\n",
" self.y_grid >= 0, self.y_grid == TYPE_BLOCKED)\n",
"\n",
" blocked_fields = np.logical_or(blocked_fields_x, blocked_fields_y)\n",
"\n",
" return np.sum(blocked_fields) / (self.w * self.h)\n",
"\n",
" def get_letters(self, y: int, x: int, length: int, is_vertical: bool):\n",
" if is_vertical:\n",
" return self.letter_grid[y:y+length, x].flatten()\n",
" return self.letter_grid[y, x:x+length].flatten()\n",
"\n",
" def get_max_extents(self, y: int, x: int, is_vertical: bool):\n",
" # check min max offsets\n",
" if is_vertical:\n",
" min_coord = y - 1\n",
" if min_coord < 0 or self.y_grid[min_coord, x] == TYPE_BLOCKED:\n",
" min_coord = y\n",
" else:\n",
" while min_coord > 0 and self.y_grid[min_coord - 1, x] != TYPE_BLOCKED:\n",
" min_coord -= 1\n",
" max_coord = y + 1\n",
" while max_coord < self.h and self.y_grid[max_coord, x] != TYPE_BLOCKED:\n",
" max_coord += 1\n",
"\n",
" return min_coord, max_coord\n",
" else:\n",
" min_coord = x - 1\n",
" if min_coord < 0 or self.x_grid[y, min_coord] == TYPE_BLOCKED:\n",
" min_coord = x\n",
" else:\n",
" while min_coord > 0 and self.x_grid[y, min_coord - 1] != TYPE_BLOCKED:\n",
" min_coord -= 1\n",
" max_coord = x + 1\n",
" while max_coord < self.w and self.x_grid[y, max_coord] != TYPE_BLOCKED:\n",
" max_coord += 1\n",
" return min_coord, max_coord\n",
"\n",
" def expand_coordinates(self, y: int, x: int, length: int, is_vertical: bool):\n",
" if is_vertical:\n",
" min_coord = y\n",
" max_coord = y + length\n",
" while min_coord > 0 and self.y_grid[min_coord - 1, x] >= 0:\n",
" min_coord -= 1\n",
" while max_coord < self.h and self.y_grid[max_coord, x] >= 0:\n",
" max_coord += 1\n",
"\n",
" return min_coord, max_coord\n",
" else:\n",
" min_coord = x\n",
" max_coord = x + length\n",
" while min_coord > 0 and self.x_grid[y, min_coord - 1] >= 0:\n",
" min_coord -= 1\n",
" while max_coord < self.w and self.x_grid[y, max_coord] >= 0:\n",
" max_coord += 1\n",
"\n",
" return min_coord, max_coord\n",
"\n",
" def place_random_word(self, min_length: int = 4, max_length: int = 15):\n",
" # first, find a random intersection\n",
" letter_locations = np.argwhere(self.letter_grid != ' ')\n",
" if len(letter_locations) == 0:\n",
" # if nothing is placed so far, just choose a random place\n",
" length = np.random.randint(min_length, max_length)\n",
" length = min(length, max_length)\n",
" y = np.random.randint(0, self.h - 1)\n",
" x = np.random.randint(0, self.w - length)\n",
" is_vertical = False\n",
" word_template = \" \" * length\n",
" else:\n",
" # possible candidates are fields where words are placed\n",
" # only horizontally or only vertically\n",
" candidates = np.argwhere(\n",
" np.logical_xor(self.x_grid >= 0, self.y_grid >= 0)\n",
" )\n",
"\n",
" if len(candidates) == 0:\n",
" #print(\"field is full\")\n",
" return None\n",
"\n",
" candidate_index = random.randint(0, len(candidates) - 1)\n",
" y, x = candidates[candidate_index]\n",
"\n",
" is_vertical = self.x_grid[y, x] == TYPE_BLOCKED\n",
"\n",
" min_coord, max_coord = self.get_max_extents(y, x, is_vertical)\n",
"\n",
" extent = max_coord - min_coord\n",
"\n",
" if extent < min_length:\n",
" #print(\"not enough space to place a word\")\n",
" return None\n",
"\n",
" min_length = min(extent, min_length)\n",
" max_length = min(extent, max_length)\n",
"\n",
" length = random.randint(min_length, max_length)\n",
" offset = random.randint(0, extent - length)\n",
"\n",
" min_coord += offset\n",
"\n",
" if is_vertical:\n",
" if min_coord + length <= y:\n",
" min_coord = y - length + 1\n",
" max_coord = min_coord + length\n",
" if min_coord > y:\n",
" min_coord = y\n",
" max_coord = min_coord + length\n",
"\n",
" min_coord, max_coord = self.expand_coordinates(y=min_coord,\n",
" x=x,\n",
" length=length,\n",
" is_vertical=is_vertical)\n",
"\n",
" length = max_coord - min_coord\n",
"\n",
" letters = self.get_letters(min_coord, x, length, is_vertical)\n",
"\n",
" y = min_coord\n",
"\n",
" else:\n",
"\n",
" if min_coord + length <= x:\n",
" min_coord = x - length + 1\n",
" max_coord = min_coord + length\n",
" if min_coord > x:\n",
" min_coord = x\n",
" max_coord = min_coord + length\n",
"\n",
" min_coord, max_coord = self.expand_coordinates(y=y,\n",
" x=min_coord,\n",
" length=length,\n",
" is_vertical=is_vertical)\n",
"\n",
" length = max_coord - min_coord\n",
"\n",
" letters = self.get_letters(y, min_coord, length, is_vertical)\n",
"\n",
" x = min_coord\n",
"\n",
" word_template = \"\".join(letters)\n",
"\n",
" word_candidates = list(find_suitable_words(\n",
" word_template, self.db, self.inverted_db))\n",
"\n",
" if len(word_candidates) == 0:\n",
" #print(\"no word available for given combination\")\n",
" return None\n",
"\n",
" word_candidate_index = random.randint(0, len(word_candidates) - 1)\n",
" word_key = word_candidates[word_candidate_index]\n",
"\n",
" if word_key in self.used_word_keys:\n",
" return None\n",
"\n",
" return self.write_word(word_key, y, x, is_vertical)\n",
"\n",
" def solve_conflicts(self, conflicts, n_retries=3, max_depth=5, depth=0):\n",
" if len(conflicts) == 0:\n",
" return self\n",
" # else:\n",
" # return None\n",
"\n",
" if depth > max_depth:\n",
" return None\n",
"\n",
" new_conflictes = []\n",
"\n",
" for conflict in conflicts:\n",
"\n",
" y, x = conflict\n",
"\n",
" if self.x_grid[y, x] >= 0 and self.y_grid[y, x] >= 0:\n",
" # conflict already solved\n",
" continue\n",
"\n",
" # find out whether the conflict is vertical or horizontal\n",
" is_vertical = self.y_grid[y, x] == TYPE_NEIGHBOR\n",
"\n",
" # calculate the minimum and maximum extend to fix the conflict\n",
" if is_vertical:\n",
" max_ymin = y\n",
" while max_ymin > 0 and self.y_grid[max_ymin-1, x] >= 0:\n",
" max_ymin -= 1\n",
" min_ymax = y + 1\n",
" while min_ymax < self.h and self.y_grid[min_ymax, x] >= 0:\n",
" min_ymax += 1\n",
"\n",
" min_ymin = max_ymin\n",
" while min_ymin > 0 and self.y_grid[min_ymin - 1, x] != TYPE_BLOCKED:\n",
" min_ymin -= 1\n",
" max_ymax = min_ymax\n",
" while max_ymax < self.h and self.y_grid[max_ymax, x] != TYPE_BLOCKED:\n",
" max_ymax += 1\n",
"\n",
" min_coord_min = min_ymin\n",
" max_coord_min = max_ymin\n",
" min_coord_max = min_ymax\n",
" max_coord_max = max_ymax\n",
"\n",
" else:\n",
" max_xmin = x\n",
" while max_xmin > 0 and self.x_grid[y, max_xmin - 1] >= 0:\n",
" max_xmin -= 1\n",
" min_xmax = x + 1\n",
" while min_xmax < self.w and self.x_grid[y, min_xmax] >= 0:\n",
" min_xmax += 1\n",
"\n",
" min_xmin = max_xmin\n",
" while min_xmin > 0 and self.x_grid[y, min_xmin - 1] != TYPE_BLOCKED:\n",
" min_xmin -= 1\n",
" max_xmax = min_xmax\n",
" while max_xmax < self.w and self.x_grid[y, max_xmax] != TYPE_BLOCKED:\n",
" max_xmax += 1\n",
"\n",
" min_coord_min = min_xmin\n",
" max_coord_min = max_xmin\n",
" min_coord_max = min_xmax\n",
" max_coord_max = max_xmax\n",
"\n",
" n_options = max_coord_max - min_coord_max + max_coord_min - min_coord_min\n",
"\n",
" solved = False\n",
"\n",
" for _ in range(min(n_options, n_retries)):\n",
" coord_min = random.randint(min_coord_min, max_coord_min)\n",
" coord_max = random.randint(min_coord_max, max_coord_max)\n",
" length = coord_max - coord_min\n",
" if length < 2:\n",
" continue\n",
"\n",
" if is_vertical:\n",
"\n",
" coord_min, coord_max = self.expand_coordinates(y=coord_min,\n",
" x=x,\n",
" length=length,\n",
" is_vertical=is_vertical)\n",
"\n",
" length = coord_max - coord_min\n",
"\n",
" y = coord_min\n",
"\n",
" else:\n",
"\n",
" coord_min, coord_max = self.expand_coordinates(y=y,\n",
" x=coord_min,\n",
" length=length,\n",
" is_vertical=is_vertical)\n",
"\n",
" length = coord_max - coord_min\n",
"\n",
" x = coord_min\n",
"\n",
" letters = self.get_letters(y, x, length, is_vertical)\n",
"\n",
" word_template = \"\".join(letters)\n",
"\n",
" candidates = list(find_suitable_words(\n",
" word_template, self.db, self.inverted_db))\n",
"\n",
" if len(candidates) == 0:\n",
" continue\n",
"\n",
" candidate_index = random.randint(0, len(candidates) - 1)\n",
" word_key = candidates[candidate_index]\n",
"\n",
" if word_key in self.used_word_keys:\n",
" continue\n",
"\n",
" word_conflicts = self.write_word(word_key, y, x, is_vertical)\n",
" if len(word_conflicts) > 0:\n",
" new_conflictes.append(word_conflicts)\n",
"\n",
" solved = True\n",
" break\n",
"\n",
" if not solved:\n",
" return None\n",
"\n",
" if len(new_conflictes) == 0:\n",
" return self\n",
"\n",
" new_conflictes = np.concatenate(new_conflictes)\n",
" for _ in range(n_retries):\n",
" next_state = self.copy()\n",
" solved_state = next_state.solve_conflicts(\n",
" new_conflictes, n_retries, max_depth, depth + 1)\n",
" if solved_state is not None:\n",
" return solved_state\n",
" return None\n",
"\n",
" def fill_grid(self, target_density: float = 0.6, inner_retries: int = 5, conflict_retries: int = 10, conflict_solver_depth=5, min_length: int = 4, max_length: int = 10, max_iterations: int = 1000):\n",
" i = 0\n",
" state = self.copy()\n",
" while i < max_iterations and state.get_density() < target_density:\n",
" i += 1\n",
" new_state = state.copy()\n",
" conflicts = new_state.place_random_word(min_length, max_length)\n",
" if conflicts is None:\n",
" continue\n",
" if len(conflicts) == 0:\n",
" state = new_state\n",
"\n",
" if len(conflicts) > 0:\n",
" \n",
" solved_state = new_state.solve_conflicts(\n",
" conflicts, inner_retries, conflict_solver_depth)\n",
" if solved_state is not None:\n",
" state = solved_state\n",
" \n",
"\n",
" print(\"finished after\", i,\n",
" \"iterations, with a density of\", state.get_density())\n",
" return state\n"
],
"outputs": [],
"metadata": {}
},
{
"cell_type": "code",
"execution_count": 6,
"source": [
"\" \" * 4"
],
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"' '"
]
},
"metadata": {},
"execution_count": 6
}
],
"metadata": {}
},
{
"cell_type": "code",
"execution_count": 7,
"source": [
"%%prun\n",
"\n",
"difficulty = 0\n",
"size = 20\n",
"\n",
"base_grid = GridCreationState(size,size, db = get_database(\"de\", difficulty=difficulty), inverted_db= get_inverted_database(\"de\", difficulty=difficulty))\n",
"\n",
"#word_key = \"hallo0\"\n",
"#\n",
"#base_grid.write_word(word_key=word_key, y=3, x=3, is_vertical=True)\n",
"#\n",
"#word_key = \"hai\"\n",
"#\n",
"#base_grid.write_word(word_key=word_key, y=3, x=3, is_vertical=False)\n",
"\n",
"final_state = base_grid\n",
"\n",
"#for _ in range(3):\n",
"#while base_grid.get_density() < 0.8:\n",
"# final_state = final_state.copy()\n",
"# conflict = final_state.place_random_word(min_length=3, max_length=4)\n",
"\n",
"final_state = base_grid.fill_grid(target_density=0.8, inner_retries=5, conflict_solver_depth=20, min_length=3, max_iterations=max(size * 75, 1000))\n",
"\n",
"#print(final_state.letter_grid)\n",
"#for word in final_state.placed_words:\n",
"# print(word.word_key)\n"
],
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"finished after 1500 iterations, with a density of 0.765\n",
" "
]
},
{
"output_type": "stream",
"name": "stdout",
"text": [
" 209587 function calls (198419 primitive calls) in 0.692 seconds\n",
"\n",
" Ordered by: internal time\n",
"\n",
" ncalls tottime percall cumtime percall filename:lineno(function)\n",
" 1500 0.094 0.000 0.442 0.000 <ipython-input-5-0c097f51c764>:259(place_random_word)\n",
" 2085 0.093 0.000 0.104 0.000 <ipython-input-2-3db35396d80b>:107(find_suitable_words)\n",
" 682 0.048 0.000 0.082 0.000 <ipython-input-5-0c097f51c764>:22(write)\n",
" 659/534 0.038 0.000 0.128 0.000 <ipython-input-5-0c097f51c764>:358(solve_conflicts)\n",
" 3681 0.032 0.000 0.032 0.000 {built-in method numpy.array}\n",
" 1501 0.029 0.000 0.073 0.000 <ipython-input-5-0c097f51c764>:197(get_density)\n",
" 3681 0.028 0.000 0.028 0.000 {method 'nonzero' of 'numpy.ndarray' objects}\n",
" 1499 0.024 0.000 0.024 0.000 <ipython-input-5-0c097f51c764>:213(get_max_extents)\n",
" 1501 0.021 0.000 0.021 0.000 {method 'reduce' of 'numpy.ufunc' objects}\n",
" 1 0.020 0.020 0.692 0.692 <ipython-input-5-0c097f51c764>:492(fill_grid)\n",
" 2084 0.019 0.000 0.019 0.000 {method 'join' of 'str' objects}\n",
"16253/5210 0.016 0.000 0.190 0.000 {built-in method numpy.core._multiarray_umath.implement_array_function}\n",
" 3681 0.016 0.000 0.055 0.000 fromnumeric.py:39(_wrapit)\n",
" 3681 0.014 0.000 0.146 0.000 numeric.py:537(argwhere)\n",
" 6361 0.013 0.000 0.028 0.000 random.py:291(randrange)\n",
" 4878 0.013 0.000 0.013 0.000 {method 'copy' of 'numpy.ndarray' objects}\n",
" 7362 0.013 0.000 0.098 0.000 fromnumeric.py:52(_wrapfunc)\n",
" 6361 0.010 0.000 0.015 0.000 random.py:238(_randbelow_with_getrandbits)\n",
" 682 0.009 0.000 0.097 0.000 <ipython-input-5-0c097f51c764>:171(write_word)\n",
" 2084 0.009 0.000 0.009 0.000 <ipython-input-5-0c097f51c764>:239(expand_coordinates)\n",
" 1627 0.009 0.000 0.027 0.000 <ipython-input-5-0c097f51c764>:141(__init__)\n",
" 6361 0.008 0.000 0.036 0.000 random.py:335(randint)\n",
" 2010 0.008 0.000 0.008 0.000 {method 'intersection' of 'set' objects}\n",
" 2694 0.008 0.000 0.008 0.000 {method 'flatten' of 'numpy.ndarray' objects}\n",
" 1501 0.007 0.000 0.030 0.000 fromnumeric.py:70(_wrapreduction)\n",
" 2084 0.006 0.000 0.011 0.000 <ipython-input-5-0c097f51c764>:208(get_letters)\n",
" 1501 0.006 0.000 0.037 0.000 fromnumeric.py:2105(sum)\n",
" 3681 0.006 0.000 0.157 0.000 <__array_function__ internals>:2(argwhere)\n",
" 3681 0.004 0.000 0.010 0.000 <__array_function__ internals>:2(ndim)\n",
" 3870 0.004 0.000 0.004 0.000 {built-in method builtins.min}\n",
" 3681 0.004 0.000 0.076 0.000 <__array_function__ internals>:2(transpose)\n",
" 11043 0.004 0.000 0.004 0.000 {built-in method builtins.getattr}\n",
" 15988 0.004 0.000 0.004 0.000 {built-in method builtins.len}\n",
" 3681 0.004 0.000 0.045 0.000 <__array_function__ internals>:2(nonzero)\n",
" 1626 0.004 0.000 0.030 0.000 <ipython-input-5-0c097f51c764>:194(copy)\n",
" 1626 0.004 0.000 0.004 0.000 {method 'copy' of 'set' objects}\n",
" 3681 0.003 0.000 0.038 0.000 fromnumeric.py:1816(nonzero)\n",
" 1501 0.003 0.000 0.044 0.000 <__array_function__ internals>:2(sum)\n",
" 3681 0.003 0.000 0.067 0.000 fromnumeric.py:601(transpose)\n",
" 3681 0.003 0.000 0.003 0.000 {method 'transpose' of 'numpy.ndarray' objects}\n",
" 3681 0.003 0.000 0.035 0.000 _asarray.py:14(asarray)\n",
" 11364 0.003 0.000 0.003 0.000 {method 'getrandbits' of '_random.Random' objects}\n",
" 3681 0.002 0.000 0.002 0.000 fromnumeric.py:3075(ndim)\n",
" 7162 0.002 0.000 0.002 0.000 {method 'append' of 'list' objects}\n",
" 610 0.002 0.000 0.002 0.000 {built-in method numpy.zeros}\n",
" 1501 0.002 0.000 0.002 0.000 fromnumeric.py:71(<dictcomp>)\n",
" 6361 0.002 0.000 0.002 0.000 {method 'bit_length' of 'int' objects}\n",
" 682 0.002 0.000 0.002 0.000 {method 'translate' of 'str' objects}\n",
" 3681 0.001 0.000 0.001 0.000 numeric.py:533(_argwhere_dispatcher)\n",
" 1626 0.001 0.000 0.001 0.000 {method 'copy' of 'list' objects}\n",
" 682 0.001 0.000 0.001 0.000 <ipython-input-5-0c097f51c764>:7(__init__)\n",
" 683 0.001 0.000 0.001 0.000 {built-in method builtins.max}\n",
" 682 0.001 0.000 0.003 0.000 <ipython-input-2-3db35396d80b>:103(normalize_word)\n",
" 3681 0.001 0.000 0.001 0.000 fromnumeric.py:3071(_ndim_dispatcher)\n",
" 1509 0.001 0.000 0.001 0.000 {built-in method builtins.isinstance}\n",
" 3681 0.001 0.000 0.001 0.000 fromnumeric.py:597(_transpose_dispatcher)\n",
" 3681 0.001 0.000 0.001 0.000 fromnumeric.py:1812(_nonzero_dispatcher)\n",
" 1501 0.001 0.000 0.001 0.000 fromnumeric.py:2100(_sum_dispatcher)\n",
" 1501 0.001 0.000 0.001 0.000 {method 'items' of 'dict' objects}\n",
" 682 0.000 0.000 0.000 0.000 <ipython-input-5-0c097f51c764>:102(set_word_key)\n",
" 682 0.000 0.000 0.000 0.000 {method 'lower' of 'str' objects}\n",
" 682 0.000 0.000 0.000 0.000 {method 'add' of 'set' objects}\n",
" 1 0.000 0.000 0.692 0.692 {built-in method builtins.exec}\n",
" 25 0.000 0.000 0.000 0.000 <__array_function__ internals>:2(concatenate)\n",
" 9 0.000 0.000 0.000 0.000 socket.py:438(send)\n",
" 3 0.000 0.000 0.000 0.000 {method 'randint' of 'numpy.random.mtrand.RandomState' objects}\n",
" 9 0.000 0.000 0.000 0.000 iostream.py:195(schedule)\n",
" 8 0.000 0.000 0.000 0.000 iostream.py:384(write)\n",
" 3 0.000 0.000 0.000 0.000 {built-in method numpy.empty}\n",
" 1 0.000 0.000 0.692 0.692 <string>:1(<module>)\n",
" 1 0.000 0.000 0.000 0.000 {built-in method builtins.print}\n",
" 9 0.000 0.000 0.000 0.000 threading.py:1093(is_alive)\n",
" 3 0.000 0.000 0.000 0.000 numeric.py:268(full)\n",
" 25 0.000 0.000 0.000 0.000 multiarray.py:143(concatenate)\n",
" 8 0.000 0.000 0.000 0.000 iostream.py:308(_is_master_process)\n",
" 9 0.000 0.000 0.000 0.000 threading.py:1039(_wait_for_tstate_lock)\n",
" 3 0.000 0.000 0.000 0.000 <__array_function__ internals>:2(copyto)\n",
" 9 0.000 0.000 0.000 0.000 {method 'acquire' of '_thread.lock' objects}\n",
" 9 0.000 0.000 0.000 0.000 iostream.py:91(_event_pipe)\n",
" 8 0.000 0.000 0.000 0.000 {built-in method posix.getpid}\n",
" 8 0.000 0.000 0.000 0.000 iostream.py:321(_schedule_flush)\n",
" 1 0.000 0.000 0.000 0.000 <ipython-input-2-3db35396d80b>:19(get_database)\n",
" 9 0.000 0.000 0.000 0.000 threading.py:529(is_set)\n",
" 1 0.000 0.000 0.000 0.000 <ipython-input-2-3db35396d80b>:91(get_inverted_database)\n",
" 9 0.000 0.000 0.000 0.000 {method 'append' of 'collections.deque' objects}\n",
" 3 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": 8,
"source": [
"#for line in base_grid.letter_grid:\n",
"# print(\"\".join(line))\n",
"\n",
"print(final_state.letter_grid)\n",
"\n",
"plt.imshow(final_state.x_grid, vmax= 0)\n",
"plt.colorbar()\n",
"plt.show()\n",
"plt.imshow(final_state.y_grid, vmax= 0)\n",
"plt.colorbar()\n",
"plt.show()\n",
"plt.imshow(final_state.letter_grid != ' ')\n",
"plt.show()\n",
"\n",
"print(sorted([word.word_key for word in final_state.placed_words]))"
],
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"[[' ' ' ' 's' 't' 'r' 'i' 'c' 'h' ' ' 'l' ' ' ' ' ' ' ' ' ' ' 'v' ' ' 'i'\n",
" ' ' ' ']\n",
" [' ' ' ' ' ' 'a' ' ' ' ' ' ' 'e' ' ' 'o' 'l' ' ' 'l' 'o' 'g' 'o' ' ' 'd'\n",
" 'i' 'e']\n",
" [' ' ' ' ' ' 'b' 'a' 's' 'i' 'l' 'i' 'k' 'a' ' ' ' ' ' ' 'e' 'r' 'g' 'o'\n",
" ' ' ' ']\n",
" [' ' ' ' ' ' 'u' ' ' ' ' ' ' 'l' ' ' ' ' 'm' 'a' 'k' 'e' 'l' ' ' 'o' ' '\n",
" ' ' 's']\n",
" [' ' 'd' 'u' 'r' ' ' 'l' 'u' 's' 'a' 'k' 'a' ' ' 'u' ' ' ' ' 'u' 'n' 'd'\n",
" ' ' 'k']\n",
" [' ' ' ' ' ' 'e' ' ' 'o' ' ' 'e' ' ' ' ' ' ' ' ' 'e' ' ' ' ' 'r' ' ' 'u'\n",
" 's' 'a']\n",
" ['n' 'a' 'u' 't' 'i' 's' 'c' 'h' ' ' ' ' 'e' 'i' 'n' 'k' 'l' 'a' 'n' 'g'\n",
" ' ' 'l']\n",
" ['a' ' ' ' ' 't' ' ' ' ' ' ' 'e' ' ' ' ' 'r' ' ' 'd' ' ' ' ' 'n' ' ' 'o'\n",
" ' ' 'd']\n",
" ['i' ' ' ' ' ' ' 'b' ' ' ' ' 'r' ' ' 'f' 'r' 'e' 'i' ' ' ' ' ' ' ' ' 'n'\n",
" 'i' 'e']\n",
" ['v' 'i' 'd' 'e' 'o' ' ' 'v' ' ' ' ' ' ' 'a' ' ' 'g' 'e' 'h' 'w' 'e' 'g'\n",
" ' ' ' ']\n",
" [' ' ' ' ' ' 't' 'e' 'r' 'e' 'b' 'i' 'n' 't' 'h' 'e' ' ' ' ' 'e' ' ' ' '\n",
" ' ' ' ']\n",
" [' ' 'z' 'e' 'h' ' ' ' ' 'r' ' ' 'n' ' ' 'e' ' ' 'n' 'a' 'd' 'i' 'r' ' '\n",
" ' ' ' ']\n",
" [' ' ' ' ' ' 'o' 's' 'e' 'l' ' ' 'd' 'o' 'n' ' ' ' ' 'g' ' ' 's' ' ' 'p'\n",
" ' ' 'b']\n",
" ['e' 'g' 'a' 'l' ' ' ' ' 'i' ' ' 'e' ' ' ' ' ' ' ' ' 'a' ' ' 's' 'e' 'k'\n",
" 't' 'e']\n",
" [' ' 'm' ' ' 'o' 'a' 's' 'e' ' ' 'x' ' ' 'c' 'h' 'e' 'r' 'u' 'b' ' ' 'w'\n",
" ' ' 'n']\n",
" [' ' 'b' ' ' 'g' ' ' ' ' 'r' ' ' ' ' 'a' ' ' 'u' ' ' ' ' ' ' 'r' ' ' ' '\n",
" ' ' 'e']\n",
" [' ' 'h' 'a' 'i' ' ' ' ' 'e' ' ' 'i' 'r' 'g' 'e' 'n' 'd' 'w' 'o' ' ' 'm'\n",
" 'a' 'i']\n",
" [' ' ' ' 'h' 'e' 'u' 'e' 'r' ' ' ' ' 'i' ' ' 'f' ' ' 'a' ' ' 't' ' ' 'e'\n",
" ' ' 'd']\n",
" ['g' 'i' 'n' ' ' 'n' ' ' ' ' ' ' ' ' 'e' ' ' 't' ' ' 'n' ' ' ' ' ' ' 'h'\n",
" ' ' 'e']\n",
" [' ' ' ' ' ' ' ' 'o' 'p' 'a' ' ' ' ' ' ' 'v' 'e' 'r' 'k' 'n' 'a' 'l' 'l'\n",
" 'e' 'n']]\n"
]
},
{
"output_type": "display_data",
"data": {
"text/plain": [
"<Figure size 432x288 with 2 Axes>"
],
"image/svg+xml": "<?xml version=\"1.0\" encoding=\"utf-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<!-- Created with matplotlib (https://matplotlib.org/) -->\n<svg height=\"252.317344pt\" version=\"1.1\" viewBox=\"0 0 320.000437 252.317344\" width=\"320.000437pt\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n <metadata>\n <rdf:RDF xmlns:cc=\"http://creativecommons.org/ns#\" xmlns:dc=\"http://purl.org/dc/elements/1.1/\" xmlns:rdf=\"http://www.w3.org/1999/02/22-rdf-syntax-ns#\">\n <cc:Work>\n <dc:type rdf:resource=\"http://purl.org/dc/dcmitype/StillImage\"/>\n <dc:date>2021-08-31T12:13:54.263271</dc:date>\n <dc:format>image/svg+xml</dc:format>\n <dc:creator>\n <cc:Agent>\n <dc:title>Matplotlib v3.3.4, https://matplotlib.org/</dc:title>\n </cc:Agent>\n </dc:creator>\n </cc:Work>\n </rdf:RDF>\n </metadata>\n <defs>\n <style type=\"text/css\">*{stroke-linecap:butt;stroke-linejoin:round;}</style>\n </defs>\n <g id=\"figure_1\">\n <g id=\"patch_1\">\n <path d=\"M 0 252.317344 \nL 320.000437 252.317344 \nL 320.000437 0 \nL 0 0 \nz\n\" style=\"fill:none;\"/>\n </g>\n <g id=\"axes_1\">\n <g id=\"patch_2\">\n <path d=\"M 36.465625 228.439219 \nL 253.905625 228.439219 \nL 253.905625 10.999219 \nL 36.465625 10.999219 \nz\n\" style=\"fill:#ffffff;\"/>\n </g>\n <g clip-path=\"url(#peeeecc95cb)\">\n <image height=\"218\" id=\"image95d1d47900\" transform=\"scale(1 -1)translate(0 -218)\" width=\"218\" x=\"36.465625\" xlink:href=\"data:image/png;base64,\niVBORw0KGgoAAAANSUhEUgAAANoAAADaCAYAAADAHVzbAAAFPElEQVR4nO3dMW4VSRSG0WLUjkkgmZgFWLIIZgVIjlgFEjsg7HV4DQSOQF7BpF6AYyeQEBMwwWzg3hH3736jc+JSvfZ7/tTJVdWLt18//VoDXt4+TWy7Hp4fS+ve/Xk98vkdP768Ka89+vtaq/edTe074QzfwR/llcB/JjQIEBoECA0ChAYBQoMAoUGA0CBAaBAgNAjYLm30p+r7h7/Ka1/d/V1e2xmr+nn/urz24flzee3N/rG8dq3H8srOdzaxb+d3OPpZu/t6o0GA0CBAaBAgNAgQGgQIDQKEBgFCgwChQYDQIGC7tJOaqjrjPL1xsfozfP9QH8Gi9zvc7J1RqeN5o0GA0CBAaBAgNAgQGgQIDQKEBgFCgwChQYDQIKB1CtbEqFRX9cSsqdOMOjpjYGu370U9a3NfbzQIEBoECA0ChAYBQoMAoUGA0CBAaBAgNAgQGgRsU6NKncsFO6Ndvef9/aYuOJx6hqlL+HqngVX3fRzYc+pZ13IRIZyM0CBAaBAgNAgQGgQIDQKEBgFCgwChQYDQIGA7+gG6Rsaa9pnP711weF1/hnX8CVAjlzfu5S3HnnXqgkNvNAgQGgQIDQKEBgFCgwChQYDQIEBoECA0CNim7oM62hkOsJnat/ObdSZOznCn3NHcjwYXTGgQIDQIEBoECA0ChAYBQoMAoUGA0CBAaBCw/fjypry4c8/U0aZGac6w79ihP0N/29H3o51hX280CBAaBAgNAoQGAUKDAKFBgNAgQGgQIDQIEBoEbC9vn45+hhGXNqJzhhOoOqNdHeXRrn1gz7XWu7vr8tqrL9/q+zbG27zRIEBoECA0CBAaBAgNAoQGAUKDAKFBgNAgQGgQsHUWd07Mmhrtqo4JtU7s2utLz3AK1hkuhJy54PBxYM/md9vQ6cEbDQKEBgFCgwChQYDQIEBoECA0CBAaBAgNAoQGAVvvUru5B/k/mhlTWmvqFKwpR5+CdYb/cW80CBAaBAgNAoQGAUKDAKFBgNAgQGgQIDQIEBoEtE7B6owJXb3vXOhWf4bqOE3nWSc+/999r8trL+0UrI7qaVGXNuLX+V/wRoMAoUGA0CBAaBAgNAgQGgQIDQKEBgFCgwChQUBrBKvj5/3r8tqH58/ltdWxplerPtI0dQJVb9+OqWcY2ve+tqzzf3Czf6x//gm+L280CBAaBAgNAoQGAUKDAKFBgNAgQGgQIDQIEBoEtEawWic1dey/f8uxy+f2+tIzfF9Tp2uN/G1Tn3+Cfb3RIEBoECA0CBAaBAgNAoQGAUKDAKFBgNAgQGgQsHUuy6teKLdW7xSsmVOKJvac23fq4sYz/G0Tn39pvNEgQGgQIDQIEBoECA0ChAYBQoMAoUGA0CBAaBDQOgXr5e1TY3Vj7V5fWj6laGLPyX3v6kvPcMJXx8Rv1vkOzsAbDQKEBgFCgwChQYDQIEBoECA0CBAaBAgNArbOgTsdRx/Oc2kH2IzdpTak87zVKY7OQVG96Zj6vlP/C95oECA0CBAaBAgNAoQGAUKDAKFBgNAgQGgQIDQIePH266dfExt3DvKZGqeZMPWsU4fNHP19rXVZB+lMfV/eaBAgNAgQGgQIDQKEBgFCgwChQYDQIEBoECA0CGjdj9Zx9MlSV++/lfecOrGLOWcYb+vwRoMAoUGA0CBAaBAgNAgQGgQIDQKEBgFCgwChQUBrBKtzstVajbV7fWn5Ary7+p5TzzqlM340ddFkR/VSyM6o1NEjfmv1xvy80SBAaBAgNAgQGgQIDQKEBgFCgwChQYDQIEBoEPAP4FRfl7PrBnsAAAAASUVORK5CYII=\" y=\"-10.439219\"/>\n </g>\n <g id=\"matplotlib.axis_1\">\n <g id=\"xtick_1\">\n <g id=\"line2d_1\">\n <defs>\n <path d=\"M 0 0 \nL 0 3.5 \n\" id=\"mfa2a981d92\" style=\"stroke:#000000;stroke-width:0.8;\"/>\n </defs>\n <g>\n <use style=\"stroke:#000000;stroke-width:0.8;\" x=\"41.901625\" xlink:href=\"#mfa2a981d92\" y=\"228.439219\"/>\n </g>\n </g>\n <g id=\"text_1\">\n <!-- 0 -->\n <g transform=\"translate(38.720375 243.037656)scale(0.1 -0.1)\">\n <defs>\n <path d=\"M 31.78125 66.40625 \nQ 24.171875 66.40
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAUAAAAD8CAYAAAAG730QAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuNCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8QVMy6AAAACXBIWXMAAAsTAAALEwEAmpwYAAAZxUlEQVR4nO3dfYwd1Znn8e8vNhjhJRDGwWAgCZp4kLwReJOWGYR2FpY3YzGBZJIsntWEvKwcUNDsSDvSkLWUtLRaCSnKjsKAID2JBZHCS/bFYA09mBeNxCCFBYMcYvPqIM9ijDCGickME6C7n/3jVqOb5t6+p6pu3VvV9ftIpb5Vde6pU93moapOnfMoIjAza6MPjbsBZmbj4gBoZq3lAGhmreUAaGat5QBoZq3lAGhmreUAaGZjJ2mjpOcl7ZN0fY/9knRjtv9pSZ8exnEdAM1srCQtA24GLgPWAZslrVtQ7DJgbbZsAW4ZxrEdAM1s3DYA+yLipYh4F7gLuGJBmSuAH0fHY8AJkk4pe+DlZSuowvLjj40Vq49PKrvsxXcqacPvnfV2ctkXnj62kjakqqqtVdU7u3ZFctmqpP67yfM7eObgR5PLrlvzeiX16iMzSeXeee0IM0feVnLFPVx6wcp4483ZpLJPPv3OXuA3XZumImIq+3wq8HLXvgPAOQuq6FXmVODVPG1eqJYBcMXq4/nXN34lqezxm/ZV0oadO3cnl710zfpK2pCqqrZWVe+RGz+ZXLYqqf9u8vwOPjN5bXLZxyfT7+Dy1HvUlWmBde+f3pZcZz9vvDnL4zs/llR22Skv/iYiJvrs7hWIF47RTSmTWy0DoJnVXwBzzA2jqgPA6V3rpwEHC5TJrdQzwHH13JjZ+AXBezGbtAzwBLBW0hmSjgauAnYsKLMD+HIWU34fOBIRpW5/ocQVYFfPzcV0ovMTknZExDNdxbp7bs6h03Oz8N7ezBpqGFeAETEj6TpgJ7AM2BYReyVdk+2/FZgGNgH7gLeBr5Y+MOVugd/vuQGQNN9z0x0A3++5AR6TdIKkU4YRuc1svIJgdkjT6UXENJ0g173t1q7PAXxzKAfrUuYWuF+vTN4yAEjaImmXpF0zR9J73sxsfOaIpKWuygTAofbcRMRURExExMTy48f7WomZDRbALJG01FWZW+Cx9dyYWT3U+eouRZkrwLH13JjZ+AXwXkTSUleFrwDH2XNjZuMXNb+9TVHqRehx9dx0OzKdPqrgvXvShxTB7uSSh7ecm1Qu9S19qK6tVdl5ML0Nl66prh2p8rQ31aqpn6UXnqyo3qnBRQCWxRCGkAbMNjv+eSSImRXTGQnSbA6AZlaQmO35okdzOACaWSGdThAHQDNroc57gA6AZtZSc74CNLM28hWgmbVWIGYbnlXDAdDMCvMtsJm1UiDejWXjbkYpDoBmVkjnRWjfAjfG2IcqJQ5T6siR7GkyT71WlSqG19WdO0HMrJUixGz4CtDMWmrOV4Bm1kadTpBmh5Bmt97MxsadIGbWarN+D9DM2sgjQcys1eYa3gtcuPWSTpf0d5KelbRX0n/uUeZ8SUck7c6Wb5drrpnVRWcyhA8lLXVV5gpwBvgvEfGUpOOAJyU9GBHPLCj39xFxeYnjmFkNBeK9tg6Fy9Jbvpp9/rWkZ4FTgYUB0MyWoAj8IjSApE8A/wb4vz12nyvp53QSov95ROztU8cWYAvA0Sd9eBjN+oDU7G0du4deb56heONuK+TL3lbVMLB82ebWD/34eeqsqq15/mZPTt6SVG7DpW8n19mfRvIitKQTgbuBTwD7gS9FxD/2KLcf+DUwC8xExMSgukuHb0n/CvjfwJ9FxFsLdj8FfDwizgb+CrinXz0RMRURExExsfz4Y8s2y8wqFnSuAFOWkq4HHo6ItcDD2Xo/F0TE+pTgByUDoKSj6AS/n0TE/1m4PyLeioh/yj5PA0dJWlXmmGZWHyPqBLkCuD37fDtwZdkK55XpBRbwI+DZiPgffcqcnJVD0obseG8UPaaZ1Ucg5iJtKWl11ucw3/dwUt8mwQOSnsweqQ1U5hngecCfAL+QtDvb9l+Bj2UNvRX4AnCtpBngX4CrIqLhueTNDObTYiaHkFWSdnWtT0XE+xPESXoIOLnH97bmaNJ5EXFQ0knAg5Kei4hHFvtCmV7gR2HxJ6ARcRNwU9FjmFmd5UqMfnix53IRcVHfo0ivSTolIl6VdApwqE8dB7OfhyRtBzYAiwbAZvdhm9nYBJ2RIClLSTuAq7PPVwP3LiwgaWX2PjKSVgKXAHsGVewAaGaFzWZXgYOWkm4ALpb0InBxto6kNZKmszKrgUezV+4eB+6LiPsHVeyxwGZWSIRGMhY4It4ALuyx/SCwKfv8EnB23rodAM2skE4nSEuHwplZ2zknSCWWvfgOx2/KkRUtWTWZ1lKHuOUbKpV+/Eoy2DVQFcP86jHEL0fFk3lbUlynE8QToppZS9V5qqsUDoBmVsj8SJAmcwA0s8KcFMnMWikC3ptzADSzFurcAjsAmllLDWGUx1g5AJpZIX4NxsxazLfAZtZio8gJUqXGB8Aj059MLvvePR/NUfPu5JLpIxCqqLO6eo+68vXksnlGK1R1bnlU8TerKoFSXXV6gT0W2MxayC9Cm1mrtfoWeFAeziwh0vfpzNn1NvCViHiqzDHNrB7cC9xxQUQc7rPvMmBttpwD3JL9NLMlwL3Ai7sC+HGWCe4xSSfMJzep+LhmVrEIMdPwAFi29YPycJ4KvNy1fiDb9gGStkjaJWnXe7xTsllmNgojygtcmbJXgIPycPY68555gbMcoVMAH9aJzh1sVnNL4RlgqSvA7jycwHwezm4HgNO71k8DDpY5ppnVR9OvAAsHwMQ8nDuAL6vj94Ejfv5ntjTMvwfY5ABY5hZ4NbC986YLy4E7IuJ+SdcARMStwDSdV2D20XkN5qvlmmtmddLa9wD75eHMAt/85wC+mbfu3zvrbXbu3J1UNlfCmDEnRaoseVFV9U6lF61Dkp9KEj7lOH7bRMCMJ0Q1s7aq8+1tCgdAMyvEY4HNrNXCAdDM2qrpnSDNfoJpZmMTMZr3ACV9UdJeSXOSJhYpt1HS85L2Sbo+pW4HQDMrSMzOfShpKWkP8HngkX4FJC0DbqYzAcs6YLOkdYMq9i2wmRU2imeAEfEsQPbOcT8bgH3Z63lIuovOZCzPLPYlB0AzKyTnWOBVknZ1rU9l4/+HpdfEKwOn3nMANLNiovMcMNHhhRMmd5P0EHByj11bI+LehPqTJ17p5gBoZoUNqxc4Ii4qWUWhiVcaHwDzZRjLY/fQa8yTNawOWeHyqaoNVdU77uOPv96yIusEqYkngLWSzgBeAa4C/njQl2rTejNrnoi0pQxJn5N0ADgXuE/Szmz7GknTnXbEDHAdsBN4FvhpROwdVHfjrwDNbHxG1Au8nc58owu3H6Qz29T8+jSdGaiSOQCaWSGdq7tmjwRxADSzwjwZgpm1Vtnne+PmAGhmhQRirj69wIU4AJpZYQ2/ACyVFOlMSbu7lrck/dmCMudLOtJV5tulW2xm9ZB1gqQsdVUmJ8jzwHp4fyaGV+jRVQ38fURcXvQ4ZlZjDb8EHNYt8IXALyPiH4ZUn5k1QJ2v7lIMKwBeBdzZZ9+5kn5OZ1zen/d7O1vSFmALwMdOrebR5FFXvp5cNs+wtdSMaJ+ZvDa5zlpkhcujqjZUVO+R6U8mlcvz72AV4z+vUWaxC2BurtkBsHQXjqSjgc8C/7PH7qeAj0fE2cBfAff0qycipiJiIiImPvo7y8o2y8yqFkAobampYfRhXwY8FRGvLdwREW9FxD9ln6eBoyStGsIxzawGRjEWuErDCICb6XP7K+lkZdO4StqQHe+NIRzTzOogEpeaKvWwTdKxwMXAN7q2XQMQEbcCXwCulTQD/AtwVUSd/39gZunq/YpLilIBMCLeBn5nwbZbuz7fBNxU5hhmVmMNv5zxSBAzKyYgGt4L7ABoZiU4AJpZW/kW2MxaywHQzFpp/kXoBmt8AMw1TChHGubU4W155GlrnuPnGa6VR12zkQ3D8Zv2JZWrw98hj9Q2vBD
},
"metadata": {
"needs_background": "light"
}
},
{
"output_type": "display_data",
"data": {
"text/plain": [
"<Figure size 432x288 with 2 Axes>"
],
"image/svg+xml": "<?xml version=\"1.0\" encoding=\"utf-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<!-- Created with matplotlib (https://matplotlib.org/) -->\n<svg height=\"252.317344pt\" version=\"1.1\" viewBox=\"0 0 320.000437 252.317344\" width=\"320.000437pt\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n <metadata>\n <rdf:RDF xmlns:cc=\"http://creativecommons.org/ns#\" xmlns:dc=\"http://purl.org/dc/elements/1.1/\" xmlns:rdf=\"http://www.w3.org/1999/02/22-rdf-syntax-ns#\">\n <cc:Work>\n <dc:type rdf:resource=\"http://purl.org/dc/dcmitype/StillImage\"/>\n <dc:date>2021-08-31T12:13:54.790527</dc:date>\n <dc:format>image/svg+xml</dc:format>\n <dc:creator>\n <cc:Agent>\n <dc:title>Matplotlib v3.3.4, https://matplotlib.org/</dc:title>\n </cc:Agent>\n </dc:creator>\n </cc:Work>\n </rdf:RDF>\n </metadata>\n <defs>\n <style type=\"text/css\">*{stroke-linecap:butt;stroke-linejoin:round;}</style>\n </defs>\n <g id=\"figure_1\">\n <g id=\"patch_1\">\n <path d=\"M 0 252.317344 \nL 320.000437 252.317344 \nL 320.000437 0 \nL 0 0 \nz\n\" style=\"fill:none;\"/>\n </g>\n <g id=\"axes_1\">\n <g id=\"patch_2\">\n <path d=\"M 36.465625 228.439219 \nL 253.905625 228.439219 \nL 253.905625 10.999219 \nL 36.465625 10.999219 \nz\n\" style=\"fill:#ffffff;\"/>\n </g>\n <g clip-path=\"url(#pc3ebe31acf)\">\n <image height=\"218\" id=\"imagede94596844\" transform=\"scale(1 -1)translate(0 -218)\" width=\"218\" x=\"36.465625\" xlink:href=\"data:image/png;base64,\niVBORw0KGgoAAAANSUhEUgAAANoAAADaCAYAAADAHVzbAAAEpUlEQVR4nO3dMW4kRRSA4RlkYieQOPYBLK0IyFeytBHBnoEVNyD0BfYCewqiRZyAlAM4ZgNINkYWXKFKUP9UD98Xt9o9M/7VydOr88O793+fFvjqw68rbnv65fffltx31OPdw/C1nz/eD197++Z5+NpLfwfM++LSDwD/B0KDgNAgIDQICA0CQoOA0CAgNAgIDQJCg8D55dP9khGsGTNjTaP+/P7b4WtnxsVmxqpmzIxgrfpsl77vkZ519r7eaBAQGgSEBgGhQUBoEBAaBIQGAaFBQGgQEBoEbl49/TB88czIycympjVbnSbu+TR+6ePd+LUz4zyn0/gIFqfTl9/9MX7xh3XPMcobDQJCg4DQICA0CAgNAkKDgNAgIDQICA0CQoPA+fX57fAWrB0OwBvdmLVqm9GMHb6vazWzOW2H38EbDQJCg4DQICA0CAgNAkKDgNAgIDQICA0CQoPAzczBejMboFaZ2yz139vh+zraIXwrDiJc9Ts4iBAOTGgQEBoEhAYBoUFAaBAQGgSEBgGhQUBoEDg/vHs/vAXLtqi57UurHOn7WmXV72AECw5MaBAQGgSEBgGhQUBoEBAaBIQGAaFB4Pzy6X54MmQHlz4fbWYpzO2b5+FrdzjP7dLPcM0TL95oEBAaBIQGAaFBQGgQEBoEhAYBoUFAaBAQGgQs55k0sxRmh8+1wzKhFeejXfost9n7eqNBQGgQEBoEhAYBoUFAaBAQGgSEBgGhQUBoEDi/Pr8dHsE60kjR0UZ0Lr2B6nTa4/ddYWYMbdWWM280CAgNAkKDgNAgIDQICA0CQoOA0CAgNAgIDQJTI1irxoSudfTnms2MNR1pC9bMCNYMbzQICA0CQoOA0CAgNAgIDQJCg4DQICA0CAgNAueXT/fDI1hHssMBfDNswdrDqv8bbzQICA0CQoOA0CAgNAgIDQJCg4DQICA0CAgNAsu2YM1YMVK06kC5VY42/nTpLVgzdvhuvdEgIDQICA0CQoOA0CAgNAgIDQJCg4DQICA0CNxc+gFWmRmr2uFQu1dPa55h1WdbNY634u8/3q2578z35Y0GAaFBQGgQEBoEhAYBoUFAaBAQGgSEBgGhQeBqDyLcwapD7XbY6nStHEQIByY0CAgNAkKDgNAgIDQICA0CQoOA0CAgNAgc7iDCFYfaHW1T1LV+NgcRAv+K0CAgNAgIDQJCg4DQICA0CAgNAkKDgNAgMDWCtcMoy+iWoh2edQertjqtGO3a4TezBQsOTGgQEBoEhAYBoUFAaBAQGgSEBgGhQeD8zc8/Dk+G/PXT10sewnKeufvuMEGxwqqpjBmfP94PX3v75nn4Wm80CAgNAkKDgNAgIDQICA0CQoOA0CAgNAgIDQJTI1gzZsZTrnWkaAc7jDUd6fe1nAcOTGgQEBoEhAYBoUFAaBAQGgSEBgGhQUBoELhZdeOZDVCPd2vuu8LMtqoZO4wp7fAMo2ZGpWY+16rvwBsNAkKDgNAgIDQICA0CQoOA0CAgNAgIDQJCg8DUFiybrebssIFq5mC9HQ6aHLXqwMBVI37eaBAQGgSEBgGhQUBoEBAaBIQGAaFBQGgQEBoE/gFKpzw+8Et+0wAAAABJRU5ErkJggg==\" y=\"-10.439219\"/>\n </g>\n <g id=\"matplotlib.axis_1\">\n <g id=\"xtick_1\">\n <g id=\"line2d_1\">\n <defs>\n <path d=\"M 0 0 \nL 0 3.5 \n\" id=\"m3dca185d7c\" style=\"stroke:#000000;stroke-width:0.8;\"/>\n </defs>\n <g>\n <use style=\"stroke:#000000;stroke-width:0.8;\" x=\"41.901625\" xlink:href=\"#m3dca185d7c\" y=\"228.439219\"/>\n </g>\n </g>\n <g id=\"text_1\">\n <!-- 0 -->\n <g transform=\"translate(38.720375 243.037656)scale(0.1 -0.1)\">\n <defs>\n <path d=\"M 31.78125 66.40625 \nQ 24.171875 66.40625 20.328125 58.90625 \nQ 16.5 51.421875 16.5 36.375 \nQ 16.5 21.390625 20.328125 13.890625 \nQ 24.171875 6.390625 31.78125 6.390625 \nQ 39.453125 6.390625 43.28125 13.890625 \nQ 47.125 21.390625 47.
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAUAAAAD8CAYAAAAG730QAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuNCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8QVMy6AAAACXBIWXMAAAsTAAALEwEAmpwYAAAaOklEQVR4nO3de4wd5Znn8e8vNhfZCyaMjcGGJGjiQfJE4E1aZhDaWbxcbCwmhNwWz2hCLisHFGt3VjvSkLWUtLRaCSnKZpMBAZ2MBZHCJZNZAxp6MBeNxCCFARsZgrk6yLOYRhhDYjLDAO7uZ/841exJc06ft+qc6lPV9ftIpa7Le956T7f1uKreet5XEYGZWRN9aNgNMDMbFgdAM2ssB0AzaywHQDNrLAdAM2ssB0AzaywHQDMbOkmbJD0vab+kazscl6QfZMefkvTJQZzXAdDMhkrSIuAG4FJgLbBF0tpZxS4F1mTLVuDGQZzbAdDMhm09sD8iXoqI94A7gMtnlbkc+HG0PAqcJOm0fk+8uN8KyrB42ZI4buWypLKLXnw3ud7fO/vtok1aMF54asmwm8DUmuOSy8avyvknuvjwvwy8zjzfK8+/28nlS4s0Z07v/eZNJt/5F/VTx8YNS+ONN6eSyu556t19wDttu8YiYixbXw283HbsIHDurCo6lVkNvJqnzbNVMgAet3IZv/+DLyeVXbZ5f3K9u3btLdagBWTjqnXDbgJHfvDx5LJH71pRShuWj/184HXm+V55/t0e/tx5RZozp+f/5nt91/HGm1M8tusjSWUXnfbiOxEx0uVwp0A8O0c3pUxulQyAZlZ9AUwzPYiqDgJntG2fDkwUKJNbX88Ah9VzY2bDFwRHYypp6eFxYI2kMyUdC1wJ3DOrzD3Al7KY8gfAkYjo6/YX+rgCbOu5uZhWdH5c0j0R8Uxbsfaem3Np9dzMvrc3s5oaxBVgRExK2gbsAhYBOyJin6Srs+M3AePAZmA/8Dbwlb5PTH+3wO/33ABImum5aQ+A7/fcAI9KOknSaYOI3GY2XEEwNaDh9CJinFaQa993U9t6AN8YyMna9HML3K1XJm8ZACRtlbRb0u7JI+6tNauDaSJpqap+AuBAe24iYiwiRiJiZPGy4b+qYWZzC2CKSFqqqp9b4KH13JhZNVT56i5FP1eAQ+u5MbPhC+BoRNJSVYWvAIfZc2NmwxcVv71N0deL0MPquWl3ZDz97ftPjaa/UZ8nU+Dw1sG/qZ9HGVkNALsm9pZS78ZVedrws1LawOjgq8z3vfbmqDlP2TTrf/56/5UETNU7/jkTxMyKaWWC1JsDoJkVJKY6vuhRHw6AZlZIqxPEAdDMGqj1HqADoJk11LSvAM2siXwFaGaNFYipms+q4QBoZoX5FtjMGikQ78WiYTejLw6AZlZI60Vo3wLXRp6UsWGnKuUyOtzTl6msSZzKSPMrL3Vw3cDrfCHeGEg97gQxs0aKEFPhK0Aza6hpXwGaWRO1OkHqHULq3XozGxp3gphZo035PUAzayJngphZo03XvBe4cOslnSHp7yU9K2mfpP/SocwFko5I2pst3+qvuWZWFa3BED6UtFRVP1eAk8B/i4gnJJ0A7JH0QEQ8M6vcP0TEZX2cx8wqKBBHm5oKl01v+Wq2/htJzwKrgdkB0MwWoAj8IjSApI8B/xb4xw6Hz5P0JK0J0f88IvZ1qWMrsBXg2FNOTD730btWJJc9vDW9bJ4ZvlJnhStrprkq1JsnDayslLEylJWKl0eemQ+Xbd5fYktm07y8CC3pZOBO4GPAAeCLEfGrDuUOAL8BpoDJiBjpVXff4VvSvwH+BviziHhr1uEngI9GxDnAXwJ3dasnIsYiYiQiRhYvW9Jvs8ysZEHrCjBl6dO1wEMRsQZ4KNvuZkNErEsJftBnAJR0DK3g95OI+D+zj0fEWxHxz9n6OHCMpOX9nNPMqmOeOkEuB27N1m8FPtNvhTP66QUW8FfAsxHxv7qUOTUrh6T12fkGMwyFmQ1VIKYjbenTyqzPYabv4ZSuTYL7Je3JHqn11M8zwPOBPwV+IWlvtu+/Ax/JGnoT8HngGkmTwL8CV0ZEzeeSNzOYmRYzOYQsl7S7bXssIsZmNiQ9CJza4XPbczTp/IiYkHQK8ICk5yLi4bk+0E8v8CMw9xPQiLgeuL7oOcysynJNjH54rudyEXFR17NIr0k6LSJelXQacKhLHRPZz0OSdgLrgTkDYL37sM1saIJWJkjK0qd7gKuy9auAu2cXkLQ0ex8ZSUuBS4Cne1XsAGhmhU1lV4G9lj5dB1ws6UXg4mwbSaskjWdlVgKPZK/cPQbcGxH39arYucBmVkiE5iUXOCLeAC7ssH8C2JytvwSck7duB0AzK6TVCdLQVDgzazrPCVKKRS++m5zSs2viZ+U0YjS9aGraXGkzzY3mqLa0etOVlV5WRppfFdL28qRlzqdWJ4gHRDWzhqryUFcpHADNrJCZTJA6cwA0s8I8KZKZNVIEHJ12ADSzBmrdAjsAmllDDSDLY6gcAM2sEL8GY2YN5ltgM2uw+ZgTpEy1D4CfGr2mlHrLmGiojImWoLxJkfKowsRMeZTxN8tj2JNIrd/4dt91tHqBnQtsZg3kF6HNrNEafQvcax7ObEKk79Mas+tt4MsR8UQ/5zSzanAvcMuGiDjc5dilwJpsORe4MftpZguAe4Hndjnw42wmuEclnTQzuUnJ5zWzkkWIyZoHwH5b32seztXAy23bB7N9HyBpq6TdknYf5d0+m2Vm82Ge5gUuTb9XgL3m4ez0zTvOC5zNEToGcKJO9tzBZhW3EJ4B9nUF2D4PJzAzD2e7g8AZbdunAxP9nNPMqqPuV4CFA2DiPJz3AF9Syx8AR/z8z2xhmHkPsM4BsJ9b4JXAztabLiwGbouI+yRdDRARNwHjtF6B2U/rNZiv9NdcM6uSur8HqFYHbbWMnHN8PLbrjN4FLbeyJiSqwuRBC1UZf7N/jId4K97sK3qdeNbKOPfmP04q++CG/71n9nvCVeBMEDMrrMq3tykcAM2sEOcCm1mjhQOgmTVV3TtB6p3HYmZDEzE/7wFK+oKkfZKmJXXtSJG0SdLzkvZLujalbgdAMytITE1/KGnp09PAZ4GHuxWQtAi4gdYALGuBLZLW9qrYt8BmVth8PAOMiGcBsneOu1kP7I+Il7Kyd9AajOWZuT7kAGhmheTMBV4uaXfb9liW/z8onQZe6Tn0ngOgmRUTreeAiQ7P9SK0pAeBUzsc2h4RdyfUnzzwSjsHQDMrbFC9wBFxUZ9VFBp4pZIB8IWnliSn/1RhlrMylDVz2pHxjyeXPXrXiuSyC3XGuyrMdleFWfQ6iawTpCIeB9ZIOhN4BbgS6JmnV5nWm1n9RKQt/ZB0haSDwHnAvZJ2ZftXSRpvtSMmgW3ALuBZ4KcRsa9X3ZW8AjSzepinXuCdtMYbnb1/gtZoUzPb47RGoErmAGhmhbSu7uqdCeIAaGaFeTAEM2usCg4nmosDoJkVEojp6vQCF+IAaGaF1fwCsK9Jkc6StLdteUvSn80qc4GkI21lvtV3i82sGrJOkJSlqgpfAUbE88A6eH8khlfo0FUN/ENEXFb0PGZWYTW/BBzULfCFwC8j4p8GVJ+Z1UCVr+5SDCoAXgnc3uXYeZKepJWX9+fd3s6WtBXYCnA8SwbUrGrJk4a2fHM5KU3LNu9PLrtr4mfpFY/macXeUuotKx0vVZ40tHyz6OUoO5pWbP3Gt3Ocv7MApqfrHQD77sKRdCzwaeCvOxx+AvhoRJwD/CVwV7d6ImIsIkYiYuQYjuu3WWZWtgBCaUtFDaIP+1LgiYh4bfaBiHgrIv45Wx8HjpG0fADnNLMKmI9c4DINIgBuocvtr6RTlQ3jKml9dr43BnBOM6uCSFwqqq9ngJKWABcDX2/bdzVARNwEfB64RtIk8K/AlRFV/v/AzNJV+xWXFH0FwIh4G/idWftualu/Hri+n3OYWYXV/HLGmSBmVkxA1LwX2AHQzPrgAGhmTeVbYDNrLAdAM2ukmReha6ySAfD3zn6bXbv2JpZOLZfT6OCrzJOqVQWfGr0
},
"metadata": {
"needs_background": "light"
}
},
{
"output_type": "display_data",
"data": {
"text/plain": [
"<Figure size 432x288 with 1 Axes>"
],
"image/svg+xml": "<?xml version=\"1.0\" encoding=\"utf-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<!-- Created with matplotlib (https://matplotlib.org/) -->\n<svg height=\"248.518125pt\" version=\"1.1\" viewBox=\"0 0 261.105625 248.518125\" width=\"261.105625pt\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n <metadata>\n <rdf:RDF xmlns:cc=\"http://creativecommons.org/ns#\" xmlns:dc=\"http://purl.org/dc/elements/1.1/\" xmlns:rdf=\"http://www.w3.org/1999/02/22-rdf-syntax-ns#\">\n <cc:Work>\n <dc:type rdf:resource=\"http://purl.org/dc/dcmitype/StillImage\"/>\n <dc:date>2021-08-31T12:13:55.251665</dc:date>\n <dc:format>image/svg+xml</dc:format>\n <dc:creator>\n <cc:Agent>\n <dc:title>Matplotlib v3.3.4, https://matplotlib.org/</dc:title>\n </cc:Agent>\n </dc:creator>\n </cc:Work>\n </rdf:RDF>\n </metadata>\n <defs>\n <style type=\"text/css\">*{stroke-linecap:butt;stroke-linejoin:round;}</style>\n </defs>\n <g id=\"figure_1\">\n <g id=\"patch_1\">\n <path d=\"M 0 248.518125 \nL 261.105625 248.518125 \nL 261.105625 0 \nL 0 0 \nz\n\" style=\"fill:none;\"/>\n </g>\n <g id=\"axes_1\">\n <g id=\"patch_2\">\n <path d=\"M 36.465625 224.64 \nL 253.905625 224.64 \nL 253.905625 7.2 \nL 36.465625 7.2 \nz\n\" style=\"fill:#ffffff;\"/>\n </g>\n <g clip-path=\"url(#pbf350132ae)\">\n <image height=\"218\" id=\"image186095787a\" transform=\"scale(1 -1)translate(0 -218)\" width=\"218\" x=\"36.465625\" xlink:href=\"data:image/png;base64,\niVBORw0KGgoAAAANSUhEUgAAANoAAADaCAYAAADAHVzbAAAD+UlEQVR4nO3dwY0cNxBA0R5jovBZATiIBZTAJqssHIUVhSAfnMDyUL/J9nvnxWw3Zz54KZCvj9fn7+sgP/75+9b///3Pv279/9d1/xqw7o+7HwD+D4QGAaFBQGgQEBoEhAYBoUFAaBAQGgSEBoH3DuM8E2NNO4xKrVj5Hlbe7bTPnbDDGtjRICA0CAgNAkKDgNAgIDQICA0CQoOA0CAgNAi8p8ZjVsZTJsbApkbL7h4nerKTxrpW2dEgIDQICA0CQoOA0CAgNAgIDQJCg4DQICA0CLxX/vipJ2ZNvZfPnf3cCVPPakeDgNAgIDQICA0CQoOA0CAgNAgIDQJCg4DQILA0grVi6kK3k+xwsd9JJ0uddnKZiwhhM0KDgNAgIDQICA0CQoOA0CAgNAgIDQJCg8DYCNaUk8a1dhirWnHS2q7YYQzNjgYBoUFAaBAQGgSEBgGhQUBoEBAaBIQGgdevn99+3/0QK+6+H+2pB+Osmni3p06mXJcdDRJCg4DQICA0CAgNAkKDgNAgIDQICA0CQoPAe4fRn5XRm6eO6Zx2N9jddhiFcz8abEZoEBAaBIQGAaFBQGgQEBoEhAYBoUFAaBBYuh9th/Gnu0/BmvLk+9EmPneHE8ZWPteOBgGhQUBoEBAaBIQGAaFBQGgQEBoEhAYBoUHg9fH6vP0iwh1GoFhz9yjcaad72dEgIDQICA0CQoOA0CAgNAgIDQJCg4DQICA0CLx+/fx2+wjWhB0uqpuyw8V6TzX1/drRICA0CAgNAkKDgNAgIDQICA0CQoOA0CAgNAgsjWCdNH409azGn/6zw2/hq3ZYWzsaBIQGAaFBQGgQEBoEhAYBoUFAaBAQGgSEBoH33Q9wXeedQjVhh1O77h5V2uF3MLVedjQICA0CQoOA0CAgNAgIDQJCg4DQICA0CAgNAo+9iHAHO5zExRojWHAwoUFAaBAQGgSEBgGhQUBoEBAaBIQGAaFB4PXx+rx9BGvi9KMdToo67cSuu99th+9sih0NAkKDgNAgIDQICA0CQoOA0CAgNAgIDQJCg8DSRYQ7jLJMmHqvHdbrtDGwr5paW6dgwcGEBgGhQUBoEBAaBIQGAaFBQGgQEBoEHns4z5QdnnWHiZMJpx2SZDIENiM0CAgNAkKDgNAgIDQICA0CQoOA0CAgNAgcN4LFmrtH1q7rrO93ar3saBAQGgSEBgGhQUBoEBAaBIQGAaFBQGgQEBoElu5H28HdI0VTpy/tMKa0wzN81dTaTq2BHQ0CQoOA0CAgNAgIDQJCg4DQICA0CAgNAkKDwNgI1tQoy0ljQlOmxtBOGm+b4hQsOJjQICA0CAgNAkKDgNAgIDQICA0CQoOA0CDwL+YzDJEn1n1NAAAAAElFTkSuQmCC\" y=\"-6.64\"/>\n </g>\n <g id=\"matplotlib.axis_1\">\n <g id=\"xtick_1\">\n <g id=\"line2d_1\">\n <defs>\n <path d=\"M 0 0 \nL 0 3.5 \n\" id=\"mc97ccd7068\" style=\"stroke:#000000;stroke-width:0.8;\"/>\n </defs>\n <g>\n <use style=\"stroke:#000000;stroke-width:0.8;\" x=\"41.901625\" xlink:href=\"#mc97ccd7068\" y=\"224.64\"/>\n </g>\n </g>\n <g id=\"text_1\">\n <!-- 0 -->\n <g transform=\"translate(38.720375 239.238438)scale(0.1 -0.1)\">\n <defs>\n <path d=\"M 31.78125 66.40625 \nQ 24.171875 66.40625 20.328125 58.90625 \nQ 16.5 51.421875 16.5 36.375 \nQ 16.5 21.390625 20.328125 13.890625 \nQ 24.171875 6.390625 31.78125 6.390625 \nQ 39.453125 6.390625 43.28125 13.890625 \nQ 47.125 21.390625 47.125 36.375 \nQ 47.125 51.421875 43.28125 58.90625 \nQ 39.453125 66.40625 31.78125 66.40625 \nz\nM 31.78125 74.21875 \nQ 44.046875 74.21875 50.515625 64.515625 \nQ 56.984375 54.828125 56.984375 36.375 \nQ 56.984375 17.96875 50.515625 8.265625 \nQ 44.046875 -1.42
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAQUAAAD4CAYAAADl7fPiAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuNCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8QVMy6AAAACXBIWXMAAAsTAAALEwEAmpwYAAAPlUlEQVR4nO3df6xkZX3H8feny69AMYgIwgKWmC3JxsjWbBYNaQOl8itEtLHtkqZSa7JqJKlJTUrbRP3TpLEmFgKulYCJgjbtKokbFkKaoIk/WMnyq/zaEizXJWyVFLQouPrtH/csuc9lZnfvnJk7M9f3K7mZOec8c85zZu5+cs6dZ59vqgpJOui3pt0BSbPFUJDUMBQkNQwFSQ1DQVLjqGl3YJBjcmwdxwlj3+/vvu2lse9z3jzx4PFH3HYl79dK9jtPJvUeTPu9/QX/xyv1cgZtyyx+Jfm6nFzn5+Kx73fXvj1j3+e8ufSMTUfcdiXv10r2O08m9R5M+739Xt3Di/X8wFDw9kFSo1coJLksyeNJ9ia5bsD2JPlct/3BJG/vczxJkzdyKCRZB9wAXA5sBK5OsnFZs8uBDd3PNuDGUY8naXX0uVLYAuytqqeq6hXgduCqZW2uAr5Ui74LnJTk9B7HlDRhfUJhPfDMkuWFbt1K2wCQZFuS3Ul2/5KXe3RLUh99QmHQXy6Xf5VxJG0WV1Ztr6rNVbX5aI7t0S1JffQJhQXgrCXLZwL7RmgjaYb0CYX7gA1JzklyDLAVuGNZmzuA93ffQrwDeKGqnu1xTEkTNvKIxqo6kORaYBewDri5qh5J8uFu+03ATuAKYC/wEvCB/l2WNEm9hjlX1U4W/+EvXXfTkucFfLTPMcZpnkacrcQsjNSchZF/a9Uk3oMtlw4fZu2IRkkNQ0FSw1CQ1DAUJDUMBUkNQ0FSw1CQ1DAUJDUMBUkNQ0FS4zdq4taVcHjt5Ex7WDjM1+frxK2SpspQkNQwFCQ1DAVJDUNBUsNQkNQwFCQ1+lSIOivJfyR5NMkjSf56QJsLk7yQZE/384l+3ZU0aX3maDwA/E1V3Z/kROAHSe6uqv9c1u5bVXVlj+NIWkUjXylU1bNVdX/3/KfAowyp/iRpfvSazfmgJL8D/B7wvQGb35nkARaLwHy8qh4Zso9tLBah5TiOH0e3Vs20h+3OwszTK+nDWh1iPE+fw6Fmc+4dCkl+G/g34GNV9eKyzfcDb66qnyW5Avg6ixWoX6OqtgPbYfH/PvTtl6TR9Pr2IcnRLAbCl6vq35dvr6oXq+pn3fOdwNFJTulzTEmT1efbhwBfBB6tqn8a0uZNXTuSbOmO95NRjylp8vrcPlwA/AXwUJI93bq/B86GVytFvQ/4SJIDwM+BrTWL/1db0qv61JL8NoNLzS9tcz1w/ajHkLT6HNEoqWEoSGoYCpIahoKkhqEgqTGWYc7TNE9DZmehr7PQh3kaOjyp92va53UoXilIahgKkhqGgqSGoSCpYShIahgKkhqGgqSGoSCpYShIasz9iMZpT4A5KfM06k+LJvWZrfbvolcKkhqGgqRG39mcn07yUFcSbveA7UnyuSR7kzyY5O19jidp8sbxN4WLqurHQ7ZdzmKdhw3A+cCN3aOkGTXp24ergC/Vou8CJyU5fcLHlNRD31Ao4K4kP+jKvi23HnhmyfICQ+pNJtmWZHeS3b/k5Z7dkjSqvrcPF1TVviSnAncneayq7l2yfdAU8APrPlg2TpoNva4Uqmpf97gf2AFsWdZkAThryfKZLBaalTSj+pSNOyHJiQefA5cADy9rdgfw/u5biHcAL1TVsyP3VtLE9bl9OA3Y0ZWKPAr4SlXdmeTD8GrZuJ3AFcBe4CXgA/26K2nSMoulHTefd1x9f9dZh2+oFVurw8LXskkMn95y6TPsfuAXA8s+OqJRUsNQkNQwFCQ1DAVJDUNBUsNQkNQwFCQ1DAVJDUNBUsNQkNRwNuch5mmG5HkbYjxPM1VP6viz/Jl5pSCpYShIahgKkhqGgqSGoSCpYShIahgKkhp9Jm49tysXd/DnxSQfW9bmwiQvLGnzid49ljRRIw9eqqrHgU0ASdYBP2JxmvflvlVVV456HEmra1y3DxcD/1VVPxzT/iRNybiGOW8Fbhuy7Z1JHmCxCMzHq+qRQY26snPbAM5eP/3R15MYsjrt4dArNamhuLM8xHe5WfjMVvv96n2lkOQY4N3Avw7YfD/w5qo6D/hn4OvD9lNV26tqc1VtfuMb1vXtlqQRjeP24XLg/qp6bvmGqnqxqn7WPd8JHJ3klDEcU9KEjCMUrmbIrUOSN6UrIZVkS3e8n4zhmJImpNfNe5LjgXcBH1qybmnZuPcBH0lyAPg5sLVmsSSVpFf1CoWqegl4w7J1Ny15fj1wfZ9jSFpdjmiU1DAUJDUMBUkNQ0FSw1CQ1Jj+eOKe5mnI7EpMexbjle53FmY9Xqu/C5P4fJ+o4cOFvFKQ1DAUJDUMBUkNQ0FSw1CQ1DAUJDUMBUkNQ0FSw1CQ1DAUJDUyixMhvS4n1/m5eKp9WKtDZteySQwHnoXh5pPwvbqHF+v5DNrmlYKkxmFDIcnNSfYneXjJupOT3J3kye7x9UNee1mSx5PsTXLdODsuaTKO5ErhFuCyZeuuA+6pqg3APd1yoysldwOLU8BvBK5OsrFXbyVN3GFDoaruBZ5ftvoq4Nbu+a3Aewa8dAuwt6qeqqpXgNu710maYaP+TeG0qnoWoHs8dUCb9cAzS5YXunWSZtgkJ1kZ9JfNoV91LK0leRzHT6pPkg5j1CuF55KcDtA97h/QZgE4a8nymSwWmR1oaS3Jozl2xG5J6mvUULgDuKZ7fg3wjQFt7gM2JDmnK0K7tXudpBl2JF9J3gZ8Bzg3yUKSDwKfBt6V5EkWy8Z9umt7RpKdAFV1ALgW2AU8CnxtWBl6SbPjsH9TqKqrh2x6zZDDqtoHXLFkeSewc+TeSVp1zuY8BvM0vHYt73favwtrZUi0w5wlNQwFSQ1DQVLDUJDUMBQkNQwFSQ1DQVLDUJDUMBQkNQwFSY25H+Y8qeGi8zS8dlJm4bymPdR6FoZvT2K/Wy59aeg2rxQkNQwFSQ1DQVLDUJDUMBQkNQwFSQ1DQVJj1FqS/5jksSQPJtmR5KQhr306yUNJ9iTZPcZ+S5qQUWtJ3g28tareBjwB/N0hXn9RVW2qqs2jdVHSahqplmRV3dVN4Q7wXRYLvUhaA8YxzPmvgK8O2VbAXUkK+HxVbR+2k6Vl485efxS7du8ZQ9dWx7Rnc56UWZ5xeBZN6jNb7d+FXqGQ5B+AA8CXhzS5oKr2JTkVuDvJY92Vx2t0gbEdYPN5xw2tOSlpskb+9iHJNcCVwJ9X1cB/xF1xGKpqP7CDxfL0kmbYSKGQ5DLgb4F3V9XA/26V5IQkJx58DlwCPDyoraTZMWotyeuBE1m8JdiT5Kau7au1JIHTgG8neQD4PvDNqrpzImchaWxGrSX5xSFtX60lWVVPAef16p2kVeeIRkkNQ0FSw1CQ1DAUJDUMBUmNmZzN+YkHj5+r2XZnYUjytM3bezCJ/s7TbM6H4pWCpIahIKlhKEhqGAqSGoaCpIahIKlhKEhqGAqSGoaCpMZMjmicN/M0ceu8jbqb9uSxs/A5rDavFCQ1DAVJjVHLxn0qyY+6+Rn3JLliyGsvS/J4kr1JrhtnxyVNxqhl4wA+25WD21RVO5dvTLIOuAG4HNgIXJ1kY5/OSpq8kcrGHaEtwN6qeqqqXgFuB64aYT+SVlGfvylc21WdvjnJ6wdsXw88s2R5oVs3UJJtSXYn2f1LXu7RLUl9jBoKNwJvATYBzwKfGdAmA9YNLQdXVduranNVbT6aY0fslqS+RgqFqnquqn5VVb8GvsDgcnALwFlLls8E9o1yPEmrZ9SycacvWXwvg8vB3QdsSHJOkmOArcAdoxxP0uo57IjGrmzchcApSRaATwIXJtnE4u3A08CHurZnAP9SVVdU1YEk1wK7gHXAzVX1yCROQtL4TKxsXLe8E3jN15XTMm+Ti07CpN6DedvvtM3yeTmiUVLDUJDUMBQkNQwFSQ1DQVLDUJD
},
"metadata": {
"needs_background": "light"
}
},
{
"output_type": "stream",
"name": "stdout",
"text": [
"['agar', 'ahn', 'arie', 'basilika', 'beneiden', 'boe', 'cherub', 'dank1', 'die', 'don', 'dugong', 'dur', 'egal', 'einklang', 'ergo', 'erraten', 'ethologie', 'frei', 'gehweg', 'gel', 'gin', 'gmbh', 'gon', 'hai', 'hellseher', 'heuer', 'huefte', 'ido', 'index', 'irgendwo', 'kuendigen', 'lama0', 'logo', 'lok', 'los0', 'lusaka', 'mai', 'makel', 'mehl', 'nadir', 'naiv', 'nautisch', 'nie', 'oase', 'ol', 'opa', 'osel', 'pkw', 'sekte', 'skalde', 'strich', 'taburett', 'terebinthe', 'und', 'uno', 'uran', 'usa', 'verknallen', 'verlierer', 'video', 'vor', 'weissbrot', 'zeh']\n"
]
}
],
"metadata": {}
},
{
"cell_type": "code",
2021-08-31 17:26:19 +02:00
"execution_count": 30,
2021-08-31 13:56:29 +02:00
"source": [
2021-08-31 17:26:19 +02:00
"get_database(\"de\")['ore']"
2021-08-31 13:56:29 +02:00
],
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
2021-08-31 17:26:19 +02:00
"{'word': 'Ore',\n",
" 'senses': ['Münze, die in Dänemark, Norwegen und Schweden verwendet wird'],\n",
2021-08-31 13:56:29 +02:00
" 'synonyms': [],\n",
2021-08-31 17:26:19 +02:00
" 'antonyms': [],\n",
" 'num_translations': 10}"
2021-08-31 13:56:29 +02:00
]
},
"metadata": {},
2021-08-31 17:26:19 +02:00
"execution_count": 30
2021-08-31 13:56:29 +02:00
}
],
"metadata": {}
},
{
"cell_type": "code",
"execution_count": 21,
"source": [
"def create_word_grid(w: int,\n",
" h: int,\n",
" lang_code: str = \"en\",\n",
" target_density: float = 0.8,\n",
" difficulty: int = 0):\n",
"\n",
" logging.info(\"generate new crossword with params: w:%s h:%s lang:%s density:%s difficulty:%s\",\n",
" str(w),\n",
" str(h),\n",
" lang_code,\n",
" str(target_density),\n",
" str(difficulty))\n",
"\n",
" db = get_database(lang_code, difficulty=difficulty)\n",
" inverted_db = get_inverted_database(lang_code, difficulty=difficulty)\n",
"\n",
" base_grid = GridCreationState(h=h, w=w, db=db, inverted_db=inverted_db)\n",
"\n",
" final_state = base_grid.fill_grid(target_density=target_density,\n",
" inner_retries=5,\n",
" conflict_solver_depth=20,\n",
" min_length=3,\n",
" max_iterations=max(size * 75, 1000))\n",
"\n",
" # generate word hints\n",
"\n",
" word_hints = {}\n",
"\n",
" opposite_prefix = \"opposite of:\" if lang_code == \"en\" else \"Gegenteil von:\"\n",
" synonym_prefix = \"other word for:\" if lang_code == \"en\" else \"anderes Wort für:\"\n",
"\n",
" for placed_word in final_state.placed_words:\n",
" word_key = placed_word.word_key\n",
" word = normalize_word(db[word_key]['word'])\n",
" y = placed_word.y\n",
" x = placed_word.x\n",
" is_vertical = placed_word.is_vertical\n",
"\n",
" word_info = WordInfo(word_key, y, x, is_vertical,\n",
" db, opposite_prefix, synonym_prefix)\n",
" word_hints[word] = word_info\n",
"\n",
" # create a solution word\n",
"\n",
" char_locations = {}\n",
" for char in list(\"abcdefghijklmnopqrstuvwxyz\"):\n",
" char_locations[char] = np.argwhere(\n",
" final_state.letter_grid == char).tolist()\n",
"\n",
" words = list(db.keys())\n",
" n_words = len(words)\n",
"\n",
" min_solution_length = 10\n",
" max_solution_length = 20\n",
"\n",
" solution_word_locations = None\n",
"\n",
" while solution_word_locations is None:\n",
"\n",
" random_index = random.randint(0, n_words - 1)\n",
" random_word_key = words[random_index]\n",
" random_word = db[random_word_key]['word']\n",
" normalized_random_word = normalize_word(random_word)\n",
" if len(normalized_random_word) < min_solution_length or len(normalized_random_word) > max_solution_length:\n",
" continue\n",
"\n",
" char_locations_copy = {}\n",
" for char in char_locations:\n",
" char_locations_copy[char] = char_locations[char].copy()\n",
" \n",
" solution = []\n",
" \n",
" aborted = False\n",
" for char in list(normalized_random_word):\n",
" if char not in char_locations_copy:\n",
" aborted = True\n",
" break\n",
" locations = char_locations_copy[char]\n",
" if len(locations) == 0:\n",
" aborted = True\n",
" break\n",
" \n",
" i = random.randint(0, len(locations) - 1)\n",
" location = locations[i]\n",
" del(locations[i])\n",
" solution.append(location)\n",
" \n",
" \n",
" if aborted:\n",
" continue\n",
"\n",
" solution_word_locations = solution\n",
" \n",
"\n",
" return final_state.letter_grid, word_hints, solution_word_locations\n"
],
"outputs": [],
"metadata": {}
},
{
"cell_type": "code",
"execution_count": 22,
"source": [
"state, hints, solution = create_word_grid(10,10)"
],
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"finished after 1500 iterations, with a density of 0.69\n"
]
}
],
"metadata": {}
},
{
"cell_type": "code",
"execution_count": 29,
"source": [
"solution"
],
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"[[6, 4],\n",
" [6, 5],\n",
" [6, 9],\n",
" [3, 4],\n",
" [5, 9],\n",
" [4, 2],\n",
" [8, 1],\n",
" [8, 0],\n",
" [1, 8],\n",
" [8, 8]]"
]
},
"metadata": {},
"execution_count": 29
}
],
"metadata": {}
},
{
"cell_type": "code",
"execution_count": 83,
"source": [
"grid = final_state.letter_grid"
],
"outputs": [],
"metadata": {}
},
{
"cell_type": "code",
"execution_count": 95,
"source": [
"[0,8] in np.argwhere(grid == \"a\").tolist()"
],
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"False"
]
},
"metadata": {},
"execution_count": 95
}
],
"metadata": {}
},
{
"cell_type": "code",
"execution_count": null,
"source": [],
"outputs": [],
"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
}