{ "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 :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 :19(get_database)\n", " 14931 0.009 0.000 0.031 0.000 :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 :1()\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 :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 :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 :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 :259(place_random_word)\n", " 2085 0.093 0.000 0.104 0.000 :107(find_suitable_words)\n", " 682 0.048 0.000 0.082 0.000 :22(write)\n", " 659/534 0.038 0.000 0.128 0.000 :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 :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 :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 :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 :171(write_word)\n", " 2084 0.009 0.000 0.009 0.000 :239(expand_coordinates)\n", " 1627 0.009 0.000 0.027 0.000 :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 :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 :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()\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 :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 :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 :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 :1()\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 :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 :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": [ "
" ], "image/svg+xml": "\n\n\n\n \n \n \n \n 2021-08-31T12:13:54.263271\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 \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n\n", "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/kXoBmt8AMw1TChHGubU4W155GlrnuPnGa6VR12zkQ3D8Zv2JZWrw98hj9Q2vBDDeR236S+1NT4AmtkYuRfYzNpKvgI0s1aq+TC3FA6AZlZQvWd6SeEAaGbF+QrQzFprbtwNKMcB0MyKWQLvATY7qaeZjZUibSl1DOmLkvZKmpM0sUi5/ZJ+kWWg3JVSt68Azay40TwD3AN8HvhBQtkLIuJwasUOgGZWaxHxLEA2ufxQ1TIAvvD0sclDelKze0H68KelLN/QrhwVT+ZtyXilD/PbXUGd+X63ef6Np5r900eHUk+O29tVC25LpyIix+DUJAE8ICmAH6TUX8sAaGYNEOQZCnc4IhZ7fvcQcHKPXVsj4t7EY5wXEQclnQQ8KOm5iHhksS8MDICStgGXA4ci4lPZthOBu4FPAPuBL0XEP/b47kbg+8Ay4IcRcUPiiZhZEwzpGWBEXDSEOg5mPw9J2g5sABYNgCm9wLcBGxdsux54OCLWAg9n679F0jLgZjppM9cBmyWtSziemTXEKHqBk9ohrZR03Pxn4BI6nSeLGhgAs0vINxdsvgK4Pft8O3Blj69uAPZFxEsR8S5wV/Y9M1sqRpAWU9LnJB0AzgXuk7Qz275G0nRWbDXwqKSfA48D90XE/YPqLvoMcHVEvAoQEa9m99wLnQq83LV+ADin4PHMrI5GcHUXEduB7T22HwQ2ZZ9fAs7OW3eVnSC9no72/XVJ2gJsATiGY6tqk5kNyahub6tUdCTIa5JOAch+HupR5gBwetf6acDBfhVGxFRETETExFGsKNgsMxupOaUtNVU0AO4Ars4+Xw306qZ+Algr6QxJRwNXZd8zsyWiLp0gRQ0MgJLuBH4GnCnpgKSvAzcAF0t6Ebg4W/+th5IRMQNcB+wEngV+GhF7qzkNMxuLEXSCVGngM8CI2Nxn14U9yr7/UDJbnwamF5YzsyWg5ld3KRo/EqQOw9tSh+1VlWWtafVWpZJhfpPpx8+VobAiqf89LIt3hnNAB0Azays1fEJUzwdoZq3lK0AzK863wGbWSu4EMbNWcwA0s9ZyADSzNhLN7wV2ADSzYvwM0MxazQHQzFrLAXD4Zteu4MiNaZmw6jAULlWuoVKTS7fePFKHGUK+oXDjzgr35OQtyWU/M5le786D/yup3IZL306uczG+BTaz9nIANLNWCvcCm1mb+QrQzNrKzwDNrL0cAM2slWo+3X0KB0AzK0Q0/xY4JSnSNkmHJO3p2vZdSc9JelrSdkkn9Pnufkm/kLRb0q4httvMamDJZ4UDbgM2Ltj2IPCpiDgLeAH41iLfvyAi1kfERLEmmlltNTwr3MAAGBGPAG8u2PZAlvYS4DE6Sc/NrG0aHgCH8Qzwa8DdffYF8ICkAH4QEVP9KpG0BdgCcAzHJg9xy5cJbH1y2So0LXtbnnqTs6zlVNW5JQ/zm0w/+lIektjTiG5vJX0X+EPgXeCXwFcj4lc9ym0Evg8sA34YETcMqrtUUiRJW4EZ4Cd9ipwXEZ8GLgO+KekP+tUVEVMRMRERE0exokyzzGxURnMFOPCRm6RlwM10Ys06YLOkdYMqLhwAJV0NXA78x4joeYpZonQi4hCwHdhQ9HhmVj+aS1vKSHzktgHYFxEvRcS7wF3AFYPqLhQAs0vNvwA+GxE9p5WQtFLScfOfgUuAPb3Kmlkz5egFXiVpV9eypeAhvwb8bY/tpwIvd60fyLYtauAzQEl3AufTOYEDwHfoXIKuAB6UBPBYRFwjaQ2de+9NwGpge7Z/OXBHRNw/6Hhm1hD5bm8PL/YmiKSHgJN77NoaEfdmZRZ75KY+LVzUwAAYEZt7bP5Rn7IHgU3Z55eAswfVb2YNNqROkIi4aLH9XY/cLuzzyO0AcHrX+mnAwUHH9UgQMytkVCNBuh65/bt+j9yAJ4C1ks4AXgGuAv54UN2leoHNrN00F0lLSTcBx9F55LZb0q0AktZImgbIOkmuA3YCzwI/jYi9gyr2FaCZFTOil5wjomd+jO5Hbtn6NDCdp24HQDMrrM7jfFM4AJpZcQ6AwzezaiWH/2j4WbvGrWlDpXLVm0O+4Ys5Kp7M25JmqGo44DD4CtDM2ssB0MxayVnhzKytlsKM0A6AZlZc73lQGsMB0MwK8xWgmbVTzWd7TuEAaGaFuRPEzFrLAdDM2ilwJ4jlfVM/1e5Kjp9nZEWeERufmbw2veIanFt6vbsrqDPnCJeicyePgDtBzKy9HADNrI2WwovQAydElbRN0iFJe7q2TUp6JZuccLekTX2+u1HS85L2Sbp+mA03szGLtMlQhzAhamVSZoS+DdjYY/tfRsT6bPnAJIRF83SaWYOMJi9wZQYGwIh4BHizQN2F8nSaWXPkSItZS2Vyglwn6ensFvkjPfbnytMpact8ztCZ3/xziWaZ2UgEMBdpS00VDYC3AL8LrAdeBb7Xo0yuPJ0RMRURExExsfyYlQWbZWYj1fBb4EK9wBHx2vxnSX8N/E2PYoXydJpZc9T59jZFoStASad0rX4O2NOj2Pt5OiUdTSdP544ixzOzemp6L/DAK0BJdwLnA6skHQC+A5wvaT2di9v9wDeysmuAH0bEpoiYkTSfp3MZsC0lT6eZNUTNb29TDAyAEbG5x+Yf9SlbOk8nwPLD/5yekGcyvd48Q7vySG1rNUPmqkteVFkbJqupt5JkS5PJVY6/rTDSxFCdF6GbHQE9EsTMivNsMGbWVr4CNLN2asMzQDOz3kbTwyvpu8AfAu8CvwS+GhG/6lFuP/BrYBaYiYiJQXWXGQliZm0XkbaU8yDwqYg4C3gB+NYiZS/I5icYGPzAAdDMisoSo6cspQ4T8UBEzGSrj9EZVDEUDoBmVtxorgC7fQ34236tAR6Q9KSkpHm0/QzQzIpLj22rJO3qWp+KiKn5FUkPASf3+N7WiLg3K7MVmAF+0ucY50XEQUknAQ9Kei6bzaovB0AzK0xzyfe3hxd7LhcRFy16HOlq4HLgwojel5TZQAwi4pCk7XSm5Fs0APoW2MyKCTovQqcsJUjaCPwF8NmIeLtPmZWSjpv/DFxC7zkKfkstrwBn167gyI2fTCpbVZazPFLrrcOQpnzD8Xa73ka1NV+9ZYkY1YvQNwEr6NzWAjwWEdd0zz0ArAa2Z/uXA3dExP2DKq5lADSzhhhBAIyInldD3XMPRMRLwNl563YANLPiPBTOzFpp/hlggzkAmllhOXqBa8kB0MwKGvpLziPnAGhmxQQOgGbWYs2+A07KCbKNzhvYhyLiU9m2u4EzsyInAL+KiPU9vrufnNPTmFlztGFC1NvovIj44/kNEfEf5j9L+h5wZJHvXxARh4s20MxqbKkHwIh4RNIneu1T57XrLwH/fsjtMrO6i4DZZt8Dl30G+G+B1yLixT7756enCeAH3bM/LJRNX7MF4BiO5fhN+0o2rZxL16xPLps6FC7PkKY8w+aOTKcNGwTgnvSilu/fAUkTMC0xS/0KcIDNwJ2L7E+eniYLjlMAH9aJzf6tmrVFwwNg4dlgJC0HPg/c3a9M9/Q0wPz0NGa2FAQwF2lLTZWZDusi4LmIONBrZ9HpacysKQJiLm2pqYEBUNKdwM+AMyUdkPT1bNdVLLj9lbRG0nS2uhp4VNLPgceB+1KmpzGzhgg6nSApS02l9AJv7rP9Kz22lZ6exswapOHPAD0SxMyKcwA0s3byZAhm1lYBeDosM2stXwGaWTt5KFwl8mSFyyNXVrYKrJr6WSX15hk2eGR6cJl5eYaBrSLHuU2mF831O6uq3irqnBx/vaUFRI3f8UtRywBoZg1R41EeKRwAzaw4PwM0s1aKcC+wmbWYrwDNrJ2CmJ0ddyNKcQA0s2Lmp8NqMAdAMyuu4a/BlJkP0MxaLICYi6SlDEn/TdLTknZLekBSzzd6JW2U9LykfZKuT6nbAdDMiomRTYj63Yg4K0u9+zfAtxcWkLQMuBm4DFgHbJa0blDFvgU2s8JG0QkSEW91ra6kc/G50AZgXzYPKZLuAq4AnlmsbkUNu7ElvQ78w4LNq4ClmF94qZ4XLN1zWwrn9fGI+GiZCiTdT+d3keIY4Ddd61OLZYnscaz/DnyZTg7yCyLi9QX7vwBsjIj/lK3/CXBORFy3WL21vALs9YeRtCsiJsbRniot1fOCpXtuS/W88oqIjcOqS9JDwMk9dm2NiHsjYiuwVdK3gOuA7yysolcTBx23lgHQzNolIi5KLHoHcB8fDIAHgNO71k8DDg6qzJ0gZlZrktZ2rX4WeK5HsSeAtZLOkHQ0naRtOwbV3aQrwOTnBQ2zVM8Llu65LdXzqqsbJJ0JzNHpG7gGOlkogR9GxKaImJF0HbATWAZsi4i9gyquZSeImdko+BbYzFrLAdDMWqv2AbDI8JamkLRf0i+yIT67xt2eoiRtk3RI0p6ubSdKelDSi9nPj4yzjUX1ObdJSa9kf7fdkjaNs41WXK0DYNHhLQ1zQUSsb/h7ZbcBC98Jux54OCLWAg9n6010Gx88N4C/zP5u6yMiR6YVq5NaB0C6hrdExLvA/PAWq5GIeAR4c8HmK4Dbs8+3A1eOsk3D0ufcbImoewA8FXi5a/1Atm2pCOABSU9K2jLuxgzZ6oh4FSD7edKY2zNs12UzlGxr6u291T8AFhre0iDnRcSn6dzif1PSH4y7QZbkFuB3gfXAq8D3xtoaK6zuAbDQ8JamiIiD2c9DwHY6t/xLxWuSTgHIfh4ac3uGJiJei4jZ6CTF/WuW1t+tVeoeAAsNb2kCSSslHTf/GbgE2LP4txplB3B19vlq4N4xtmWo5gN75nMsrb9bq9R6KFzR4S0NsRrYLgk6f4c7IuL+8TapGEl3AucDqyQdoDNQ/Qbgp5K+Dvw/4Ivja2Fxfc7tfEnr6TyO2Q98Y1zts3I8FM7MWqvut8BmZpVxADSz1nIANLPWcgA0s9ZyADSz1nIANLPWcgA0s9b6/xNdUsQXf5cCAAAAAElFTkSuQmCC" }, "metadata": { "needs_background": "light" } }, { "output_type": "display_data", "data": { "text/plain": [ "
" ], "image/svg+xml": "\n\n\n\n \n \n \n \n 2021-08-31T12:13:54.790527\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 \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n\n", "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/HLGmSBmVkxA1LwX2AHQzPrgAGhmTeVbYDNrLAdAM2ukmReha6ySAfD3zn6bXbv2JpZOLZfT6OCrzJOqVQWfGr0muWxZs5HlSRkrJb1sNEeVJUmdITGPF2Iwr+PW/aW2SgZAM6sJ9wKbWVPJV4Bm1kgVT3NL4QBoZgVVe6SXFA6AZlacrwDNrLGmh92A/jgAmlkxC+A9wHpP6mlmQ6VIW/o6h/QFSfskTUsamaPcAUm/yGag3J1St68Azay4+XkG+DTwWeDmhLIbIuJwasUOgGZWaRHxLEA2uPxAVTIAvvDUkuT0nzyze5U3a9fw6izX3vSio2W1IV2elLHUfzd5/s2U9W8xz2yCqab+8yMDqSfH7e3yWbelYxExNpBG/H8B3C8pgJtT6q9kADSzGgjypMIdjoi5nt89CJza4dD2iLg78RznR8SEpFOAByQ9FxEPz/WBngFQ0g7gMuBQRHwi23cycCfwMeAA8MWI+FWHz24Cvg8sAn4UEdclfhEzq4MBPQOMiIsGUMdE9vOQpJ3AemDOAJjSC3wLsGnWvmuBhyJiDfBQtv1bJC0CbqA1beZaYIuktQnnM7OamI9e4KR2SEslnTCzDlxCq/NkTj0DYHYJ+eas3ZcDt2brtwKf6fDR9cD+iHgpIt4D7sg+Z2YLxTxMiynpCkkHgfOAeyXtyvavkjSeFVsJPCLpSeAx4N6IuK9X3UWfAa6MiFcBIuLV7J57ttXAy23bB4FzC57PzKpoHq7uImInsLPD/glgc7b+EnBO3rrL7ATp9HS0669L0lZgK8DxLCmrTWY2IPN1e1umopkgr0k6DSD7eahDmYPAGW3bpwMT3SqMiLGIGImIkWM4rmCzzGxeTSttqaiiAfAe4Kps/SqgUzf148AaSWdKOha4MvucmS0QVekEKapnAJR0O/Bz4CxJByV9DbgOuFjSi8DF2fZvPZSMiElgG7ALeBb4aUTsK+drmNlQzEMnSJl6PgOMiC1dDl3Yoez7DyWz7XFgfHY5M1sAKn51l6L2mSB7Rm9MLzxaThuGnbZXt3rzqNescOnn3zi2Lk/FyZZt3p9UblG8O5gTOgCaWVOp5gOiejxAM2ssXwGaWXG+BTazRnIniJk1mgOgmTWWA6CZNZGofy+wA6CZFeNngGbWaA6AZtZYDoCDN7l8KYc/l5aGtXFVOW0oJwUrvc48KVh5fgelpItBzvauK6VsHkOfFY70eo/etSK5LKSlwg2Kb4HNrLkcAM2skcK9wGbWZL4CNLOm8jNAM2suB0Aza6SKD3efwgHQzAoR9b8FTpkUaYekQ5Kebtv3HUnPSXpK0k5JJ3X57AFJv5C0V9LuAbbbzCpgwc8KB9wCbJq17wHgExFxNvAC8M05Pr8hItZFxEixJppZZdV8VrieATAiHgbenLXv/mzaS4BHaU16bmZNU/MAOIhngF8F7uxyLID7JQVwc0SMdatE0lZgK8BHVi9On+1tNE9TyzHsWeGOjH88uWyetLkqzApXVhtSy1YhdbCMetdvfDtPAzqbp9tbSd8B/gh4D/gl8JWI+HWHcpuA7wOLgB9FxHW96u5rUiRJ24FJ4CddipwfEZ8ELgW+IekPu9UVEWMRMRIRIyt+Z1E/zTKz+TI/V4A9H7lJWgTcQCvWrAW2SFrbq+LCAVDSVcBlwJ9ERMevmE2UTkQcAnYC64uez8yqR9NpSz8SH7mtB/ZHxEsR8R5wB3B5r7oLBcDsUvMvgE9HRMdraUlLJZ0wsw5cAjzdqayZ1VOOXuDlkna3LVsLnvKrwN912L8aeLlt+2C2b049nwFKuh24gNYXOAh8m9Yl6HHAA5IAHo2IqyWtonXvvRlYCezMji8GbouI+3qdz8xqIt/t7eG53gSR9CBwaodD2yPi7qzMXI/c1KWFc+oZACNiS4fdf9Wl7ASwOVt/CTinV/1mVmMD6gSJiIvmOt72yO3CLo/cDgJntG2fDkz0Oq8zQcyskPnKBGl75Pbvuz1yAx4H1kg6E3gFuBL4415199ULbGbNpulIWvp0PXACrUdueyXdBCBplaRxgKyTZBuwC3gW+GlE7OtVsa8AzayYeXrJOSI6vuja/sgt2x4HxvPU7QBoZoVVOc83hQOgmRXnADh4z0ys4FOj1ySVLSsFa6HOCpdHnt9tvpSxPHLUO1pSExINewY7SP+bvRBvFG3Ob/EVoJk1lwOgmTWSZ4Uzs6ZaCCNCOwCaWXGdx0GpDQdAMyvMV4Bm1kwVH+05hQOgmRXmThAzaywHQDNrpsCdIGXQhyc55jOvpxXuOs1Sf/K81Z/nTf1UZU2KtGzz/iLN6Sk1cwfyfbeyJkVKrbduf4f55k4QM2suB0Aza6KF8CJ0zwFRJe2QdEjS0237RiW9kg1OuFfS5i6f3STpeUn7JV07yIab2ZBF2mCoAxgQtTQpI0LfAmzqsP97EbEuWz4wCGHReTrNrEbmZ17g0vQMgBHxMPBmgboLzdNpZvWRY1rMSupnTpBtkp7KbpE/3OF4rnk6JW2dmTN08ki3eU/MrDICmI60paKKBsAbgd8F1gGvAt/tUCbXPJ0RMRYRIxExsnjZkoLNMrN5VfNb4EK9wBHx2sy6pB8Cf9uhWKF5Os2sPqp8e5ui0BWgpNPaNq8Anu5Q7P15OiUdS2ueznuKnM/MqqnuvcA9rwAl3Q5cACyXdBD4NnCBpHW0Lm4PAF/Pyq4CfhQRmyNiUtLMPJ2LgB0p83SaWU1U/PY2haKCuXwn6uQ4VxcmlS1vMp50qWlzZaV15VGF39dClSd9cth/h/UbX2b3k+90ek6f7MQTT4+Rc7cllf37B7+5JyJG+jlfGZwJYmbFeTQYM2sqVfAOMg8HQDMrZgE8A3QANLOC5qeHV9J3gD8C3gN+CXwlIn7dodwB4DfAFDCZ8syxn0wQM2u6iLSlPw8An4iIs4EXgG/OUXZDNj5BUoeLA6CZFZNNjJ6y9HWaiPsjYjLbfJRWUsVAOACaWXHzcwXY7qvA33VrDXC/pD2StqZU5meAZlZcemxbLml32/ZYRLw/oYWkB4FTO3xue0TcnZXZDkwCP+lyjvMjYkLSKcADkp7LRrPqygHQzArTdPL97eG5nstFxEVznke6CrgMuDC6ZG9ExET285CknbSG5JszAPoW2MyKCVovQqcsfZC0CfgL4NMR0XGsPElLJZ0wsw5cQucxCn5LJa8AJ5cv5fDn0tLGNq5Kr7es9KP0enOcfzS9aJ4UrIU6e1tZ9ZY1K1yef7dl/A5eiDfSG9CFiPl6Efp64Dhat7UAj0bE1e1jDwArgZ3Z8cXAbRFxX6+KKxkAzawm5iEARkTH/1myW97N2fpLwDl563YANLPinApnZo008wywxhwAzaywHL3AleQAaGYFDfwl53nnAGhmxQQOgGbWYPW+A06aE2QHrTewD0XEJ7J9dwJnZUVOAn4dEes6fPYAOYenMbP6aMKAqLfQehHxxzM7IuI/zqxL+i5wZI7Pb4iIw0UbaGYVttADYEQ8LOljnY6p9dr1F4H/MOB2mVnVRcBUve+B+30G+O+A1yLixS7HZ4anCeDm9tEfZsuGr9kK8JHVi9kzemNaC0bzNDddnvSyVGWldeVJwTqG15PL0vWvZZ0cvWtFjtL7S2vHvFroV4A9bAFun+N48vA0WXAcAxg55/h6/1bNmqLmAbDwaDCSFgOfBe7sVqZ9eBpgZngaM1sIApiOtKWi+hkO6yLguYg42Olg0eFpzKwuAmI6bamongFQ0u3Az4GzJB2U9LXs0JXMuv2VtErSeLa5EnhE0pPAY8C9KcPTmFlNBK1OkJSlolJ6gbd02f/lDvv6Hp7GzGqk5s8AnQliZsU5AJpZM3kwBDNrqgA8HJaZNZavAM2smeqfCqcuU2wO1ZIVZ8RZn/uvA683T3pZHmXNNpcqT9penrS5ZZvT07WG/TuwfNZvfJndT76jfupYtnhFnHfSFUlld73xwz1VHA3KV4BmVlyFszxSOACaWXEVvIPMwwHQzIqJcC+wmTWYrwDNrJmCmJoadiP64gBoZsXMDIdVYw6AZlZchYe6StHPeIBm1mABxHQkLf2Q9D8kPSVpr6T7Ja3qUm6TpOcl7Zd0bUrdDoBmVkzM24Co34mIs7Opd/8W+NbsApIWATcAlwJrgS2S1vaq2LfAZlbYfHSCRMRbbZtLaV18zrYe2J+NQ4qkO4DLgWfmqruSqXCSXgf+adbu5cBCnF94oX4vWLjfbSF8r49GRJ5p7D5A0n20fhcpjgfeadsem2uWyA7n+p/Al2jNQb4hIl6fdfzzwKaI+E/Z9p8C50bEtrnqreQVYKc/jKTdVcwl7NdC/V6wcL/bQv1eeUXEpkHVJelB4NQOh7ZHxN0RsR3YLumbwDbg27Or6NTEXuetZAA0s2aJiIsSi94G3MsHA+BB4Iy27dOBiV6VuRPEzCpN0pq2zU8Dz3Uo9jiwRtKZko6lNWnbPb3qrtMVYPLzgppZqN8LFu53W6jfq6quk3QWME2rb+BqaM1CCfwoIjZHxKSkbcAuYBGwIyL29aq4kp0gZmbzwbfAZtZYDoBm1liVD4BF0lvqQtIBSb/IUnx2D7s9RUnaIemQpKfb9p0s6QFJL2Y/PzzMNhbV5buNSnol+7vtlbR5mG204iodAIumt9TMhohYV/P3ym4BZr8Tdi3wUESsAR7KtuvoFj743QC+l/3d1kXE+Dy3yQak0gGQtvSWiHgPmElvsQqJiIeBN2ftvhy4NVu/FfjMfLZpULp8N1sgqh4AVwMvt20fzPYtFAHcL2mPpK3DbsyArYyIVwGyn6cMuT2Dti0boWRHXW/vrfoBsFB6S42cHxGfpHWL/w1JfzjsBlmSG4HfBdYBrwLfHWprrLCqB8BC6S11ERET2c9DwE5at/wLxWuSTgPIfh4acnsGJiJei4ipiJgGfsjC+rs1StUDYKH0ljqQtFTSCTPrwCXA03N/qlbuAa7K1q8C7h5iWwZqJrBnrmBh/d0apdKpcEXTW2piJbBTErT+DrdFxH3DbVIxkm4HLgCWSzpIK1H9OuCnkr4G/F/gC8NrYXFdvtsFktbRehxzAPj6sNpn/XEqnJk1VtVvgc3MSuMAaGaN5QBoZo3lAGhmjeUAaGaN5QBoZo3lAGhmjfX/AL55Y4xtZxrJAAAAAElFTkSuQmCC" }, "metadata": { "needs_background": "light" } }, { "output_type": "display_data", "data": { "text/plain": [ "
" ], "image/svg+xml": "\n\n\n\n \n \n \n \n 2021-08-31T12:13:55.251665\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", "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+Ti07CpN6DedvvtM3yeTmiUVLDUJDUMBQkNQwFSQ1DQVLDUJDUMBQkNQwFSQ1DQVLDUJDUmPvZnCc1i/BKzPKQ1eVmYdbledrvLHy2q/077pWCpIahIKlhKEhqGAqSGoaCpIahIKlhKEhqHMkcjTcDVwL7q+qt3bqvAud2TU4C/reqNg147dPAT4FfAQeqavNYei1pYo5k8NItwPXAlw6uqKo/O/g8yWeAFw7x+ouq6sejdlDS6jqSiVvvTfI7g7YlCfCnwB+OuV+SpqTvMOffB56rqieHbC/griQFfL6qtg/bUZJtwDaAs9cfxa7de3p2rZ9JDC1dyT41G34TP7O+oXA1cNshtl9QVfuSnArcneSxrmDta3SBsR1g83nHDS0vJ2myRv72IclRwB8DXx3WpqsDQVXtB3YwuLycpBnS5yvJPwIeq6qFQRuTnJDkxIPPgUsYXF5O0gw5bCh0ZeO+A5ybZCHJB7tNW1l265DkjCQHK0KdBnw7yQPA94FvVtWd4+u6pEkYtWwcVfWXA9a9Wjauqp4CzuvZP0mrzBGNkhqGgqSGoSCpYShIahgKkhqpmr3Bg6/LyXV+Lp52N47YtGf8nYWhuNN+D7QyWy59ht0P/CKDtnmlIKlhKEhqGAqSGoaCpIahIKlhKEhqGAqSGoaCpIahIKlhKEhqzOQw5yT/A/xw2epTgLVYP2Ktnhes3XNbC+f15qp646ANMxkKgyTZvRYrTK3V84K1e25r9bwO8vZBUsNQkNSYp1AYWl1qzq3V84K1e25r9byAOfqbgqTVMU9XCpJWgaEgqTHzoZDksiSPJ9mb5Lpp92eckjyd5KEke5LsnnZ/RpXk5iT7kzy8ZN3JSe5O8mT3+Ppp9nFUQ87tU0l+1H1ue5JcMc0+jttMh0KSdcANwOXARuDqJBun26uxu6iqNs359963AJctW3cdcE9VbQDu6Zbn0S289twAPtt9bpuqaueA7XNrpkOBxSrVe6vqqap6BbgduGrKfdIyVXUv8Pyy1VcBt3bPbwXes5p9Gpch57amzXoorAeeWbK80K1bKwq4K8kPkmybdmfG7LSqehagezx1yv0Zt2uTPNjdXszlrdEwsx4Kg6agXkvfoV5QVW9n8fboo0n+YNod0hG5EXgLsAl4FvjMVHszZrMeCgvAWUuWzwT2TakvY9dV6aaq9gM7WLxdWiueS3I6QPe4f8r9GZuqeq6qflVVvwa+wNr63GY+FO4DNiQ5J8kxwFbgjin3aSySnJDkxIPPgUuAhw/9qrlyB3BN9/wa4BtT7MtYHQy7zntZW58bR027A4dSVQeSXAvsAtYBN1fVI1Pu1ricBuxIAoufw1eq6s7pdmk0SW4DLgROSbIAfBL4NPC1JB8E/hv4k+n1cHRDzu3CJJtYvJV9GvjQtPo3CQ5zltSY9dsHSavMUJDUMBQkNQwFSQ1DQVLDUJDUMBQkNf4f290COkby7EcAAAAASUVORK5CYII=" }, "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", "execution_count": 30, "source": [ "get_database(\"de\")['ore']" ], "outputs": [ { "output_type": "execute_result", "data": { "text/plain": [ "{'word': 'Ore',\n", " 'senses': ['Münze, die in Dänemark, Norwegen und Schweden verwendet wird'],\n", " 'synonyms': [],\n", " 'antonyms': [],\n", " 'num_translations': 10}" ] }, "metadata": {}, "execution_count": 30 } ], "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 }