p1/izpiti/2020/01_resitev.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Izpit 18. januar 2021\n",
    "\n",
    "\n",
    "## 1. Valovi epidemije\n",
    "\n",
    "V nekem kraju je bilo število okuženih, po dnevih, takšno:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "po_dnevih = [1, 5, 6, 0, 0, 0, 2, 3, 0, 5, 8, 0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "V prvem valu je bilo torej okuženih 1 + 5 + 6 = 12 ljudi, v drugem 2 + 3 = 5 in v tretjem 13, skratka `[12, 5, 13]`.\n",
    "\n",
    "Napiši funkcijo `po_valovih(po_dnevih)`, ki prejme seznam s številom okuženih po dnevih in vrne seznam s številom okuženih po valovih. Valovi so ločeni z enim ali več dnevi brez okužb. Dnevi brez okužb so lahko tudi na začetku ali koncu seznama. Za več primerov glej teste.\n",
    "\n",
    "### Rešitev\n",
    "\n",
    "Običajna rešitev je nekako takšna."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def valovi(s):\n",
    "    v_valovih = []\n",
    "    okuzenih = 0\n",
    "    for x in s + [0]:\n",
    "        if x == 0 and okuzenih:\n",
    "            v_valovih.append(okuzenih)\n",
    "            okuzenih = 0\n",
    "        else:\n",
    "            okuzenih += x\n",
    "    return v_valovih"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[12, 5, 13]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "valovi([1, 5, 6, 0, 0, 0, 2, 3, 0, 5, 8, 0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Lepa finta te rešitve je, da na konec seznama pripnemo `0` (glej `for`!), tako da se vedno konča z 0, ki poskrbi, da pripnomo tudi število okuženih v zadnjem valu. Brez tega je rešitev takšna."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def valovi(s):\n",
    "    v_valovih = []\n",
    "    okuzenih = 0\n",
    "    for x in s:\n",
    "        if x == 0 and okuzenih:\n",
    "            v_valovih.append(okuzenih)\n",
    "            okuzenih = 0\n",
    "        else:\n",
    "            okuzenih += x\n",
    "            \n",
    "    if okuzenih:\n",
    "        v_valovih.append(okuzenih)\n",
    "        \n",
    "    return v_valovih"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[12, 5, 13]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "valovi([1, 5, 6, 0, 0, 0, 2, 3, 0, 5, 8])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nekaj študentov je napisalo eno od takšnih rešitev in dodalo komentar \"ne znam lepše\".\n",
    "\n",
    "Lepše gre, če poznamo funkcijo `groupby`, ki jo dobimo v modulu `itertools`. Podamo ji seznam in ključ, po katerem na sestavi zaporedne skupine znotraj tega seznama. Pri nas bo ključ to, ali je element enak 0 ali ne. Funkcija vrne generator skupin. Poglejmo, kaj naredi z našimi bolniki."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(True, <itertools._grouper at 0x7fd24d083890>),\n",
       " (False, <itertools._grouper at 0x7fd24d083910>),\n",
       " (True, <itertools._grouper at 0x7fd24d0839d0>),\n",
       " (False, <itertools._grouper at 0x7fd24d083750>),\n",
       " (True, <itertools._grouper at 0x7fd24d083650>),\n",
       " (False, <itertools._grouper at 0x7fd24d083790>)]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from itertools import groupby\n",
    "\n",
    "list(groupby(po_dnevih, lambda x: x != 0))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Najprej je skupina elementov, za katere funkcija, ki smo jo podali vrne `True`, za drugo skupino vrne `False` in tako naprej. (Funkcija bi lahko vračala tudi drugačne vrednosti; `groupby` da v isto skupino takšne, pri katerih je vrednost enaka).\n",
    "\n",
    "Poglejmo, kakšne so v resnici te skupine."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True [1, 5, 6]\n",
      "False [0, 0, 0]\n",
      "True [2, 3]\n",
      "False [0]\n",
      "True [5, 8]\n",
      "False [0]\n"
     ]
    }
   ],
   "source": [
    "for k, group in groupby(po_dnevih, lambda x: x  != 0):\n",
    "    print(k, list(group))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pobrati moramo skupine, pri katerih je ključ `True` in izračunati njihove vsote, vse skupaj pa zložiti v seznam."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[12, 5, 13]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def valovi(s):\n",
    "    return [sum(g) for v, g in groupby(s, lambda x: x != 0) if v]\n",
    "\n",
    "valovi(po_dnevih)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Sledilnik\n",
    "\n",
    "- Prvi dan so zaprli gledališča in smučišča.\n",
    "- Drugi dan so zaprli še šole, frizerje in muzeje, vendar so ob tem odprli smučišča.\n",
    "- Tretji dan so zaprli knjižnice in odprli muzeje in smučišča (ki pa so bila itak že odprta!).\n",
    "- Četrti dan so zaprli smučišča (in knjižnice in gledališča, ampak ta so bila zaprta že od prej) in odprli šole.\n",
    "- Peti dan so odprli šole ter zaprli frizerje in smučišča.\n",
    "- Šesti dan so zaprli smučišča.\n",
    "- Sedmi dan so počivali(!).\n",
    "- Osmi dan so odprli smučišča.\n",
    "\n",
    "Vse skupaj predstavimo s seznamom parov seznamov. Vsak par ustreza enemu dnevu; prvi element para pove, kaj se je tisti dan zaprlo, drugi pa, kaj se je odprlo. Če je vse skupaj zapleteno: tako pač v resnici je. Tisti Janez, ki je sestavil to nalogo, s tem nima ničesar."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "dnevi = [\n",
    "    ([\"gledališča\", \"smučišča\"],              []),\n",
    "    ([\"šole\", \"frizer\", \"muzeji\"],            [\"smučišča\"]),\n",
    "    ([\"knjižnice\"],                           [\"muzeji\", \"smučišča\"]),\n",
    "    ([\"smučišča\", \"knjižnice\", \"gledališča\"], [\"šole\"]),\n",
    "    ([\"šole\"],                                [\"frizer\", \"smučišča\"]),\n",
    "    ([\"smučišča\"],                            []),\n",
    "    ([],                                      []),\n",
    "    ([],                                      [\"smučišča\"])\n",
    "]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Napiši funkcijo `sledilnik(dnevi)`, ki prejme seznam, kot je gornji, in vrne, kolikšno je največje število hkrati zaprtih stvari. V gornjem primeru vrne 4, ker so bile na, recimo, drugi dan, istočasno zaprte štiri stvari (gledališča, šole, frizerji in muzeji).\n",
    "\n",
    "### Rešitev\n",
    "\n",
    "Tole je bila naloga iz množic: vzdrževati je bilo potrebno množico prepovedanih dejavnosti ter v vsakem koraku od nje odšteti, kar je sveže dovoljeno ter \"priunijati\", kar je na novo prepovedano. Po vsakem koraku pa preverimo, ali je trenutno število prepovedi večje od največjega doslej."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sledilnik(dnevi):\n",
    "    zaprto = set()\n",
    "    zaprtih = 0\n",
    "    for zaprli, odprli in dnevi:\n",
    "        zaprto -= set(odprli)\n",
    "        zaprto |= set(zaprli)\n",
    "        if len(zaprto) > zaprtih:\n",
    "            zaprtih = len(zaprto)\n",
    "    return zaprtih"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sledilnik(dnevi)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nekdo je pisal samo 99 %, ker je pri tej nalogi kompliciral z nekim slovarjem. Na Discordu sva ugotovila, da pravzaprav ni tako slaba ideja, saj vodi - če jo odkompliciramo iz slovarja v seznam - v takšno rešitev."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sledilnik(dnevi):\n",
    "    zaprto = [set()]\n",
    "    for zapiranja, odpiranja in dnevi:\n",
    "        zaprto.append((zaprto[-1] | set(zapiranja)) - set(odpiranja))\n",
    "    return max(len(x) for x in zaprto)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Seznam `zaprto` bo vseboval vse, kar je zaprto od dneva 0 naprej. No, prvi element seznama bo prazna množica. Potem pa za vsak dan dodamo nov element, ki je enak zadnjemu, ki mu dodamo vse, kar se je ta dan zaprlo, in odvzamemo vse, kar se je odprlo. Na koncu vrnemo največjo velikost množice (lepše slovensko bi bilo velikost največje množice, ampak v Pythonu se to pač napiše največja velikost, `max(len(...`).\n",
    "\n",
    "Naloga je imela le en test in predpostavil sem, da bo to zadoščalo. Pravzaprav bi moralo ... a nekateri so računali vse mogoče druge stvari; nekdo je napisal funkcijo, ki vrne število dni, pri katerih imamo vsaj en `[]` (ni nove prepovedi ali odprtja), nekateri so vrnili maksimalno število prepovedi v enem dnevu, ki so mu prišteli 1, zato da so dobili 4 in ne 3, mnogi so opazovali le prepovedi in ne odprtij ter vse skupaj obrnili tako, da je bil rezultat slučajno 4. Vse take rešitve, ki so očitno napačne, sem štel kot napačne.\n",
    "\n",
    "Bolj pogosta pomanjkljivost je bila, da niste uporabljali unij in presekov, temveč napisali zanko, v kateri kličete `add` oziroma `remove` ali `discard`. Še bolj žalosten se, bil, če ste namesto množic uporabljali sezname. Nekateri so uporabljali slovarje namesto množic... Storilci takih dejanj so tu izgubili par točk, za nikogar pa to ni bilo usodno.\n",
    "\n",
    "\n",
    "## 3. Širjenje okužbe\n",
    "\n",
    "<img style=\"float: right\" src=\"data:image/.png;base64,iVBORw0KGgoAAAANSUhEUgAAANIAAACLCAMAAAAjxjdPAAAAGXRFWHRTb2Z0d2FyZQBBZG9iZSBJbWFnZVJlYWR5ccllPAAAADBQTFRFf39/QkJCv7+/7+/vEBAQn5+f39/fYGBgICAgMDAwz8/Pj4+Pr6+vcHBwAAAA////zukQ0gAAABB0Uk5T////////////////////AOAjXRkAAAtDSURBVHja7J2JkuMoDEARlwFj8v9/uwjwlXA6nuwkNa6a7p4+iB8IXUgOefzcRf4hDV7SOfljSLNy848h6Qn0byFJJ+YgeVQwAmDwewJgkd+LNDsmg+QRrSeiuUexmhCl2NciafD/UPIIgjG3xG8bZ78VycsdrpREJPw/QAASxJFvRZpduOYjktFq+WIkram/lD4igfb76GuRomZ4LF7ydiSkYV+LFPV3INuRFDA2fS2S1tvnHcly5wgsP+W2MvqHvb5/nvg/pH9I/5D+XyS58In+EhKdgq8H9leQhA5AE+FOiR9AYkQ5RcAJ7wOxWTlO2HcjGS9xWnjHdUrOtwDHpy/2Hix4cfNKQXiiLZ6g6ZtfiBSlLKRS3DlEkn7pQPxFSIyGqyE8ckJdELaN4Rw/H+MJRrafFgcQxH4KyQBe9YQjChck4WKah1zXOURioq4pJJ8WrtkHBU/wyqvh3e4qQLsoYy9Rn8BNVVxstgXFH0JSxT+TKFPzDjyt95UJZNECQ1lTMCc+hyRKuXv6vPMJKrsSUtxyJU0hp08KnprypChK5swOjxpS0hRz5t6d4/TxMaTsIqGbEJX2QZUcdng5gyJe/zBagYs52StIMGUlSIsXtcX3NaslhWxeU0zqU0j0ZZEs5PY50+4ghfU8V1ZTxLTSJ5CeFimYmNzxCpw0Vit15yOqwzoHedXwISTq6NOd5B2Bp/xjOxsZnPakKWa1EKXMh5AMfXITbEGHnBezK8G6L7iZyVXf9h23FWO7kv237smqdOaM6Ysh+BxSMChFL83w54O+HYmIZowF9PNIph4gsKP6fkIirrXr4/78LJJohHFefb/8dAsBFbQVGQZb6mpIP460x3bFa8o4nAmJKQvQuVH5tZP3UaRDbFe8FpfxARPSAg/oNDdXQ/oxJAodW1dkN0tEsj7QAuifvyvJvwEkdo7tyqY4GxQEJMbtYwAphV/iDyHJUhTwor7zEW9AIvGI3dHRrcvuR6K9IrCmGkp76TG2SquCHUn+kU7t02vSdSm6fgNpUFO0kWJs17nyUzEF8hbSUPKPdAylu/cncdOjifSOBybYu0h2zDSIiq9zQ6lDK/nXRgq6ZsSAm1oy8Z7qjXryr4FUju2Kf8F5RYXcVZBCm4564YUMDNvtc6rhjyHVk38VpKliCBiNa2eJKacaXpF6dYycienRFEWzT64oHlx3BoocU5StUqdeEV7UsvC2mhflcODCyYUISMSHrWafelFW34PjM3QTO2TeljTFpTweIqnlaDWt03eewfZtPNQUNyKxtFSlVMN7CqA3dSzpjUhxqVI+lFXV94Ugjr8zQXcg5VINb22n92quCeYaKb0qeLqUanjEcYuzzUzFZE8l6xGu7JiCPqyNyoWksGzpV7xJPeD6hvT4kld2EMYthaRQtMtMT8W5LMePRtGggiEihbOcTFDASQUpKnFa9lWDNjRTQbnbiY0SPWXjX/Yfys5kV6T8KYGrITGtCUoILanvpODnwRNX5fDEfhlGOu6liBTMDMXcGYqSEJx4N0/5oUNSyBQdolKqYbdZCmJSDpdFLH5ULoJLXVqKcJkaUjifs+E+rXLxfAMNr59b9P0QiVIbauypI1QgEwBfqCQOiHiImVqth1MNO9LiMA0eByZKCW8g6bXjsBXJLJQCdtmA1pZqnFPvvFA6R8FK6gGTUfFUWbht726CVzxBL6cadqT15vGYkoSbQnm9hhSq+pI19i8MSINe2dYesCKhL+q/L91ECME5TJ1h8fcMgaLdmSrVFsdV8kIKyh1bL64hzVEm5TwB3lx8Cf/VNuc7UphDv9FDMY1Z7yal3hY6F5BIzVddkVDxAJ+9vGWRJO24zoJnOVh6QtpGOyL5j7vRPiCFqpeCqhHVY5U0CPXrL1CQSR4JXMdlTkhhg5yQ5swqMQVRNz0j0Wh66GiqYR2E8rXVp7BKZnyV4lQfkeTzXiJkUai4/IJ65bdnrZWikvnv+XCLjqYa/CDK70ztIKjShfrI8f29RNPI1mp+REIPhlKyIgncP3NYOKu9B4O/EC2dV/oEP4DM5C8aqQY/Mo6bYm7Ps1APF60RDi8u5CdNso9oMekyr/cZ8hBEOZy9aJcuXuA+UU38oeCiK9XwfUi3pRr+GqSbUw1/AdLNqYaPIJlqVemVVIMktxe8CzuCVLUaF1INGKHcq04wQwq3IU2j6jtES7ciheIYdRvSMqbsZKo1uhEpFcfAXUjCweh0iv4EaofEbcUxdyHREfV9rDW6B+lYHHMTUjnVUJnOPiS5wELbWmZ3N+9BqqQastPZTjcdJmuiS02VvhTH3IOkO5VdptaohTTpR61AN1MccwvS1NXYkS9JbiGFfEcpLUlzVQ93IJEe9R2OrTOHjh2CZwiXRS1jismNN5B61He51qipHuaUentxE0rFDn1IMiVSc0im3SJVqzVqIQlO5fJyClMrjulBkkrpeISRQWqlGlK7aZG6dTodFM9Tl0W9OKZrlShGQiKL1Eo1mFatUQPpdKq427VacUz3XooPd3JjqYaOWqOW4HFgXkymk5apF8f0Is1B6bwg1RzpvlqjpsZTHNx66ER7imP6kEDFDfOMVEk1NKcz9au2fbxVN8VgpDRFhsxyBIlaCExPSOVUQ7MkWajE0uu2ymrjw0Nrshr87r0UfvGMVEw1dJQkazqEZFrFkVGJsCGkQHNCKqQaekuSB5BEX0VjSiT3r5J+VqbZVAPtrjXtRepofNh2dvcqicn6O7VPSLlUgxjoMupDeglG2qquy3uYAeI0HZBeUw25dtM3kboaH8525rrb+uKrvrabhqPDN5CK/ZEFs75KzUWk51RDpt3Ub9ZqxU4DqRSMlIMQ8VZwcU415KfT6jcEj472vuxE15BOqYbSdBK4jDTQ+LCnc1DMxWWkQ6qhPJ2Tq/e4lRyiRjBS2HeHZ4JcQdpTDbV20xC+Qa/i6w5GunX5CNKaaqi3mya9KIeQ7B2PuRlHSurb9LgJHTVYO9Jw48NdSDHV0Ol1JRelB2m88eEuJEw1dHldzIcvgpPOvTTkJtyMpJ2duqZTAu/a54jU1x/5p5Acv286I9JExtyEP4B089PE3O1PvRpD8gH+3UfmhPS5CRZizWj7okPHz//jJSx25r81eY+/8Lr4HJi/GQl+bJUo0cB+DQnee8omyfjvbIsI/qdrfustTEhKKCjv68/epWPRBb3jSH+BYqvBYCRySLvwdkxCUrwjKPXqc3LmPqRQ3EquyFDhyXgM3GQpnV/tkZ2fkMye15KPG5Eu6S1vkSXkiyuWZjPEhgTb2ZukByQWC+cvP8Zyex3K/Ch+skR8ABQTpOINL9qpvC92fFCjkWym291RfKuGbWBykly0cSsS0wo3FoCDN5HcrEA5q7UOM8U18CvNfkcDDAuOJfxQ4ZmweG0Dk1NIekSacJkZw1zgNY8c1mSO8yOx8K5FwKNwX3pXiKN0AfqBks+xiyT9KA1cRNoEV9KLGyuqBxxsWec4zQ6jexkKJe3reJ4UFiTOTWyBxea9lTYMTE4NkjuSjiqDLbi25E3BIytSGHtWCvaUUn/PRezXoaEfJYyd/hTWl0oD46vtHZI7koo1CEH67kUSu6RcM8BkQ9JrR1r47zowWe/7ZS+FPi5HHncjxbu5gCSTntqQFn56qfVDfOBRfJ4oO2s87GnBBZxvRlKP2Cw67o7EE/cNSYbNwVYztA5MYkrEKQC1nJD8FxPmVTToi0hR1J+RqH8tddEMc2zndCuSFzU/EAqTcHrZBk53a2ZCLAumdndbjf+Keo/GXGtAN2vvURgsdMiHsSWZmbxmF5hFHYoNgPGWvKmN5tui45UG/sE3hfhPgAEAeVYx6YfqNqEAAAAASUVORK5CYII=\"/>\n",
    "\n",
    "Vemo, kdo se je na kateri dan družil s kom (glej sliko). Podatki so shranjeni v slovarju (vsako druženje je zabeleženo dvakrat, pri obeh družabnikih):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "druzenja = {\n",
    "    \"Ana\": [(\"Berta\", 7), (\"Cilka\", 10), (\"Dani\", 4), (\"Fanči\", 3)],\n",
    "    \"Berta\": [(\"Ana\", 7), (\"Cilka\", 3)],\n",
    "    \"Cilka\": [(\"Ana\", 10), (\"Berta\", 3), (\"Dani\", 5)],\n",
    "    \"Dani\": [(\"Ana\", 4), (\"Cilka\", 5), (\"Ema\", 1), (\"Fanči\", 2)],\n",
    "    \"Ema\": [(\"Dani\", 1), (\"Fanči\", 8), (\"Greta\", 3)],\n",
    "    \"Fanči\": [(\"Ana\", 3), (\"Dani\", 2), (\"Ema\", 8), (\"Greta\", 2)],\n",
    "    \"Greta\": [(\"Ema\", 3), (\"Fanči\", 2)]\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Če se nekdo druži s kom, ki je okužen, postane sam kužen naslednji dan (na isti dan, ko se je okužil, pa še ni nevaren).\n",
    "\n",
    "Napiši funkcijo `okuzeni(oseba, cas, druzenja)`, ki prejme ime osebe, dan, na katerega se je okužila, in slovar druženj. Funkcija vrne množico vseh okuženih.\n",
    "\n",
    "Klic `okuzeni(\"Ana\", 3, druzenja)` vrne `{\"Ana\", \"Berta\", \"Cilka\", \"Dani\"}`, ker Ana okuži Dani in Berto, Dani pa še Cilko (Cilko bi tudi direktno okužila Ana, vendar jo Dani prehiti). Fanči ni okužena: Ana na dan 3 še ni bila kužna, Dani pa se je tako ali tako okužila šele na dan 4.\n",
    "\n",
    "\n",
    "**Namig:** ne boj se, da se kaj *zacilka*, saj nihče ni kužen na dan, ko se je okužil, zato časi vedno naraščajo.\n",
    "\n",
    "### Rešitev\n",
    "\n",
    "Naloga je praktično enaka nalogi, v kateri iščemo vse člane rodbine, le da pazimo še na časovne omejitve. Preprosti rekurzivni rešitvi sta"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "def okuzeni(oseba, cas, druzenja):\n",
    "    okuzenih = {oseba}\n",
    "    for kdo, kdaj in druzenja[oseba]:\n",
    "        if kdaj > cas:\n",
    "            okuzenih |= okuzeni(kdo, kdaj, druzenja)\n",
    "    return okuzenih"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "def okuzeni(oseba, cas, druzenja):\n",
    "    return set.union({oseba},\n",
    "                     *(okuzeni(kdo, kdaj, druzenja)\n",
    "                       for kdo, kdaj in druzenja[oseba] if kdaj > cas))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'Ana', 'Berta', 'Cilka', 'Dani'}"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "okuzeni(\"Ana\", 3, druzenja)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Se da rešiti nalogo brez rekurzije? V drugem letniku boste to spoznali kot iskanje v širino, videli pa smo ga tudi letos na dodatnih predavanjih. Takole:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "def okuzeni(oseba, cas, druzenja):\n",
    "    preveriti = [(oseba, cas)]\n",
    "    okuzenih = set()\n",
    "    for oseba, cas in preveriti:\n",
    "        okuzenih.add(oseba)\n",
    "        for stik, cas_stika in druzenja[oseba]:\n",
    "            if cas_stika > cas:\n",
    "                preveriti.append((stik, cas_stika))\n",
    "    return okuzenih"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'Ana', 'Berta', 'Cilka', 'Dani'}"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "okuzeni(\"Ana\", 3, druzenja)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Kot običajno se je naloga iz rekurzije izkazala za najtežjo nalogo, čeprav jo je rešilo veliko (pravzaprav morda celo nerealno veliko) število študentov).\n",
    "\n",
    "Nekaj študentov je nalogo rešilo tako, da je napisalo zanko znotraj zanke znotraj zanke znotraj zanke ... pač toliko zank, kolikor je bila dolga najdaljša pot v testih. Tega nisem mogel šteti za pravilno rešitev.\n",
    "\n",
    "## 4. Identifikator\n",
    "\n",
    "V laboratorij so dobili tri različne viruse, ki pa so vsi predstavniki \"angleškega\" seva Covida. Zaporedja mRNA teh treh, gentlemanskih virusov so:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "pozitivni = ['GGGUGCCCCA', 'CCCAUAGGGU', 'CAGCUCGGUU']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tole pa so štirje primeri \"običajnega\" Covida:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "negativni = ['ACCUCAGGAG', 'UCGACCGAAG', 'GUCACUCGCA', 'CGCUUCCCGC']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "V laboratoriju uporabljajo naslednje testne fragmente (koščke) mRNA:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "fragmenti = [\"GGU\", \"CCC\", \"ACC\", \"GGG\"]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Idealno bi bilo, če bi našli fragment, ki se pojavlja v vseh angleških in nobenem od ostalih. Ker ni nujno, da tak fragment obstaja, pa bomo zadovoljni s takšnim, ki se pojavi v čimveč angleških in čim manj neangleških.\n",
    "\n",
    "- GGU se pojavi v 3 pozitivnih in 0 negativnih, razlika je 3.\n",
    "- CCC se pojavi v 2 pozitivnih in 1 negativnem, razlika je 1.\n",
    "- GGG se pojavi v 2 pozitivnih in 0 negativnih, razlika je 0.\n",
    "- ACC se pojavi v 0 pozitivnih in 2 negativnih, razlika je -1.\n",
    "\n",
    "Najboljši je GGU.\n",
    "\n",
    "Napiši funkcijo `identifikator(pozitivni, negativni, fragmenti)`, ki prejme seznam pozitivnih in negativnih primerov ter seznam fragmentov. Vrniti mora fragment, pri katerem je razlika med številom njegovih pojavitev v pozitivnih in v negativnih primerih virusov čim večja. Če je takšnih fragmentov več, lahko vrne kateregakoli od njih.\n",
    "\n",
    "### Rešitev\n",
    "\n",
    "Nalogo je bilo možno rešiti na kup načinov. Večina je komplicirala s slovarja in na koncu dokazala, da znajo googlati in najti zapleten klic (ki ga pretežno ne razumejo) in vrne ključ, ki pripada največji vrednosti.\n",
    "\n",
    "Tole je nekoliko daljša, a čisto lepa rešitev."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "def identifikator(pozitivni, negativni, fragmenti):\n",
    "    naj_frag = None\n",
    "    naj_razlika = 0  # Če ne dobimo pozitivne razlike, naj gre vse k vragu :)\n",
    "    for fragment in fragmenti:\n",
    "        razlika = 0\n",
    "        for poz in pozitivni:\n",
    "            if fragment in poz:\n",
    "                razlika += 1\n",
    "        for neg in negativni:\n",
    "            if fragment in neg:\n",
    "                razlika -= 1\n",
    "        if razlika > naj_razlika:\n",
    "            naj_razlika = razlika\n",
    "            naj_frag = fragment\n",
    "    return naj_frag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'GGU'"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "identifikator(pozitivni, negativni, fragmenti)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Skrajšamo jo, če se spomnimo, da je `True` isto kot `1` in `False` isto kot `0`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "def identifikator(pozitivni, negativni, fragmenti):\n",
    "    naj_frag = None\n",
    "    naj_razlika = 0  # Če ne dobimo pozitivne razlike, naj gre vse k vragu :)\n",
    "    for fragment in fragmenti:\n",
    "        razlika = 0\n",
    "        for poz in pozitivni:\n",
    "            razlika += fragment in poz\n",
    "        for neg in negativni:\n",
    "            razlika -= fragment in neg\n",
    "        if razlika > naj_razlika:\n",
    "            naj_razlika = razlika\n",
    "            naj_frag = fragment\n",
    "    return naj_frag"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Odtod je le korak do"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "def identifikator(pozitivni, negativni, fragmenti):\n",
    "    naj_frag = None\n",
    "    naj_razlika = 0  # Če ne dobimo pozitivne razlike, naj gre vse k vragu :)\n",
    "    for fragment in fragmenti:\n",
    "        razlika = sum(fragment in poz for poz in pozitivni) \\\n",
    "                  - sum(fragment in neg for neg in negativni)\n",
    "        if razlika > naj_razlika:\n",
    "            naj_razlika = razlika\n",
    "            naj_frag = fragment\n",
    "    return naj_frag"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Toliko bi po tem predmetu načelno morali znati vsi. Kdor zna še malo več, pa je napisal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "def identifikator(pozitivni, negativni, fragmenti):\n",
    "    return max(fragmenti,\n",
    "               key=lambda f: sum(f in primer for primer in pozitivni)\n",
    "                             -sum(f in primer for primer in negativni))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pravzaprav bi to morali znati napisati vsi, ki so v rešitev napisali tisti `max`, ki so ga nagooglali. :)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5. Izbijanje zob\n",
    "\n",
    "Južnoameriški sev je posebej trdovraten in lotiti se ga je mogoče le s pestmi: izbiti mu je potrebno vse dele mRNA. Recimo, da je njegova mRNA v začetku takšna: `\"ACCUTCCUUGUACUUTAA\"`. Če mu izbijemo `\"CUU\"`, ostane le še `\"ACCUTCGUATAA\"` (iz niza odstranimo obe pojavitvi `CUU`). Vendar je še vedno živ in brca in grize in davi. Če mu izbijemo `A`, ostane `\"CCUTCGUT\"`. In tako naprej. Virus je mrtev šele, ko mu ne ostane nič več.\n",
    "\n",
    "Napiši razred `Virus` z naslednjimi metodami:\n",
    "\n",
    "- konstruktor sprejme začetno mRNA virusa.\n",
    "- `izbij(fragment)` iz virusove mRNA odstrani vse pojavitve podanega fragmenta; metoda ne vrne ničesar,\n",
    "- `ostanek()` vrne trenutno virusovo mRNA, \n",
    "- `mrtev()` vrne `True`, če je virus mrtev (od njegove mRNA ni ostalo nič več) in `False`, če je živ.\n",
    "\n",
    "(Vsaka metoda seveda prejme še `self`.)\n",
    "\n",
    "### Rešitev"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Virus:\n",
    "    def __init__(self, mRNA):\n",
    "        self.mRNA = mRNA\n",
    "\n",
    "    def mrtev(self):\n",
    "        return self.mRNA == \"\"\n",
    "\n",
    "    def izbij(self, fragment):\n",
    "        self.mRNA = self.mRNA.replace(fragment, \"\")\n",
    "\n",
    "    def ostanek(self):\n",
    "        return self.mRNA"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tipična \"napaka\" je bila\n",
    "\n",
    "```python\n",
    "    def mrtev(self):\n",
    "        if self.mRNA == \"\":\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "```\n",
    "\n",
    "Kot je napisal Pesnik: \"*Vsi bodo dosegli svoj cilj, samo jaz ga ne bom dosegel*\". Nekateri bodo pač vedno pisali tako.\n",
    "\n",
    "V resnici ni napaka, samo nerazumevanje tega, kakšno vrednost ima `self.mRNA == \"\"`. Vredno ene odbite točke, ki se nikomur ni poznala, le jaz sem bil mirnejši.\n",
    "\n",
    "Drugo: nekateri se niso spomnili na `replace` in se mučili z odstranjevanjem podniza."
   ]
  }
 ],
 "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.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}