p1/advent of code/2023/12 Hot Springs/resitev.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "a6eadb52",
   "metadata": {},
   "source": [
    "## Day 12: Hot Springs\n",
    "\n",
    "[(besedilo naloge)](https://adventofcode.com/2023/day/12)\n",
    "\n",
    "Leta 2023 se je v avtorju Advent of Code prebudil Dostojevski. Če vas zanima celotno besedilo naloge (recimo, ker je moj spodnji opis prehiter), berite original, vendar lahko prvih nekaj poglavij mirno preskočite. Roman postane zanimiv nekje pri odstavku \"*In the giant field just outside* ...\"\n",
    "\n",
    "Na kratko in brez zgobice, takole: imamo zaporedje znakov `#` in `.`, poleg tega pa niz števil, ki pove dolžine skupine `#`-ov. Na primer\n",
    "\n",
    "```\n",
    "..###..##....###..#. 3,2,3,1\n",
    "```\n",
    "\n",
    "Med dvema skupinama je vedno `.`. Zaporedje `####...#` lahko opišemo samo s `4,1`, ne pa `2,2,1` ali `3,1,1`.\n",
    "\n",
    "Potem pa pokvarimo niz tako, da nekatere znake zamenjamo z vprašaji, na primer\n",
    "\n",
    "```\n",
    ".??##?.#?....??????? 3,2,3,1\n",
    "```\n",
    "\n",
    "Na koliko načinov je možno zamenjati znake `?` z `#` in `.`, da bo niz ustrezal številkam? Tega na 12.\n",
    "\n",
    "```\n",
    ".###...##....###.#..\n",
    ".###...##....###..#.\n",
    ".###...##....###...#\n",
    ".###...##.....###.#.\n",
    ".###...##.....###..#\n",
    ".###...##......###.#\n",
    "..###..##....###.#..\n",
    "..###..##....###..#.\n",
    "..###..##....###...#\n",
    "..###..##.....###.#.\n",
    "..###..##.....###..#\n",
    "..###..##......###.#\n",
    "```\n",
    "\n",
    "Pa v splošnem?\n",
    "\n",
    "Naloga na Advent of Code je bila prebrati datoteko s 1000 takšnimi nizi in številkami, za vsakega prešteti na koliko načinov ga je mogoče \"popraviti\" in to sešteti. Drugi del je spremenjen tako, da postanejo ti nizi res dolgi, dobimo lahko, recimo niz\n",
    "\n",
    "```\n",
    "???.??????#?????.##.????.??????#?????.##.????.??????#?????.##.????.??????#?????.##.????.??????#?????.##.\n",
    "```\n",
    "\n",
    "s skupinami\n",
    "\n",
    "```\n",
    "1,1,7,1,1,2,1,1,7,1,1,2,1,1,7,1,1,2,1,1,7,1,1,2,1,1,7,1,1,2\n",
    "```\n",
    "\n",
    "### Rešitev\n",
    "\n",
    "Tule bomo za začetek napisali funkcijo `ways(line, groups)`, ki prejme niz in seznam števil ter vrne število možnih konfiguracij.\n",
    "\n",
    "Preden preberete rešitev, predlagam, da poskusite nalogo rešite sami. Tako boste najbolj dojeli, v čem je problem. Priporočam tudi, da pozabite na regularne izraze. Ne pozabite pa na rekurzijo. :)\n",
    "\n",
    "----\n",
    "\n",
    "Tole bo čisto lep - zgleden, šolski primer rekurzije. Najprej robni pogoji, s katerimi se rekurzija konča.\n",
    "\n",
    "Najprej odstranimo začetne pike, saj nas ne zanimajo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "ad128efb",
   "metadata": {},
   "outputs": [],
   "source": [
    "def ways(line, groups):\n",
    "    line = line.lstrip(\".\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ed37b81f",
   "metadata": {},
   "source": [
    "Zdaj se lahko zgodi, da je vrstica prazna. Če je prazen tudi seznam `groups`, potem imamo očitno točno eno pravilno konfiguracijo. Če seznam `groups` ni prazen, pa imamo nič možnih konfiguracij - morali bi razporediti še nekaj skupin, a jih nimamo kam."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "64a2a202",
   "metadata": {},
   "outputs": [],
   "source": [
    "def ways(line, groups):\n",
    "    line = line.lstrip(\".\")\n",
    "    if not line:\n",
    "        return not groups"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5f31721f",
   "metadata": {},
   "source": [
    "Vrnili smo kar `not groups`. Če ni vel skupin, bo to `True`, kar je enako kot `1`; če so, bo `False`, torej `0`.\n",
    "\n",
    "Zdaj pa drug primer: kaj če je zmanjkalo skupin. Ker nas ta zanima samo, če še ni zmanjkalo tudi vrstice, bomo nadaljevali kar z `elif not groups`, torej, vrstica ni prazna, skupine pa. Če vrstica vsebuje le še vprašaje in pike, imamo točno eno možno konfiguracijo - vse vprašaje zamenjamo s pikami. Čim vrstica vsebuje kak `#`, pa imamo nič možnih konfiguracij, saj vrstica predvideva nove skupin, skupin pa ni več."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "3ee97bf4",
   "metadata": {},
   "outputs": [],
   "source": [
    "def ways(line, groups):\n",
    "    line = line.lstrip(\".\")\n",
    "    if not line:\n",
    "        return not groups\n",
    "    elif not groups:\n",
    "        return \"#\" not in line"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0cd4bb20",
   "metadata": {},
   "source": [
    "Tako smo opravili z robnimi pogoji. Zdaj pa rekurzivni del. Ta bo obravnaval dva scenarija: prvi znak vrstice je lahko `?` ali `#`. Pike smo namreč od-`lstrip`-ali na začetku funkcije.\n",
    "\n",
    "Če je prvi znak `?` je stvar silno preprosta. Zamenjati ga je možno s `#` ali s `.`. Število vseh konfiguracij je enako vsoti konfiguracij, ki se začnejo s `#` in vsoti konfiguracij, ki se začnejo s `.`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "1188a033",
   "metadata": {},
   "outputs": [],
   "source": [
    "def ways(line, groups):\n",
    "    line = line.lstrip(\".\")\n",
    "    if not line:\n",
    "        return not groups\n",
    "    elif not groups:\n",
    "        return \"#\" not in line\n",
    "\n",
    "    if line[0] == \"?\":\n",
    "        return ways(\"#\" + line[1:], groups) + ways(\".\" + line[1:], groups)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "66574278",
   "metadata": {},
   "source": [
    "Če je prvi znak `#`, pa nas prisili, da prav tu začnemo naslednjo skupino. Najprej moramo preveriti, ali je na tem mestu lahko skupina zahtevane dolžine. To zahteva tri pogoje:\n",
    "\n",
    "- preostanek vrstice mora biti dovolj dolg,\n",
    "- v toliko znakih vrstice, kolikor je dolga skupina, ne sme biti nobene pike (poleg `#` pa seveda dovolimo tudi vprašaje)\n",
    "- skupina se mora končati; torej, ostanek niza mora biti dolg natančno toliko, kolikor je dolga skupina, ali pa mora biti znak, ki je za koncem skupine, `.` ali `?`, nikakor ne pa `#`.\n",
    "\n",
    "Če ti pogoji niso izpolnjeni, se vrstica tu ne more začeti z naslednjo skupino."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "a730652e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def ways(line, groups):\n",
    "    line = line.lstrip(\".\")\n",
    "    if not line:\n",
    "        return not groups\n",
    "    elif not groups:\n",
    "        return \"#\" not in line\n",
    "\n",
    "    if line[0] == \"?\":\n",
    "        return ways(\"#\" + line[1:], groups) + ways(\".\" + line[1:], groups)\n",
    "    g0 = groups[0]\n",
    "    if len(line) < g0 or \".\" in line[:g0] or (len(line) > g0 and line[g0] == \"#\"):\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "64587e7e",
   "metadata": {},
   "source": [
    "Če je vse v redu, pa bo ta skupina pač tu, število konfiguracij pa je enako številu konfiguracij brez te skupine - na začetku niza odbijemo toliko znakov, kolikor je dolga ta skupina in še enega zraven (to je potrebno zato, ker bi skupini lahko sledil `?` in nočemo, da bi ga v naslednjem klicu slučajno zamenjali s `#`!), iz seznama skupin pa odstranimo prvo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "323f33b2",
   "metadata": {},
   "outputs": [],
   "source": [
    "def ways(line, groups):\n",
    "    line = line.lstrip(\".\")\n",
    "    if not line:\n",
    "        return not groups\n",
    "    elif not groups:\n",
    "        return \"#\" not in line\n",
    "\n",
    "    if line[0] == \"?\":\n",
    "        return ways(\"#\" + line[1:], groups) + ways(\".\" + line[1:], groups)\n",
    "    g0 = groups[0]\n",
    "    if len(line) < g0 or \".\" in line[:g0] or (len(line) > g0 and line[g0] == \"#\"):\n",
    "        return 0\n",
    "    return ways(line[g0 + 1:], groups[1:])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c03ea19f",
   "metadata": {},
   "source": [
    "Še hitro preverjanje: imamo tri rekurzivne klice. Da se rekurzija ne zacikla, moramo biti z vsakim klicem bližje robnemu pogoju. Je to tu res?\n",
    "\n",
    "Pri tretjem klicu - očitno: tako vrstica kot seznam skupin sta krajša. Pri prvih dveh - manj očitno. A vendar. Če zamenjamo `?` s `#`, bomo v naslednjem klicu očitno padli v zadnji, tretji klic in ta bo skrajšal vrstico in seznam. Če zamenjamo `?` s `.`, pa jo bo v naslednjem klicu od-`lstrip`-al in tako skrajšal vrstico."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bff5668a",
   "metadata": {},
   "source": [
    "## Deluje že, deluje, ampak počasi\n",
    "\n",
    "**Kdor se preveč boji matematike, lahko preskoči ta razdelek. Čeprav ... saj ne bo tako huda.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "55e55f21",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ways(\".??##?.#?....???????\", [3, 2, 3, 1])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dc61aed7",
   "metadata": {},
   "source": [
    "Če je bilo gornje, ročno štetje pravilno, je pravilna tudi funkcija. Je. Prestala je tudi teste na Advent of Code.\n",
    "\n",
    "No, skoraj. V tej obliki funkcija zmore kratke nize, za one, zverinsko dolge, pa je počasna."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "15a49c1e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.41 s ± 7.48 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "\n",
    "ways(\"???.??????#?????.##.????.??????#?????.##.????.??????#?????.##.????.??????#?????.##.????.??????#?????.##.\",\n",
    "     [1, 1, 7, 1, 1, 2, 1, 1, 7, 1, 1, 2, 1, 1, 7, 1, 1, 2, 1, 1, 7, 1, 1, 2, 1, 1, 7, 1, 1, 2])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "664a7338",
   "metadata": {},
   "source": [
    "Če za tale niz potrebuje sekundo in pol, bo za 1000 nizov potrebovala pol ure.\n",
    "\n",
    "Da bomo lažje opazovali, kaj se dogaja, dodajmo štetje klicev. V Pythonu to najpreprosteje naredimo tako, da funkcijo priredimo atribut, recimo `calls` (funkcije v Pythonu so objekti in to takšni, ki jim lahko dodajamo atribute). Funkcija ga bo ob vsakem klicu povečala, mi pa ga bomo pred testiranjem resetirali in po njem izpisali."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "2b972766",
   "metadata": {},
   "outputs": [],
   "source": [
    "def ways(line, groups):\n",
    "    ways.calls += 1\n",
    "    \n",
    "    line = line.lstrip(\".\")\n",
    "    if not line:\n",
    "        return not groups\n",
    "    elif not groups:\n",
    "        return \"#\" not in line\n",
    "\n",
    "    if line[0] == \"?\":\n",
    "        return ways(\"#\" + line[1:], groups) + ways(\".\" + line[1:], groups)\n",
    "    g0 = groups[0]\n",
    "    if len(line) < g0 or \".\" in line[:g0] or (len(line) > g0 and line[g0] == \"#\"):\n",
    "        return 0\n",
    "    return ways(line[g0 + 1:], groups[1:])\n",
    "\n",
    "\n",
    "def test_ways(line, groups):\n",
    "    ways.calls = 0\n",
    "    ways(line, groups)\n",
    "    return ways.calls"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "579d0c1c",
   "metadata": {},
   "source": [
    "(Nekateri študenti bi to znali narediti še lepše, s splošnejšim dekoratorjem. To vajo prepuščam njim; tule jo bomo preskočili.)\n",
    "\n",
    "Kolikokrat se funkcija pokliče, če vsebuje niz 12 vprašajev in enega od njih je potrebno zamenjati s `#`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "f01b1fbf",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "37"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "test_ways(\"?\" * 12, [1])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fa7adaf6",
   "metadata": {},
   "source": [
    "37 ni malo, je pa sprejemljivo in razložljivo - to je trikrat 12 in še en zraven (za konec, ko sta tako seznam kot skupina prazna). Zakaj trikrat? Funkcija za vsak vprašaj funkcija opravi dva klica - enkrat ga zamenja s `?`, enkrat z `#`. Tisti z `#` vodi v samo en klic - skupina je vstavljena, novih skupin ni in robni pogoj konča rekurzijo. Tisti z `.` pa pač nadaljuje \"zanko\" na ostanku seznama.\n",
    "\n",
    "Če je torej seznam dolg `n` znakov, bomo imeli $3n + 1$ klicev. Če je seznam dvakrat daljši, bo klicev pač dvakrat toliko (z malo napake zaradi enice)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "0f90228b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "73"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "test_ways(\"?\" * 24, [1])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f704f7db",
   "metadata": {},
   "source": [
    "Očitno. Če v $3n + 1$ zamenjamo $n$ z $2n$, dobimo $3(2n) + 1 = 6n+1$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b3ed2367",
   "metadata": {},
   "source": [
    "Kaj pa, če moramo v enako dolg niz postaviti dve skupini dolžine 1?\n",
    "\n",
    "Tu je računanje malo bolj zoprno. Izkaže se, da bo število klicev enako $3\\frac{n(n - 1)}{2} + 4$, a tega nam ni potrebno natančno razumeti, saj si lahko pomagamo s tem, da razmislimo, kako bi skupini razporejali ročno, uganemo obliko formule in jo preverimo tako, da kličemo funkcijo.\n",
    "\n",
    "Torej, kako bi skupini razporejali ročno? Najprej postavimo prvo čisto na levo, druga bo na enem ob 10 možnih mest (če je niz dolg 12). Nato premaknemo prvo skupino za eno mesto proti desni; druga bo na enem od 9 možnih mest. Nato gre prva še za en korak desno in druga bo na enem od 8 mest. In tako naprej. Različnih razporedov je 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "78afce6b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "55"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ways(\"?\" * 12, [1, 1])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9c54b7f4",
   "metadata": {},
   "source": [
    "V splošnem imamo niz dolžine `n` in število konfiguracij je enako vsoti števil od $1$ do $n - 2$, ki je, kot vemo iz izmišljene anekdote o Gaussu (hvalabogu je to vsaj ena stvar, ki je niso pripisali Einsteinu, ki je zagotovo deležen največjega deleža izmišljenih citatov; v okviru znanosti, seveda - če gre za politiko, je to gotovo rekel Churchill, če za strategiju, Sun Tzu, vse ostalo pa je rekel Mark Twain) enaka $(n - 1)(n - 2)/2$. Tudi če zanemarimo vso šaro koeficientov - polovice, trikratne klice in bogvekaj še, smo prisiljeni ugotoviti tole: rezultat, ki ga vrača funkcija, je sorazmeren kvadratu $n$. Ker funkcija na koncu, čisto na dnu, vedno vrne `0` ali `1` in končni rezultat je samo vsota vseh teh enic, bo morala funkcija za rezultat sorazmeren kvadratu, vrniti $\\sim n^2$ enic, kar bo zahtevalo vsaj $n^2$ klicev.\n",
    "\n",
    "V resnici za niz dolžine 12 potrebuje 202 klicev."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "237dee3c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "202"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "test_ways(\"?\" * 12, [1, 1])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "68de8027",
   "metadata": {},
   "source": [
    "Za dvakrat daljši niz potrebuje - ne več dvakrat, temveč štirikrat toliko klicev!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "3f7099df",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "832"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "test_ways(\"?\" * 24, [1, 1])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "02016ad4",
   "metadata": {},
   "source": [
    "Zakaj štirikrat? Število je, vemo, sorazmerno $n^2$. Če v $n^2$ zamenjamo $n$ z $2n$, dobimo $(2n)^n$ je $4n^2$. Štirikrat toliko kot prej.\n",
    "\n",
    "Za trikrat daljši niz potrebujemo devetkrat toliko klicev in za štirikrat daljši seznam šestnajstkrat toliko klicev."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "3cb1e858",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1894"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "test_ways(\"?\" * 36, [1, 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "38cea9c4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3388"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "test_ways(\"?\" * 48, [1, 1])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "adf1d492",
   "metadata": {},
   "source": [
    "Vidimo? Začeli smo pri 200 in ko je bilo število klicev dvakrat, trikrat in štirikrat večje, smo dobili štirikratnik, devetkratnih in šestnajstkratnik 200 - približno 800, 1800 in 3200 (plus veliko zaokrožitvene napake)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d8505fa3",
   "metadata": {},
   "source": [
    "Tragedija se poglobi, ko vstavljamo tri skupine."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "ddac4144",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "562"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "test_ways(\"?\" * 12, [1, 1, 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "39cbb7c2",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5452"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "test_ways(\"?\" * 24, [1, 1, 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "8a7be8b3",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "19846"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "test_ways(\"?\" * 36, [1, 1, 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "42c2b744",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "48928"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "test_ways(\"?\" * 48, [1, 1, 1])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "94eafff2",
   "metadata": {},
   "source": [
    "Zdaj je število konfiguracij - in s tem število klicev - sorazmerno kubu dolžine niza. Ko se ta podvoji, potroji in početveri, je število klicev 8-krat, 27-krat in 64-krat večje (ne *točno* tolikokrat; tak je trend).\n",
    "\n",
    "Če pri štirih skupinah število klicev narašča s četrto potenco dolžine niza, pri petih s peto... Število klicev bo torej sorazmerno $n^g$, kjer je $n$ dolžina niza, $g$ pa število skupin. Za takšno zahtevnost pravimo, da je *eksponentna* glede na število skupin. Če si predstavljamo, da imajo daljši niz tudi večje število skupin in je torej $g$ sorazmeren $n$, lahko tu pričakujemo zahtevnost $n^n$. Grozno."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9257de15",
   "metadata": {},
   "source": [
    "## Kako pospešiti funkcijo?\n",
    "\n",
    "Zelo preprosto. Preprečiti ji je potrebno, da bi večkrat računala, kar je že izračunala.\n",
    "\n",
    "Vrnimo se k dvema skupinama.\n",
    "\n",
    "- Najprej postavi prvo skupino čisto na levo, na prvi znak, in se vpraša, na koliko načinov je možno postaviti preostalo skupino na preostalih deset znakov (drugi je prepovedan).\n",
    "- Da izve, na koliko načino je možno postaviti skupino na deset znakov, preveri dve možnosti. Bodisi je skupina na prvem (izmed teh desetih) in v tem primeru smo v bistvu končali. Potem pa predpostavi, da *ni* na prvem in naredi rekurzivni klic, da preveri, na koliko načinov je možno postaviti preostalo eno skupino na devet prostih mest.\n",
    "- ... sledi še precej klicev ...\n",
    "- Ko kočna z vsemi konfiguracijami, v katerih je prva skupina na prvem znaku, začne s tistimi, v katerih prva skupina *ni* na prvem znaku. Morda je na drugem. V tem primeru mora preveriti vse možne postavitve druge skupine na preostalih devetih znakih. To pa je že delala! Če si zapomni rezultat tega klica, ko smo ga izvedli prvič, ga lahko uporabi, ne da bi dejansko ponovno računala.\n",
    "\n",
    "Takšnemu pomnjenju rečemo *memoizacija* in v Pythonu ga je preprosto dodati: iz modula `functools` uvozimo dekorator `cache` in ga dodamo pred funkcijo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "20db3a73",
   "metadata": {},
   "outputs": [],
   "source": [
    "from functools import cache\n",
    "\n",
    "@cache\n",
    "def ways(line, groups):\n",
    "    ways.calls += 1\n",
    "    \n",
    "    line = line.lstrip(\".\")\n",
    "    if not line:\n",
    "        return not groups\n",
    "    elif not groups:\n",
    "        return \"#\" not in line\n",
    "\n",
    "    if line[0] == \"?\":\n",
    "        return ways(\"#\" + line[1:], groups) + ways(\".\" + line[1:], groups)\n",
    "    g0 = groups[0]\n",
    "    if len(line) < g0 or \".\" in line[:g0] or (len(line) > g0 and line[g0] == \"#\"):\n",
    "        return 0\n",
    "    return ways(line[g0 + 1:], groups[1:])\n",
    "\n",
    "\n",
    "def test_ways(line, groups):\n",
    "    ways.calls = 0\n",
    "    ways.cache_clear()\n",
    "    ways(line, groups)\n",
    "    return ways.calls"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0fef45bd",
   "metadata": {},
   "source": [
    "Dekoriranje bo zahtevalo še dve spremembi. V `test_ways` moramo poklicati `cache_clear`, da funkcija pred vsakim testom pozabi zapomnjeno.\n",
    "\n",
    "Druga: skupin ne bomo več mogli podajati s seznamom, saj `cache` temelji na slovarju, katerega ključi so argumenti funkcije, pripadajoče vrednosti pa (znani) rezultati. Ker je seznam spremenljiv, ne more nastopati kot ključ. Nič ne de, bomo pač delali s terkami. Funkcije ne bo potrebno spreminjati le klicali jo bomo s terko namesto s seznamom."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "860e6332",
   "metadata": {},
   "source": [
    "Pri eni sami skupini se to ne bo poznalo prav nič. Raje kar takoj pofleksajmo s štirimi (ki se jih prej nismo upali niti dotakniti)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "0d4e041e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "105"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "test_ways(\"?\" * 12, (1, 1, 1, 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "d48a9e9f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "249"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "test_ways(\"?\" * 24, (1, 1, 1, 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "fdb9e935",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "393"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "test_ways(\"?\" * 36, (1, 1, 1, 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "f265d72e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "537"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "test_ways(\"?\" * 48, (1, 1, 1, 1))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cc3f8af5",
   "metadata": {},
   "source": [
    "Videti je kar lepo. Poskusimo z do desetkrat daljšimi nizi."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "a1950d32",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[105, 249, 393, 537, 681, 825, 969, 1113, 1257, 1401, 1545, 1689, 1833, 1977, 2121, 2265, 2409, 2553, 2697, 2841]\n"
     ]
    }
   ],
   "source": [
    "ks = [12 * k for k in range(1, 21)]\n",
    "calls = [test_ways(\"?\" * k, (1, 1, 1, 1)) for k in ks]\n",
    "\n",
    "print(calls)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5ccfb264",
   "metadata": {},
   "source": [
    "Pravzaprav: narišimo, pa bomo videli, ali narašča s četrto potenco (očitno ne), kubom, kvadratom ali, morda, celo, linearno."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "ce717180",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Intel MKL WARNING: Support of Intel(R) Streaming SIMD Extensions 4.2 (Intel(R) SSE4.2) enabled only processors has been deprecated. Intel oneAPI Math Kernel Library 2025.0 will require Intel(R) Advanced Vector Extensions (Intel(R) AVX) instructions.\n",
      "Intel MKL WARNING: Support of Intel(R) Streaming SIMD Extensions 4.2 (Intel(R) SSE4.2) enabled only processors has been deprecated. Intel oneAPI Math Kernel Library 2025.0 will require Intel(R) Advanced Vector Extensions (Intel(R) AVX) instructions.\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[<matplotlib.lines.Line2D at 0x114cbea50>]"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAjsAAAGdCAYAAAD0e7I1AAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjcuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8pXeV/AAAACXBIWXMAAA9hAAAPYQGoP6dpAABD10lEQVR4nO3deXhTdd738Xe6paW0gdIdSgXZaSktKMuoICiLA4goW3249R5vdUYKIuCCM464DDguMGgZx1kedZQCLqCoDIoiKIO40BYospS9QEtZ2nRP2+Q8f3ibZwooW9uTpp/XdeW6aM4v5ZMe0nw435PEYhiGgYiIiIiX8jE7gIiIiEhDUtkRERERr6ayIyIiIl5NZUdERES8msqOiIiIeDWVHREREfFqKjsiIiLi1VR2RERExKv5mR2gobhcLo4dO0ZISAgWi8XsOCIiInIBDMOgtLSU2NhYfHzq55iM15adY8eOERcXZ3YMERERuQR5eXm0a9euXr6X15adkJAQ4IcfVmhoqMlpRERE5EKUlJQQFxfnfh6vD15bdn4cXYWGhqrsiIiINDH1eQqKTlAWERERr6ayIyIiIl5NZUdERES8msqOiIiIeDWVHREREfFqKjsiIiLi1VR2RERExKup7IiIiIhXU9kRERERr6ayIyIiIl5NZUdERES8msqOiIiIeDWVHREREbkoxRXV3PvGd/x770mzo1wQlR0RERG5YFsOFfHLFzfy8Y7jPPTONmqcLrMjnZef2QFERETE87lcBn/7cj/PfbybWpfBFW1akJ6agr+v5x83UdkRERGRn3W6vJpZb2Xz+e4TAIxOimXeLQmEBPqbnOzCqOyIiIjIT/rmwGmmL82ioKQKq58Pc8f0ZNJVcVgsFrOjXTCVHRERETmLy2Xw8oZ9LFi7B6fLoGNEMItTU+geE2p2tIumsiMiIiJ1nCxz8MDybL7M/eHVVuOS2/LU2ASCrU2zNjTN1CIiItIgNu07yf3LsjlR6iDQ34cnb05gfJ92TWpsdSaVHREREcHpMnhpXS4vfpaLy4AuUS1ZnJpC56gQs6NdNpUdERGRZq6wpIoZy7PZtO8UABP6tuOJMQkEBfianKx+qOyIiIg0Y1/mnuCB5dmcLKumRYAvf7glgVuS25kdq16p7IiIiDRDtU4Xf/o0l8Xr92IY0C06hMW3p3BlREuzo9U7lR0REZFmpsBexfSlWXxz8DQAqf3a8/tRPQj0946x1ZlUdkRERJqRz3cXMuutrZwur6al1Y/54xIZnRRrdqwGpbIjIiLSDNQ4XTz/yW5e2bAfgIS2oaRPTuGK8GCTkzU8lR0REREvd7S4kulLs9hyqAiAOwdewZybumH1886x1ZlUdkRERLzYp98fZ9bbW7FX1hAS6Mdzt/ViREKM2bEalcqOiIiIF6qudfHsml38feMBAJLa2UhPTSEurIXJyRqfyo6IiIiXyTtdQdrSLLbmFQNw1zUdeHhENwL8fMwNZhKVHRERES+yJiefB9/ZRmlVLbYgf54fn8SNPaLMjmUqlR0REREv4Kh1Mu+jnbz+1SEAUtq34qXUFNq2CjI5mflUdkRERJq4gyfLSVuaSc7REgDuHdSR2cO64u/bPMdWZ1LZERERacI+3HaMR97dTpmjltYt/FkwoTfXd4s0O5ZHUdkRERFpgqpqnDz54fdkfH0YgKuvCGPR5N7E2DS2OpPKjoiISBOz70QZU5dksqugFIsF0q7vxP1DO+OnsdU5qeyIiIg0ISuzjvDblTlUVDsJbxnAwom9ubZzhNmxPJrKjoiISBNQWe3k8VU5vPXdEQAGdGzDokm9iQwNNDmZ51PZERER8XC5x0uZmpHJnuNlWCxw/9DOTBvSGV8fi9nRmgSVHREREQ/29nd5PPZ+DlU1LiJCrCya1JuBV4abHatJUdkRERHxQOWOWh57P4cVmUcBuLZzOAsn9ia8pdXkZE2Pyo6IiIiH2VVQwtQlmew7UY6PBWYN68pvBl2Jj8ZWl0RlR0RExEMYhsGyb/OYu2oHjloX0aGBvDg5mas7hJkdrUlT2REREfEApVU1PLoyhw+2HgNgcNcIFkzoTVhwgMnJmj6VHREREZPlHLWTlpHJwVMV+PpYeGh4V+6+tqPGVvVEZUdERMQkhmHw5uZDPPXhTqqdLtq2CuLFycn0iW9tdjSvorIjIiJigpKqGh55dxurtxcAcEP3KJ4f34tWLTS2qm8qOyIiIo1sa14xaUszyTtdib+vhUdGdudXv7gCi0Vjq4agsiMiItJIDMPg//77IM/8ayc1ToN2rYNYnJpCUlwrs6N5NZUdERGRRlBcUc2D72xj7ffHARiZEM0zt/bCFuRvcjLvd1GfBT9//nyuuuoqQkJCiIyMZOzYsezevbvOmjvvvBOLxVLn0r9//zprHA4H06ZNIzw8nODgYMaMGcORI0fqrCkqKmLKlCnYbDZsNhtTpkyhuLj40u6liIiIiTIPF/HLFzey9vvjBPj68OTNPfnz7SkqOo3kosrOhg0bmDp1Kps3b2bt2rXU1tYybNgwysvL66wbMWIE+fn57svq1avrbJ8xYwYrV65k2bJlbNy4kbKyMkaNGoXT6XSvSU1NJTs7mzVr1rBmzRqys7OZMmXKZdxVERGRxuVyGbyyYR8T/vIVR4sriW/TghX3DeS/Buj8nMZkMQzDuNQbnzhxgsjISDZs2MB1110H/HBkp7i4mPfee++ct7Hb7URERPDGG28wceJEAI4dO0ZcXByrV69m+PDh7Ny5kx49erB582b69esHwObNmxkwYAC7du2ia9eu581WUlKCzWbDbrcTGhp6qXdRRETkkpwur2b221tZt6sQgFG9Ypg/LpGQQB3N+TkN8fx9UUd2zmS32wEIC6v7Ntbr168nMjKSLl26cPfdd1NYWOjetmXLFmpqahg2bJj7utjYWBISEti0aRMAX331FTabzV10APr374/NZnOvOZPD4aCkpKTORURExAzfHjzNTYu+ZN2uQgL8fJh3SyIvTU5W0THJJZ+gbBgGM2fO5JprriEhIcF9/ciRIxk/fjzx8fEcOHCAxx57jCFDhrBlyxasVisFBQUEBATQunXdN0yKioqioOCH9xooKCggMjLyrL8zMjLSveZM8+fP54knnrjUuyMiInLZXC6DlzfsY8HaPThdBh0jglmcmkL3GE0YzHTJZSctLY1t27axcePGOtf/OJoCSEhIoG/fvsTHx/PRRx8xbty4n/x+hmHUmV+ea5Z55pr/NGfOHGbOnOn+uqSkhLi4uAu+PyIiIpfjZJmDB5Zn82XuSQBuSW7L02MTCLbqhc9mu6Q9MG3aNFatWsUXX3xBu3btfnZtTEwM8fHx5ObmAhAdHU11dTVFRUV1ju4UFhYycOBA95rjx4+f9b1OnDhBVFTUOf8eq9WK1Wq9lLsjIiJyWb7ad4r7l2VRWOog0N+HJ29OYHyfdjoJ2UNc1Dk7hmGQlpbGihUrWLduHR06dDjvbU6dOkVeXh4xMTEA9OnTB39/f9auXetek5+fT05OjrvsDBgwALvdzjfffONe8/XXX2O3291rREREzOZ0GSz6NJfb/76ZwlIHnSNbsirtGib0jVPR8SAX9Wqs++67j4yMDN5///06r4iy2WwEBQVRVlbG3LlzufXWW4mJieHgwYM8+uijHD58mJ07dxISEgLAb37zGz788ENee+01wsLCmD17NqdOnWLLli34+voCP5z7c+zYMV555RUA7rnnHuLj4/nggw8uKKtejSUiIg2psLSKGcuy2bTvFADj+7TjiZt70iJAY6vL0RDP3xdVdn6qpb766qvceeedVFZWMnbsWLKysiguLiYmJobrr7+ep556qs75M1VVVTz44INkZGRQWVnJ0KFD+fOf/1xnzenTp5k+fTqrVq0CYMyYMaSnp9OqVasLyqqyIyIiDWVj7klmLM/iZFk1LQJ8eXpsAuNSfv60DrkwppedpkRlR0RE6lut08Wiz3JJ/3wvhgHdokNIT02hU2RLs6N5jYZ4/taxNhERkQtQYK9i+rIsvjlwGoDJV7fn8dE9CPT3NTmZnI/KjoiIyHms313IzLe2crq8muAAX+bf2osxSbFmx5ILpLIjIiLyE2qcLl74ZA9/2bAPgJ6xoaSnptAhPNjkZHIxVHZERETO4VhxJdOWZrHlUBEA/zUgnkdv6q6xVROksiMiInKGT78/zux3tlJcUUOI1Y8/3taLmxJjzI4ll0hlR0RE5H9V17p4ds0u/r7xAAC92tlIn5xC+zYtTE4ml0NlR0REBMg7XUHa0iy25hUD8KtfdOCRkd0I8LuoDxsQD6SyIyIizd6anHwefGcbpVW1hAb68fz4JIb1jDY7ltQTlR0REWm2HLVO5n20k9e/OgRAcvtWvDQ5mXatNbbyJio7IiLSLB08WU7a0kxyjpYAcO91HZk9vCv+vhpbeRuVHRERaXY+3HaMR97dTpmjltYt/HlhQhJDukWZHUsaiMqOiIg0G1U1Tp768HuWfH0YgKuuaM2Lk5OJsQWZnEwaksqOiIg0C/tOlDF1SSa7CkqxWOC+wVfywA1d8NPYyuup7IiIiNd7L+soj67cTkW1kzbBASyc2JvrukSYHUsaicqOiIh4rcpqJ3NX7WD5d3kA9O8YxqJJyUSFBpqcTBqTyo6IiHil3OOlTM3IZM/xMiwWmD6kM9OHdsbXx2J2NGlkKjsiIuJ13v4uj9+/v4PKGicRIVYWTezNwE7hZscSk6jsiIiI1yh31PLY+zmsyDwKwDWdwlk4sTcRIVaTk4mZVHZERMQr7CooYeqSTPadKMfHAjNv7MJvBnfS2EpUdkREpGkzDINl3+Yxd9UOHLUuokKtvDgpmX4d25gdTTyEyo6IiDRZpVU1PLoyhw+2HgNgUJcIFkxIok1Lja3k/1PZERGRJinnqJ1pS7M4cLIcXx8LDw7vyj3XdsRHYys5g8qOiIg0KYZh8ObmQzz14U6qnS5ibYG8lJpMn/gws6OJh1LZERGRJqOkqoZH3t3G6u0FANzQPZLnbkuidXCAycnEk6nsiIhIk7DtSDFTMzLJO12Jn4+FR0Z2465rOmCxaGwlP09lR0REPJphGLz674PM/9dOapwG7VoHkZ6aQu+4VmZHkyZCZUdERDxWcUU1D76zjbXfHwdgeM8onr0tCVuQv8nJpClR2REREY+UebiIaRlZHC2uJMDXh9/+sjv/NSBeYyu5aCo7IiLiUVwug79v3M+za3ZT6zKIb9OC9MkpJLazmR1NmiiVHRER8Riny6uZ/fZW1u0qBOCXvWKYPy6R0ECNreTSqeyIiIhH+PbgaaYvzSLfXkWAnw+/H9WD2/u119hKLpvKjoiImMrlMnh5wz4WrN2D02XQMTyY9NQUesSGmh1NvITKjoiImOZkmYMHlmfzZe5JAMb2juXpWxJpadXTk9Qf/WsSERFTfLXvFPcvy6Kw1EGgvw9PjOnJhL5xGltJvVPZERGRRuV0GaSv28uiz/bgMqBTZEsWp6bQNTrE7GjipVR2RESk0RSWVjFjWTab9p0C4LY+7Xjy5p60CNDTkTQc/esSEZFGsTH3JDOWZ3OyzEGQvy9Pj03g1j7tzI4lzYDKjoiINKhap4tFn+WS/vleDAO6RoWw+PYUOkW2NDuaNBMqOyIi0mAK7FVMX5bFNwdOAzD56jgeH92TQH9fk5NJc6KyIyIiDWL97kJmvrWV0+XVBAf4Mm9cIjf3bmt2LGmGVHZERKRe1ThdvPDJHv6yYR8APWJCSU9NpmOExlZiDpUdERGpN8eKK5m2NIsth4oAmNI/nt/+srvGVmIqlR0REakXn35/nNnvbKW4ooYQqx/P3NqLX/aKMTuWiMqOiIhcnupaF8+u2cXfNx4AoFc7G+mTU2jfpoXJyUR+oLIjIiKXLO90BWlLs9iaVwzAf//iCh4Z2Q2rn8ZW4jlUdkRE5JKsySngwXe2UlpVS2igH8+NT2J4z2izY4mcRWVHREQuiqPWyfzVu3ht00EAese1Ij01mXatNbYSz6SyIyIiF+zQqXLSMrLYftQOwD3XdeTB4V3x9/UxOZnIT1PZERGRC/LhtmM88u52yhy1tG7hzwsTkhjSLcrsWCLnpbIjIiI/q6rGyVMffs+Srw8D0De+NS+lJhNjCzI5mciFUdkREZGftO9EGVOXZLKroBSA+wZfycwbu+CnsZU0IRf1r3X+/PlcddVVhISEEBkZydixY9m9e3edNYZhMHfuXGJjYwkKCmLw4MHs2LGjzhqHw8G0adMIDw8nODiYMWPGcOTIkTprioqKmDJlCjabDZvNxpQpUyguLr60eykiIhftvayjjH5pI7sKSmkTHMDrv7qah0Z0U9GRJuei/sVu2LCBqVOnsnnzZtauXUttbS3Dhg2jvLzcvebZZ59lwYIFpKen8+233xIdHc2NN95IaWmpe82MGTNYuXIly5YtY+PGjZSVlTFq1CicTqd7TWpqKtnZ2axZs4Y1a9aQnZ3NlClT6uEui4jIz6msdvLwO9uYsTybimon/TuGsfr+axnUJcLsaCKXxGIYhnGpNz5x4gSRkZFs2LCB6667DsMwiI2NZcaMGTz88MPAD0dxoqKi+OMf/8i9996L3W4nIiKCN954g4kTJwJw7Ngx4uLiWL16NcOHD2fnzp306NGDzZs3069fPwA2b97MgAED2LVrF127dj1vtpKSEmw2G3a7ndDQ0Eu9iyIizUru8VKmZmSy53gZFgtMG9KZ+4d2xtfHYnY0aSYa4vn7so5F2u0/vPQwLCwMgAMHDlBQUMCwYcPca6xWK4MGDWLTpk0AbNmyhZqamjprYmNjSUhIcK/56quvsNls7qID0L9/f2w2m3vNmRwOByUlJXUuIiJy4d7+Lo8x6f9mz/EywltaWXJXP2be2EVFR5q8Sy47hmEwc+ZMrrnmGhISEgAoKCgAICqq7ksRo6Ki3NsKCgoICAigdevWP7smMjLyrL8zMjLSveZM8+fPd5/fY7PZiIuLu9S7JiLSrJQ7apn5VjYPvrONyhon13QK51/3X8vATuFmRxOpF5f8aqy0tDS2bdvGxo0bz9pmsdT9X4BhGGddd6Yz15xr/c99nzlz5jBz5kz31yUlJSo8IiLnsaughKlLMtl3ohwfCzxwQxfuu76TjuaIV7mksjNt2jRWrVrFF198Qbt27dzXR0f/8JkoBQUFxMTEuK8vLCx0H+2Jjo6murqaoqKiOkd3CgsLGThwoHvN8ePHz/p7T5w4cdZRox9ZrVasVuul3B0RkWbHMAyWfZvH3FU7cNS6iAq1smhSMv07tjE7mki9u6gxlmEYpKWlsWLFCtatW0eHDh3qbO/QoQPR0dGsXbvWfV11dTUbNmxwF5k+ffrg7+9fZ01+fj45OTnuNQMGDMBut/PNN9+413z99dfY7Xb3GhERuTRljlruX5bNnBXbcdS6GNQlgtXTr1XREa91UUd2pk6dSkZGBu+//z4hISHu82dsNhtBQUFYLBZmzJjBvHnz6Ny5M507d2bevHm0aNGC1NRU99q77rqLWbNm0aZNG8LCwpg9ezaJiYnccMMNAHTv3p0RI0Zw991388orrwBwzz33MGrUqAt6JZaIiJxbzlE7aRmZHDxVga+PhdnDunLvdR3x0dhKvNhFlZ2XX34ZgMGDB9e5/tVXX+XOO+8E4KGHHqKyspL77ruPoqIi+vXrxyeffEJISIh7/cKFC/Hz82PChAlUVlYydOhQXnvtNXx9fd1rlixZwvTp092v2hozZgzp6emXch9FRJo9wzB4c/MhnvpoJ9W1LmJtgbyUmkyf+DCzo4k0uMt6nx1PpvfZERH5QUlVDY+8u43V2384Gn9D90ieuy2J1sEBJicTOVtDPH/rs7FERLzYtiPFpGVkcfh0BX4+Fh4Z2Y27rulw3lfIingTlR0RES9kGAavbTrIvNU7qXEatG0VRHpqMsntW5//xiJeRmVHRMTL2CtqePCdrXzy/Q9v4TG8ZxTP3pqErYW/yclEzKGyIyLiRbIOF5GWkcXR4koCfH149KZu3DHwCo2tpFlT2RER8QKGYfD3Lw/wxzW7qHUZtA9rweLUFBLb2cyOJmI6lR0RkSauqLya2W9v5bNdhQD8slcM88clEhqosZUIqOyIiDRp3x08zbSlWeTbqwjw8+H3o3pwe7/2GluJ/AeVHRGRJsjlMvjLF/t44ZM9OF0GHcKDSU9NpmesxlYiZ1LZERFpYk6VOZj51lY27DkBwM29Y/nDLYm0tOpXusi56JEhItKEbN5/ivuXZXG8xIHVz4cnb+7JhL5xGluJ/AyVHRGRJsDpMlj8+V7+9OkeXAZ0imzJ4tQUukaHnP/GIs2cyo6IiIcrLK3igeXZ/HvvKQBu69OOJ2/uSYsA/QoXuRB6pIiIeLBNe08yfVk2J8scBPn78vTYBG7t087sWCJNisqOiIgHcroMFn2Wy0vrcjEM6BoVwuLbk+kUqbGVyMVS2RER8TDHS6qYvjSLrw+cBmDSVXE8PronQQG+JicTaZpUdkREPMiGPSeYuTybU+XVBAf4Mm9cIjf3bmt2LJEmTWVHRMQD1DpdvLB2Dy+v3wdA95hQFqcm0zGipcnJRJo+lR0REZMdK65k+tIsvjtUBMCU/vH89pfdCfTX2EqkPqjsiIiYaN2u48x8ayvFFTWEWP145tZe/LJXjNmxRLyKyo6IiAlqnC6e+3g3f/1iPwCJbW2kpyYT3ybY5GQi3kdlR0SkkR0pqiAtI4vsvGIA/vsXV/DIyG5Y/TS2EmkIKjsiIo3o4x0FPPj2VkqqagkN9OO58UkM7xltdiwRr6ayIyLSCKprXcz/105e/fdBAHrHteKlycnEhbUwN5hIM6CyIyLSwA6fqiBtaSbbjtgBuOe6jjw4vCv+vj4mJxNpHlR2REQa0Ort+Tz8zjZKHbW0auHPgglJDOkWZXYskWZFZUdEpAFU1Tj5w0c7eWPzIQD6xrfmxcnJxLYKMjmZSPOjsiMiUs8OnCxn6pJMvs8vAeC+wVcy88Yu+GlsJWIKlR0RkXr0fvZRHl2xnfJqJ22CA1gwsTeDukSYHUukWVPZERGpB1U1Tp74YAdLv8kDoH/HMBZNSiYqNNDkZCKisiMicpn2FpYxdUkmu4+XYrHAtCGduX9oZ3x9LGZHExFUdkRELsu7W47w2Ps5VFQ7CW9pZdGk3vyiU7jZsUTkP6jsiIhcgorqWn7//g7e2XIEgF90asPCib2JDNHYSsTTqOyIiFykPcdLmbokk9zCMnws8MANXbjv+k4aW4l4KJUdEZELZBgGb32Xx+OrdlBV4yIq1MqiScn079jG7Ggi8jNUdkRELkCZo5bfrdzOe9nHABjUJYIFE5Jo09JqcjIROR+VHRGR8/j+WAlpGZnsP1mOr4+F2cO6cu91HfHR2EqkSVDZERH5CYZhsOTrwzz54fdU17qIsQXy0uRk+l4RZnY0EbkIKjsiIudQWlXDIyu289G2fACGdovk+fFJtA4OMDmZiFwslR0RkTNsP2InbWkmh05V4Odj4ZGR3bjrmg5YLBpbiTRFKjsiIv/LMAxe33SQeat3Ue100bZVEOmpySS3b212NBG5DCo7IiKAvaKGh97dysc7jgMwrEcUz92WhK2Fv8nJRORyqeyISLOXnVdMWkYmR4oq8fe18OhN3blz4BUaW4l4CZUdEWm2DMPgHxsP8My/dlHrMmgf1oL01GR6tWtldjQRqUcqOyLSLBWVVzP77a18tqsQgJsSo3nm1l6EBmpsJeJtVHZEpNnZcug00zKyOGavIsDPh8dG9eD/9GuvsZWIl1LZEZFmw+UyeOWL/Tz/yW6cLoMO4cGkpybTM9ZmdjQRaUAqOyLSLJwqczDzra1s2HMCgDFJscwbl0hLq34Ning7PcpFxOt9vf8U05dlcbzEgdXPhyfG9GTiVXEaW4k0Eyo7IuK1nC6DP3++l4Wf7sFlwJURwSy+PYVu0aFmRxORRqSyIyJe6USpgweWZ7Nx70kAxqW05ambEwjW2Eqk2fG52Bt88cUXjB49mtjYWCwWC++9916d7XfeeScWi6XOpX///nXWOBwOpk2bRnh4OMHBwYwZM4YjR47UWVNUVMSUKVOw2WzYbDamTJlCcXHxRd9BEWl+/r33JCMXfcnGvScJ8vfludt6sWBCbxUdkWbqostOeXk5SUlJpKen/+SaESNGkJ+f776sXr26zvYZM2awcuVKli1bxsaNGykrK2PUqFE4nU73mtTUVLKzs1mzZg1r1qwhOzubKVOmXGxcEWlGnC6DBWv38H/+8TUnyxx0iWrJqrRfML5vnNnRRMREF/3fnJEjRzJy5MifXWO1WomOjj7nNrvdzj/+8Q/eeOMNbrjhBgDefPNN4uLi+PTTTxk+fDg7d+5kzZo1bN68mX79+gHwt7/9jQEDBrB79266du16sbFFxMsdL6ni/mVZbN5/GoCJfeOYO6YnQQG+JicTEbNd9JGdC7F+/XoiIyPp0qULd999N4WFhe5tW7ZsoaamhmHDhrmvi42NJSEhgU2bNgHw1VdfYbPZ3EUHoH///thsNveaMzkcDkpKSupcRKR52LDnBDct+pLN+0/TIsCXP03szR9v66WiIyJAA5ygPHLkSMaPH098fDwHDhzgscceY8iQIWzZsgWr1UpBQQEBAQG0bt26zu2ioqIoKCgAoKCggMjIyLO+d2RkpHvNmebPn88TTzxR33dHRDxYrdPFgrV7+PP6fQB0jwllcWoyHSNampxMRDxJvZediRMnuv+ckJBA3759iY+P56OPPmLcuHE/eTvDMOq858W53v/izDX/ac6cOcycOdP9dUlJCXFxmtOLeKt8eyXTl2bx7cEiAG7v157HRvUg0F9Hc0SkrgZ/aUJMTAzx8fHk5uYCEB0dTXV1NUVFRXWO7hQWFjJw4ED3muPHj5/1vU6cOEFUVNQ5/x6r1YrVam2AeyAinmbdruPMemsrRRU1tLT68cytiYzqFWt2LBHxUA1yzs5/OnXqFHl5ecTExADQp08f/P39Wbt2rXtNfn4+OTk57rIzYMAA7HY733zzjXvN119/jd1ud68Rkeanxuli3uqd/Oq17yiqqCGhbSgfTrtGRUdEftZFH9kpKytj79697q8PHDhAdnY2YWFhhIWFMXfuXG699VZiYmI4ePAgjz76KOHh4dxyyy0A2Gw27rrrLmbNmkWbNm0ICwtj9uzZJCYmul+d1b17d0aMGMHdd9/NK6+8AsA999zDqFGj9EoskWbqSFEF05ZmkXW4GIA7B17BnJu6YfXT2EpEft5Fl53vvvuO66+/3v31j+fJ3HHHHbz88sts376df/7znxQXFxMTE8P111/P8uXLCQkJcd9m4cKF+Pn5MWHCBCorKxk6dCivvfYavr7//5fWkiVLmD59uvtVW2PGjPnZ9/YREe/1yY4CZr+9lZKqWkIC/Xjutl6MSIgxO5aINBEWwzAMs0M0hJKSEmw2G3a7ndBQfQ6OSFNUXeti/r928uq/DwKQFNeK9MnJxIW1MDeYiDSYhnj+1nuni4hHOnyqgrSlmWw7Ygfgf67pwEMjuhHg1+CnGoqIl1HZERGPs3p7Pg+/s41SRy22IH9eGJ/EDT3O/UpMEZHzUdkREY9RVePkDx/t5I3NhwDoE9+aFycn07ZVkMnJRKQpU9kREY9w4GQ5U5dk8n3+Dx/18utBVzJrWBf8fTW2EpHLo7IjIqZbtfUYc97dRnm1k7DgAF6YkMT1Xc/+yBgRkUuhsiMipqmqcfLEBztY+k0eAFdfEcaLk5OJtgWanExEvInKjoiYYm9hGWkZmewqKMVigamDOzHjhs74aWwlIvVMZUdEGt27W47wu/dyqKxxEt4ygIUTe3Nt5wizY4mIl1LZEZFGU1Fdy+/f38E7W44AMPDKNvxpYm8iQzW2EpGGo7IjIo1iz/FSpi7JJLewDB8L3D+0C2lDOuHrYzE7moh4OZUdEWlQhmHw1nd5PL5qB1U1LiJDrCyalMyAK9uYHU1EmgmVHRFpMGWOWn63cjvvZR8D4NrO4Syc2JvwllaTk4lIc6KyIyIN4vtjJaRlZLL/ZDm+PhZm3tiF3wy6Eh+NrUSkkansiEi9MgyDjG8O88QH31Nd6yI6NJCXUpO56oows6OJSDOlsiMi9aa0qoZHVmzno235AAzpFsnz45MICw4wOZmINGcqOyJSL7YfsZO2NJNDpyrw87Hw0Iiu/M81HTW2EhHTqeyIyGUxDIPXNx1k3updVDtdtG0VxEupyaS0b212NBERQGVHRC6DvbKGh9/ZxpodBQDc2COK527rRasWGluJiOdQ2RGRS5KdV0xaRiZHiirx97UwZ2R3/vsXV2CxaGwlIp5FZUdELophGPxj4wGe+dcual0GcWFBpE9OISmuldnRRETOSWVHRC5YcUU1s9/eyqc7CwG4KTGaZ27tRWigv8nJRER+msqOiFyQLYdOMy0ji2P2KgJ8fXhsVHf+T/94ja1ExOOp7IjIz3K5DP765X6e+3g3TpfBFW1akJ6aQkJbm9nRREQuiMqOiPykU2UOZr29lfW7TwAwJimWeeMSaWnVrw4RaTr0G0tEzunr/aeYviyL4yUOrH4+zB3Tk0lXxWlsJSJNjsqOiNThdBn8+fO9LPx0Dy4DrowIZvHtKXSLDjU7mojIJVHZERG3E6UOHliezca9JwEYl9KWp25OIFhjKxFpwvQbTEQA2LT3JPcvz+ZEqYMgf1+evLkn4/vGmR1LROSyqeyINHNOl8Giz3J5aV0uhgFdolqyODWFzlEhZkcTEakXKjsizdjxkiruX5bF5v2nAZjYN465Y3oSFOBrcjIRkfqjsiPSTH2x5wQPLM/mVHk1LQJ8mXdLImOT25odS0Sk3qnsiDQztU4XC9bu4c/r9wHQLTqExbencGVES5OTiYg0DJUdkWYk317J9KVZfHuwCIDb+7XnsVE9CPTX2EpEvJfKjkgz8fmuQma+lU1RRQ0trX7MH5fI6KRYs2OJiDQ4lR0RL1fjdPH8x7t55Yv9ACS0DSV9cgpXhAebnExEpHGo7Ih4sSNFFUxbmkXW4WIA7hx4BXNu6obVT2MrEWk+VHZEvNQnOwp48J1t2CtrCAn047nbejEiIcbsWCIijU5lR8TLVNe6mP+vnbz674MAJLWzkZ6aQlxYC3ODiYiYRGVHxIscPlVB2tJMth2xA/A/13TgoRHdCPDzMTmZiIh5VHZEvMS/tufz0DvbKHXUYgvy54XxSdzQI8rsWCIiplPZEWniqmqczFu9k39+dQiAlPateCk1hbatgkxOJiLiGVR2RJqwAyfLScvIZMexEgDuHdSR2cO64u+rsZWIyI9UdkSaqFVbj/Hoiu2UOWoJCw7ghQlJXN810uxYIiIeR2VHpImpqnHyxAffs/SbwwBcfUUYL05OJtoWaHIyERHPpLIj0oTsLSwjLSOTXQWlWCyQdn0n7h/aGT+NrUREfpLKjkgTsSLzCL97L4eKaifhLQNYOLE313aOMDuWiIjHU9kR8XAV1bU8/v4O3t5yBIABHduwaFJvIkM1thIRuRAqOyIebM/xUqYuySS3sAwfC9w/tAtpQzrh62MxO5qISJOhsiPigQzD4O0tR/j9+zlU1biICLHy4qRkBlzZxuxoIiJNjsqOiIcpd9Tyu/dyWJl1FIBrO4ezcGJvwltaTU4mItI0XfRLOL744gtGjx5NbGwsFouF9957r852wzCYO3cusbGxBAUFMXjwYHbs2FFnjcPhYNq0aYSHhxMcHMyYMWM4cuRInTVFRUVMmTIFm82GzWZjypQpFBcXX/QdFGlKduaXMDp9IyuzjuLrY+HB4V15/b+vVtEREbkMF112ysvLSUpKIj09/Zzbn332WRYsWEB6ejrffvst0dHR3HjjjZSWlrrXzJgxg5UrV7Js2TI2btxIWVkZo0aNwul0utekpqaSnZ3NmjVrWLNmDdnZ2UyZMuUS7qKI5zMMg4yvD3Pz4n+z/0Q50aGBLLunP1Ov74SPzs8REbksFsMwjEu+scXCypUrGTt2LPDDL+zY2FhmzJjBww8/DPxwFCcqKoo//vGP3HvvvdjtdiIiInjjjTeYOHEiAMeOHSMuLo7Vq1czfPhwdu7cSY8ePdi8eTP9+vUDYPPmzQwYMIBdu3bRtWvX82YrKSnBZrNht9sJDQ291Lso0uBKq2p4dGUOH2w9BsD1XSN4YUJvwoIDTE4mItL4GuL5u17fiezAgQMUFBQwbNgw93VWq5VBgwaxadMmALZs2UJNTU2dNbGxsSQkJLjXfPXVV9hsNnfRAejfvz82m829RsQb5By1M/qljXyw9Rh+PhYevakb/7jjKhUdEZF6VK8nKBcUFAAQFRVV5/qoqCgOHTrkXhMQEEDr1q3PWvPj7QsKCoiMPPszfiIjI91rzuRwOHA4HO6vS0pKLv2OiDQwwzB4Y/Mhnv5wJ9VOF21bBfHi5GT6xLc+/41FROSiNMirsSyWuucYGIZx1nVnOnPNudb/3PeZP38+TzzxxCWkFWlc9soa5qzYxurtPxT3G3tE8dxtvWjVQkdzREQaQr2OsaKjowHOOvpSWFjoPtoTHR1NdXU1RUVFP7vm+PHjZ33/EydOnHXU6Edz5szBbre7L3l5eZd9f0Tq29a8Yka99CWrtxfg72vh96N68NcpfVR0REQaUL2WnQ4dOhAdHc3atWvd11VXV7NhwwYGDhwIQJ8+ffD396+zJj8/n5ycHPeaAQMGYLfb+eabb9xrvv76a+x2u3vNmaxWK6GhoXUuIp7CMAz+sfEAt/1lE3mnK4kLC+KdXw/kV9d0OO9RTxERuTwXPcYqKytj79697q8PHDhAdnY2YWFhtG/fnhkzZjBv3jw6d+5M586dmTdvHi1atCA1NRUAm83GXXfdxaxZs2jTpg1hYWHMnj2bxMREbrjhBgC6d+/OiBEjuPvuu3nllVcAuOeeexg1atQFvRJLxJMUV1Tz4DvbWPv9D0crRyZE88ytvbAF+ZucTESkebjosvPdd99x/fXXu7+eOXMmAHfccQevvfYaDz30EJWVldx3330UFRXRr18/PvnkE0JCQty3WbhwIX5+fkyYMIHKykqGDh3Ka6+9hq+vr3vNkiVLmD59uvtVW2PGjPnJ9/YR8VSZh4uYlpHF0eJKAnx9+N2o7kzpH6+jOSIijeiy3mfHk+l9dsRMLpfB377cz3Mf76bWZXBFmxakp6aQ0NZmdjQREY/WEM/f+mwskXp2uryaWW9l8/nuEwCMTopl3i0JhARqbCUiYgaVHZF69M2B00xfmkVBSRVWPx/mjunJpKviNLYSETGRyo5IPXC5DF7esI8Fa/fgdBl0jAhmcWoK3WM0QhURMZvKjshlOlnm4IHl2XyZexKAcclteWpsAsFWPbxERDyBfhuLXIZN+05y/7JsTpQ6CPT34ambExjfN87sWCIi8h9UdkQugdNl8NK6XF78LBeXAV2iWrI4NYXOUSHnv7GIiDQqlR2Ri1RYUsWM5dls2ncKgAl92/HEmASCAnzPc0sRETGDyo7IRfgy9wQPLM/mZFk1LQJ8+cMtCdyS3M7sWCIi8jNUdkQuQK3TxZ8+zWXx+r0YBnSLDmHx7SlcGdHS7GgiInIeKjsi55Fvr+T+pdl8c/A0AKn92vP7UT0I9NfYSkSkKVDZEfkZn+8uZObybIoqamhp9WP+uERGJ8WaHUtERC6Cyo7IOdQ4XTz/yW5e2bAfgIS2oaRPTuGK8GCTk4mIyMVS2RE5w9HiSqZlZJJ5uBiAOwbE8+gvu2P109hKRKQpUtkR+Q9rvz/O7Le3Yq+sISTQj2dv7cXIxBizY4mIyGVQ2REBqmtd/HHNLv6x8QAASe1spKemEBfWwuRkIiJyuVR2pNnLO11BWkYmW4/YAbjrmg48PKIbAX4+JicTEZH6oLIjzdqanHwefGcbpVW12IL8eX58Ejf2iDI7loiI1COVHWmWHLVO5n20k9e/OgRASvtWvJSaQttWQSYnExGR+qayI83OwZPlpC3NJOdoCQD3DurI7GFd8ffV2EpExBup7Eiz8sHWY8xZsZ0yRy2tW/izYEJvru8WaXYsERFpQCo70ixU1Th58sPvyfj6MABXXxHGosm9ibFpbCUi4u1UdsTr7TtRxtQlmewqKMVigamDOzHjhs74aWwlItIsqOyIV1uZdYTfrsyhotpJeMsAFk7szbWdI8yOJSIijUhlR7xSZbWTx1fl8NZ3RwAY0LENiyb1JjI00ORkIiLS2FR2xOvkHi9lakYme46XYbHA/UM7M21IZ3x9LGZHExERE6jsiFd5+7s8Hns/h6oaFxEhVhZN6s3AK8PNjiUiIiZS2RGvUO6o5bH3c1iReRSAazuHs2BCbyJCrCYnExERs6nsSJO3M7+EtIxM9p0ox8cCs4Z15TeDrsRHYysREUFlR5owwzBY+k0eT3ywA0eti+jQQF6cnMzVHcLMjiYiIh5EZUeapNKqGh5dmcMHW48BMLhrBAsm9CYsOMDkZCIi4mlUdqTJyTlqJy0jk4OnKvD1sfDQ8K7cfW1Hja1EROScVHakyTAMgzc3H+KpD3dS7XQRawvkpdQU+sS3NjuaiIh4MJUdaRJKqmp45N1trN5eAMAN3aN4fnwvWrXQ2EpERH6eyo54vK15xaQtzSTvdCX+vhYeHtGNu67pgMWisZWIiJyfyo54LMMwePXfB5n/r53UOA3atQ4iPTWF3nGtzI4mIiJNiMqOeKTiimoefGcba78/DsCIntH88bZe2IL8TU4mIiJNjcqOeJzMw0VMy8jiaHElAb4+/G5Ud6b0j9fYSkRELonKjngMl8vgb1/u57mPd1PrMohv04LFqSkktLWZHU1ERJowlR3xCKfLq5n99lbW7SoEYFSvGOaPSyQkUGMrERG5PCo7YrpvD55mWkYWBSVVBPj5MHd0TyZfHaexlYiI1AuVHTGNy2Xw8oZ9LFi7B6fLoGN4MItvT6F7TKjZ0URExIuo7IgpTpY5eGB5Nl/mngTgluS2PD02gWCr/kmKiEj90jOLNLqv9p3i/mVZFJY6CPT34ckxCYzv205jKxERaRAqO9JonC6Dl9bl8uJnubgM6BzZksW3p9AlKsTsaCIi4sVUdqRRFJZWMWNZNpv2nQJgfJ92PHFzT1oE6J+giIg0LD3TSIPbmHuSGcuzOFlWTYsAX54em8C4lHZmxxIRkWZCZUcaTK3TxZ8+zWXx+r0YBnSLDiE9NYVOkS3NjiYiIs2Iyo40iAJ7FdOXZvHNwdMATL66PY+P7kGgv6/JyUREpLlR2ZF69/nuQma9tZXT5dUEB/gy/9ZejEmKNTuWiIg0Uyo7Um9qnC6e/2Q3r2zYD0DP2FDSU1PoEB5scjIREWnOVHakXhwtrmT60iy2HCoC4L8GxPPoTd01thIREdP51Pc3nDt3LhaLpc4lOjravd0wDObOnUtsbCxBQUEMHjyYHTt21PkeDoeDadOmER4eTnBwMGPGjOHIkSP1HVXqyaffH+emRV+y5VARIVY//nx7Ck/enKCiIyIiHqHeyw5Az549yc/Pd1+2b9/u3vbss8+yYMEC0tPT+fbbb4mOjubGG2+ktLTUvWbGjBmsXLmSZcuWsXHjRsrKyhg1ahROp7Mh4solqq518fSH3/M///wOe2UNvdrZ+Gj6tdyUGGN2NBEREbcGGWP5+fnVOZrzI8Mw+NOf/sRvf/tbxo0bB8Drr79OVFQUGRkZ3Hvvvdjtdv7xj3/wxhtvcMMNNwDw5ptvEhcXx6effsrw4cMbIrJcpLzTFaQtzWJrXjEAv/pFBx4Z2Y0AvwbpzyIiIpesQZ6ZcnNziY2NpUOHDkyaNIn9+384YfXAgQMUFBQwbNgw91qr1cqgQYPYtGkTAFu2bKGmpqbOmtjYWBISEtxrzsXhcFBSUlLnIg1jTU4+N734JVvzigkN9OOvU/rw+9E9VHRERMQj1fuzU79+/fjnP//Jxx9/zN/+9jcKCgoYOHAgp06doqCgAICoqKg6t4mKinJvKygoICAggNatW//kmnOZP38+NpvNfYmLi6vneyaOWiePv5/Dr9/MpLSqluT2rVh9/7UM63n2UTwRERFPUe9jrJEjR7r/nJiYyIABA7jyyit5/fXX6d+/P8BZn25tGMZ5P/H6fGvmzJnDzJkz3V+XlJSo8NSjgyfLSVuaSc7RH46Y3XtdR2YP74q/r47miIiIZ2vwZ6rg4GASExPJzc11n8dz5hGawsJC99Ge6OhoqqurKSoq+sk152K1WgkNDa1zkfrx4bZjjHppIzlHS2jdwp//e2df5tzUXUVHRESahAZ/tnI4HOzcuZOYmBg6dOhAdHQ0a9eudW+vrq5mw4YNDBw4EIA+ffrg7+9fZ01+fj45OTnuNdI4qmqcPLpyO2kZWZQ5arnqitasvv9ahnT76dIpIiLiaep9jDV79mxGjx5N+/btKSws5Omnn6akpIQ77rgDi8XCjBkzmDdvHp07d6Zz587MmzePFi1akJqaCoDNZuOuu+5i1qxZtGnThrCwMGbPnk1iYqL71VnS8PadKGPqkkx2FfzwlgD3Db6SmTd2wU9Hc0REpImp97Jz5MgRJk+ezMmTJ4mIiKB///5s3ryZ+Ph4AB566CEqKyu57777KCoqol+/fnzyySeEhIS4v8fChQvx8/NjwoQJVFZWMnToUF577TV8ffUmdY3hvayjPLpyOxXVTtoEB7BgYm8GdYkwO5aIiMglsRiGYZgdoiGUlJRgs9mw2+06f+cCVVY7mbtqB8u/ywOgf8cwFk1KJio00ORkIiLSXDTE87c+G0sAyD1eytSMTPYcL8NigelDOjN9aGd8fX7+VXIiIiKeTmVHePu7PH7//g4qa5xEhFhZNLE3AzuFmx1LRESkXqjsNGPljloeez+HFZlHAbimUzgLJ/YmIsRqcjIREZH6o7LTTO0qKGHqkkz2nSjHxwIzb+zCbwZ30thKRES8jspOM2MYBsu+zWPuqh04al1EhVp5cVIy/Tq2MTuaiIhIg1DZaUbKHLU8umI7q7YeA2BQlwgWTEiiTUuNrURExHup7DQTOUftpGVkcvBUBb4+FmYP68q913XER2MrERHxcio7Xs4wDN7cfIinPtxJtdNFrC2Ql1KT6RMfZnY0ERGRRqGy48VKqmp45N1trN7+wwev3tA9kuduS6J1cIDJyURERBqPyo6X2nakmKkZmeSdrsTPx8IjI7tx1zUdsFg0thIRkeZFZcfLGIbBq/8+yPx/7aTGadCudRDpqSn0jmtldjQRERFTqOx4EXtFDQ++s5VPvj8OwPCeUTx7WxK2IH+Tk4mIiJhHZcdLZB4uYlpGFkeLKwnw9eG3v+zOfw2I19hKRESaPZWdJs7lMvj7xv08u2Y3tS6D+DYtSJ+cQmI7m9nRREREPILKThNWVF7NrLe3sm5XIQC/7BXD/HGJhAZqbCUiIvIjlZ0m6tuDp5m+NIt8exUBfj48ProHqVe319hKRETkDCo7TYzLZfDyhn0sWLsHp8ugY3gw6akp9IgNNTuaiIiIR1LZaUJOljl4YHk2X+aeBGBs71ieviWRllbtRhERkZ+iZ8km4qt9p7h/WRaFpQ4C/X14ckwC4/u209hKRETkPFR2PJzTZZC+bi+LPtuDy4BOkS1ZnJpC1+gQs6OJiIg0CSo7HqywtIoZy7LZtO8UAOP7tOOJm3vSIkC7TURE5ELpWdNDbcw9yYzl2ZwscxDk78sfbklgXEo7s2OJiIg0OSo7HqbW6WLRZ7mkf74Xw4Bu0SGkp6bQKbKl2dFERESaJJUdD1Jgr2L6siy+OXAagMlXx/H46J4E+vuanExERKTpUtnxEOt3FzLzra2cLq8mOMCXeeMSubl3W7NjiYiINHkqOyarcbpYsHYPL6/fB0CPmFAW355Ch/Bgk5OJiIh4B5UdEx0rrmTa0iy2HCoC4L8GxPPoTd01thIREalHKjsm+WzncWa9vZXiihpCrH788bZe3JQYY3YsERERr6Oy08iqa108u2YXf994AIBe7WykT06hfZsWJicTERHxTio7jSjvdAVpS7PYmlcMwK9+0YGHR3bF6qexlYiISENR2Wkka3IKeOidrZRU1RIa6Mfz45MY1jPa7FgiIiJeT2WngTlqncxfvYvXNh0EILl9K16anEy71hpbiYiINAaVnQZ06FQ5aRlZbD9qB+De6zoye3hX/H19TE4mIiLSfKjsNJCPtuXzyLvbKHXU0rqFPy9MSGJItyizY4mIiDQ7Kjv1rKrGydMffc+bmw8DcNUVrXlxcjIxtiCTk4mIiDRPKjv1aP+JMqZmZLEzvwSA+wZfycwbu+CnsZWIiIhpVHbqyfvZR3l0xXbKq520CQ5gwcTeDOoSYXYsERGRZk9l5zJVVjuZu2oHy7/LA6B/xzAWTUomKjTQ5GQiIiICKjuXZW9hKVOXZLH7eCkWC0wb0pn7h3bG18didjQRERH5Xyo7l+idLUd47L0cKmucRIRYWTSxNwM7hZsdS0RERM6gsnORKqpr+d17OazIPArANZ3CWTixNxEhVpOTiYiIyLmo7FykjK8PsyLzKD4WmHljF34zuJPGViIiIh5MZeci3TnwCrLzipnSP55+HduYHUdERETOQ2XnIvn5+pCemmJ2DBEREblAerc7ERER8WoqOyIiIuLVVHZERETEq6nsiIiIiFdT2RERERGvprIjIiIiXs3jy86f//xnOnToQGBgIH369OHLL780O5KIiIg0IR5ddpYvX86MGTP47W9/S1ZWFtdeey0jR47k8OHDZkcTERGRJsJiGIZhdoif0q9fP1JSUnj55Zfd13Xv3p2xY8cyf/78n71tSUkJNpsNu91OaGhoQ0cVERGRetAQz98ee2SnurqaLVu2MGzYsDrXDxs2jE2bNp213uFwUFJSUuciIiIi4rFl5+TJkzidTqKioupcHxUVRUFBwVnr58+fj81mc1/i4uIaK6qIiIh4MI8tOz+yWOp+orhhGGddBzBnzhzsdrv7kpeX11gRRURExIN57AeBhoeH4+vre9ZRnMLCwrOO9gBYrVasVmtjxRMREZEmwmPLTkBAAH369GHt2rXccsst7uvXrl3LzTfffN7b/3jetc7dERERaTp+fN6uz9dPeWzZAZg5cyZTpkyhb9++DBgwgL/+9a8cPnyYX//61+e9bWlpKYDO3REREWmCSktLsdls9fK9PLrsTJw4kVOnTvHkk0+Sn59PQkICq1evJj4+/ry3jY2NJS8vj5CQkHOe4yONo6SkhLi4OPLy8vQWACbTvvAc2heeQ/vCM/znfggJCaG0tJTY2Nh6+/4e/T470vTp/Y48h/aF59C+8BzaF56hofeDx78aS0RERORyqOyIiIiIV1PZkQZltVp5/PHH9bYAHkD7wnNoX3gO7QvP0ND7QefsiIiIiFfTkR0RERHxaio7IiIi4tVUdkRERMSrqeyIiIiIV1PZkcs2d+5cLBZLnUt0dLR7u2EYzJ07l9jYWIKCghg8eDA7duwwMbH3+OKLLxg9ejSxsbFYLBbee++9Otsv5GfvcDiYNm0a4eHhBAcHM2bMGI4cOdKI98I7nG9f3HnnnWc9Tvr3719njfbF5Zs/fz5XXXUVISEhREZGMnbsWHbv3l1njR4XjeNC9kVjPS5UdqRe9OzZk/z8fPdl+/bt7m3PPvssCxYsID09nW+//Zbo6GhuvPFG9+eXyaUrLy8nKSmJ9PT0c26/kJ/9jBkzWLlyJcuWLWPjxo2UlZUxatQonE5nY90Nr3C+fQEwYsSIOo+T1atX19mufXH5NmzYwNSpU9m8eTNr166ltraWYcOGUV5e7l6jx0XjuJB9AY30uDBELtPjjz9uJCUlnXOby+UyoqOjjWeeecZ9XVVVlWGz2Yy//OUvjZSweQCMlStXur++kJ99cXGx4e/vbyxbtsy95ujRo4aPj4+xZs2aRsvubc7cF4ZhGHfccYdx8803/+RttC8aRmFhoQEYGzZsMAxDjwsznbkvDKPxHhc6siP1Ijc3l9jYWDp06MCkSZPYv38/AAcOHKCgoIBhw4a511qtVgYNGsSmTZvMitssXMjPfsuWLdTU1NRZExsbS0JCgvZPA1i/fj2RkZF06dKFu+++m8LCQvc27YuGYbfbAQgLCwP0uDDTmfviR43xuFDZkcvWr18//vnPf/Lxxx/zt7/9jYKCAgYOHMipU6coKCgAICoqqs5toqKi3NukYVzIz76goICAgABat279k2ukfowcOZIlS5awbt06XnjhBb799luGDBmCw+EAtC8agmEYzJw5k2uuuYaEhARAjwuznGtfQOM9Lvzq525IczZy5Ej3nxMTExkwYABXXnklr7/+uvtEM4vFUuc2hmGcdZ00jEv52Wv/1L+JEye6/5yQkEDfvn2Jj4/no48+Yty4cT95O+2LS5eWlsa2bdvYuHHjWdv0uGhcP7UvGutxoSM7Uu+Cg4NJTEwkNzfX/aqsMxt4YWHhWf+zkvp1IT/76OhoqqurKSoq+sk10jBiYmKIj48nNzcX0L6ob9OmTWPVqlV8/vnntGvXzn29HheN76f2xbk01ONCZUfqncPhYOfOncTExNChQweio6NZu3ate3t1dTUbNmxg4MCBJqb0fhfys+/Tpw/+/v511uTn55OTk6P908BOnTpFXl4eMTExgPZFfTEMg7S0NFasWMG6devo0KFDne16XDSe8+2Lc2mwx8WFn0ctcm6zZs0y1q9fb+zfv9/YvHmzMWrUKCMkJMQ4ePCgYRiG8cwzzxg2m81YsWKFsX37dmPy5MlGTEyMUVJSYnLypq+0tNTIysoysrKyDMBYsGCBkZWVZRw6dMgwjAv72f/617822rVrZ3z66adGZmamMWTIECMpKcmora016241ST+3L0pLS41Zs2YZmzZtMg4cOGB8/vnnxoABA4y2bdtqX9Sz3/zmN4bNZjPWr19v5Ofnuy8VFRXuNXpcNI7z7YvGfFyo7MhlmzhxohETE2P4+/sbsbGxxrhx44wdO3a4t7tcLuPxxx83oqOjDavValx33XXG9u3bTUzsPT7//HMDOOtyxx13GIZxYT/7yspKIy0tzQgLCzOCgoKMUaNGGYcPHzbh3jRtP7cvKioqjGHDhhkRERGGv7+/0b59e+OOO+446+esfXH5zrUPAOPVV191r9HjonGcb1805uPC8r+BRERERLySztkRERERr6ayIyIiIl5NZUdERES8msqOiIiIeDWVHREREfFqKjsiIiLi1VR2RERExKup7IiIiIhXU9kRERERr6ayIyIiIl5NZUdERES8msqOiIiIeLX/B6M77tf+wuthAAAAAElFTkSuQmCC",
      "text/plain": [
       "<Figure size 640x480 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "\n",
    "plt.plot(ks, calls)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "66663241",
   "metadata": {},
   "source": [
    "Črta je tako ravna, da se človek kar ustraši. Poglejmo razmerje med številom klicev in dolžino seznama."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "1139f2ca",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[8.75,\n",
       " 10.375,\n",
       " 10.916666666666666,\n",
       " 11.1875,\n",
       " 11.35,\n",
       " 11.458333333333334,\n",
       " 11.535714285714286,\n",
       " 11.59375,\n",
       " 11.63888888888889,\n",
       " 11.675,\n",
       " 11.704545454545455,\n",
       " 11.729166666666666,\n",
       " 11.75,\n",
       " 11.767857142857142,\n",
       " 11.783333333333333,\n",
       " 11.796875,\n",
       " 11.808823529411764,\n",
       " 11.819444444444445,\n",
       " 11.828947368421053,\n",
       " 11.8375]"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[c / k for c, k in zip(calls, ks)]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0d2f734d",
   "metadata": {},
   "source": [
    "Temu rečemo asimptota. Ko je število dolžina seznama dovolj velika, je število klicev enaka dolžini krat 11.83... S podaljševanjem dolžine se bo \"ustalilo\" vedno več decimalk. (V resnici število klicev leze proti $12n$. Zakaj ravno toliko, se mi ne da računati. Z malo poskušanja pa uvidimo, da je pri `2` skupinah število klicev leze proti $6n$, pri `3` skupinah proti $9n$, pri `4` proti $12n$. Pri $g$ skupinah je število klicev, izgleda $3(g + 1)n$. Odkod $3$ je očitno, odkod $g$ in $n$ tudi, o $+ 1$ pa se mi zdajle ne razmišlja. :)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "5fa2fcb0",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "149 ns ± 0.255 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "\n",
    "ways(\"???.??????#?????.##.????.??????#?????.##.????.??????#?????.##.????.??????#?????.##.????.??????#?????.##.\",\n",
    "     (1, 1, 7, 1, 1, 2, 1, 1, 7, 1, 1, 2, 1, 1, 7, 1, 1, 2, 1, 1, 7, 1, 1, 2, 1, 1, 7, 1, 1, 2))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3165c0ed",
   "metadata": {},
   "source": [
    "Klic, ki je prej potreboval 1,42 s, zdaj potrebuje 148 ns, kar je"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "d28cdb49",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'9_594_594.594594594'"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f\"{1.42 / 148e-9:_}\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "05fde6c1",
   "metadata": {},
   "source": [
    "-krat (se pravi: skoraj deset milijonkrat) hitreje."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3b061562",
   "metadata": {},
   "source": [
    "## Mami, jest ne maram rekurzije\n",
    "\n",
    "Tule je rešitev brez.\n",
    "\n",
    "`count` bo število najdenih konfiguracij in `to_count` bo seznam situacij, ki jih je potrebno še prešteti. V začetku je to pač `(line, groups)`. \n",
    "\n",
    "Za vsako konfiguracijo, ki jo je potrebno prešteti preverimo takšne pogoje kot prej - prej smo jih imenovali \"robni\". Razlika je le v tem, da zdaj ne vračamo števila konfiguracij, temveč jih prištejemo v `count`.\n",
    "\n",
    "Sledi tisto, kar so bili prej rekurzivni klici. Tu namesto rekurzivnega klica le dodamo nove konfiguracije v preverjanje."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "6ce61844",
   "metadata": {},
   "outputs": [],
   "source": [
    "def ways(line, groups):\n",
    "    count = 0\n",
    "    to_count = [(line, groups)]\n",
    "\n",
    "    while to_count:\n",
    "        line, groups = to_count.pop()\n",
    "        line = line.lstrip(\".\")\n",
    "        if not line:\n",
    "            count += not groups\n",
    "        elif not groups:\n",
    "            count += \"#\" not in line\n",
    "            \n",
    "        elif line[0] == \"?\":\n",
    "            to_count += [(\"#\" + line[1:], groups), (\".\" + line[1:], groups)]\n",
    "        else:\n",
    "            g0 = groups[0]\n",
    "            if len(line) >= g0 and \".\" not in line[:g0] and (len(line) == g0 or line[g0] != \"#\"):\n",
    "                to_count.append((line[g0 + 1:], groups[1:]))\n",
    "    return count"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c5ca69e7",
   "metadata": {},
   "source": [
    "Kdor vidi v tem goljufijo, ima kar prav: rekurzijo sem zgolj preoblikoval v iteracijo. Namesto klicev imamo zdaj seznam, v katerem se sčasoma naberejo vsi argumenti, s katerimi bi funkcijo klicali sicer. Ker mi je za vrstni red obravnavanja vseeno, pobiram nove \"naloge\" s konca seznama, s `pop`; na ta način lahko preprosto odstranjujem elemente iz seznama.\n",
    "\n",
    "Še več: `to_count` je zelo v sorodu s skladom, na katerega bi Python shranjeval rekurzivne klice. (Vendar samo v sorodu: `to_count` ne vsebuje le \"aktivnih\" klicev, temveč tudi klice, ki se morajo še zgoditi.)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5aa8aef5",
   "metadata": {},
   "source": [
    "## Brez rekurzije - zares\n",
    "\n",
    "Problem gornje funkcije je počasnost: nanjo ne moremo prilepiti `@cache`, tako kot na rekurzivno različico. Če bi jo hoteli pospešiti, bi jo morali sprogramirati povsem drugače, teči bi morala nekako z desne proti levi. To pa se mi, iskreno, ne da. Niti to ni namen teh zapiskov, ki naj bi v osnovi govorili o rekurziji. :)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.11.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}