examples/domino_tiling.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Замощение доминошками\n",
    "Есть старая известная задача: можно ли разрезать шахматную доску без двух противоположных по диагонали углов на \"доминошки\" -- фигурки, состоящие из двух клеток с общей стороной?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "from matplotlib import colors as mcolors\n",
    "colors = dict(mcolors.BASE_COLORS, **mcolors.CSS4_COLORS)\n",
    "\n",
    "# Sort colors by hue, saturation, value and name.\n",
    "by_hsv = sorted((tuple(mcolors.rgb_to_hsv(mcolors.to_rgba(color)[:3])), name)\n",
    "                for name, color in colors.items())\n",
    "names = [name for hsv, name in by_hsv if name not in {'black', 'k', 'w', 'white', 'crimson', 'royalblue', 'limegreen', 'yellow', 'orange'}]\n",
    "import random\n",
    "random.shuffle(names)\n",
    "names = ['crimson', 'royalblue', 'limegreen', 'yellow', 'orange', *names]\n",
    "names.append('red')\n",
    "names.append('white')\n",
    "names.append('black')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fill_cell(i, j, color, ax):\n",
    "    ax.fill([i, i, i + 1, i + 1, i], [j, j + 1, j + 1, j, j], color=color)\n",
    "\n",
    "def draw_filling(filling, colors=None):\n",
    "    if filling is not None:\n",
    "        n = len(filling)\n",
    "        m = len(filling[0])\n",
    "        fig = plt.figure(figsize=(m * 0.75, n * 0.75))\n",
    "        \n",
    "        ax = fig.add_axes([0, 0, 1, 1])\n",
    "        ax.get_xaxis().set_visible(False)\n",
    "        ax.get_yaxis().set_visible(False)      \n",
    "        \n",
    "        for name, spine in ax.spines.items():\n",
    "            spine.set_visible(False)\n",
    "            spine.set_visible(False)\n",
    "        \n",
    "        for i, row in enumerate(filling):\n",
    "            i = n - i - 1\n",
    "            for j, cell in enumerate(row):\n",
    "                fill_cell(j, i, names[cell], ax)\n",
    "\n",
    "        for i in range(n + 1):\n",
    "            ax.plot([0, m], [i, i], color='black')\n",
    "        for i in range(m + 1):\n",
    "            ax.plot([i, i], [0, n], color='black')\n",
    "        plt.close(fig)\n",
    "        return fig\n",
    "    else:\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAb4AAAG+CAYAAADsjWHpAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy86wFpkAAAACXBIWXMAAAsTAAALEwEAmpwYAAAL30lEQVR4nO3dMW4i2xqF0R/LkYUg6oyQAVAzYOgwglsDeKEh6QhMavMCx2C5qa467r1WeqSqg3fwCaFWz67XawFAiqepLwAAYxI+AKIIHwBRhA+AKMIHQBThAyDK8xfn/q0DAD/R7NaBb3wARBE+AKIIHwBRhA+AKMIHQBThAyCK8AEQRfgAiCJ8AEQRPgCiCB8AUYQPgCjCB0AU4QMgivABEEX4AIgifABE+ep/YB9M13X1+/fvWq/XY71ycP/73/+qqnyGifkMbfAZ2vAvfIaqz8/x69ev+u+///76u0YL3+/fv+tyPFYdDmO9cnCXqqrFYuprPORyudT5fK7DD96hqmphhybYoQ0/fYeqzy3GMlr41ut11eFQu7Fe+Bdsq6q6rna73bQXecB2u639fj/1NR7W2aEJdmjDT9+h6nOLsfiND4AowgdAFOEDIIrwARBF+ACIInwARBE+AKIIHwBRhA+AKMIHQBThAyCK8AEQRfgAiCJ8AEQRPgCiCB8AUYQPgCjCB0AU4QMgivABEEX4AIgifABEET4AoggfAFGED4AowgdAFOEDIIrwARBF+ACIInwARBE+AKIIHwBRhA+AKMIHQBThAyCK8AEQRfgAiCJ8AEQRPgCiCB8AUYQPgCjCB0AU4QMgivABEEX4AIgifABEET4Aosyu1+u987uH37FarepyONRmqAdOoK+qWi5rs9lMe5EH9H1fp9Np6ms8bGmHJtihDT99h6rPLebzeb2+vg71yNnNg1HD9/ZWm64b6pGj6/u+zudzffE3a95isajODpOzQxvs0I6np6d6f38f6nE3w/c81Bu+sl6vq6pqt9uN9crBbbfb2u/3U1/jYV3X2aEBdmiDHdrx8fExynv8xgdAFOEDIIrwARBF+ACIInwARBE+AKIIHwBRhA+AKMIHQBThAyCK8AEQRfgAiCJ8AEQRPgCiCB8AUYQPgCjCB0AU4QMgivABEEX4AIgifABEET4AoggfAFGED4AowgdAFOEDIIrwARBF+ACIInwARBE+AKIIHwBRhA+AKMIHQBThAyCK8AEQRfgAiCJ8AEQRPgCiCB8AUYQPgCjCB0AU4QMgivABEEX4AIgifABEET4Aosyu1+u987uH37FarepyudRmsxnqkaPr+75Op9PU13jYcrm0QwPs0AY7tOWLJn3H7ObBmOE7Ho9DfqhJLBaL6rpu6mv8sb7v63w+22FidmiDHdrR9329vLzU8Xgc6pE3w/c81Bu+sl6v63A4jPW6v6brutrtdlNf449tt9va7/dTX+NhdmiDHdrw03eo+txiLH7jAyCK8AEQRfgAiCJ8AEQRPgCiCB8AUYQPgCjCB0AU4QMgivABEEX4AIgifABEET4AoggfAFGED4AowgdAFOEDIIrwARBF+ACIInwARBE+AKIIHwBRhA+AKMIHQBThAyCK8AEQRfgAiCJ8AEQRPgCiCB8AUYQPgCjCB0AU4QMgivABEEX4AIgifABEET4AoggfAFGED4AowgdAFOEDIIrwARBF+ACIInwARBE+AKIIHwBRZtfr9d753cPvWK1WdTgchnrcZJbLZW02m6mv8cf6vq/T6TT1NR5mhzbYoQ0/fYeqzy3m83m9vr4O9cjZzYMxw/f29lZd1w31yNH1fV/n87m++Js1b7FY2KEBdmiDHdrx9PRU7+/vQz3uZvieh3rDV9brdVVV7Xa7sV45uO12W/v9fuprPKzrOjs0wA5tsEM7Pj4+RnmP3/gAiCJ8AEQRPgCiCB8AUYQPgCjCB0AU4QMgivABEEX4AIgifABEET4AoggfAFGED4AowgdAFOEDIIrwARBF+ACIInwARBE+AKIIHwBRhA+AKMIHQBThAyCK8AEQRfgAiCJ8AEQRPgCiCB8AUYQPgCjCB0AU4QMgivABEEX4AIgifABEET4AoggfAFGED4AowgdAFOEDIIrwARBF+ACIInwARBE+AKIIHwBRhA+AKMIHQJTZ9Xq9d3738DtWq1VdLpfabDZDPXJ0fd/X6XSa+hoPWy6XdmiAHdpgh7Z80aTvmN08GDN8x+NxyA81icViUV3XTX2NP9b3fZ3PZztMzA5tsEM7+r6vl5eXOh6PQz3yZvieh3rDV9brdR0Oh7Fe99d0XVe73W7qa/yx7XZb+/1+6ms8zA5tsEMbfvoOVZ9bjMVvfABEET4AoggfAFGED4AowgdAFOEDIIrwARBF+ACIInwARBE+AKIIHwBRhA+AKMIHQBThAyCK8AEQRfgAiCJ8AEQRPgCiCB8AUYQPgCjCB0AU4QMgivABEEX4AIgifABEET4AoggfAFGED4AowgdAFOEDIIrwARBF+ACIInwARBE+AKIIHwBRhA+AKMIHQBThAyCK8AEQRfgAiCJ8AEQRPgCiCB8AUYQPgCjCB0AU4QMgyux6vd47v3v4HavVqg6Hw1CPm8xyuazNZjP1Nf5Y3/d1Op2mvsbD7NAGO7Thp+9Q9bnFfD6v19fXoR45u3kwZvje3t6q67qhHjm6vu/rfD7XF3+z5i0WCzs0wA5tsEM7np6e6v39fajH3Qzf81Bv+Mp6va6qqt1uN9YrB7fdbmu/3099jYd1XWeHBtihDXZox8fHxyjv8RsfAFGED4AowgdAFOEDIIrwARBF+ACIInwARBE+AKIIHwBRhA+AKMIHQBThAyCK8AEQRfgAiCJ8AEQRPgCiCB8AUYQPgCjCB0AU4QMgivABEEX4AIgifABEET4AoggfAFGED4AowgdAFOEDIIrwARBF+ACIInwARBE+AKIIHwBRhA+AKMIHQBThAyCK8AEQRfgAiCJ8AEQRPgCiCB8AUYQPgCjCB0AU4QMgivABEEX4AIgyu16v987vHn7HarWqy+VSm81mqEeOru/7Op1OU1/jYcvl0g4NsEMb7NCWL5r0HbObB2OG73g8DvmhJrFYLKrruqmv8cf6vq/z+WyHidmhDXZoR9/39fLyUsfjcahH3gzf81Bv+Mp6va7D4TDW6/6arutqt9tNfY0/tt1ua7/fT32Nh9mhDXZow0/foepzi7H4jQ+AKMIHQBThAyCK8AEQRfgAiCJ8AEQRPgCiCB8AUYQPgCjCB0AU4QMgivABEEX4AIgifABEET4AoggfAFGED4AowgdAFOEDIIrwARBF+ACIInwARBE+AKIIHwBRhA+AKMIHQBThAyCK8AEQRfgAiCJ8AEQRPgCiCB8AUYQPgCjCB0AU4QMgivABEEX4AIgifABEET4AoggfAFGED4AowgdAFOEDIIrwARBF+ACIInwARJldr9d753cPv2O1WtXhcBjqcZNZLpe12WymvsYf6/u+TqfT1Nd4mB3aYIc2/PQdqj63mM/n9fr6OtQjZzcPxgzf29tbdV031CNH1/d9nc/n+uJv1rzFYmGHBtihDf/CDnU+1+aH79BX1fzpqV7f34d65M3wPQ/1hq+s1+uqqtrtdmO9cnDb7bb2+/3U13hY13V2aIAd2vAv7FD7fe2mvsiDtlVVHx+jvMtvfABEET4AoggfAFGED4AowgdAFOEDIIrwARBF+ACIInwARBE+AKIIHwBRhA+AKMIHQBThAyCK8AEQRfgAiCJ8AEQRPgCiCB8AUYQPgCjCB0AU4QMgivABEEX4AIgifABEET4AoggfAFGED4AowgdAFOEDIIrwARBF+ACIInwARBE+AKIIHwBRhA+AKMIHQBThAyCK8AEQRfgAiCJ8AEQRPgCiCB8AUYQPgCjCB0AU4QMgyux6vd47v3v4HavVqi6XS202m6EeObq+7+t0Ok19jYctl0s7NMAObfgXdqjTqTZTX+RBfVXNq+r1fpO+Y3brYLRvfL9+/ar5fD7W6/6K+XxeT08//0vyy8vL1Fd4iB3aYIc2zOfzmv8DO8yr6tfz8yjvGu0bHwCMaPpvfADQAuEDIIrwARBF+ACIInwARBE+AKIIHwBRhA+AKMIHQBThAyCK8AEQRfgAiCJ8AEQRPgCiCB8AUYQPgCjCB0AU4QMgyvMX5zf/63YA+Il84wMgivABEEX4AIgifABEET4AoggfAFH+D8UMVYbQYxgGAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x432 with 1 Axes>"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "filling = [[-1 if (i + j) % 2 == 0 else -2 for j in range(8)] for i in range(8)]\n",
    "filling[0][0] = -3\n",
    "filling[7][7] = -3\n",
    "draw_filling(filling)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAHoAAABECAYAAABOKSE5AAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy86wFpkAAAACXBIWXMAAAsTAAALEwEAmpwYAAABbklEQVR4nO3dMY6CQBhA4V+ylSFSTUfJAfQGHt0b4AEokYbW3i22chPCjppFfO9rJ5P85DFEG9jcbrfQ5yuWHkD/w9AQhoYwNIShIQwN8TWz7n+vddlMLcyFvnM4HGIcx2ia5vmRFtJ1XUTE6q8hpRRt2/55T1bocRxjGIa4XC7Zw72T3W639AhPuV6v2XuyQjdNs/rIET9PptPptPQYDzsej9l7/DEGYWgIQ0MYGsLQEIaGMDSEoSEMDWFoCENDGBrC0BCGhjA0hKEhDA1haAhDQxgawtAQhoYwNIShIQwNYWgIQ0MYGsLQEIaGMDSEoSEMDWFoCENDGBrC0BCGhjA0hKEhDA1haAhDQxgawtAQhobYzHzg7G6xruuPeI1zVVWx3++XHuNh5/M5yrKMvu9/L02+gT/rRKeUoijW/xDYbrdLj/CUsiwjpZS1J+tE6+295kRrveY+tTB5h2hdPNEQhoYwNIShIQwNYWiIb4dyNCTg7Xq2AAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 108x54 with 1 Axes>"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "domino = [[-1, -2]]\n",
    "draw_filling(domino)\n",
    "# а вот и сама доминошка"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Сделать это невозможно, и этому есть красивое и простое объяснение:\n",
    "* На оставшейся части доски 30 черных и 32 белых клетки\n",
    "* Каждая доминошка состоит из одной черной и одной белой клетки\n",
    "* Как бы мы не разрезали фигуру на доминошки, в итоге на доминошках будет равное число белых и черных клеток"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Давайте теперь разберем несколько методов, как можно:\n",
    "* Понять, можно ли разрезать произвольную фигуру, составленную из клеток на плоскости, и если можно, то как\n",
    "* Посчитать количество возможных вариантов разрезать, фигуру если существует хотя бы одно\n",
    "\n",
    "## Динамическое программирование по профилю\n",
    "\n",
    "Более подробно про этот подход написано [здесь](https://neerc.ifmo.ru/wiki/index.php?title=Динамическое_программирование_по_профилю), лично мне больше по душе <b>изломанный профиль</b>, про него и расскажу. Основной идеей динамического программирования является использование рекуррентных зависимостей функций, например одно из самых простых применений динамического программирования -- это подсчет чисел Фибоначчи, для которых справедливо соотношение\n",
    "\\begin{align*}\n",
    "F_0&=F_1=1\\\\\n",
    "F_{n+1}&=F_n+F_{n-1}\n",
    "\\end{align*}\n",
    "Для подсчета $F_{100}$ мы можем последовательно вычислить все $F_i$ вплоть до $F_{100}$, просто последовательно применяя это рекуррентное соотношение. Чуть более сложный пример -- вычисление числа сочетаний, для которых справедливо\n",
    "\\begin{align*}\n",
    "C_n^0&=1\\\\\n",
    "C_n^k&=\\frac{n}{k}C_{n-1}^{k-1} \\\\\n",
    "C_n^k&=C_{n-1}^k+C_{n-1}^{k-1}\n",
    "\\end{align*}\n",
    "В зависимости от задачи мы можем использовать одно из двух рекуррентных соотношений, в первом мы точно также как и с числами Фибоначчи последовательно вычисляем сочетания. Во втором же случае у нас появляется зависимость с двумя параметрами, но ситуация принципиально не изменяется: мы просто вычисляем в порядке увеличения $n$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "              1              \n",
      "             1 1             \n",
      "            1 2 1            \n",
      "           1 3 3 1           \n",
      "          1 4 6 4 1          \n",
      "        1 5 10 10 5 1        \n",
      "      1 6 15 20 15 6 1       \n",
      "     1 7 21 35 35 21 7 1     \n",
      "   1 8 28 56 70 56 28 8 1    \n",
      " 1 9 36 84 126 126 84 36 9 1 \n"
     ]
    }
   ],
   "source": [
    "C = [[1]]\n",
    "for n in range(1, 10):\n",
    "    C.append([1]) # C[n][0] == 1\n",
    "    for k in range(1, n):\n",
    "        C[n].append(C[n - 1][k - 1] + C[n - 1][k])\n",
    "    C[n].append(1)\n",
    "        \n",
    "# Дальнейший код просто чтобы вывести в виде треугольника Паскаля\n",
    "def total_len(ints):\n",
    "    return len(ints) + sum(map(len, map(str, ints))) - 1\n",
    "\n",
    "def print_padded(ints, width):\n",
    "    pad_len = width - total_len(ints)\n",
    "    print(''.join([' ' for i in range(pad_len // 2)]), ' '.join(map(str, ints)), ''.join([' ' for i in range((pad_len + 1) // 2)]))\n",
    "\n",
    "width = total_len(C[-1])\n",
    "for row in C:\n",
    "    print_padded(row, width)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Для замощения доминошками ситуация к сожалению гораздо сложние, как ни крути, но простого рекуррентного соотношения для функции \"Каким числом способов можно замостить доминошками доску размера $n\\times m$\" не существует, тут надо что-нибудь придумывать. Здесь общая идея заключается примерно в следующем: давайте рассматрим следующую фигуру, состоящую из первых $k-1$ строк длины $m$ и каких-то клеточек на строке $k$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAb4AAAG+CAYAAADsjWHpAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy86wFpkAAAACXBIWXMAAAsTAAALEwEAmpwYAAAI2UlEQVR4nO3dMWpbWxRA0avgKoikcqfyDUCagYfujCAagEqTJlWC2kS/CJ9UsjFf/0r2Xqu98M47EGlzEcGr0+k0AKDiw7VfAABmEj4AUoQPgBThAyBF+ABIET4AUu5eOPd/HQB4i1bnDtz4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEh56S+wX8xutxvfv38fy7LMGnlxh8NhjDHscGV2uA12uA3vYYcx/uxxf38/vn79+r/PWp1Op+fOnz18jc1mM759+zZemAdA1IcPH8avX78u9bjV2TmXmvCSZVlED4Czfv/+PWWO3/gASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4CUaeE7HA6zRgHAWW58AKRMC9+yLLNGAcBZbnwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnTwnc4HGaNAoCz3PgASJkWvmVZZo0CgLPc+ABIET4AUoQPgBThAyBF+ABIET4AUoQPgBThAyBF+ABIET4AUoQPgBThAyBF+ABIET4AUoQPgBThAyBF+ABIET4AUoQPgBThAyBF+ABIET4AUoQPgBThAyBF+ABIET4AUoQPgBThAyBF+ABIET4AUoQPgBThAyBF+ABIET4AUoQPgBThAyBF+ABIET4AUoQPgBThAyBF+ABIET4AUoQPgBThAyBF+ABIET4AUqaF73A4zBoFAGe58QGQMi18y7LMGgUAZ7nxAZAifACkCB8AKcIHQIrwAZAifACkCB8AKcIHQIrwAZAifACkCB8AKcIHQIrwAZAifACkCB8AKcIHQIrwAZAifACkCB8AKcIHQIrwAZAifACkCB8AKcIHQIrwAZAifACkCB8AKcIHQIrwAZAifACkCB8AKcIHQIrwAZAifACkCB8AKcIHQIrwAZAifACkCB8AKcIHQIrwAZAifACkCB8AKcIHQIrwAZAifACkTAvf4XCYNQoAznLjAyBlWviWZZk1CgDOcuMDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEiZFr7D4TBrFACcdTdz2KdPn8Zut5s58qL2+/34+fPnOJ1O134VuAnv4TM9xhjb7faq7/Ff+F56vWnhW5ZljDHG4+PjrJEX9/DwML58+XLt14Cbsdvt3vxnegzfSzV+4wMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASFmdTqfnzp89fI3NZjOOx+PYbreXeuR0+/1+/Pjx49qvATfj8+fPb/4zPcZ48zu8p++lF5r0GqtzB3eXmlDhg359drgN/+7A9b3176Ux/vx7+vjx45RZ08K3LMsYY4zHx8dZIy/u4eFhjGGHa7PDbbDDbXgPO4zxd48Z/MYHQIrwAZAifACkCB8AKcIHQIrwAZAifACkCB8AKcIHQIrwAZAifACkCB8AKcIHQIrwAZAifACkCB8AKcIHQIrwAZAifACkCB8AKcIHQIrwAZAifACkCB8AKcIHQIrwAZAifACkCB8AKcIHQIrwAZAifACkCB8AKcIHQIrwAZAifACkCB8AKcIHQIrwAZAifACkCB8AKcIHQIrwAZAifACkCB8AKcIHQIrwAZCyOp1Oz50/e/gam81mHI/Hsd1uL/XI6fb7/Rhj2OHK7HAb7HAb3sMOY/zZY71ej6enp0s9cnXuwI0PgJS7WYOWZRljjPH4+Dhr5MU9PDyMMexwbXa4DXa4De9hhzH+7jGDGx8AKcIHQIrwAZAifACkCB8AKcIHQIrwAZAifACkCB8AKcIHQIrwAZAifACkCB8AKcIHQIrwAZAifACkCB8AKcIHQIrwAZAifACkCB8AKcIHQIrwAZAifACkCB8AKcIHQIrwAZAifACkCB8AKcIHQIrwAZAifACkCB8AKcIHQIrwAZAifACkCB8AKcIHQIrwAZAifACkCB8AKcIHQIrwAZAifACkCB8AKcIHQMrqdDo9d/7s4WtsNptxPB7Hdru91COn2+/3Y4xhhyuzw22ww214DzuM8WeP9Xo9np6eLvXI1bmDu0tNeMn9/f2sUf+b9Xp97Vf4z+xwG+xwG+xwO9br9bROTLvxAcBEZ298fuMDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEi5e+H87J9uB4C3yI0PgBThAyBF+ABIET4AUoQPgBThAyDlH5asDfH+Cz46AAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x432 with 1 Axes>"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fig = [[-1 if i < 5 else (-1 if i == 5 and (random.randint(1, 10) <= 4) else -2) for j in range(8)] for i in range(8)]\n",
    "draw_filling(fig)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Такая фигура однозначно задается тройкой $(k, m, p)$, где $0\\leq p< 2^m$ -- число, двоичное представление которого указывает, какие клетки в последнем ряду используются, а какие нет (это число как раз принято называть <b>профилем</b>). Если обозначить за $f_m(k, p)$ количество способов замостить фигуру с такими параметрами, то оказывается, что \n",
    "$$\n",
    "f_m(k+1, p)=\\sum_{u\\in U(p)}f_m(k, u),\n",
    "$$\n",
    "где $U(p)$ -- это множество профилей, из которых путем замощения остатка строки $k$ можно получить $p$ на следующей строке. Собственно такое представление возможно ровно из-за того, что одна доминошка затрагивает не больше двух строк. С алгоритмической точки зрения $U$ составляется перебором, в любом случае этот вариант профиля мне не очень нравится, о нем можно почитать в первоисточнике. Давайте теперь рассмотрим другой класс фигурок: как и прежде, у нас есть прямоугольник $(k-1)\\times m$, на строке $k$ присутствуют первые $j$ клеток, остальные задаются профилем, на строке $k+1$ первые $j$ клеток задаются профилем, остальные не участвуют"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAb4AAAG+CAYAAADsjWHpAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy86wFpkAAAACXBIWXMAAAsTAAALEwEAmpwYAAAJ7klEQVR4nO3dvW6UZxqA4ceE/A+iiTuXkypI2GfgM0iZY0y5Z+AyHbMFnUuDVoJqDcUiJbMFu0plE/DkmzH3dbWv9D3vo8Hc+hghH2232wGAigf7vgAALEn4AEgRPgBShA+AFOEDIEX4AEh5+IFz/9cBgPvo6KYDb3wApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApHzoN7DvzNnZ2bx69WrW6/VSI3fu8vJyZsYOe2aHw2CHw/A57DDzfo/j4+N59uzZ3z7raLvd3nZ+6+HHODk5mZcvX84H5gEQ9eDBg/n999939bijG+fsasKHrNdr0QPgRn/88ccic3zHB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApCwWvsvLy6VGAcCNvPEBkLJY+Nbr9VKjAOBG3vgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFIWC9/l5eVSowDgRt74AEhZLHzr9XqpUQBwI298AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApi4Xv8vJyqVEAcCNvfACkLBa+9Xq91CgAuJE3PgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AlMXCd3l5udQoALjRw31fALi/vvhyNY+On+z7Gp/s+vXzmZl59MNPe77Jp7t+/Xy+f3c9Z/u+yB1tZua7hWYtFr71ej0vXrxYahywgEfHT+bs51/3fY1P9uwfv8zM3Psdnr78bS72fZE7Ol9wlu/4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBSjrbb7W3ntx5+jJOTk3nx4sWuHgccgC++ejSPfvhp39f4ZNevn8/M3PsdVu+u53TfF7mjzcysZubq9iZ9jKObDh7uasJf8cWXq3l0/GTJkTv1ufyQfP/ues72fZE72MzM2y9Xs7rnf5Y+h89hvjmapz9+veebfLrN2/f/6HXvd/j28czp6b6vcjebzcx33y0yarHwrdfrebv9z5z9/OtSI3fu2T9+mZm59zs8ffnbXOz7IndwPjP/PH7ic9iz85mZs7O5uLjY70Xu4Pz8fGbGDgfg/3sswXd8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApR9vt9rbzWw8/xsnJyfzr1b/n0Q8/7eqRi7t+/Xxm5t7vsHp3Paf7vsgdbGbmzVePfA57tpmZefx4Tk9P93uRO9hsNjMzdjgAm81mVqvVXF1d7eqRRzcdPNzVhL/i+28ezNMfv15y5E5t3r5/Qb73O3z7eOY+/5BsNrMan8Pe/e8vXLhvFgvfer2emZmLi4ulRu7c+fn5zNhh3+xwGOxwGD6HHWb+3GMJvuMDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEg52m63t53fevgxTk5O5s2bN3N6erqrRy5us9nMzNhhz+xwGOxwGD6HHWbe77Farebq6mpXjzy66cAbHwApD5catF6vZ2bm4uJiqZE7d35+PjN22Dc7HAY7HIbPYYeZP/dYgjc+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4CUo+12e9v5rYcf4+TkZN68eTOnp6e7euTiNpvNzIwd9swOh8EOh+Fz2GHm/R6r1Wqurq529cijmw4e7mrChxwfHy816m+zWq32fYU7s8NhsMNhsMPhWK1Wi3VisTc+AFjQjW98vuMDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEh5+IHzG391OwDcR974AEgRPgBShA+AFOEDIEX4AEgRPgBS/gs130gZSBtM7QAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x432 with 1 Axes>"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "n = 8\n",
    "m = 8\n",
    "k = 4\n",
    "j = 4\n",
    "fig = [[-1 if i < k else -2 for j in range(8)] for i in range(8)]\n",
    "profile = [0, 0, 1, 0, 1, 0, 0, 1]\n",
    "for l in range(m):\n",
    "    if l <= j:\n",
    "        fig[k][l] = -1\n",
    "        fig[k + 1][l] = -3 if profile[l] == 1 else 1\n",
    "    else:\n",
    "        fig[k][l] = -3 if profile[l] == 1 else 1\n",
    "    \n",
    "draw_filling(fig)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Фигура соответствует черным и красным клеткам, красные выделены для наглядности, за них отвечает профиль. По сравнению с предыдущими фигурками у нас добавилась одна степени свободы. Давайте побозначим за $g(k, j, m, p)$ количество способо замостить такую фигурку, тогда $g(k, m, m, p)=g(k+1, 0, m, p)$ и при этом $g(k, j, m, p)$ выражется через сумму нескольких $g(k, j - 1, m, \\cdot)$. По большому счету переход от $j$ к $j+1$ -- это три варианта, первый -- поставить вертикальную доминошку, если это возможно"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "4f173956c4514feda29c17e673fe29f2",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "HBox(children=(Button(description='Prev', style=ButtonStyle()), Button(description='Next', style=ButtonStyle()…"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "05aad90f1bfc48588bce3e59d27dfb32",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "interactive(children=(IntSlider(value=0, description='step', max=1), Output()), _dom_classes=('widget-interact…"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import interactive_visualization\n",
    "from interactive_visualization.animation_utils import animate_list\n",
    "\n",
    "fig_vertical_domino = [[-1 if i < k else -2 for j in range(8)] for i in range(8)]\n",
    "profile = [0, 0, 1, 0, 1, 0, 0, 1]\n",
    "for l in range(m):\n",
    "    if l <= j:\n",
    "        fig_vertical_domino[k][l] = -1\n",
    "        fig_vertical_domino[k + 1][l] = -3 if profile[l] == 1 else 1\n",
    "    else:\n",
    "        fig_vertical_domino[k][l] = -3 if profile[l] == 1 else 1\n",
    "fig_vertical_domino[k][j + 1] = -1\n",
    "fig_vertical_domino[k + 1][j + 1] = -3\n",
    "animate_list([draw_filling(fig), draw_filling(fig_vertical_domino)]);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "второй -- поставить горизонтальную доминошку, если это возможно"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "9fd9f09086d2452d84872e1f51373105",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "HBox(children=(Button(description='Prev', style=ButtonStyle()), Button(description='Next', style=ButtonStyle()…"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "e5614b7700394d8982004cb9e89de601",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "interactive(children=(IntSlider(value=0, description='step', max=1), Output()), _dom_classes=('widget-interact…"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "fig_horizontal_domino = [[-1 if i < k else -2 for j in range(8)] for i in range(8)]\n",
    "profile = [0, 0, 1, 0, 1, 0, 0, 1]\n",
    "for l in range(m):\n",
    "    if l <= j:\n",
    "        fig_horizontal_domino[k][l] = -1\n",
    "        fig_horizontal_domino[k + 1][l] = -3 if profile[l] == 1 else 1\n",
    "    else:\n",
    "        fig_horizontal_domino[k][l] = -3 if profile[l] == 1 else 1\n",
    "fig_horizontal_domino[k][j + 1] = -1\n",
    "fig_horizontal_domino[k + 1][j + 1] = 1\n",
    "fig_horizontal_domino[k][j + 2] = -3\n",
    "fig_horizontal_domino[k][j + 1] = -1\n",
    "\n",
    "animate_list([draw_filling(fig), draw_filling(fig_horizontal_domino)]);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Или ничего не ставить, если клетка уже заполнена в профиле"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "9803cf3f40b54eaba36bdd51ab6ffc8c",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "HBox(children=(Button(description='Prev', style=ButtonStyle()), Button(description='Next', style=ButtonStyle()…"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "bd0496a7f9bd4d3eacaa059079fbfbe8",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "interactive(children=(IntSlider(value=0, description='step', max=1), Output()), _dom_classes=('widget-interact…"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "fig_skip = [[-1 if i < k else -2 for j in range(8)] for i in range(8)]\n",
    "profile = [0, 0, 1, 0, 1, 1, 0, 1]\n",
    "for l in range(m):\n",
    "    if l <= j:\n",
    "        fig_skip[k][l] = -1\n",
    "        fig_skip[k + 1][l] = -3 if profile[l] == 1 else 1\n",
    "    else:\n",
    "        fig_skip[k][l] = -3 if profile[l] == 1 else 1\n",
    "fig[k][j + 1] = -3\n",
    "fig_skip[k][j + 1] = -1\n",
    "fig_skip[k + 1][j + 1] = 1\n",
    "\n",
    "\n",
    "animate_list([draw_filling(fig), draw_filling(fig_skip)]);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Очень важным является то, что несложно в эту логику добавить заранее покрытые клетки. Таким образом мы сможем посчитать число способов замощения для произвольной фигуры на плоскости. Давайте собственно попробуем это реализовать. Начнем с шахматной доски"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "tiling = [\n",
    "    '........',\n",
    "    '........',\n",
    "    '........',\n",
    "    '........',\n",
    "    '........',\n",
    "    '........',\n",
    "    '........',\n",
    "    '........',\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def count_tilings(tiling):\n",
    "    n = len(tiling)\n",
    "    m = len(tiling[0])\n",
    "    if ((n + 1) * m * 2 ** m) <= 10000000:\n",
    "        dp = [[[(0 if k != 0 or j != 0 or mask != 0 else 1) for mask in range(2 ** m)] for j in range(m)] for k in range(n + 1)]\n",
    "    for k in range(n):\n",
    "        for j in range(m):\n",
    "            for mask in range(2 ** m):\n",
    "                # Вертикальная доминошка\n",
    "                if k < n - 1 and tiling[k][j] == '.' and tiling[k + 1][j] == '.' and (mask &  (1 << j)) == 0:\n",
    "                    dp[k + ((j + 1) // m)][(j + 1) % m][mask + (1 << j)] += dp[k][j][mask]\n",
    "                # Горизонтальная доминошка\n",
    "                if j < m - 1 and tiling[k][j] == '.' and tiling[k][j + 1] == '.' and (mask & (3 << j)) == 0:\n",
    "                    dp[k + ((j + 1) // m)][(j + 1) % m][mask + (2 << j)] += dp[k][j][mask]\n",
    "                # Клетка занята\n",
    "                if ((1 << j) &  mask) != 0 or tiling[k][j] != '.':\n",
    "                    dp[k + ((j + 1) // m)][(j + 1) % m][(mask | (1 << j)) - (1 << j)] += dp[k][j][mask]\n",
    "    return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "12988816\n"
     ]
    }
   ],
   "source": [
    "dp = count_tilings(tiling)\n",
    "print(dp[8][0][0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Отлично, получили как раз то, что нужно, можно свериться с [соответствующей последовательностью](https://oeis.org/A004003). Заодно можно свериться с числами Фибоначчи (количество способов замостить доминошками полоску $2\\times n$ -- это $n-1$-ое число Фибоначчи)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 1 2 3 5 8 13 21 "
     ]
    }
   ],
   "source": [
    "tiling_fib = [\n",
    "    '..',\n",
    "    '..',\n",
    "    '..',\n",
    "    '..',\n",
    "    '..',\n",
    "    '..',\n",
    "    '..',\n",
    "    '..'\n",
    "]\n",
    "dp = count_tilings(tiling_fib)\n",
    "for i in range(8):\n",
    "    print(dp[i][0][0], end=' ')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ну и давайте проверим для доски с вырезанными клетками"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n"
     ]
    }
   ],
   "source": [
    "tiling_no_corners_opposite = [\n",
    "    '.......#',\n",
    "    '........',\n",
    "    '........',\n",
    "    '........',\n",
    "    '........',\n",
    "    '........',\n",
    "    '........',\n",
    "    '#.......',\n",
    "]\n",
    "dp = count_tilings(tiling_no_corners_opposite)\n",
    "print(dp[8][0][0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Давайте попробуем сделать какое-нибудь замощение, если это возможно. Для это обычно в динамическом программировании используется стандартный способ: пройтись в обратном порядке по тем состояниям, которые привели хотя бы к одному способу замощения."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "def cover_if_possible(tiling, dp=None):\n",
    "    if dp is None:\n",
    "        dp = count_tilings(tiling)\n",
    "    n = len(dp) - 1\n",
    "    m = len(dp[0])\n",
    "    if dp[n][0][0] == 0:\n",
    "        return None\n",
    "    \n",
    "    result = [[-1 if tiling[i][j] == '#' else 0 for j in range(m)] for i in range(n)]\n",
    "    num = 0\n",
    "    \n",
    "    k = n\n",
    "    j = 0\n",
    "    mask = 0\n",
    "    \n",
    "    while k > 0 or j > 0:\n",
    "        #print(k, j, mask)\n",
    "        prev_j = j - 1\n",
    "        prev_k = k\n",
    "        if prev_j == -1:\n",
    "            prev_j += m\n",
    "            prev_k -= 1\n",
    "        \n",
    "        # Начинаем перебирать варианты, каким образом мы могли попасть в i, j, mask\n",
    "        # Этот вариант очень не оптимален, но занимает меньше кода и все равно быстрее \n",
    "        # самого подсчета динамики\n",
    "        for prev_mask in range(2 ** m):\n",
    "            if prev_k < n - 1 and tiling[prev_k][prev_j] == '.' and tiling[prev_k + 1][prev_j] == '.' and \\\n",
    "                (prev_mask & (1 << prev_j)) == 0 and (prev_mask + (1 << prev_j)) == mask and dp[prev_k][prev_j][prev_mask] != 0:\n",
    "                mask = prev_mask\n",
    "                result[prev_k][prev_j] = num\n",
    "                result[prev_k + 1][prev_j] = num\n",
    "                #print(f'Vertical at ({prev_k}, {prev_j}) ({prev_k + 1}, {prev_j})')\n",
    "                num += 1\n",
    "                break\n",
    "            elif prev_j < m - 1 and tiling[prev_k][prev_j] == '.' and tiling[prev_k][prev_j + 1] == '.' and (prev_mask & (3 << prev_j)) == 0 and \\\n",
    "                prev_mask + (2 << prev_j) == mask and dp[prev_k][prev_j][prev_mask] != 0:\n",
    "                mask = prev_mask\n",
    "                result[prev_k][prev_j] = num\n",
    "                result[prev_k][prev_j + 1] = num\n",
    "                #print(f'Horisontal at ({prev_k}, {prev_j}) ({prev_k}, {prev_j + 1})')\n",
    "                num += 1\n",
    "                break\n",
    "            elif (((1 << prev_j) & prev_mask) != 0 or tiling[prev_k][prev_j] != '.') and \\\n",
    "                (prev_mask | (1 << prev_j)) - (1 << prev_j) == mask and dp[prev_k][prev_j][prev_mask] != 0:\n",
    "                mask = prev_mask\n",
    "                break\n",
    "        \n",
    "        j = prev_j\n",
    "        k = prev_k\n",
    "    \n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAb4AAAG+CAYAAADsjWHpAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy86wFpkAAAACXBIWXMAAAsTAAALEwEAmpwYAAAQKklEQVR4nO3dzYtd933H8c+duXoajWOribBr31I7XPwYOyPoHzDQNhtTumiDwaUL1yQlhZBANoWWJiktdBNwCDQ0JfWi1GDSLkrxJm1hsiiU0NSTuJItR01kqtGD9WDLGj3MaDS3i6vilcbW0c05Of2+Xpuz+MH5fb82mvfMXIQGk8kkAFDFXNcDAECbhA+AUoQPgFKED4BShA+AUoQPgFKGH3Du7zoA0EeDWx34iQ+AUoQPgFKED4BShA+AUoQPgFKED4BShA+AUoQPgFKED4BShA+AUoQPgFKED4BShA+AUoQPgFKED4BShA+AUoQPgFI+6F9gn5lDhw7l7NmzGY/HbV05c8eOHUsSO3TMDj8f7PDz4f/DDsl0j4MHD+bVV1/9md/VWvjOnj2bC+sXcnJysq0rZ+7C+oUk6f0ON24Msr1+tutRGjt/8Z0k6f0Oc9fnsy9Xux6lsfNn30uS3u8wHF7P5fN7uh6lsYvvnE+SXu+QTPfY2rjcyl2thW88Hufk5GS+9K9fauvKmfvar34tSXq/w/rlXfmNb32l61Ea+6fPfiVJer/D/tOL+cKn/67rURr7+nd+J0l6v8M9B87lb/7iD7oepbHf+8O/TJJe75C8v0cbfMYHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0Apg8lkstP5joe3YzQa5cL6hYw+OZrVK1t34ocnkqT3O9y4MchHH3mw61EaO3/0eJL0foe5zfmMDj7W9SiNnTj7epL0fofh8Hoe/fj9XY/S2Bs/OZkkvd4hme6xsG9Pzpx7d1avHNzqYDirGz6M7Y2r2Xzrx21eOVPb16bPvu+wNfhILrx7sOtRGru+tZYkvd/hrj3beeCX+vtLl7PvTZ9932HzUnLhv7qepLmtm88+75BM99i4OrOftXbUWvjG43GGw7U891xbN87eiy9On33f4fTwUO79/ErXozR25hvLSdL7HQ4d3MjK37/c9SiNLf/2M0nS+x3+59/fzufyua5Haeyb+WaS9HqH5OYe7XTPZ3wA1CJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlDKYTCY7ne94eDtGo1HOnVvLfffN6o3tO316+uz7DpuDu7P7gaWuR2lsc201SXq/w0d2bWfpiSe6HqWx1cOHk6T3O2xcup77c3/XozR2MieTpNc7JNM9dmd3Lk4uzuqVg1sdDGd1w4ea4kYy/16rV87U4MZWkv7vsG/XZh7cc7brURo7Pnc9SXq/w7XN7Rw71d8drm5O/z/0fYfNxWF+8sgvdD1Kc0ffTpJ+75AkR9/Oxt49rVzV2lfw8XicPVfO5HO/cndbV87cN/9j+p1I33fY+4sP5ctf/nLXozT21a9+NUl6v8PFyxv59HOf73qUxr7z4jeSpPc7rH3sQPLX3+56lOY+8/z02ecdkuQzz8/uV4wfwGd8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQymEwmO53veHg7RqNRzp9Zy/13DWf1ytadvLSVJL3fYW73Qh588MGuR2ns+PHjSdL7HbZubOfgfQ90PUpjZ0+vJUnvd9jcNUweebTrUZo7+sb02ecdkukeCwuZnDkzqzcObnXQ6lfwub2L2ffwk21eOVNzRw4nmWTfw5/oepTG5o4cznAuOXDwQNejNHZi7USS/u+wa7Cd8T13dz1KY+vnpl+g+r7DcDDIQ3O7uh6lsZ8Opr+46/MOyXSP3YN2fgnZWvjG43HOXdvMn7/8D21dOXN/9MxvJUnvd7hn71xeWXml61Eae3r56STp/Q7Dd69m5et/1fUojS1/4feTpPc7nNu9J3/6t/39M/0nvzv9utTnHZL392iDz/gAKEX4AChF+AAoRfgAKEX4AChF+AAoRfgAKEX4AChF+AAoRfgAKEX4AChF+AAoRfgAKEX4AChF+AAoRfgAKEX4AChF+AAoRfgAKEX4AChF+AAoRfgAKEX4AChF+AAoRfgAKEX4AChF+AAoRfgAKEX4AChF+AAoRfgAKEX4AChF+AAoRfgAKEX4AChF+AAoRfgAKEX4AChF+AAoRfgAKEX4AChF+AAoRfgAKEX4AChF+AAoRfgAKGUwmUx2Ot/x8HaMRqO8896lPPT4E7N6Zet+euRwkvR+h+Fc8uTSk12P0thrq68l6f8Og63tLI0f7nqUxlaPvZkkvd/h+txcHnq0x3+m37j5danHOyTTPfYuLOT86VOzeuXgVgfDWd3wYVyZG+Tw3t1tXjlbc9P/jn3f4a6NjeT4ia4nae7axvTZ9x02NpIf/mfXk9y5nu+wubg/J+Y2ux6jsY1sJ0mvd0ime9wYbLdyV2vhG4/HWUuSlZW2rpy95eXps+c7PHX8eF557rmuJ2ns6RdfTJLe7zB8662sdD3IHVi++VzpcIY7tZxk9YlHc+jlb3c9SmOvPvN8kvR6h+T9PdrgMz4AShE+AEoRPgBKET4AShE+AEoRPgBKET4AShE+AEoRPgBKET4AShE+AEoRPgBKET4AShE+AEoRPgBKET4AShE+AEoRPgBKET4AShE+AEoRPgBKET4AShE+AEoRPgBKET4AShE+AEoRPgBKET4AShE+AEoRPgBKET4AShE+AEoRPgBKET4AShE+AEoRPgBKET4AShE+AEoRPgBKET4AShE+AEoRPgBKET4AShE+AEoRPgBKET4AShlMJpOdznc8vB2j0Shr6+vJ0tKsXtm+1dXps+c7fOTatTx5331dT9LYa6dPJ0nvdxhsbGSp60HuwOrN51KHM9yp1STrdy1m8fFHuh6lsfUjR5Ok1zsk0z3m9y9k49SZWb1ycKuD4axu+DAWkzzR5oUzduTm8/FOp7gzR5JMdu/O9Xvv7XqUxiYXLiRJ73e4sTHMuxl3PUpjWzmWJL3fYX/m84ndi12P0thrc/NJ0usdkukeC3O7WrmrtfCNx+NcS/LyykpbV87cM8vLSfq/w+Tq1bz00ktdj9LYs88+myS932Hj+xt5IS90PUpjX8wXk6T3Oywu3ZNX/nml61Eae/rXl5Ok1zsk7+/RBp/xAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVDKYDKZ7HS+4+HtGI1GeW99PY8vLc3qla07srqaJP3fYXs7jz32WNejNPb6668nSe932L60nXHGXY/S2LEcS5Le7zB/9zBPPrXU9SiNvfaj1STp9Q7JdI/9+xdzcu3ErF45uNXBcFY3fBhzmWTvZKvNK2dq7ub3AX3f4b3tuXx/Y1/XozS3Pf1FRd932L9rI8MDp7qepLHBO5tJ0vsdBpuXMzz3va5HaWxwffrs8w7JdI+5a5dauau18I3H42SylZV/eaWtK2du+deeTpLe7/C9i8PkhZWuR2nui8vTZ893ePTU6/nWpz7V9SSNffa7302S3u+w+NG3s/LHXU/S3PKfTZ993iH5vz22W7nLZ3wAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlDKYTCY7ne94eDtGo1HW1y9l6ZNPzuqVrVv94WtJ0vsdLm4NkvFS16M0d2x1+uz5DoubV/LIgQNdT9LY0XfeSZLe7zC/63qWfrnrSZpbfWv67PMOyXSPxT3JiQszy87gVgfDWd3w4VxKBv/W7pU/Cz3fYX4wl33DH3Q9RmNXBleSJAs93+HqYCH/Pfx416M0dnVwOEl6v8O+q5Nc/fFC16M0tr11ORkkV3+8v+tR7sj21uXc2Gjnl5CthW88HidZy8pKWzfO3vLy9Nn3HX6wvpCHv/Vw16M09uZn30yS3u8wPPWJHPrNl7sepbFX//GZJOn9Dg+/fSQv3fNU16M09uy7P0qSXu+QvL9HG3zGB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0Apg8lkstP5joe3YzQaZX19LUtLs3pj+1ZXp8++73DpxlwWHlnoepTGrhy9kiS932GwuT93feyJrkdp7NK5w0nS+x0WNq/kseH+rkdp7PWty0nS6x2S6R4Lg/mc3t6Y1SsHtzoYzuqGD3Lw4MEkp5Jst3XlzC0udj3BnVtcTK5d7/cP+vML812PcMfmF+YzyL6ux7gj87v6/YU2me6w78Zm12PckYXB/A5f4vtjYTCfj+7e28pdrf3EBwAtuuW3A/3+1h8AbpPwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQyvADzm/5T7cDQB/5iQ+AUoQPgFKED4BShA+AUoQPgFKED4BS/hfVEDMPlRb/dwAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x432 with 1 Axes>"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "filling = cover_if_possible(tiling)\n",
    "draw_filling(filling)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Здесь ничего интересного, давайте вырежем несколько клеток"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAb4AAAG+CAYAAADsjWHpAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy86wFpkAAAACXBIWXMAAAsTAAALEwEAmpwYAAAQq0lEQVR4nO3dz4td93nH8c+duRqNRqPYbqpGsSZUDhdbsqx0BP0DZtFmo0UXSTC4dKGGprgQ4mWhpSGlhS4dAjVNSbUoNZgkiy60SbsYLwwmJPU4iiTbCNstGlv1jGJZo1+WRnO7uC5eaRydubknJ8/rtTmLL5zv84A877m6GPWGw2EAoIqptgcAgEkSPgBKET4AShE+AEoRPgBKET4ASul/wrn/1wGALurd68AnPgBKET4AShE+AEoRPgBKET4AShE+AEoRPgBKET4AShE+AEoRPgBKET4AShE+AEoRPgBKET4AShE+AEoRPgBKET4ASvmkf4F9bI4fP561tbUMBoNJXTl2Fy5cSBI7tMwOvx7s8OvhN2GHZLTH/v3788orr/zK75pY+NbW1vKL9atZzc1JXTl2l9euJkn2dHyHfv9Orl/e3fYojX3w/uUk6fwOm1u30u+vtj1KY+vro2fXd7jT+1TWZ9uepLnbl68lSad3SEZ7vHd9MndNLHyDwSCruZlvfOXfJnXl2H37+3+cJJ3f4cGH1vMv//AXbY/S2J/+5T8mSed3WNt4MydPtj1Jc6dOjZ5d3+FS/3g+8/Xltkdp7H+/s5Qknd4h+XiPSfAdHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApfSGw+F259se3o+FhYVcXruahf1HxvXKibu4dj5JOr9Dv38nhz//cNujNPbam+8kSed3uHP3Vg4caHuS5i5dGj27vsPt3gOZObjY9iiN3V5dSZJO75CM9pjaPZ/NKxfH9crevQ7647rhl3Hr9kYurP54kleO3afm53Pwc939oLx2Nbm6cSs/+fmbbY+yI7uzO7/4edtTNLeZpDfdy/TV6bZHaax3dzNJMn11oj9Gxqp3dzN7dt3Ood1rbY/S2NtTd5Kk0zskoz1mpm5O5K6J/YkdDAZZXV2d1HW/MsefeCLLP3ih7TEaW/ryk3nx5ZfbHmPHDuZgns7TbY/R2HN5LvnU/+Tp33+g7VEae+4nHyRJ53eY/ewj+eY3v9n2KI1961vfSpJO75B8vMckdPejCwA0IHwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACU0hsOh9udb3t4PxYWFrK6ujqu17XmgX37snj0aNtjNLZy9mw+2Nhoe4wdm81sHs7DbY/R2Dt5J+nfysP7+m2P0tg7G5tJ0vkdpmbmcujQobZHaeztt99Okk7vkIz2mJ2dzeXLl8f1yt69Dib6J3Zm9+7sP7AwySvHau3S6vh+E2hRL2P8jaYlw85vkNzaPZ83P3+47TGae/21JOn8Dnt6vfT2PdD2JM1Nj36Md3qHZLTHrpmJXDWx8A0Gg6Q/m6+c/Pqkrhy775/6Tgaf3Z/lH7zQ9iiNLX35ybz48sttj7FjB3MwT+fptsdo7Lk8lzcP/1byz99re5Tm/uyro2fHd/h8f1f+/oUftj1JY3/15JeSpNM7JB/vMQm+4wOgFOEDoBThA6AU4QOgFOEDoBThA6AU4QOgFOEDoBThA6AU4QOgFOEDoBThA6AU4QOgFOEDoBThA6AU4QOgFOEDoBThA6AU4QOgFOEDoBThA6AU4QOgFOEDoBThA6AU4QOgFOEDoBThA6AU4QOgFOEDoBThA6AU4QOgFOEDoBThA6AU4QOgFOEDoBThA6AU4QOgFOEDoBThA6AU4QOgFOEDoBThA6AU4QOgFOEDoBThA6AU4QOglN5wONzufNvD+7GwsJC19cvZf+DguF45cWuXVrNnZlcWjx5te5TGVs6ezQcbG22PsWOzmc3DebjtMRp7J+/k1nw/eexw26M09/pro2fHd5jrTeWRx7v73/Rb584mSad3SEZ7zO6dy+V33x3XK3v3OuiP64Yqhr1eNndPtz1GY8OpXh7YO5/FwaNtj9LYyoU3kiSfGzzY7iA7cPnCe5nq9fLI1K62R2nsrd7oL4y6vsONqV7Ozs60PUpzU6Of753eIUmmerk5PZmfrRML32AwSPqz+crJr0/qyrH7/qnv5NChAzm9fLrtURo7sXQi/Ss3s/ztf2p7lMaWvvHnSdL5HdZndudv//WHbY/S2N/8yZeSpPM7nJ2bSZaX2x6luaWl0bPLOyTJ0tL4/orxE/iOD4BShA+AUoQPgFKED4BShA+AUoQPgFKED4BShA+AUoQPgFKED4BShA+AUoQPgFKED4BShA+AUoQPgFKED4BShA+AUoQPgFKED4BShA+AUoQPgFKED4BShA+AUoQPgFKED4BShA+AUoQPgFKED4BShA+AUoQPgFKED4BShA+AUoQPgFKED4BShA+AUoQPgFKED4BShA+AUoQPgFKED4BShA+AUoQPgFKED4BShA+AUoQPgFKED4BSesPhcLvzbQ/vx8LCQtbWL2f/gYPjeuXErV1azezsTI4tHmt7lMbOrJxJb3Mri4NH2x6lsZULbyRJ53e4MzWVRw4fbXuUxt567WySdH6HG1O9ZHGx7VGaW1kZPbu8QzLaY34+w4sXx/XG3r0O+uO64Zcxm2EOZXOSV47VRoZj/FWgRTeuJ6/+V9tT7FzHd7g9vzcXp263PUZjH2YrSTq/w3ym0910J+c+ej7e6hQ7dy7JngndNbHwDQaDbPb7OX3y5KSuHLsTp04lhxZyevl026M0dmLpRPovvpTltgfZgaWPnsstzrBTS0lWjh7O8Re+1/Yojb3y5FeTpPM7HJ6dzwvLy22P0tiTS0tJ0ukdko/3mATf8QFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQSm84HG53vu3h/VhYWMjG+nqOHTgwrldO3JlLl5LZ3Tm2eKztURo7s3ImvQ+uZrHtQXZg5aPnYosz7NRKkmv75jP/+GNtj9LYtXOvJ0nnd5ibms7ji4ttj9LYuZWVJOn0Dsloj73z83n34sVxvbJ3r4P+uG6oYnh3K3du3ml7jMaGW8Pczd5cyaDtURrbzIUk6fwOezOdJ2bm2x6lsTNT00nS+R16GWZ2uNn2KI1NffT5pMs7JKM9psf3WWtbEwvfYDDIZr+f0ydPTurKsTtx6lTufOYzef7559sepbGnnnoqH/74wzybZ9sepbFn8kySdH6H+cUHc/o/ltsepbETf7iUJJ3fod/bzPJ/nm57lMaW/uBEknR6h+TjPSbBd3wAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlNIbDofbnW97eD8WFhaysb6eYwcOjOuVE3fm0qUMZ2Zy5MiRtkdp7Pz589na2Mogg7ZHaexCLiRJ53eYfqCfY19YbHuUxs78bCVJOr9DL8Ms/t6xtkdpbOXVM0nS6R2S0R7z83tz8eI743pl714H/XHd8MvY6O/OSw8emuSV47V+JfPZanuKHevN3En/wXfbHqOx3vu3kyT9h7q9Q+/29fTXX2x7lMZ6d0bPzu+wK0nvpbZH2bnfhB1ybSK3TCx8g8Egq1eSPLs8qSvH75mlPL77Zp5//vm2J2nsqaeeyt233853v/jFtkdp7Gs/+lGSdH6H+U+/l+W/bnuS5pb+bvTs/A6/kywvtz1Jc0tLo2eXd0j+f4/JfLDwHR8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApfSGw+F259se3o+FhYWsXrmWDBbH9crJu7CSfVNbOXLkSNuTNHb+/PkMb93KYw891PYojb3+/vtJ0vkdpnfdyeLvtj1Jcyv/PXp2foddyeJi25M0t7IyenZ5h2S0x/x8cvHi2LLTu9dBf1w3VHF9eCPn7p5re4zGbgxvJLuT1z93o+1RGrtx4262rm3lp++91/YoOzKd+bz6wRNtj9HYtc2zSZJXPzja8iTNXds8mz03b+bmS3Ntj9LY1ub1pJfcfGlv26PsyNbm9dy9Ppm/hJxY+AaDQVavJHl2eVJXjt8zS5nr/zSPfvfRtidp7I2vvZEknd/h2k+vtT3Gju3b/0SO/9ELbY/R2Cv//mSSdH6HR987l+cf/ELbozT21JWfJUmnd0g+3mMSfMcHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCm94XC43fm2h/djYWEhq1euJYPFcb1y8i6sZKq3kbnH5tqepLEbr99Iks7vsHVtq+0xdmx6Zl/2/fbRtsdobGP9bJJ0foe52zdypL+37VEaO795PUk6vUMy2mOuN51LWx+O65W9ex30x3XDJ9m/f3/e/TDp9I+rPfOZ6t1qe4odmZ6bbnuEHZuem87W9a0x/lrWjun+nrZH2JHpXd3+QZuMdthz93bbY+zIXG96mx/x3THXm86nZ2YnctfEPvEBwATd89cB3/EBUIrwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQSv8Tzu/5T7cDQBf5xAdAKcIHQCnCB0ApwgdAKcIHQCnCB0Ap/wc+k/EWmbt1SQAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x432 with 1 Axes>"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tiling_random = [\n",
    "    '........',\n",
    "    '#.#.....',\n",
    "    '..#.....',\n",
    "    '........',\n",
    "    '........',\n",
    "    '........',\n",
    "    '........',\n",
    "    '...#....'\n",
    "]\n",
    "filling_random = cover_if_possible(tiling_random)\n",
    "draw_filling(filling_random)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ладно, с количеством вроде бы разобрались. А что если мы просто хотим понять, получится ли замостить или нет? Можно использовать тот же самый способ для подсчета максимального числа клеток, которое можно замостить. Для этого нужно добавить переход \"пропустить клетку\" и заменить сумму на минимум в рекуррентном соотношении. В целом получается как-то так"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "def maxmimum_cover(tiling):\n",
    "    n = len(tiling)\n",
    "    m = len(tiling[0])\n",
    "    if ((n + 1) * m * 2 ** m) <= 10000000:\n",
    "        dp = [[[(n * m if k != 0 or j != 0 or mask != 0 else 0) for mask in range(2 ** m)] for j in range(m)] for k in range(n + 1)]\n",
    "    for k in range(n):\n",
    "        for j in range(m):\n",
    "            for mask in range(2 ** m):\n",
    "                next_k, next_j = k + ((j + 1) // m), (j + 1) % m\n",
    "                # Вертикальная доминошка\n",
    "                if k < n - 1 and tiling[k][j] == '.' and tiling[k + 1][j] == '.' and (mask &  (1 << j)) == 0:\n",
    "                    dp[next_k][next_j][mask + (1 << j)] = min(dp[next_k][next_j][mask + (1 << j)], dp[k][j][mask])\n",
    "                # Горизонтальная доминошка\n",
    "                if j < m - 1 and tiling[k][j] == '.' and tiling[k][j + 1] == '.' and (mask & (3 << j)) == 0:\n",
    "                    dp[next_k][next_j][mask + (2 << j)] = min(dp[next_k][next_j][mask + (2 << j)], dp[k][j][mask])\n",
    "                # Клетка занята\n",
    "                if ((1 << j) &  mask) != 0 or tiling[k][j] != '.':\n",
    "                    dp[next_k][next_j][(mask | (1 << j)) - (1 << j)] = \\\n",
    "                        min(dp[next_k][next_j][(mask | (1 << j)) - (1 << j)], dp[k][j][mask])\n",
    "                # Клетка не занята, рассмотриваем случай её пропуска\n",
    "                else:\n",
    "                    dp[next_k][next_j][(mask | (1 << j)) - (1 << j)] = \\\n",
    "                        min(dp[next_k][next_j][(mask | (1 << j)) - (1 << j)], dp[k][j][mask] + 1)\n",
    "    return dp\n",
    "\n",
    "def cover_maximum_possible(tiling, dp=None):\n",
    "    if dp is None:\n",
    "        dp = maxmimum_cover(tiling)\n",
    "    n = len(dp) - 1\n",
    "    m = len(dp[0])\n",
    "\n",
    "    result = [[-1 if tiling[i][j] == '#' else -2 for j in range(m)] for i in range(n)]\n",
    "    num = 0\n",
    "    \n",
    "    k = n\n",
    "    j = 0\n",
    "    mask = 0\n",
    "    \n",
    "    while k > 0 or j > 0:\n",
    "        #print(k, j, mask)\n",
    "        prev_j = j - 1\n",
    "        prev_k = k\n",
    "        if prev_j == -1:\n",
    "            prev_j += m\n",
    "            prev_k -= 1\n",
    "        \n",
    "        # Начинаем перебирать варианты, каким образом мы могли попасть в i, j, mask\n",
    "        # Этот вариант очень не оптимален, но занимает меньше кода и все равно быстрее \n",
    "        # самого подсчета динамики\n",
    "        for prev_mask in range(2 ** m):\n",
    "            # Раньше мы здесь проверяли, что количество вариантов в этой ветке не 0, сейчас нужно\n",
    "            # проверить, что эта ветка ведет к максимальному покрытию\n",
    "            if prev_k < n - 1 and tiling[prev_k][prev_j] == '.' and tiling[prev_k + 1][prev_j] == '.' and \\\n",
    "                    (prev_mask & (1 << prev_j)) == 0 and (prev_mask + (1 << prev_j)) == mask and \\\n",
    "                    dp[prev_k][prev_j][prev_mask] == dp[k][j][mask]:\n",
    "                mask = prev_mask\n",
    "                result[prev_k][prev_j] = num\n",
    "                result[prev_k + 1][prev_j] = num\n",
    "                num += 1\n",
    "                break\n",
    "            elif prev_j < m - 1 and tiling[prev_k][prev_j] == '.' and tiling[prev_k][prev_j + 1] == '.' and (prev_mask & (3 << prev_j)) == 0 and \\\n",
    "                    prev_mask + (2 << prev_j) == mask and dp[prev_k][prev_j][prev_mask] == dp[k][j][mask]:\n",
    "                mask = prev_mask\n",
    "                result[prev_k][prev_j] = num\n",
    "                result[prev_k][prev_j + 1] = num\n",
    "                num += 1\n",
    "                break\n",
    "            elif (((1 << prev_j) & prev_mask) != 0 or tiling[prev_k][prev_j] != '.') and \\\n",
    "                    (prev_mask | (1 << prev_j)) - (1 << prev_j) == mask and dp[prev_k][prev_j][prev_mask] == dp[k][j][mask]:\n",
    "                mask = prev_mask\n",
    "                break\n",
    "            elif ((1 << prev_j) & prev_mask) == 0 and tiling[prev_k][prev_j] == '.' and \\\n",
    "                    (prev_mask | (1 << prev_j)) - (1 << prev_j) == mask and dp[prev_k][prev_j][prev_mask] + 1 == dp[k][j][mask]:\n",
    "                mask = prev_mask\n",
    "                break\n",
    "                \n",
    "        \n",
    "        j = prev_j\n",
    "        k = prev_k\n",
    "    \n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAb4AAAG+CAYAAADsjWHpAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy86wFpkAAAACXBIWXMAAAsTAAALEwEAmpwYAAAQq0lEQVR4nO3dz4td93nH8c+duRqNRqPYbqpGsSZUDhdbsqx0BP0DZtFmo0UXSTC4dKGGprgQ4mWhpSGlhS4dAjVNSbUoNZgkiy60SbsYLwwmJPU4iiTbCNstGlv1jGJZo1+WRnO7uC5eaRydubknJ8/rtTmLL5zv84A877m6GPWGw2EAoIqptgcAgEkSPgBKET4AShE+AEoRPgBKET4ASul/wrn/1wGALurd68AnPgBKET4AShE+AEoRPgBKET4AShE+AEoRPgBKET4AShE+AEoRPgBKET4AShE+AEoRPgBKET4AShE+AEoRPgBKET4ASvmkf4F9bI4fP561tbUMBoNJXTl2Fy5cSBI7tMwOvx7s8OvhN2GHZLTH/v3788orr/zK75pY+NbW1vKL9atZzc1JXTl2l9euJkn2dHyHfv9Orl/e3fYojX3w/uUk6fwOm1u30u+vtj1KY+vro2fXd7jT+1TWZ9uepLnbl68lSad3SEZ7vHd9MndNLHyDwSCruZlvfOXfJnXl2H37+3+cJJ3f4cGH1vMv//AXbY/S2J/+5T8mSed3WNt4MydPtj1Jc6dOjZ5d3+FS/3g+8/Xltkdp7H+/s5Qknd4h+XiPSfAdHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApfSGw+F259se3o+FhYVcXruahf1HxvXKibu4dj5JOr9Dv38nhz//cNujNPbam+8kSed3uHP3Vg4caHuS5i5dGj27vsPt3gOZObjY9iiN3V5dSZJO75CM9pjaPZ/NKxfH9crevQ7647rhl3Hr9kYurP54kleO3afm53Pwc939oLx2Nbm6cSs/+fmbbY+yI7uzO7/4edtTNLeZpDfdy/TV6bZHaax3dzNJMn11oj9Gxqp3dzN7dt3Ood1rbY/S2NtTd5Kk0zskoz1mpm5O5K6J/YkdDAZZXV2d1HW/MsefeCLLP3ih7TEaW/ryk3nx5ZfbHmPHDuZgns7TbY/R2HN5LvnU/+Tp33+g7VEae+4nHyRJ53eY/ewj+eY3v9n2KI1961vfSpJO75B8vMckdPejCwA0IHwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACU0hsOh9udb3t4PxYWFrK6ujqu17XmgX37snj0aNtjNLZy9mw+2Nhoe4wdm81sHs7DbY/R2Dt5J+nfysP7+m2P0tg7G5tJ0vkdpmbmcujQobZHaeztt99Okk7vkIz2mJ2dzeXLl8f1yt69Dib6J3Zm9+7sP7AwySvHau3S6vh+E2hRL2P8jaYlw85vkNzaPZ83P3+47TGae/21JOn8Dnt6vfT2PdD2JM1Nj36Md3qHZLTHrpmJXDWx8A0Gg6Q/m6+c/Pqkrhy775/6Tgaf3Z/lH7zQ9iiNLX35ybz48sttj7FjB3MwT+fptsdo7Lk8lzcP/1byz99re5Tm/uyro2fHd/h8f1f+/oUftj1JY3/15JeSpNM7JB/vMQm+4wOgFOEDoBThA6AU4QOgFOEDoBThA6AU4QOgFOEDoBThA6AU4QOgFOEDoBThA6AU4QOgFOEDoBThA6AU4QOgFOEDoBThA6AU4QOgFOEDoBThA6AU4QOgFOEDoBThA6AU4QOgFOEDoBThA6AU4QOgFOEDoBThA6AU4QOgFOEDoBThA6AU4QOgFOEDoBThA6AU4QOgFOEDoBThA6AU4QOgFOEDoBThA6AU4QOgFOEDoBThA6AU4QOglN5wONzufNvD+7GwsJC19cvZf+DguF45cWuXVrNnZlcWjx5te5TGVs6ezQcbG22PsWOzmc3DebjtMRp7J+/k1nw/eexw26M09/pro2fHd5jrTeWRx7v73/Rb584mSad3SEZ7zO6dy+V33x3XK3v3OuiP64Yqhr1eNndPtz1GY8OpXh7YO5/FwaNtj9LYyoU3kiSfGzzY7iA7cPnCe5nq9fLI1K62R2nsrd7oL4y6vsONqV7Ozs60PUpzU6Of753eIUmmerk5PZmfrRML32AwSPqz+crJr0/qyrH7/qnv5NChAzm9fLrtURo7sXQi/Ss3s/ztf2p7lMaWvvHnSdL5HdZndudv//WHbY/S2N/8yZeSpPM7nJ2bSZaX2x6luaWl0bPLOyTJ0tL4/orxE/iOD4BShA+AUoQPgFKED4BShA+AUoQPgFKED4BShA+AUoQPgFKED4BShA+AUoQPgFKED4BShA+AUoQPgFKED4BShA+AUoQPgFKED4BShA+AUoQPgFKED4BShA+AUoQPgFKED4BShA+AUoQPgFKED4BShA+AUoQPgFKED4BShA+AUoQPgFKED4BShA+AUoQPgFKED4BShA+AUoQPgFKED4BShA+AUoQPgFKED4BShA+AUoQPgFKED4BSesPhcLvzbQ/vx8LCQtbWL2f/gYPjeuXErV1azezsTI4tHmt7lMbOrJxJb3Mri4NH2x6lsZULbyRJ53e4MzWVRw4fbXuUxt567WySdH6HG1O9ZHGx7VGaW1kZPbu8QzLaY34+w4sXx/XG3r0O+uO64Zcxm2EOZXOSV47VRoZj/FWgRTeuJ6/+V9tT7FzHd7g9vzcXp263PUZjH2YrSTq/w3ym0910J+c+ej7e6hQ7dy7JngndNbHwDQaDbPb7OX3y5KSuHLsTp04lhxZyevl026M0dmLpRPovvpTltgfZgaWPnsstzrBTS0lWjh7O8Re+1/Yojb3y5FeTpPM7HJ6dzwvLy22P0tiTS0tJ0ukdko/3mATf8QFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQSm84HG53vu3h/VhYWMjG+nqOHTgwrldO3JlLl5LZ3Tm2eKztURo7s3ImvQ+uZrHtQXZg5aPnYosz7NRKkmv75jP/+GNtj9LYtXOvJ0nnd5ibms7ji4ttj9LYuZWVJOn0Dsloj73z83n34sVxvbJ3r4P+uG6oYnh3K3du3ml7jMaGW8Pczd5cyaDtURrbzIUk6fwOezOdJ2bm2x6lsTNT00nS+R16GWZ2uNn2KI1NffT5pMs7JKM9psf3WWtbEwvfYDDIZr+f0ydPTurKsTtx6lTufOYzef7559sepbGnnnoqH/74wzybZ9sepbFn8kySdH6H+cUHc/o/ltsepbETf7iUJJ3fod/bzPJ/nm57lMaW/uBEknR6h+TjPSbBd3wAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlCJ8AJQifACUInwAlNIbDofbnW97eD8WFhaysb6eYwcOjOuVE3fm0qUMZ2Zy5MiRtkdp7Pz589na2Mogg7ZHaexCLiRJ53eYfqCfY19YbHuUxs78bCVJOr9DL8Ms/t6xtkdpbOXVM0nS6R2S0R7z83tz8eI743pl714H/XHd8MvY6O/OSw8emuSV47V+JfPZanuKHevN3En/wXfbHqOx3vu3kyT9h7q9Q+/29fTXX2x7lMZ6d0bPzu+wK0nvpbZH2bnfhB1ybSK3TCx8g8Egq1eSPLs8qSvH75mlPL77Zp5//vm2J2nsqaeeyt233853v/jFtkdp7Gs/+lGSdH6H+U+/l+W/bnuS5pb+bvTs/A6/kywvtz1Jc0tLo2eXd0j+f4/JfLDwHR8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApfSGw+F259se3o+FhYWsXrmWDBbH9crJu7CSfVNbOXLkSNuTNHb+/PkMb93KYw891PYojb3+/vtJ0vkdpnfdyeLvtj1Jcyv/PXp2foddyeJi25M0t7IyenZ5h2S0x/x8cvHi2LLTu9dBf1w3VHF9eCPn7p5re4zGbgxvJLuT1z93o+1RGrtx4262rm3lp++91/YoOzKd+bz6wRNtj9HYtc2zSZJXPzja8iTNXds8mz03b+bmS3Ntj9LY1ub1pJfcfGlv26PsyNbm9dy9Ppm/hJxY+AaDQVavJHl2eVJXjt8zS5nr/zSPfvfRtidp7I2vvZEknd/h2k+vtT3Gju3b/0SO/9ELbY/R2Cv//mSSdH6HR987l+cf/ELbozT21JWfJUmnd0g+3mMSfMcHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCnCB0ApwgdAKcIHQCm94XC43fm2h/djYWEhq1euJYPFcb1y8i6sZKq3kbnH5tqepLEbr99Iks7vsHVtq+0xdmx6Zl/2/fbRtsdobGP9bJJ0foe52zdypL+37VEaO795PUk6vUMy2mOuN51LWx+O65W9ex30x3XDJ9m/f3/e/TDp9I+rPfOZ6t1qe4odmZ6bbnuEHZuem87W9a0x/lrWjun+nrZH2JHpXd3+QZuMdthz93bbY+zIXG96mx/x3THXm86nZ2YnctfEPvEBwATd89cB3/EBUIrwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQSv8Tzu/5T7cDQBf5xAdAKcIHQCnCB0ApwgdAKcIHQCnCB0Ap/wc+k/EWmbt1SQAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x432 with 1 Axes>"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "filling = cover_maximum_possible(tiling_random)\n",
    "draw_filling(filling)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "А вот нетривиальный пример, когда замостить не получается, но количество черных и белых клеток одинаково"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYgAAAGICAYAAABbQ3cmAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy86wFpkAAAACXBIWXMAAAsTAAALEwEAmpwYAAAMBklEQVR4nO3dMW9VZ57H8f+1LyExBpPZYYfirnaKu8PADOT6HbjYSUOxZaR00Uip8wK23BeQOtIqXaSUU9BktrA1irQbKeISNiDPuIkU76DAiNgYMwTw3QK22NXPNjqHu8fX+XyaUzzSc/6PwOfL0bW4vclkUgDwf811PQAAR5NAABAJBACRQAAQCQQAkUAAEPUPWfc7sADHW2+/BW8QAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEh30fRCvLy8t19+7dGg6H07zNVG1sbFRVzfQZqo7HOZzhaHCGo2FjY6POnTtX169fn9o9epPJgd8J1OoLgwaDQT34y1/q8s9+1mabTt28c6d6jx/XqOtBWhq/uI46nKGtcVVtl2+xgv8xNzdXz549a7vNvl8YNNU3iOFwWE/7/br23nvTvM1UXf344+p/802tdj1ISysvrqsdztDWSlWtdT0EHCF7e3tT3d9nEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQNSbTCYHrR+4eJjBYFAP7t2ry+fPt9mmUzfv3Kne48c16nqQlsYvrqMOZ2hrXFVbXQ8BR8whz/CX0dtvod925x+Dh6cXa3zpQtdjtLJza72qaqbPsXNrvc7MzdfyaNT1KI2Nx+Pa3t5+FT/UMHVTDcRwOKyn/X5de++9ad5mqq5+/HH95/mf1vKn/9r1KK1cf+e3VVUzfY7r7/y2Rq8v1urqatejNLayslJra2tdjwEvxWcQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFA1JtMJgetH7h4mMFgUA/u3avL58+32aZTN+/cqYevnajFSxe6HqWVnVvrVVUzfY6dW+u1ODdfo9Go61EaG4/HtbW11fUYHCOHPMNfRm+/hX7bnQ8zOXmynv7859O+zdRMvv++Fqrql68vdj1KK7fm5qv29urCZL7rURq7Xb3a29urR48edT1KY3t7e3WqTtWwhl2P0thGbVRVzfwZHtbDrsc48qYaiOFwWH+tqk9XV6d5m6l6Z2Wlqmb7DFXPzzF59Kg++eSTrkdp7N13362qmvkzPP7icX1YH3Y9SmMf1AdVVTN/hht1o+sxjjyfQQAQCQQAkUAAEAkEAJFAABAJBACRQAAQCQQAkUAAEAkEAJFAABAJBACRQAAQCQQAkUAAEAkEAJFAABAJBACRQAAQCQQAkUAAEAkEAJFAABAJBACRQAAQCQQAkUAAEAkEAJFAABAJBACRQAAQCQQAkUAAEAkEAJFAABAJBACRQAAQCQQAkUAAEAkEAJFAABAJBACRQAAQCQQAkUAAEAkEAFFvMpkctH7g4mEGg0Ft7+zUpdGozTadujUeV1XN9BmqXpxjb68uXrzY9SiN3b59u6pq5s+w92CvhjXsepTGNmqjqmrmz/CwHnY9xitxyDP8ZfT2W+i33fkwO9vb9R9ra9O+zVSdPn2m+ntdT9FOr6oe7OzUF1980fUorZw5fbreeP1E12M0NjfXq7ml+Tr71mLXozTWvzFf2097dWN4tutRmtvoV9VS1XDU9STNbYyrTi5M9RZTDcRwOKzNzc1p3uL/xZXRcl37/WrXY7Ry9Tcr9fkfZjvUVVXLy1dq9d+udT1GYyv/eLWqaubPsLbVr/pwtetRmvtg5fn1OJxhinwGAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARL3JZHLQ+oGLhxkMBrW5udlmiyPhzNJSXb4y6nqMVm5+Na7tra2ux2htaelMjd663PUYjY1v3KyqmvkzbD3tVQ1HXY/S3Mb4+XXWz/DGYk3uftt2p95+C/22O/8YTPZadfLIWHzttbpw9mzXYzS2fv9+1Q/bVXc/73qU5p68uM74GZZOVI3OrnU9SWPjF0++WT/DwmsPpnqPqQZiOBweizeIK6Pluvb71a7HaOXqb1bqr+u366O33+56lMbe/+yzWvyb72r1n7uepLmVf3l+nfkz/G3V6mrXkzS3svL8Ovtn2JvqPXwGAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARL3JZHLQ+oGLhxkMBrW5udlmiyPhzNJSXb4y6nqMVm5+Na693d268OabXY/S2Pr9+zV/4kmN/r7rSZobf/P8OvNnOFE1GnU9SXPj8fPrrJ9hcbHq229bPaarqnr7LfTb7vxjsL21VZ//Ya3rMVo71Z/9P+6d3nx9ufBG12M0tju3W1VVXy4sdDxJc7tzu9V7tFA3/vTrrkdpbOfR11VVdeNPv+p4kuZ2Hn1dj59N92dhqk+M4XB4LN4gjotf/uQn9dHbb3c9RmPvf/ZZrf/dbv3io190PUpjf3z/j1VVM3+G/p9/Xcv/9GnXozR2/XfvVFUdizNMk88gAIgEAoBIIACIBAKASCAAiAQCgEggAIgEAoBIIACIBAKASCAAiAQCgEggAIgEAoBIIACIBAKASCAAiAQCgEggAIgEAoBIIACIBAKASCAAiAQCgEggAIgEAoBIIACIBAKASCAAiAQCgEggAIgEAoBIIACIBAKASCAAiAQCgEggAIgEAoBIIACIBAKASCAAiAQCgEggAIgEAoBIIACIBAKASCAAiHqTyeSg9QMXDzMYDGpzc7PNFrxCiydO1IU33+x6jMbW79+v3ZPPauHCQtejNLa7vltVNfNn6P1wqk7/9Fddj9LYg3tfV1XN/BnmT5yqxzt/brtVb7+FftudmR07T57Ul9991/UYrSw+ma9LN2b3xff2015Vr+rijJ9h7kyv3vqHk12P0tj44Vxtb2/X9//1712P0sqzHx5Odf+pBmI4HHqD4JW61D9Vn5y90vUYjb37/VdVVTN/hjeWl2t1dbXrURpbWVmptbW1rsd4Bfamuvvs/jMGgKkSCAAigQAgEggAIoEAIBIIACKBACASCAAigQAgEggAIoEAIBIIACKBACASCAAigQAgEggAIoEAIBIIACKBACASCAAigQAgEggAIoEAIBIIACKBACASCAAigQAgEggAIoEAIBIIACKBACASCAAigQAgEggAIoEAIBIIACKBACASCAAigQAgEggAIoEAIBIIACKBACASCAAigQAgEggAot5kMjlo/cDFwwwGg9rc3GyzBfwvp2u+LvZPdT1GY7efPqyqmvkzzC0t1mg06nqUxsbjcW1tbXU9xitxyDP8ZfT2W5jqG8S5c+dqbs5LCq/O673Z/vu00Juvhbn5rsdoZaE3X4sLC12P0cri4uKxeDb1+/2p7j/VNwgAjrxu3iAAmF0CAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEh33bxL7/TzgAx5s3CAAigQAgEggAIoEAIBIIACKBACD6b7V+9fjVFCpNAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 378x378 with 1 Axes>"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tiling_custom=[\n",
    "    '...####',\n",
    "    '....###',\n",
    "    '......#',\n",
    "    '#.#....',\n",
    "    '#......',\n",
    "    '##.....',\n",
    "    '###...#',\n",
    "]\n",
    "filling = cover_maximum_possible(tiling_custom)\n",
    "draw_filling(filling)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Замощение с помощью решения задачи о максимальном паросочетнии\n",
    "Возвращаясь к черно-белой раскраске как на шахматной доске, можно заметить интересную интерпретацию задачи замощения доминошками. Давайте посмотрим на граф, в котором клетки фигуры -- это вершины, ребрами соеденины клетки, имющие общую сторону. Так вот, доминошка в этом графе -- это как раз ребро. Если раскрасить граф в шахматном порядке, то внезапмно можно обнаружить, что этот граф -- двудольный, черные -- одна доля, белые -- другая. Если переформулировать задачу замощения наибольшего числа клеток в терминах этого графа, то получается, что нужно найти максимальное по размеру множество ребер такое, чтобы вершины являлись концом не более одного ребра. В общем то, это довольно известная [задача о максимальном паросочетании](https://ru.wikipedia.org/wiki/Паросочетание). Давайте попробуем её применить для решения этой задачи, тут получится даже с анимацией, приведу базовый алгоритм Куна для нахождения максимального паросочетания"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "def check_valid(i, j, n, m, tiling):\n",
    "    return 0 <= i and i < n and 0 <= j and j < m and tiling[i][j] != '#'\n",
    "\n",
    "def find_augmenting_path(x, y, n, m, visited, matched, tiling):\n",
    "    if not check_valid(x, y, n, m, tiling):\n",
    "        return False\n",
    "    if (x, y) in visited:\n",
    "        return False\n",
    "    visited.add((x, y))\n",
    "    \n",
    "    for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:\n",
    "        if not check_valid(x + dx, y + dy, n, m, tiling):\n",
    "            continue\n",
    "        if (x + dx, y + dy) not in matched or find_augmenting_path(*matched[(x + dx , y + dy)], n, m, visited, matched, tiling):\n",
    "            matched[(x + dx, y + dy)] = (x, y)\n",
    "            return True\n",
    "    return False\n",
    "\n",
    "def convert_match(matched, tiling, n, m):\n",
    "    result = [[-1 if tiling[i][j] == '#' else -2 for j in range(m)] for i in range(n)]\n",
    "    num = 0\n",
    "    for x, y in matched:\n",
    "        _x, _y = matched[(x, y)]\n",
    "        result[x][y] = num\n",
    "        result[_x][_y] = num\n",
    "        num += 1\n",
    "    return result\n",
    "\n",
    "def match_with_flow(tiling):\n",
    "    result_slices = []\n",
    "    n = len(tiling)\n",
    "    m = len(tiling[0])\n",
    "    \n",
    "    matched = dict()\n",
    "    # Для наглядности визуализации\n",
    "    rows = list(range(n))\n",
    "    columns = list(range(m))\n",
    "    random.shuffle(rows)\n",
    "    random.shuffle(columns)\n",
    "    result_slices.append(convert_match(matched, tiling, n, m))\n",
    "            \n",
    "    for i in rows:\n",
    "        for j in columns:\n",
    "            if (i + j) % 2 == 1:\n",
    "                continue\n",
    "            visited = set()\n",
    "            if find_augmenting_path(i, j, n, m, visited, matched, tiling):\n",
    "                result_slices.append(convert_match(matched, tiling, n, m))\n",
    "            \n",
    "    return result_slices"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYgAAAGICAYAAABbQ3cmAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy86wFpkAAAACXBIWXMAAAsTAAALEwEAmpwYAAAMXElEQVR4nO3dT29V953H8e8FEwLYk2RUZrLwKJV6U4Ip6eUZeNFmw6JLJHZRpax5AF32AbCOVGWHxLILNmkXZqSoGqSIS1BiEblSoomVSFTCfy4mmRjfWURdzOiDjc7h5ofJ67Xx4ied8zkx3LdvLoLBdDotAPj/jrQeAMDzSSAAiAQCgEggAIgEAoBIIACI5g4492dgAV5sgycdeAcBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUB00L8H0cuFCxfq/v37NRwOZ3mbmVpbW6uqOtTPUPViPIdneD54hufD2tpanT59um7fvj2ze8w0EPfv36/JZDLLW8zcZDKpx48e1eT771tP6WXzwYM6euLlqulu6ymdTSbbtbW1Xevr662n9OYZng+H/Rm+/vrrmV5/poH4Z51XVlZmeZuZWl5ersnqar3/zjutp/Ty3ocf1vxbb9bKX2+0ntLZ8m8u1s3//Kj1DHhu7O3tzfT6PoMAIBIIACKBACASCAAigQAgEggAIoEAIBIIACKBACASCAAigQAgEggAIoEAIBIIACKBACASCAAigQAgEggAIoEAIBIIACKBACASCAAigQAgEggAIoEAIBIIACKBACASCAAigQAgEggAIoEAIBIIACKBACASCAAigQAgEggAIoEAIBIIACKBACASCAAigQAgEggAIoEAIBIIACKBACASCACiwXQ63e9838ODLC4u1mQyqdFo1OcyTY3H43q8s1NnXnut9ZRe7j14UEdPnqjRr8+3ntLZ+M7d2tzcaj0DnisHvIY/jcGTDub6Xvkgu1u7tXFzY9a3mZnd2q3BzP8r/Uj6/0Jq7pWTVaM3Wq/obvxl1dZOz5+84Ecy05e+4XBYG+sbdbWuzvI2M3WlrtTcv35d77/zTuspvbz34Yc1/9abtfLXG62ndLb8m4tV9z+qlT+0XtLd8h+rbq62XgFPx2cQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFANJhOp/ud73t4kMXFxdpY36hhDftcpqm1WqvBsf+pM6+91npKL/cePKijJ0/U6NfnW0/pbHznbtX3WzV6o/WS7sZfVm3utF7Bi+SA1/CnMXjSwVzfK/8UPHppr+79x+H+Xb2z87jq8aQ+fnin9ZTOdh7v1HzrEc/AK69UjUatV3Q3Hv/w9bA/w9ZWVf/X1hfbTAMxHA5rY32jrtbVWd5mpq7Ulfr7W3+vX77/y9ZTevn8vc+rqg71c3z+3ud1YWdSK39ovaS75T9W1b9Vray0XtLd8vIPXw/7M9y82XrF889nEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQDSYTqf7ne97eJDFxcXaWN+oYQ37XKaptVqrR/OP6uSZk62n9LJzb6eq6lA/x869nVrY26vRG62XdDf+sqqOVY1GrZd0Nx7/8PWwP8PmZusVz8YBr+FPY/Ckg7m+Vz7Iw3pYd+rOrG8zU/M1X0tHl1rP6GV1sFrb29s1+XjSekovk2PzdWfzV61ndDbZ/bROzh2p3b1R6ymdTWtc0+2H9eijw/vDxt7uw3qlHteo9ZAexlU16+/ATAMxHA5rfX19lrf4USwtLdW1a9daz+jl8uXLdevWrdYzels4/au68LvrrWd0dvvPl+rcL47Xjb+stJ7S2cXfLtf3f7td1159u/WUzi5vfFIndrdqpfWQHpZ/hHv4DAKASCAAiAQCgEggAIgEAoBIIACIBAKASCAAiAQCgEggAIgEAoBIIACIBAKASCAAiAQCgEggAIgEAoBIIACIBAKASCAAiAQCgEggAIgEAoBIIACIBAKASCAAiAQCgEggAIgEAoBIIACIBAKASCAAiAQCgEggAIgEAoBIIACIBAKASCAAiAQCgEggAIgEAoBIIACIBAKASCAAiAQCgEggAIgG0+l0v/N9Dw+yuLhY6+vrfS7xXFhYWKizZ8+2ntHL6upqbW9vt57R29GXFmrhZ+daz+hs+x+f1qkTR+r826PWUzq7+8m4ppuTOjt3qvWUzlZ3H9aRelyj1kN6GFfVfFV9tf9r+NMYPOlgru+VfwoOiOihMbcwX6eWzrSe0dnks3tV37Ve0d8L8cvpyBNfU3iBzDQQw+HwhXgHsbS0VNeuXWs9o5fLly/XvcHjunD9T62ndHb70u9r8N/H6sLvrree0tntP1+qc784Xjf+stJ6SmcXf7tc3//tdl179e3WUzq7vPFJndjdqpXWQ3pY/hHu4TMIACKBACASCAAigQAgEggAIoEAIBIIACKBACASCAAigQAgEggAIoEAIBIIACKBACASCAAigQAgEggAIoEAIBIIACKBACASCAAigQAgEggAIoEAIBIIACKBACASCAAigQAgEggAIoEAIBIIACKBACASCAAigQAgEggAIoEAIBIIACKBACASCAAigQAgEggAIoEAIBIIACKBACASCAAigQAgGkyn0/3O9z08yOLiYq2vr/e5xHNhYWGhzp4923pGL6urq7VT05pfOtN6SmeTz+5VfTeohZ+daz2ls+1/fFqnThyp82+PWk/p7O4n45puTurs3KnWUzpb3X1YR+pxjVoP6WFcVfNV9dX+r+FPY/Ckg7m+V/4p2N7erlu3brWe0dvR+cP7G/qfHh87Uhunj7ee0d3mkdqrqt1D/N59WlWDl4/VsX9/rfWUzgbffFd1/FTVhQutp3Q3HledPDnTW8w0EMPh8IV4B/GimD/3Vl24/qfWMzq7fen3tfntfNXVldZTuruyXOderbq+stJ6SWeXlpdr7osv6sa777ae0tnFDz6ouZ//vFYO8fdheXl55vc4xD/HADBLAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAESD6XS63/m+hwdZXFys9fX1PpfgGTq6MF/zS2daz+hs8tm9erx3tGo4aj2lu7VxLcxVLY1GrZd09tl4XINvv63zr7/eekpnd7/5pgYvv1yjQ/x9GI/HNT8/X1999VXfSw2edDDX98ocHo+3J7X5Xx+3ntHPyX9pvaC3Xj91PS8GT3xNOTS2Njfr5s2brWf0sr29PdPrzzQQw+HQOwierTcvVF1dab2iuyvLde7VqusrK62XdHZpebnmvviibrz7buspnV384IP66MsvW8/obW9vb6bX9xkEAJFAABAJBACRQAAQCQQAkUAAEAkEAJFAABAJBACRQAAQCQQAkUAAEAkEAJFAABAJBACRQAAQCQQAkUAAEAkEAJFAABAJBACRQAAQCQQAkUAAEAkEAJFAABAJBACRQAAQCQQAkUAAEAkEAJFAABAJBACRQAAQCQQAkUAAEAkEAJFAABAJBACRQAAQCQQAkUAAEAkEAJFAABAJBACRQAAQDabT6X7n+x4eZHFxsdbX1/tcAv6vU69UDUetV3S3Nq6Fuaql0aj1ks4+G49r8O23df7111tP6ezuN9/U1nfftZ7xTBzwGv40Bk86mOk7iNOnT9eRI96k8AwdP9l6QT8n5uvE/HzrFb2cmp+vU8ePt57Ry6mXXnoh/vfJ3NzcTK8/03cQADz32ryDAODwEggAIoEAIBIIACKBACASCAAigQAgEggAIoEAIBIIACKBACASCAAigQAgEggAIoEAIDroX5t44t8TDsCLzTsIACKBACASCAAigQAgEggAIoEAIPpf6f4QOH+emKcAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 378x378 with 1 Axes>"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sequencial_match = match_with_flow(tiling_custom)\n",
    "filling = sequencial_match[-1]\n",
    "draw_filling(filling)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "93950d608af649dcb98a98b6036a3ba8",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "HBox(children=(Play(value=0, interval=200), Button(description='Prev', style=ButtonStyle()), Button(descriptio…"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "818c180c0ce64043a3f5d6fffe720066",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "interactive(children=(IntSlider(value=0, description='step', max=15), Output()), _dom_classes=('widget-interac…"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "animate_list(list(map(draw_filling, sequencial_match)), play=True);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Суть алгоритма Куна (да и любого другого алгоритм для нахождения максимального паросочетания) заключается в нахождении \"аугментирующих путей\". В терминах доминошек это цепочки из доминошек, у которых на обоих концах рядом есть по свободной клетке, такие цепочки можно заменить на цепочки большей длины, охватывающие эти клетки. Более того, основное утверждение, на котором работают все алгоритмы нахождения максимального паросочетания, заключается в том, что если такой цепочки не удается найти, то значит большего замощения нам не получить"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Раскраска планарного графа в 5 цветов\n",
    "Эта задача идет в качестве бонуса: иллюстрации выше не всегда из-за того, что используется множество цветов. Чтобы проще было отделить доминошки друг от друга для каждой выделяется отдельный цвет. Однако можно использовать гораздо меньше цветов, чтобы при этом соседние доминошки были разных цветов. Для этого можно рассмотреть другой граф: вершины -- доминошки, ребра между соседними доминошками. Искомая раскраска -- это стандартная вершинная раскраска графа, т.е. такая раскраска, в которой соседние вершины имеют разный цвет. Для планарных графов известно, что они могут быть раскрашены в [4 цвета](https://ru.wikipedia.org/wiki/Теорема_о_четырёх_красках). Правда хорошего алгоритма для покраски в 4 цвета нет, а вот для 5 есть."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "def color_5(filling):\n",
    "    result = [[i for i in row] for row in filling]\n",
    "    # Строим граф\n",
    "    domino_tiles = [[] for i in range(max(map(max, filling)) + 1)]\n",
    "    domino_neighbours = [set() for i in range(max(map(max, filling)) + 1)]\n",
    "    degree = [0 for i in range(max(map(max, filling)) + 1)]\n",
    "    \n",
    "    n = len(filling)\n",
    "    m = len(filling[0])\n",
    "    \n",
    "    for i, row in enumerate(filling):\n",
    "        for j, num in enumerate(row):\n",
    "            if num >= 0:\n",
    "                domino_tiles[num].append((i, j))\n",
    "                \n",
    "    for i, tiles in enumerate(domino_tiles):\n",
    "        for x, y in tiles:\n",
    "            for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)]:\n",
    "                a, b = x + dx, y + dy\n",
    "                if 0 <= a and a < n and 0 <= b and b < m and filling[a][b] >= 0 and filling[a][b] != i \\\n",
    "                        and filling[a][b] not in domino_neighbours[i]:\n",
    "                    domino_neighbours[i].add(filling[a][b])\n",
    "                    degree[i] += 1\n",
    "    \n",
    "    # Первым делом нужно найти такой порядок вершин, все вершины имели не больше 5 соседей среди\n",
    "    # предыдущих. Такой существует в силу того, что граф планарный, а найти его эффективнее всего\n",
    "    # по очереди находя вершину наименшей степени и удаляя её из графа, так мы получем обратный порядок\n",
    "    active_degrees = [set() for i in range(max(degree) + 1)]\n",
    "    for i, deg in enumerate(degree):\n",
    "        active_degrees[deg].add(i)\n",
    "    \n",
    "    reversed_order = []\n",
    "    \n",
    "    for step in range(len(domino_tiles)):\n",
    "        min_degree = min([i for i, dominoes in enumerate(active_degrees) if len(dominoes) > 0])\n",
    "        domino = active_degrees[min_degree].pop()\n",
    "        \n",
    "        reversed_order.append(domino)\n",
    "        for other in domino_neighbours[domino]:\n",
    "            if other in active_degrees[degree[other]]:\n",
    "                active_degrees[degree[other]].remove(other)\n",
    "                degree[other] -= 1\n",
    "                active_degrees[degree[other]].add(other)                \n",
    "        \n",
    "    # Теперь перебираем в обратном порядке и либо красим в еще не занятый цвет,\n",
    "    # если есть свободный из 5 цветов, иначе находим цепочку из чередующихся цветов,\n",
    "    # которые могут быть перекрашены. Такая найдется в силу планарности\n",
    "    colors = [-1 for domino in domino_tiles]\n",
    "    slices = [draw_filling(result)]\n",
    "    for domino in reversed(reversed_order):\n",
    "        used_colors = [colors[other] for other in domino_neighbours[domino] if colors[other] != -1]\n",
    "        \n",
    "        domino_color = len(used_colors)\n",
    "        for i, color in enumerate(sorted(set(used_colors))):\n",
    "            if i != color:\n",
    "                domino_color = i\n",
    "                break\n",
    "     \n",
    "        if domino_color < 5:\n",
    "            colors[domino] = domino_color\n",
    "            for x, y in domino_tiles[domino]:\n",
    "                result[x][y] = domino_color\n",
    "                \n",
    "            slices.append(draw_filling(result))        \n",
    "            continue\n",
    "           \n",
    "        # Начиная отсюда код я не тестировал, не нашел примера        \n",
    "        c = 0\n",
    "        other = [other for other in domino_neighbours[domino] if colors[other] == c]\n",
    "        visited = set([other])\n",
    "        q = Queue()\n",
    "        q.put(other)\n",
    "        domino_was_reached = False\n",
    "        while not q.empty():\n",
    "            cur = q.get()\n",
    "            for other in domino_neighbours[cur]:\n",
    "                if other == domino:\n",
    "                    domino_was_reached = True\n",
    "                    break\n",
    "                if color[other] == c or color[other] == c + 1 and other not in visited:\n",
    "                    visited.add(other)\n",
    "                    q.put(other)\n",
    "                    \n",
    "        if not domino_was_reached:\n",
    "            for other in visited:\n",
    "                color[other] = color[other] ^ 1\n",
    "                for x, y in domino_tiles[other]:\n",
    "                    result[x][y] = color[other]\n",
    "            color[domino] = c\n",
    "            for x, y in domino_tiles[domino]:\n",
    "                result[x][y] = c\n",
    "                \n",
    "            slices.append(draw_filling(result))\n",
    "            continue\n",
    "            \n",
    "        # Проделываем тоже самое для 2 и 3.\n",
    "        c = 2\n",
    "        other = [other for other in domino_neighbours[domino] if colors[other] == c]\n",
    "        visited = set([other])\n",
    "        q = Queue()\n",
    "        q.put(other)\n",
    "        domino_was_reached = False\n",
    "        while not q.empty():\n",
    "            cur = q.get()\n",
    "            for other in domino_neighbours[cur]:\n",
    "                if other == domino:\n",
    "                    domino_was_reached = True\n",
    "                    break\n",
    "                if color[other] == c or color[other] == c + 1 and other not in visited:\n",
    "                    visited.add(other)\n",
    "                    q.put(other)\n",
    "        for other in visited:\n",
    "            color[other] = color[other] ^ 1\n",
    "            for x, y in domino_tiles[other]:\n",
    "                result[x][y] = color[other]\n",
    "        color[domino] = c\n",
    "        for x, y in domino_tiles[domino]:\n",
    "            result[x][y] = c\n",
    "        slices.append(draw_filling(result))\n",
    "                    \n",
    "    return result, slices      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "6bf98b8d66a241cfacebe5b9741cfa14",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "HBox(children=(Play(value=0, interval=200), Button(description='Prev', style=ButtonStyle()), Button(descriptio…"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "0e6e31aa72dd4d6ca6c5377d35531189",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "interactive(children=(IntSlider(value=0, description='step', max=15), Output()), _dom_classes=('widget-interac…"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "filling_colored, slices =color_5(filling)\n",
    "animate_list(slices, play=True);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAb4AAAG+CAYAAADsjWHpAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy86wFpkAAAACXBIWXMAAAsTAAALEwEAmpwYAAAPXUlEQVR4nO3dzW4UB7rH4bfdDcJteyYj4cVIXnbM4UMJvgPugCVSLiAXlQuIxJI7YBMJjYRwojEIzyyHAwRGAveHDx7bfRZWlJWdUPR0Ufk/z6YXJVW9r1zVv+60Inrz+bwAIMVK2wMAwDIJHwBRhA+AKMIHQBThAyCK8AEQZfAbx/2/DgB0Ue+8A77xARBF+ACIInwARBE+AKIIHwBRhA+AKMIHQBThAyCK8AEQRfgAiCJ8AEQRPgCiCB8AUYQPgCjCB0AU4QMgivABEOW3/gX2hdnZ2ak3b97UaDRa1iUX7p///GdVlR1aZofPgx0+D3+EHarO9tjc3KwnT57816+1tPC9efOmXr89qOn8w7IuuXDjtwdVVZ3fYX5pVu8n79sepbHZ+1lVVed3GM56dfh63PYojR0cT6t61fkdDi+tdv6Zrur2+1LV2R7/fn+ylGstLXyj0aim8w+1c/f+si65cE8e3Kuq6vwOx3/9e21/t932KI3tf7tfVdX5HW78uFLff/FV26M09s27n6qqOr/D/uaNzj/TVd1+X6r6dY9l8BsfAFGED4AowgdAFOEDIIrwARBF+ACIInwARBE+AKIIHwBRhA+AKMIHQBThAyCK8AEQRfgAiCJ8AEQRPgCiCB8AUYQPgCjCB0AU4QMgivABEEX4AIgifABEET4AoggfAFGED4AowgdAFOEDIIrwARBF+ACIInwARBE+AKIIHwBRhA+AKMIHQBThAyCK8AEQRfgAiCJ8AEQRPgCiCB8AUYQPgCjCB0AU4QMgivABEEX4AIgifABE6c3n84uOX3jwY2xtbdWrNwe1cfXmok65dOO3e1VVnd9hfnlaw2vDtkdpbPZ8VlXV+R3WJr26Plhre5TGnh1Pq6o6v8Ps8rDzz3RVt9+Xqs726F9aqw+Tl4s6Ze+8A4NFXeH3ODma1Lv/fbTMSy7cevVr++enbY/R2LPjWY2PTmvyeNL2KJ+kf2m9Bi9vtT1GY72jver9aVyrOwdtj9LYyu7Z6+rtju9wMq3jv/697VEamx+cfRDs8g5VZ3vMVz8s5VpLC99oNKoXL14s63L/NTcGa/X9F1+1PUZj37z7qf523N03ql9sbN6qnbv32x6jsScP7tXXXz6qhw/bnqS5O3fOXru+w+PJsLa/2257lMb2v92vqur0DlW/7rEMfuMDIIrwARBF+ACIInwARBE+AKIIHwBRhA+AKMIHQBThAyCK8AEQRfgAiCJ8AEQRPgCiCB8AUYQPgCjCB0AU4QMgivABEEX4AIgifABEET4AoggfAFGED4AowgdAFOEDIIrwARBF+ACIInwARBE+AKIIHwBRhA+AKMIHQBThAyCK8AEQRfgAiCJ8AEQRPgCiCB8AUYQPgCjCB0AU4QMgivABEEX4AIgifABEET4AoggfAFF68/n8ouMXHvwYW1tb9eLFi0WdrjUb1a/rg7W2x2js2fG0xnXS9hifrH95ozau3mx7jMbGb/dqfXVct2+3PUlzu7tnr13fYXyyUsNrw7ZHaWz2fFZV1ekdqs726A/7dfT6aFGn7J13YLCoK/weK2srNfyf7v5xZs9nNZ+2PQVVVXXxB7ZOODkY1OEP3X0eTo+nVb2qwx+6+0Hw9HhaK5dWa/DyVtujNNY72quqqsHL7n4QrDrbo1erS7nW0sI3Go3q/eR9bX+3vaxLLtz+t/t148eV+v6Lr9oepbFv3v1Ufzs+aHuMT7axeat27t5ve4zGnjy4V9s/P+38vVRVnd9hf/NG5++lqur0DlW/7rEMfuMDIIrwARBF+ACIInwARBE+AKIIHwBRhA+AKMIHQBThAyCK8AEQRfgAiCJ8AEQRPgCiCB8AUYQPgCjCB0AU4QMgivABEEX4AIgifABEET4AoggfAFGED4AowgdAFOEDIIrwARBF+ACIInwARBE+AKIIHwBRhA+AKMIHQBThAyCK8AEQRfgAiCJ8AEQRPgCiCB8AUYQPgCjCB0AU4QMgivABEEX4AIgifABEET4AoggfAFF68/n8ouMXHvwYW1tb9fL9yxpeGy7qlEs3ez6rtUmvrg/W2h6lsWfH0xrXSdtjfLL+5Y3auHqz7TEaG7/dq+HRrPP3UlV1fofZ5WHn76Wq6vQOVWd79C+t1YfJy0WdsnfegcGirpBidnm19q/eaHuMxmZv9+pPV8a1s9P2JM3t7lZVjevrLx+1PElzu9OqyeWVenrttO1RGps9P/tc3PUd1vvdv5eqqtM7VJ3tMVybLuVaSwvfaDSq95P3tf3d9rIuuXD73+7X4OWt2rl7v+1RGnvy4F59/eWjeviw7Umau3Pn7LXrOzyeDDv/PFRV53fYWZ90/l6q6vbzUPXLHsv5EOU3PgCiCB8AUYQPgCjCB0AU4QMgivABEEX4AIgifABEET4AoggfAFGED4AowgdAFOEDIIrwARBF+ACIInwARBE+AKIIHwBRhA+AKMIHQBThAyCK8AEQRfgAiCJ8AEQRPgCiCB8AUYQPgCjCB0AU4QMgivABEEX4AIgifABEET4AoggfAFGED4AowgdAFOEDIIrwARBF+ACIInwARBE+AKIIHwBRhA+AKMIHQBThAyCK8AEQpTefzy86fuHBj7G1tVUv37+s4bXhok65dLPns+odrdXG1Zttj9LY+O1era+O6/bttidpbnf37LXrO4xPVjr/PFRV53fY6J92/l6q6vbzUHW2x/p61b/+tbDs9M47MFjUFX6P4axXN37s7pfMZ8e9Ory0sD9Ka04OBnX4Q3ffrE6Pp1W9qsMf1toepbHT42mtXFqtwctbbY/SWO9or6qqBi+7+0Gwd7RXJ/859Dx8Bk6Pp3UyXU4flha+0WhUh6/H9f0XXy3rkgv3zbufan/zRu3cvd/2KI09eXCvtn9+2vm/Q1V1foc/wr1UVZ3fwfPwefhlj2Xo7tcvAGhA+ACIInwARBE+AKIIHwBRhA+AKMIHQBThAyCK8AEQRfgAiCJ8AEQRPgCiCB8AUYQPgCjCB0AU4QMgivABEEX4AIgifABEET4AoggfAFGED4AowgdAFOEDIIrwARBF+ACIInwARBE+AKIIHwBRhA+AKMIHQBThAyCK8AEQRfgAiCJ8AEQRPgCiCB8AUYQPgCjCB0AU4QMgivABEEX4AIgifABEET4AoggfAFGED4Aovfl8ftHxCw9+jK2trTp48aquD9YWdcqle3Y8rdnlYW1cvdn2KI2N3+7V8GjW+b9DVXV+hz/CvVRVnd/B8/B5eHY8rWGvX69OPyzqlL3zDgwWdYXf5dwxumP9yri+/vJR22M0tjutmlxeqafXTtsepbHZ87PPY13fYb3f/Xupqjq/g+fh8zB7Pq8PVxb2XetCSwvfaDSqw9fj+v6Lr5Z1yYX75t1PtbpzUA8ftj1Jc3fuVD2eDGv7u+22R2ls/9v9qqrO77CzPun8vVRVnd/B8/B5+GWPZfAbHwBRhA+AKMIHQBThAyCK8AEQRfgAiCJ8AEQRPgCiCB8AUYQPgCjCB0AU4QMgivABEEX4AIgifABEET4AoggfAFGED4AowgdAFOEDIIrwARBF+ACIInwARBE+AKIIHwBRhA+AKMIHQBThAyCK8AEQRfgAiCJ8AEQRPgCiCB8AUYQPgCjCB0AU4QMgivABEEX4AIgifABEET4AoggfAFGED4AowgdAFOEDIIrwARBF+ACI0pvP5xcdv/Dgx9ja2qqDF6/q+mBtUadcumfH01r580ndvt32JM3t7laNT1ZqeG3Y9iiNzZ7Pqqo6v8NG/7Tz91JVdX4Hz8PnYfZ8Vv1hv45eHy3qlL3zDgwWdYXf4/DSau1v3ljmJRdq9nav1ubjtsf4ZGuzXl3/sbtf9p8d96p61fkdppfW68d/3Gp7lMYmh3tVVfXjP262PElzk8O9Gv7nsG50/F7q+vNQdbbH6uG5rVqopYVvNBrVdP6hdu7eX9YlF+7Jg3v19ZeP6uHDtidp7s6dqsMf1ur7L75qe5TGvnn3U1VV53fY37zR+eehqjq/w/bPTzt/L1V1+3mo+nWPZej2RwQA+EjCB0AU4QMgivABEEX4AIgifABEET4AoggfAFGED4AowgdAFOEDIIrwARBF+ACIInwARBE+AKIIHwBRhA+AKMIHQBThAyCK8AEQRfgAiCJ8AEQRPgCiCB8AUYQPgCjCB0AU4QMgivABEEX4AIgifABEET4AoggfAFGED4AowgdAFOEDIIrwARBF+ACIInwARBE+AKIIHwBRhA+AKMIHQBThAyCK8AEQRfgAiCJ8AETpzefzi45fePBjbG1t1as3B7Vx9eaiTrl047d7tb46rtu3256kud3dqtP3/bo+WGt7lMaeHU+rqjq/w+zysPPPQ1V1fofh0azz91JVt5+HqrM9hr1+vTr9sKhT9s47MFjUFVKMj/v1eLLa9hiNzU5mVevzenrttO1RGps9n9fp5LT+dnzQ9iif5E9XxvX1l4/aHqOx3bP3287vMLm80vnnoao6vUPV2R4frizsu9aFlha+0WhU0/mH2rl7f1mXXLgnD+7V8V//Xtvfbbc9SmP73+5XVXV+h8njSdtjfLKdnaqHD9ueork7d85eu77D48mw889DVbef6apf91gGv/EBEEX4AIgifABEET4AoggfAFGED4AowgdAFOEDIIrwARBF+ACIInwARBE+AKIIHwBRhA+AKMIHQBThAyCK8AEQRfgAiCJ8AEQRPgCiCB8AUYQPgCjCB0AU4QMgivABEEX4AIgifABEET4AoggfAFGED4AowgdAFOEDIIrwARBF+ACIInwARBE+AKIIHwBRhA+AKMIHQBThAyCK8AEQRfgAiCJ8AEQRPgCiCB8AUYQPgCi9+Xx+0fELD36Mra2tevXmoDau3lzUKZdu/Hav5penNbw2bHuUxmbPZ1VVnd/hdHLa9hif7M9/rrp9u+0pmtvdPXvt+g7jk5XOPw9V3X6mq8726A/7dfT6aFGn7J13YLCoK/yWzc3N+vf7k2Vd7r+if2mt5lc+tD3GJ+kP+22P8Mn6w36dTk8X+LGsHcNuv0/V+nrbE3y69fWq//tPt//D1x/hma462+PKX64s5VpL+8YHAEt07je+bn/UAYCPJHwARBE+AKIIHwBRhA+AKMIHQBThAyCK8AEQRfgAiCJ8AEQRPgCiCB8AUYQPgCjCB0AU4QMgivABEEX4AIgifABEGfzG8XP/6XYA6CLf+ACIInwARBE+AKIIHwBRhA+AKMIHQJT/B6qDb1dK1Ua6AAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x432 with 1 Axes>"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "filling_random = cover_maximum_possible(tiling_random)\n",
    "colored, slices = color_5(filling_random)\n",
    "draw_filling(colored)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.5"
  },
  "widgets": {
   "application/vnd.jupyter.widget-state+json": {
    "state": {
     "05aad90f1bfc48588bce3e59d27dfb32": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "VBoxModel",
      "state": {
       "_dom_classes": [
        "widget-interact"
       ],
       "children": [
        "IPY_MODEL_dca6f1bc6d24423faa41dcd515b30541",
        "IPY_MODEL_23ca7c6f9bb14e708da95bfd1bd68f2d"
       ],
       "layout": "IPY_MODEL_32b12a14665546e49aad430a4a514c08"
      }
     },
     "07cc4c2e0232472aa7e02615ffd17591": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.2.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "0d19ff4618e54727a94cf1135a5eba80": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "ButtonStyleModel",
      "state": {}
     },
     "0d94b89163d64e1bb8c8ca2391b42505": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.2.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "0defc0b51be549b3b5e8f99fc5b0de43": {
      "model_module": "@jupyter-widgets/output",
      "model_module_version": "1.0.0",
      "model_name": "OutputModel",
      "state": {
       "layout": "IPY_MODEL_17651766388e4fa88b7102eb180fdc86",
       "outputs": [
        {
         "data": {
          "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYgAAAGICAYAAABbQ3cmAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy86wFpkAAAACXBIWXMAAAsTAAALEwEAmpwYAAAI/0lEQVR4nO3dMW4a7RbH4UNEZSFTuaNkAbCDWTqsILMAl0YpXEGoPbeKPt2rvyE348kw8z1P+0rvnCPL/DQiihdd1xUA/K9vYw8AwGMSCAAigQAgEggAIoEAIBIIAKLlnXP/BhZg3hafHXiDACASCAAigQAgEggAIoEAIBIIACKBACASCAAigQAgEggAIoEAIBIIACKBACASCAAigQAguvf3IHrZ7/f1/v5e2+12yMcM6vX1tapq0jtUzWMPOzwGOzyG19fXenl5qe/fvw/2jEED8f7+XtfrdchHDG7q8/8yhz2u12tdLpc6nU5jj9KbHR7D1Hf48ePHoPcPGohfdT4cDkM+ZlBN01TVtHeomsceTdPU8Xgcewx4GB8fH4Pe7zsIACKBACASCAAigQAgEggAIoEAIBIIACKBACASCAAigQAgEggAIoEAIBIIACKBACASCAAigQAgEggAIoEAIBIIACKBACASCAAigQAgEggAIoEAIBIIACKBACASCAAigQAgEggAIoEAIBIIACKBACASCAAigQAgEggAIoEAIBIIACKBACASCAAigQAgEggAIoEAIBIIACKBACASCAAigQAgWnRdd+v85uE9m82mrtdr7Xa7PteMqm3bqqpJ71A1jz3atq3z+Tz2GPBQ7nyG/47FZwfLvjfD37Rerycfucvl8hW/1DC4QQOx3W6rqupwOAz5mEE1TVNV096hah57zGWH4/E49hjwW3wHAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARIuu626d3zy8Z7PZ1PV6rd1u1+eaUbVtW1U16R2q5rHHXHY4n89jj8GM3PkM/x2Lzw6WfW8G/j/r9Xrykauafqgvl8tXfLjO2qCB2G63VVV1OByGfMygmqapqmnvUDWPPezwGOayw/F4HHuMh+c7CAAigQAgEggAIoEAIBIIACKBACASCAAigQAgEggAIoEAIBIIACKBACASCAAigQAgEggAIoEAIBIIACKBACASCAAigQAgEggAIoEAIBIIACKBACASCAAigQAgEggAIoEAIBIIACKBACASCAAigQAgEggAIoEAIBIIACKBACASCAAigQAgEggAIoEAIBIIACKBACASCAAigQAgEggAIoEAIFp0XXfr/ObhPZvNpq7Xa+12uz7XjKpt26qqSe9QNY897PAY5rLD+Xwee4wvcecz/HcsPjtY9r35nsvlUsfjcejHDOr5+XnsEb6EnwX8Y71eTz5yT09Pgz5j0EBst9s6nU5DPuKv2O/3dTgcxh6jl6ZpJh+Hqun/LJqmqaqyw8jmtMOQfAcBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEi67rbp3fPLxns9nU6XTqc8VDWK/Xtdvtxh6jl7Zt63w+jz1Gb1P/WbRtW1Vlh5HNZYfValVvb299r1p8drDse/O/wZ2ITsZcPlyBv2PQQGy321m8Qez3+zocDmOP0UvTNFVVk97DDo/BDo/h1w5D8h0EAJFAABAJBACRQAAQCQQAkUAAEAkEAJFAABAJBACRQAAQCQQAkUAAEAkEAJFAABAJBACRQAAQCQQAkUAAEAkEAJFAABAJBACRQAAQCQQAkUAAEAkEAJFAABAJBACRQAAQCQQAkUAAEAkEAJFAABAJBACRQAAQCQQAkUAAEAkEAJFAABAJBACRQAAQCQQAkUAAEAkEAJFAABAJBACRQAAQLbquu3V+8/CezWZTp9OpzxUPYb1e1263G3uMXtq2raqa9B52eAx2eAxt29Zqtaq3t7e+Vy0+O1j2vfnf4Hw+1/F4HHuM3p6fn8ceAZiQQQOx3W5n8QYxF/v9vg6Hw9hj/LGmaaqq7DAyOzyGXzsMyXcQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARIuu626d3zy8Z7PZ1Ol06nMFX2i9Xtdutxt7jD/Wtm1VlR1GZofH0LZtrVarent763vV4rODZd+bmY7z+VzH43HsMXp5fn4eewRm4nK5TP734efPn4PeP2ggttutNwi+1H6/r8PhMPYYf6xpmqoqO4ysaZrJx6Gq6uPjY9D7fQcBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEi67rbp3fPLxns9nU6XTqcwX8l/V6Xbvdbuwx/ljbtlVVdhhZ27Z1Pp/HHuNL3PkM/x2Lzw4GfYN4eXmpb9+8pPB1np6exh6hl9VqVavVauwxepnLDnP4bFoul4PeP+gbBAAPb5w3CACmSyAAiAQCgEggAIgEAoBIIACIBAKASCAAiAQCgEggAIgEAoBIIACIBAKASCAAiAQCgOjeX5v49P8JB2DevEEAEAkEAJFAABAJBACRQAAQCQQA0X8AeJO3/4mt1HgAAAAASUVORK5CYII=\n",
          "text/plain": "<Figure size 378x378 with 1 Axes>"
         },
         "metadata": {},
         "output_type": "display_data"
        }
       ]
      }
     },
     "0e54d8098fca453e91eb071df42d27bf": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "PlayModel",
      "state": {
       "interval": 200,
       "layout": "IPY_MODEL_584c9264bc8b4cc6b297a85fd0a12fa9",
       "style": "IPY_MODEL_8b7bd1a9344f404281b1fe0110f527e0"
      }
     },
     "0e6e31aa72dd4d6ca6c5377d35531189": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "VBoxModel",
      "state": {
       "_dom_classes": [
        "widget-interact"
       ],
       "children": [
        "IPY_MODEL_16c1407e582041bbacdc0055e9d25b21",
        "IPY_MODEL_728f2c0b73884beba5ed148ab1dc14d6"
       ],
       "layout": "IPY_MODEL_1e4ef1d82c3d4f2d8793b4f7213a22a8"
      }
     },
     "0e717dd0246b401d813f6dfe6067ebee": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "ButtonStyleModel",
      "state": {}
     },
     "1311d1c1bc124baa9f2ba51552d9676e": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "LinkModel",
      "state": {
       "source": [
        "IPY_MODEL_42decf7650c04ae5ba4aa0d72714ebb2",
        "value"
       ],
       "target": [
        "IPY_MODEL_16c1407e582041bbacdc0055e9d25b21",
        "value"
       ]
      }
     },
     "16c1407e582041bbacdc0055e9d25b21": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "IntSliderModel",
      "state": {
       "description": "step",
       "layout": "IPY_MODEL_696e24d5adfa48e9bf889af2c0d3d5db",
       "max": 15,
       "style": "IPY_MODEL_f7eeb21f2c7247f2b0ddbe5a654def05"
      }
     },
     "17651766388e4fa88b7102eb180fdc86": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.2.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "184f9828e51541f8ad6f708155f4b48e": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "ButtonModel",
      "state": {
       "description": "Next",
       "layout": "IPY_MODEL_3ef96eb952e54e6d8f5f168c837a675c",
       "style": "IPY_MODEL_e0fd9d5a8d064eb7945e68aaf9634bbc"
      }
     },
     "19166e624f3d48a599da796384d8cfc0": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.2.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "1b7fd73e01374c4ebe85b2a98bcb2fa9": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "IntSliderModel",
      "state": {
       "description": "step",
       "layout": "IPY_MODEL_df22d0c094c5445cb5e477381da40e9d",
       "max": 1,
       "style": "IPY_MODEL_3e6fbb7f02cc4a9c9018636d07156e85"
      }
     },
     "1e4ef1d82c3d4f2d8793b4f7213a22a8": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.2.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "2172f4092c7547a28223a6140485715a": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.2.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "23ca7c6f9bb14e708da95bfd1bd68f2d": {
      "model_module": "@jupyter-widgets/output",
      "model_module_version": "1.0.0",
      "model_name": "OutputModel",
      "state": {
       "layout": "IPY_MODEL_97e76bb217394ce2b88204556fb8dcde",
       "outputs": [
        {
         "data": {
          "image/png": "iVBORw0KGgoAAAANSUhEUgAAAb4AAAG+CAYAAADsjWHpAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy86wFpkAAAACXBIWXMAAAsTAAALEwEAmpwYAAAJ7klEQVR4nO3dvW6UZxqA4ceE/A+iiTuXkypI2GfgM0iZY0y5Z+AyHbMFnUuDVoJqDcUiJbMFu0plE/DkmzH3dbWv9D3vo8Hc+hghH2232wGAigf7vgAALEn4AEgRPgBShA+AFOEDIEX4AEh5+IFz/9cBgPvo6KYDb3wApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApHzoN7DvzNnZ2bx69WrW6/VSI3fu8vJyZsYOe2aHw2CHw/A57DDzfo/j4+N59uzZ3z7raLvd3nZ+6+HHODk5mZcvX84H5gEQ9eDBg/n999939bijG+fsasKHrNdr0QPgRn/88ccic3zHB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApCwWvsvLy6VGAcCNvPEBkLJY+Nbr9VKjAOBG3vgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFIWC9/l5eVSowDgRt74AEhZLHzr9XqpUQBwI298AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApi4Xv8vJyqVEAcCNvfACkLBa+9Xq91CgAuJE3PgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AlMXCd3l5udQoALjRw31fALi/vvhyNY+On+z7Gp/s+vXzmZl59MNPe77Jp7t+/Xy+f3c9Z/u+yB1tZua7hWYtFr71ej0vXrxYahywgEfHT+bs51/3fY1P9uwfv8zM3Psdnr78bS72fZE7Ol9wlu/4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBSjrbb7W3ntx5+jJOTk3nx4sWuHgccgC++ejSPfvhp39f4ZNevn8/M3PsdVu+u53TfF7mjzcysZubq9iZ9jKObDh7uasJf8cWXq3l0/GTJkTv1ufyQfP/ues72fZE72MzM2y9Xs7rnf5Y+h89hvjmapz9+veebfLrN2/f/6HXvd/j28czp6b6vcjebzcx33y0yarHwrdfrebv9z5z9/OtSI3fu2T9+mZm59zs8ffnbXOz7IndwPjP/PH7ic9iz85mZs7O5uLjY70Xu4Pz8fGbGDgfg/3sswXd8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApR9vt9rbzWw8/xsnJyfzr1b/n0Q8/7eqRi7t+/Xxm5t7vsHp3Paf7vsgdbGbmzVePfA57tpmZefx4Tk9P93uRO9hsNjMzdjgAm81mVqvVXF1d7eqRRzcdPNzVhL/i+28ezNMfv15y5E5t3r5/Qb73O3z7eOY+/5BsNrMan8Pe/e8vXLhvFgvfer2emZmLi4ulRu7c+fn5zNhh3+xwGOxwGD6HHWb+3GMJvuMDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEg52m63t53fevgxTk5O5s2bN3N6erqrRy5us9nMzNhhz+xwGOxwGD6HHWbe77Farebq6mpXjzy66cAbHwApD5catF6vZ2bm4uJiqZE7d35+PjN22Dc7HAY7HIbPYYeZP/dYgjc+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4CUo+12e9v5rYcf4+TkZN68eTOnp6e7euTiNpvNzIwd9swOh8EOh+Fz2GHm/R6r1Wqurq529cijmw4e7mrChxwfHy816m+zWq32fYU7s8NhsMNhsMPhWK1Wi3VisTc+AFjQjW98vuMDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEh5+IHzG391OwDcR974AEgRPgBShA+AFOEDIEX4AEgRPgBS/gs130gZSBtM7QAAAABJRU5ErkJggg==\n",
          "text/plain": "<Figure size 432x432 with 1 Axes>"
         },
         "metadata": {},
         "output_type": "display_data"
        }
       ]
      }
     },
     "2ab848292ae147d985856cff34a2acba": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.2.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "3179d782383940f486560ed349f2f58d": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "ButtonStyleModel",
      "state": {}
     },
     "32b12a14665546e49aad430a4a514c08": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.2.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "35ff847b5f6946eba97ce5b8b2f22729": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.2.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "392aca3ee4084e5eb91a41de4bedadf3": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.2.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "3da70ce9d67a4ea592e412f953675d33": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.2.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "3e6fbb7f02cc4a9c9018636d07156e85": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "SliderStyleModel",
      "state": {
       "description_width": ""
      }
     },
     "3ef96eb952e54e6d8f5f168c837a675c": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.2.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "41415e78c89744e6b301bc62aecd8b4d": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "ButtonModel",
      "state": {
       "description": "Prev",
       "layout": "IPY_MODEL_7dd62590349d4e049725be1a00f5ab0a",
       "style": "IPY_MODEL_67f9a023c35f450a9faabcebb345fad1"
      }
     },
     "42decf7650c04ae5ba4aa0d72714ebb2": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "PlayModel",
      "state": {
       "interval": 200,
       "layout": "IPY_MODEL_f754cf99022f4a1a8f48a1f22828e823",
       "style": "IPY_MODEL_e10bcbc0ba9c4e548a108d1d0dea9b40"
      }
     },
     "43d60195c6514b54a18ef1ec028c544a": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.2.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "496565b7864d444da0511f104ab12c79": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "ButtonModel",
      "state": {
       "description": "Next",
       "layout": "IPY_MODEL_f060f1a244784b7b99d796e5b7d3cd54",
       "style": "IPY_MODEL_0d19ff4618e54727a94cf1135a5eba80"
      }
     },
     "4a860d35c66b4253a11707051921b035": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.2.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "4aadece1175a4b308dd6fb88c85fc5b5": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "ButtonModel",
      "state": {
       "description": "Next",
       "layout": "IPY_MODEL_d4080037e42848a0a6e6d09bf53e891b",
       "style": "IPY_MODEL_5ab8d002a5c143c1b78bb211f6a9f8d9"
      }
     },
     "4f173956c4514feda29c17e673fe29f2": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "HBoxModel",
      "state": {
       "children": [
        "IPY_MODEL_41415e78c89744e6b301bc62aecd8b4d",
        "IPY_MODEL_a590eb256ca44b4093fe4d197c49cd53"
       ],
       "layout": "IPY_MODEL_07cc4c2e0232472aa7e02615ffd17591"
      }
     },
     "553a9884bdd54405b7872e7e97959044": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.2.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "584c9264bc8b4cc6b297a85fd0a12fa9": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.2.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "5ab8d002a5c143c1b78bb211f6a9f8d9": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "ButtonStyleModel",
      "state": {}
     },
     "61e154e37c5947b29b4090583f6b0764": {
      "model_module": "@jupyter-widgets/output",
      "model_module_version": "1.0.0",
      "model_name": "OutputModel",
      "state": {
       "layout": "IPY_MODEL_3da70ce9d67a4ea592e412f953675d33",
       "outputs": [
        {
         "data": {
          "image/png": "iVBORw0KGgoAAAANSUhEUgAAAb4AAAG+CAYAAADsjWHpAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy86wFpkAAAACXBIWXMAAAsTAAALEwEAmpwYAAAJ7klEQVR4nO3dvW6UZxqA4ceE/A+iiTuXkypI2GfgM0iZY0y5Z+AyHbMFnUuDVoJqDcUiJbMFu0plE/DkmzH3dbWv9D3vo8Hc+hghH2232wGAigf7vgAALEn4AEgRPgBShA+AFOEDIEX4AEh5+IFz/9cBgPvo6KYDb3wApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApHzoN7DvzNnZ2bx69WrW6/VSI3fu8vJyZsYOe2aHw2CHw/A57DDzfo/j4+N59uzZ3z7raLvd3nZ+6+HHODk5mZcvX84H5gEQ9eDBg/n999939bijG+fsasKHrNdr0QPgRn/88ccic3zHB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApCwWvsvLy6VGAcCNvPEBkLJY+Nbr9VKjAOBG3vgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFIWC9/l5eVSowDgRt74AEhZLHzr9XqpUQBwI298AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApi4Xv8vJyqVEAcCNvfACkLBa+9Xq91CgAuJE3PgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AlMXCd3l5udQoALjRw31fALi/vvhyNY+On+z7Gp/s+vXzmZl59MNPe77Jp7t+/Xy+f3c9Z/u+yB1tZua7hWYtFr71ej0vXrxYahywgEfHT+bs51/3fY1P9uwfv8zM3Psdnr78bS72fZE7Ol9wlu/4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBSjrbb7W3ntx5+jJOTk3nx4sWuHgccgC++ejSPfvhp39f4ZNevn8/M3PsdVu+u53TfF7mjzcysZubq9iZ9jKObDh7uasJf8cWXq3l0/GTJkTv1ufyQfP/ues72fZE72MzM2y9Xs7rnf5Y+h89hvjmapz9+veebfLrN2/f/6HXvd/j28czp6b6vcjebzcx33y0yarHwrdfrebv9z5z9/OtSI3fu2T9+mZm59zs8ffnbXOz7IndwPjP/PH7ic9iz85mZs7O5uLjY70Xu4Pz8fGbGDgfg/3sswXd8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApwgdAivABkCJ8AKQIHwApR9vt9rbzWw8/xsnJyfzr1b/n0Q8/7eqRi7t+/Xxm5t7vsHp3Paf7vsgdbGbmzVePfA57tpmZefx4Tk9P93uRO9hsNjMzdjgAm81mVqvVXF1d7eqRRzcdPNzVhL/i+28ezNMfv15y5E5t3r5/Qb73O3z7eOY+/5BsNrMan8Pe/e8vXLhvFgvfer2emZmLi4ulRu7c+fn5zNhh3+xwGOxwGD6HHWb+3GMJvuMDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEg52m63t53fevgxTk5O5s2bN3N6erqrRy5us9nMzNhhz+xwGOxwGD6HHWbe77Farebq6mpXjzy66cAbHwApD5catF6vZ2bm4uJiqZE7d35+PjN22Dc7HAY7HIbPYYeZP/dYgjc+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4CUo+12e9v5rYcf4+TkZN68eTOnp6e7euTiNpvNzIwd9swOh8EOh+Fz2GHm/R6r1Wqurq529cijmw4e7mrChxwfHy816m+zWq32fYU7s8NhsMNhsMPhWK1Wi3VisTc+AFjQjW98vuMDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEh5+IHzG391OwDcR974AEgRPgBShA+AFOEDIEX4AEgRPgBS/gs130gZSBtM7QAAAABJRU5ErkJggg==\n",
          "text/plain": "<Figure size 432x432 with 1 Axes>"
         },
         "metadata": {},
         "output_type": "display_data"
        }
       ]
      }
     },
     "64e667bdb58d4836afaf091eb2fd5dba": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.2.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "67007b7739f34e7da9e487788bedebcd": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "IntSliderModel",
      "state": {
       "description": "step",
       "layout": "IPY_MODEL_d522e29408244271b25be33eb3691363",
       "max": 15,
       "style": "IPY_MODEL_8f0be7bdb6cb46efbe9600976353239e"
      }
     },
     "672a3d5937b04f88b1e81a4266c1458b": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "ButtonStyleModel",
      "state": {}
     },
     "67f9a023c35f450a9faabcebb345fad1": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "ButtonStyleModel",
      "state": {}
     },
     "696e24d5adfa48e9bf889af2c0d3d5db": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.2.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "6ab14bea309d402a8a95dcb40e41bf85": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "ButtonModel",
      "state": {
       "description": "Prev",
       "layout": "IPY_MODEL_19166e624f3d48a599da796384d8cfc0",
       "style": "IPY_MODEL_6db45bb9b8774dd496cbbb29852e6441"
      }
     },
     "6b52f952f7c04a8695be9233277e173c": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "ButtonModel",
      "state": {
       "description": "Prev",
       "layout": "IPY_MODEL_9279ab6962944fc58ddca0c3f2185f50",
       "style": "IPY_MODEL_f76ce08cc2d841c8a3eacc09b90ec834"
      }
     },
     "6bf98b8d66a241cfacebe5b9741cfa14": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "HBoxModel",
      "state": {
       "children": [
        "IPY_MODEL_42decf7650c04ae5ba4aa0d72714ebb2",
        "IPY_MODEL_6b52f952f7c04a8695be9233277e173c",
        "IPY_MODEL_9d9ec0f07c1247cdb109b1c923bcbace"
       ],
       "layout": "IPY_MODEL_0d94b89163d64e1bb8c8ca2391b42505"
      }
     },
     "6d5749585b54469a8266c25964e9d198": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "ButtonModel",
      "state": {
       "description": "Prev",
       "layout": "IPY_MODEL_35ff847b5f6946eba97ce5b8b2f22729",
       "style": "IPY_MODEL_0e717dd0246b401d813f6dfe6067ebee"
      }
     },
     "6db45bb9b8774dd496cbbb29852e6441": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "ButtonStyleModel",
      "state": {}
     },
     "728f2c0b73884beba5ed148ab1dc14d6": {
      "model_module": "@jupyter-widgets/output",
      "model_module_version": "1.0.0",
      "model_name": "OutputModel",
      "state": {
       "layout": "IPY_MODEL_4a860d35c66b4253a11707051921b035",
       "outputs": [
        {
         "data": {
          "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYgAAAGICAYAAABbQ3cmAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy86wFpkAAAACXBIWXMAAAsTAAALEwEAmpwYAAAMXElEQVR4nO3dT29V953H8e8FEwLYk2RUZrLwKJV6U4Ip6eUZeNFmw6JLJHZRpax5AF32AbCOVGWHxLILNmkXZqSoGqSIS1BiEblSoomVSFTCfy4mmRjfWURdzOiDjc7h5ofJ67Xx4ied8zkx3LdvLoLBdDotAPj/jrQeAMDzSSAAiAQCgEggAIgEAoBIIACI5g4492dgAV5sgycdeAcBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUB00L8H0cuFCxfq/v37NRwOZ3mbmVpbW6uqOtTPUPViPIdneD54hufD2tpanT59um7fvj2ze8w0EPfv36/JZDLLW8zcZDKpx48e1eT771tP6WXzwYM6euLlqulu6ymdTSbbtbW1Xevr662n9OYZng+H/Rm+/vrrmV5/poH4Z51XVlZmeZuZWl5ersnqar3/zjutp/Ty3ocf1vxbb9bKX2+0ntLZ8m8u1s3//Kj1DHhu7O3tzfT6PoMAIBIIACKBACASCAAigQAgEggAIoEAIBIIACKBACASCAAigQAgEggAIoEAIBIIACKBACASCAAigQAgEggAIoEAIBIIACKBACASCAAigQAgEggAIoEAIBIIACKBACASCAAigQAgEggAIoEAIBIIACKBACASCAAigQAgEggAIoEAIBIIACKBACASCAAigQAgEggAIoEAIBIIACKBACASCACiwXQ63e9838ODLC4u1mQyqdFo1OcyTY3H43q8s1NnXnut9ZRe7j14UEdPnqjRr8+3ntLZ+M7d2tzcaj0DnisHvIY/jcGTDub6Xvkgu1u7tXFzY9a3mZnd2q3BzP8r/Uj6/0Jq7pWTVaM3Wq/obvxl1dZOz5+84Ecy05e+4XBYG+sbdbWuzvI2M3WlrtTcv35d77/zTuspvbz34Yc1/9abtfLXG62ndLb8m4tV9z+qlT+0XtLd8h+rbq62XgFPx2cQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFANJhOp/ud73t4kMXFxdpY36hhDftcpqm1WqvBsf+pM6+91npKL/cePKijJ0/U6NfnW0/pbHznbtX3WzV6o/WS7sZfVm3utF7Bi+SA1/CnMXjSwVzfK/8UPHppr+79x+H+Xb2z87jq8aQ+fnin9ZTOdh7v1HzrEc/AK69UjUatV3Q3Hv/w9bA/w9ZWVf/X1hfbTAMxHA5rY32jrtbVWd5mpq7Ulfr7W3+vX77/y9ZTevn8vc+rqg71c3z+3ud1YWdSK39ovaS75T9W1b9Vray0XtLd8vIPXw/7M9y82XrF889nEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQDSYTqf7ne97eJDFxcXaWN+oYQ37XKaptVqrR/OP6uSZk62n9LJzb6eq6lA/x869nVrY26vRG62XdDf+sqqOVY1GrZd0Nx7/8PWwP8PmZusVz8YBr+FPY/Ckg7m+Vz7Iw3pYd+rOrG8zU/M1X0tHl1rP6GV1sFrb29s1+XjSekovk2PzdWfzV61ndDbZ/bROzh2p3b1R6ymdTWtc0+2H9eijw/vDxt7uw3qlHteo9ZAexlU16+/ATAMxHA5rfX19lrf4USwtLdW1a9daz+jl8uXLdevWrdYzels4/au68LvrrWd0dvvPl+rcL47Xjb+stJ7S2cXfLtf3f7td1159u/WUzi5vfFIndrdqpfWQHpZ/hHv4DAKASCAAiAQCgEggAIgEAoBIIACIBAKASCAAiAQCgEggAIgEAoBIIACIBAKASCAAiAQCgEggAIgEAoBIIACIBAKASCAAiAQCgEggAIgEAoBIIACIBAKASCAAiAQCgEggAIgEAoBIIACIBAKASCAAiAQCgEggAIgEAoBIIACIBAKASCAAiAQCgEggAIgEAoBIIACIBAKASCAAiAQCgEggAIgG0+l0v/N9Dw+yuLhY6+vrfS7xXFhYWKizZ8+2ntHL6upqbW9vt57R29GXFmrhZ+daz+hs+x+f1qkTR+r826PWUzq7+8m4ppuTOjt3qvWUzlZ3H9aRelyj1kN6GFfVfFV9tf9r+NMYPOlgru+VfwoOiOihMbcwX6eWzrSe0dnks3tV37Ve0d8L8cvpyBNfU3iBzDQQw+HwhXgHsbS0VNeuXWs9o5fLly/XvcHjunD9T62ndHb70u9r8N/H6sLvrree0tntP1+qc784Xjf+stJ6SmcXf7tc3//tdl179e3WUzq7vPFJndjdqpXWQ3pY/hHu4TMIACKBACASCAAigQAgEggAIoEAIBIIACKBACASCAAigQAgEggAIoEAIBIIACKBACASCAAigQAgEggAIoEAIBIIACKBACASCAAigQAgEggAIoEAIBIIACKBACASCAAigQAgEggAIoEAIBIIACKBACASCAAigQAgEggAIoEAIBIIACKBACASCAAigQAgEggAIoEAIBIIACKBACASCAAigQAgGkyn0/3O9z08yOLiYq2vr/e5xHNhYWGhzp4923pGL6urq7VT05pfOtN6SmeTz+5VfTeohZ+daz2ls+1/fFqnThyp82+PWk/p7O4n45puTurs3KnWUzpb3X1YR+pxjVoP6WFcVfNV9dX+r+FPY/Ckg7m+V/4p2N7erlu3brWe0dvR+cP7G/qfHh87Uhunj7ee0d3mkdqrqt1D/N59WlWDl4/VsX9/rfWUzgbffFd1/FTVhQutp3Q3HledPDnTW8w0EMPh8IV4B/GimD/3Vl24/qfWMzq7fen3tfntfNXVldZTuruyXOderbq+stJ6SWeXlpdr7osv6sa777ae0tnFDz6ouZ//vFYO8fdheXl55vc4xD/HADBLAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAEQCAUAkEABEAgFAJBAARAIBQCQQAESD6XS63/m+hwdZXFys9fX1PpfgGTq6MF/zS2daz+hs8tm9erx3tGo4aj2lu7VxLcxVLY1GrZd09tl4XINvv63zr7/eekpnd7/5pgYvv1yjQ/x9GI/HNT8/X1999VXfSw2edDDX98ocHo+3J7X5Xx+3ntHPyX9pvaC3Xj91PS8GT3xNOTS2Njfr5s2brWf0sr29PdPrzzQQw+HQOwierTcvVF1dab2iuyvLde7VqusrK62XdHZpebnmvviibrz7buspnV384IP66MsvW8/obW9vb6bX9xkEAJFAABAJBACRQAAQCQQAkUAAEAkEAJFAABAJBACRQAAQCQQAkUAAEAkEAJFAABAJBACRQAAQCQQAkUAAEAkEAJFAABAJBACRQAAQCQQAkUAAEAkEAJFAABAJBACRQAAQCQQAkUAAEAkEAJFAABAJBACRQAAQCQQAkUAAEAkEAJFAABAJBACRQAAQCQQAkUAAEAkEAJFAABAJBACRQAAQDabT6X7n+x4eZHFxsdbX1/tcAv6vU69UDUetV3S3Nq6Fuaql0aj1ks4+G49r8O23df7111tP6ezuN9/U1nfftZ7xTBzwGv40Bk86mOk7iNOnT9eRI96k8AwdP9l6QT8n5uvE/HzrFb2cmp+vU8ePt57Ry6mXXnoh/vfJ3NzcTK8/03cQADz32ryDAODwEggAIoEAIBIIACKBACASCAAigQAgEggAIoEAIBIIACKBACASCAAigQAgEggAIoEAIDroX5t44t8TDsCLzTsIACKBACASCAAigQAgEggAIoEAIPpf6f4QOH+emKcAAAAASUVORK5CYII=\n",
          "text/plain": "<Figure size 378x378 with 1 Axes>"
         },
         "metadata": {},
         "output_type": "display_data"
        }
       ]
      }
     },
     "7dd62590349d4e049725be1a00f5ab0a": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.2.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "7e8e72da48ef41239b1516892524bb78": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.2.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "7eecf437965c4718b33bc5d0da8ab65e": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "ButtonStyleModel",
      "state": {}
     },
     "818c180c0ce64043a3f5d6fffe720066": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "VBoxModel",
      "state": {
       "_dom_classes": [
        "widget-interact"
       ],
       "children": [
        "IPY_MODEL_67007b7739f34e7da9e487788bedebcd",
        "IPY_MODEL_0defc0b51be549b3b5e8f99fc5b0de43"
       ],
       "layout": "IPY_MODEL_7e8e72da48ef41239b1516892524bb78"
      }
     },
     "8534486c2bae40ada69a949f5468e77b": {
      "model_module": "@jupyter-widgets/output",
      "model_module_version": "1.0.0",
      "model_name": "OutputModel",
      "state": {
       "layout": "IPY_MODEL_553a9884bdd54405b7872e7e97959044",
       "outputs": [
        {
         "data": {
          "image/png": "iVBORw0KGgoAAAANSUhEUgAAAb4AAAG+CAYAAADsjWHpAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy86wFpkAAAACXBIWXMAAAsTAAALEwEAmpwYAAAJ/0lEQVR4nO3dsW5cZRqA4c/ZAAtMSIM7l0NFpNh34Dug5BopuQOXdBmKdC6daKWk2jjFIsFskV1R2SHxcGac93naXzrf/+kkvDoaoRxtt9sBgIoH+74AACxJ+ABIET4AUoQPgBThAyBF+ABIefiec/+vAwD30dFNB774AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEh537/AvjNnZ2fz6tWrWa/XS43cucvLy5kZO+yZHQ6DHQ7Dp7DDzLs9jo+P59mzZ3/7rKPtdnvb+a2HH+Lk5GRevnw575kHQNSDBw/m999/39Xjjm6cs6sJ77Ner0UPgBv98ccfi8zxGx8AKcIHQIrwAZAifACkCB8AKcIHQIrwAZAifACkCB8AKcIHQIrwAZAifACkCB8AKcIHQIrwAZAifACkCB8AKcIHQIrwAZAifACkCB8AKcIHQIrwAZAifACkCB8AKcIHQIrwAZAifACkCB8AKcIHQIrwAZAifACkCB8AKcIHQIrwAZAifACkCB8AKcIHQIrwAZAifACkCB8AKcIHQIrwAZAifACkCB8AKcIHQIrwAZCyWPguLy+XGgUAN/LFB0DKYuFbr9dLjQKAG/niAyBF+ABIET4AUoQPgBThAyBF+ABIET4AUoQPgBThAyBF+ABIET4AUoQPgBThAyBF+ABIET4AUoQPgBThAyBF+ABIET4AUoQPgBThAyBF+ABIET4AUoQPgBThAyBF+ABIET4AUoQPgBThAyBF+ABIET4AUoQPgBThAyBF+ABIET4AUoQPgBThAyBF+ABIET4AUoQPgBThAyBF+ABIET4AUoQPgBThAyBF+ABIWSx8l5eXS40CgBv54gMgZbHwrdfrpUYBwI188QGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApCwWvsvLy6VGAcCNfPEBkLJY+Nbr9VKjAOBGvvgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFKED4AU4QMgRfgASBE+AFIWC9/l5eVSowDgRg/3fQHg/vpmZs72fYk72MzM289Wszp+su+rfLQ3r5/P17+9udfvYebdu/hqoVmLhW+9Xs+LFy+WGgcs4GxmLvZ9iTs4n5lfj5/M2Q8/7fsqH+3Zzz/O05e/3Ov3MPPuXSzFb3wApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfACnCB0CK8AGQInwApAgfAClH2+32tvNbDz/EycnJvHjxYlePAw7A45k53fcl7mAzM9efP5pH336/76t8tDevn8/qtzf3+j3MvHsXq5m5ur1JH+LopoOHu5rwV/zjs9U8On6y5MidevP6+czMvf9L8vVvb+Zs3xe5g83MvP1sNat7/mfpU3gP8803M2f3eIvNZlYz8/S7L/Z9k4+2eftg5svHM6en+77K3Ww2M199tcioxcK3Xq/n7fY/c/bDT0uN3LlnP/84M3Pvd3j68pe52PdF7uB8Zn49fuI97Nn5zMzZ2VxcXOz3Indwfn4+M2OHA/D/PZbgNz4AUoQPgBThAyBF+ABIET4AUoQPgBThAyBF+ABIET4AUoQPgBThAyBF+ABIET4AUoQPgBThAyBF+ABIET4AUoQPgBThAyBF+ABIET4AUoQPgBThAyBF+ABIET4AUoQPgBThAyBF+ABIET4AUoQPgBThAyBF+ABIET4AUoQPgBThAyBF+ABIET4AUoQPgBThAyBF+ABIET4AUoQPgBThAyBF+ABIET4AUoQPgJSj7XZ72/mthx/i5ORk/vXq3/Po2+939cjFvXn9fGbm3u+w+u3NnO77InewmZnrzx95D3u2mZl5/HhOT0/3e5E72Gw2MzN2OACbzWZWq9VcXV3t6pFHNx083NWEv+Lrfz6Yp999seTIndq8ffeBfO93+PLxzH3+S7LZzGq8h737339w4b5ZLHzr9XpmZi4uLpYauXPn5+czY4d9s8NhsMNh+BR2mPlzjyX4jQ+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIOVou93edn7r4Yc4OTmZ6+vrOT093dUjF7fZbGZm7LBndjgMdjgMn8IOM+/2WK1Wc3V1tatHHt104IsPgJSHSw1ar9czM3NxcbHUyJ07Pz+fGTvsmx0Ogx0Ow6eww8yfeyzBFx8AKcIHQIrwAZAifACkCB8AKcIHQIrwAZAifACkCB8AKcIHQIrwAZAifACkCB8AKcIHQIrwAZAifACkCB8AKcIHQIrwAZAifACkCB8AKcIHQIrwAZAifACkCB8AKcIHQIrwAZAifACkCB8AKcIHQIrwAZAifACkCB8AKcIHQIrwAZAifACkCB8AKcIHQIrwAZAifACkCB8AKcIHQIrwAZAifACkCB8AKcIHQMrRdru97fzWww9xcnIy19fXc3p6uqtHLm6z2czM2GHP7HAY7HAYPoUdZt7tsVqt5urqalePPLrp4OGuJrzP8fHxUqP+NqvVat9XuDM7HAY7HAY7HI7VarVYJxb74gOABd34xec3PgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AFOEDIEX4AEgRPgBShA+AlIfvOb/xn24HgPvIFx8AKcIHQIrwAZAifACkCB8AKcIHQMp/AZ8BRQ3lOw6AAAAAAElFTkSuQmCC\n",
          "text/plain": "<Figure size 432x432 with 1 Axes>"
         },
         "metadata": {},
         "output_type": "display_data"
        }
       ]
      }
     },
     "88f3dec4398a49f88808726a0e9f59db": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "LinkModel",
      "state": {
       "source": [
        "IPY_MODEL_0e54d8098fca453e91eb071df42d27bf",
        "value"
       ],
       "target": [
        "IPY_MODEL_67007b7739f34e7da9e487788bedebcd",
        "value"
       ]
      }
     },
     "8b3dd698069b4c5381bd1a9b5e3fcd41": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "ButtonModel",
      "state": {
       "description": "Prev",
       "layout": "IPY_MODEL_f51961a41ca44be38d86f0eafd606341",
       "style": "IPY_MODEL_7eecf437965c4718b33bc5d0da8ab65e"
      }
     },
     "8b7bd1a9344f404281b1fe0110f527e0": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "DescriptionStyleModel",
      "state": {
       "description_width": ""
      }
     },
     "8f0be7bdb6cb46efbe9600976353239e": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "SliderStyleModel",
      "state": {
       "description_width": ""
      }
     },
     "9279ab6962944fc58ddca0c3f2185f50": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.2.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "93950d608af649dcb98a98b6036a3ba8": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "HBoxModel",
      "state": {
       "children": [
        "IPY_MODEL_0e54d8098fca453e91eb071df42d27bf",
        "IPY_MODEL_6d5749585b54469a8266c25964e9d198",
        "IPY_MODEL_184f9828e51541f8ad6f708155f4b48e"
       ],
       "layout": "IPY_MODEL_43d60195c6514b54a18ef1ec028c544a"
      }
     },
     "9740b8bac085405ebb2f6a5504f04009": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.2.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "97e76bb217394ce2b88204556fb8dcde": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.2.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "9803cf3f40b54eaba36bdd51ab6ffc8c": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "HBoxModel",
      "state": {
       "children": [
        "IPY_MODEL_8b3dd698069b4c5381bd1a9b5e3fcd41",
        "IPY_MODEL_4aadece1175a4b308dd6fb88c85fc5b5"
       ],
       "layout": "IPY_MODEL_2172f4092c7547a28223a6140485715a"
      }
     },
     "9d9ec0f07c1247cdb109b1c923bcbace": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "ButtonModel",
      "state": {
       "description": "Next",
       "layout": "IPY_MODEL_2ab848292ae147d985856cff34a2acba",
       "style": "IPY_MODEL_672a3d5937b04f88b1e81a4266c1458b"
      }
     },
     "9fd9f09086d2452d84872e1f51373105": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "HBoxModel",
      "state": {
       "children": [
        "IPY_MODEL_6ab14bea309d402a8a95dcb40e41bf85",
        "IPY_MODEL_496565b7864d444da0511f104ab12c79"
       ],
       "layout": "IPY_MODEL_f896db6f76e242eeb84ca910b0486684"
      }
     },
     "a590eb256ca44b4093fe4d197c49cd53": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "ButtonModel",
      "state": {
       "description": "Next",
       "layout": "IPY_MODEL_bd2b7b5c596b4853b2d2696f576405e5",
       "style": "IPY_MODEL_3179d782383940f486560ed349f2f58d"
      }
     },
     "aa185fafa5a14edf85347824161b6694": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "SliderStyleModel",
      "state": {
       "description_width": ""
      }
     },
     "af6d5d58f21840ba943d0f3b72b6c2ed": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "SliderStyleModel",
      "state": {
       "description_width": ""
      }
     },
     "b1ddcb2d0eac411c8e6a8f86212cf162": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "IntSliderModel",
      "state": {
       "description": "step",
       "layout": "IPY_MODEL_d3dc162a05cc424a9ec0be7aa0154573",
       "max": 1,
       "style": "IPY_MODEL_af6d5d58f21840ba943d0f3b72b6c2ed"
      }
     },
     "bd0496a7f9bd4d3eacaa059079fbfbe8": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "VBoxModel",
      "state": {
       "_dom_classes": [
        "widget-interact"
       ],
       "children": [
        "IPY_MODEL_b1ddcb2d0eac411c8e6a8f86212cf162",
        "IPY_MODEL_8534486c2bae40ada69a949f5468e77b"
       ],
       "layout": "IPY_MODEL_9740b8bac085405ebb2f6a5504f04009"
      }
     },
     "bd2b7b5c596b4853b2d2696f576405e5": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.2.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "d3dc162a05cc424a9ec0be7aa0154573": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.2.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "d4080037e42848a0a6e6d09bf53e891b": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.2.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "d522e29408244271b25be33eb3691363": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.2.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "dca6f1bc6d24423faa41dcd515b30541": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "IntSliderModel",
      "state": {
       "description": "step",
       "layout": "IPY_MODEL_64e667bdb58d4836afaf091eb2fd5dba",
       "max": 1,
       "style": "IPY_MODEL_aa185fafa5a14edf85347824161b6694"
      }
     },
     "df22d0c094c5445cb5e477381da40e9d": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.2.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "e0fd9d5a8d064eb7945e68aaf9634bbc": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "ButtonStyleModel",
      "state": {}
     },
     "e10bcbc0ba9c4e548a108d1d0dea9b40": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "DescriptionStyleModel",
      "state": {
       "description_width": ""
      }
     },
     "e5614b7700394d8982004cb9e89de601": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "VBoxModel",
      "state": {
       "_dom_classes": [
        "widget-interact"
       ],
       "children": [
        "IPY_MODEL_1b7fd73e01374c4ebe85b2a98bcb2fa9",
        "IPY_MODEL_61e154e37c5947b29b4090583f6b0764"
       ],
       "layout": "IPY_MODEL_392aca3ee4084e5eb91a41de4bedadf3"
      }
     },
     "f060f1a244784b7b99d796e5b7d3cd54": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.2.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "f51961a41ca44be38d86f0eafd606341": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.2.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "f754cf99022f4a1a8f48a1f22828e823": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.2.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "f76ce08cc2d841c8a3eacc09b90ec834": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "ButtonStyleModel",
      "state": {}
     },
     "f7eeb21f2c7247f2b0ddbe5a654def05": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "SliderStyleModel",
      "state": {
       "description_width": ""
      }
     },
     "f896db6f76e242eeb84ca910b0486684": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.2.0",
      "model_name": "LayoutModel",
      "state": {}
     }
    },
    "version_major": 2,
    "version_minor": 0
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}