p1/izpiti/2020/02_resitev.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Vrhovi valov\n",
    "\n",
    "Naloga predstavlja nadaljevanje prve naloge s prejšnjega izpita (glej [rešitve](https://github.com/janezd/predavanja/blob/master/p1/izpiti/2020/01_resitev.ipynb)).\n",
    "\n",
    "Epidemije prihajajo v valovih. V neki državi se je število okuženih po dnevih spreminjalo tako:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "okuzbe = [1, 6, 5, 0, 0, 0, 2, 8, 5, 3, 0, 5, 8, 0, 0, 0, 5, 1, 1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tule vidimo štiri valove. Zanimajo nas vrhunci valov. V prvem valu je to drugi dan od treh (2, 3), v drugem prvi od štirih (1, 4), v tretjem drugi od dveh (2, 2), v četrtem prvi od treh (1, 3). Od obeh števil odštejemo 1 in ju delimo: tako izvemo, da so vrhovi ob `[1 / 2, 1 / 3, 1 / 1, 0 / 3]`. Tako odštevanje lepše opiše, kje se nahaja vrh: to se najlepše vidi v prvem valu, ko je vrh na polovici.\n",
    "\n",
    "Če je val dolg 1, je vrh na položaju 0.\n",
    "\n",
    "Na začetku in koncu seznama je lahko še poljubno število ničel. Med dvema valovoma je vsaj ena ničla.\n",
    "\n",
    "Napiši funkcijo `vrhovi(okuzbe)`, ki za podani seznam dnevnih okužb vrne položaje vrhov valov. Klic `vrhovi([1, 6, 5, 0, 0, 0, 2, 8, 5, 3, 0, 5, 8, 0, 0, 0, 5, 1, 1])` torej vrne `[0.5, 0.333, 1, 0]`.\n",
    "\n",
    "### Rešitev\n",
    "\n",
    "Tu so bili v rahli prednosti študenti, ki so si že prej ogledali rešitve prejšnjega izpita. Logika funkcije je namreč enake, tako da jo lahko kar hitro predelamo - a le, če jo razumemo. Če ne, pa ne. :)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0.5, 0.3333333333333333, 1.0, 0.0]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def vrhovi(s):\n",
    "    v_valovih = []\n",
    "    dan = -1\n",
    "    naj = 0\n",
    "    # Spredaj in zadaj dodamo 0, da se ni potrebno ukvarjati z začetkom in koncem\n",
    "    for x in [0] + s + [0]:\n",
    "        if x > 0:  # Val se nadaljuje\n",
    "            # Pogledamo, ali je število višje od najvišjega in v tem primeru\n",
    "            # zabeležimo število okuženih in dan\n",
    "            if x > naj:\n",
    "                naj = x\n",
    "                najdan = dan\n",
    "            dan += 1\n",
    "        else:  # Vala je konec\n",
    "            if naj > 0:  # Če ni bil prazen...\n",
    "                if dan > 1: \n",
    "                    v_valovih.append(najdan / (dan - 1))\n",
    "                else:  # Poseben primer, ko se je potrebno izogniti deljenju z 0\n",
    "                    v_valovih.append(0)\n",
    "            naj = 0\n",
    "            najdan = 0\n",
    "            dan = 0\n",
    "    return v_valovih\n",
    "\n",
    "vrhovi(okuzbe)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nekaterih - mogoče celo vsi, ki so se naloge lotili in jo uspešno rešili - so raje nabrali cel val v seznam ter nato poiskali indeks maksimalnega elementa ter ga delili z dolžino seznama. Seveda gre tudi tako.\n",
    "\n",
    "## Najpodobnejši\n",
    "\n",
    "Seve virusov primerjajo glede na markerje. Recimo, da bomo uporabljali naslednje markerje (vendar naj vaša rešitev deluje za poljuben nabor markerjev, ne le te, ki so v testih!)\n",
    "\n",
    "```python\n",
    "markerji = {\"ATTA\", \"GGT\", \"TTG\", \"TCCCTC\"}\n",
    "```\n",
    "\n",
    "V genskem materialu vzorca virusa je vsak od teh markerjev prisoten ali pa ne. (Ali je prisoten enkrat ali večkrat, ne igra vloge). Podobnost sevov opazujemo glede na to, v koliko markerjih se ujemata. \n",
    "\n",
    "Vzemimo, recimo\n",
    "\n",
    "```python\n",
    "        markerji =                         {\"ATTA\", \"GGT\", \"TTG\", \"TCCCTC\"}\n",
    "        vzorec = \"GCGCATTAGCGGTCCCTCAAAGGT\"  #  1     1      0       1\n",
    "        sev4 = \"ATTAATTAATTAATTA\"            #  1     0      0       0   => 2\n",
    "```\n",
    "\n",
    "Njuno ujemanje je 2: oba *vsebujeta* ATTA in oba *ne vsebujeta* TTG. (Glede preostalih dveh markerjev pa se razlikujeta.)\n",
    "\n",
    "Napiši funkcijo `najpodobnejsi(vzorec, sevi, markerji)`, ki prejme nek vzorec, množico znanih sevov in množico markerjev. Vrniti mora tistega izmed znanih sevov, ki je najbolj podoben vzorcu. Če je enako podobnih več, naj vrne poljubnega izmed njih.\n",
    "\n",
    "V testih je naštetih več sevov, v komentarjih pa so na enak način kot v gornjem primeru zapisane podobnosti.\n",
    "\n",
    "### Rešitev\n",
    "\n",
    "Tu je bilo zelo zanimivo - morda bi moral napisati tudi *nekoliko žalostno* opazovati izdelke študentov. Pravilna rešitev gre prek vseh sevov in poišče tistega, ki se po markerjih najbolj ujema z vzorcem, torej\n",
    "\n",
    "```python\n",
    "...\n",
    "for sev in sevi:\n",
    "    for marker in markerji:\n",
    "        ...\n",
    "```\n",
    "\n",
    "Namesto tega so mnogi, morda celo večina, pisali\n",
    "\n",
    "```python\n",
    "...\n",
    "for marker in markerji:\n",
    "    for sev in sevi:\n",
    "        ...\n",
    "```\n",
    "\n",
    "Tako se stvar zelo zaplete; tisti, ki so uspeli priti po tej poti do cilja, so se iz jame, ki so si jo skopali, izvlekli s slovarji. Če zanki razporedimo pravilno, pa je rešitev preprosta."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def najpodobnejsi(vzorec, sevi, markerji):\n",
    "    naj_podobnost = -1\n",
    "    naj_sev = 0\n",
    "    for sev in sevi:\n",
    "        podobnost = 0\n",
    "        for marker in markerji:\n",
    "            if (marker in vzorec) == (marker in sev):\n",
    "                podobnost += 1\n",
    "        if podobnost > naj_podobnost:\n",
    "            naj_podobnost = podobnost\n",
    "            naj_sev = sev\n",
    "    return naj_sev"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pogoj, ki preverja, ali oba vsebujeta ali ne vsebujeta markerja, je eleganten: to ali drži `marker in vzorec` mora biti enako temu, ali drži `marker in sev`. Oboje `True` ali oboje `False`. Brez tega bi pisali (in večina študentov tudi je pisala) `(marker in vzorec and marker in sev) or (marker not in vzorec and marker not in sev)`, ali pa je napisala celo dva `if`-a. Bolj žalostno, in tudi nedelujoče, pa je pisati `marker in sev and vzorec`. To deluje v angleščini, v Pythonu pa ne.\n",
    "\n",
    "```python\n",
    "        podobnost = 0\n",
    "        for marker in markerji:\n",
    "            if (marker in vzorec) == (marker in sev):\n",
    "                podobnost += 1\n",
    "```\n",
    "\n",
    "lahko nadomestimo z\n",
    "\n",
    "```python\n",
    "        podobnost = sum((marker in vzorec) == (marker in sev) for marker in markerji)\n",
    "```\n",
    "\n",
    "Odtod hitro pridemo do"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def najpodobnejsi(vzorec, sevi, markerji):\n",
    "    return max(sevi,\n",
    "               key=lambda sev: sum((marker in sev) == (marker in vzorec)\n",
    "                                   for marker in markerji))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Stanje regij\n",
    "\n",
    "V datoteki `obcine.txt` je seznam občin s številom prebivalcev in regijo, ki ji občina pripada. Podatki so ločeni z vejicami.\n",
    "\n",
    "```\n",
    "Moravče, 5354, Osrednjeslovenska\n",
    "Ljubljana, 288832, Osrednjeslovenska\n",
    "Koper, 51828, Primorska\n",
    "Kočevje ob gozdu, 16549, Južnoslovenska\n",
    "Piran, 17613, Primorska\n",
    "Kamnik, 13768, Osrednjeslovenska\n",
    "```\n",
    "\n",
    "V datoteki `okuzbe.txt` je dnevno število okužb po občinah, v takšni obliki:\n",
    "\n",
    "```\n",
    "Kamnik: 80\n",
    "Kočevje ob gozdu: 50\n",
    "Ljubljana: 90\n",
    "```\n",
    "\n",
    "Vse občine iz druge datoteke se pojavijo tudi v prvi. Obratno ni nujno: če nekje ni novih okužb, te občine v drugi datoteki ni.\n",
    "\n",
    "Napiši funkcijo `stanje_regij()`, ki prebere tidve datoteki in vrne slovar, katerega ključi so **vse regije, ki se pojavijo v prvi datoteki**, pripadajoča vrednost pa je delež okuženih. V gornjem primeru ključu `\"Osrednjeslovenska\"` pripada vrednost `(80 + 90) / (5354 + 288832 + 13768)` (število okuženih v občinah iz te regije, deljeno s število prebivalcev v vseh občinah te regije). Ključu `\"Primorska\"` pa `0`, ker v primorskih občinah ni bilo okužb.\n",
    "\n",
    "(Datoteke niso priložene, ker se sestavijo kar znotraj testov.)\n",
    "\n",
    "### Rešitev\n",
    "\n",
    "Naloga združuje dve veščini: branje datotek in uporabo slovarjev. Sicer pa je precej rutinska."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import defaultdict\n",
    "\n",
    "def stanje_regij():\n",
    "    regije = {}\n",
    "    populacija = defaultdict(int)\n",
    "    for vrstica in open(\"obcine.txt\"):\n",
    "        ime, prebivalcev, regija = vrstica.strip().split(\", \")\n",
    "        regije[ime] = regija\n",
    "        populacija[regija] += int(prebivalcev)\n",
    "\n",
    "    okuzenost = dict.fromkeys(populacija, 0)\n",
    "    for vrstica in open(\"okuzbe.txt\"):\n",
    "        obcina, okuzenih = vrstica.split(\":\")\n",
    "        okuzenost[regije[obcina]] += int(okuzenih)\n",
    "\n",
    "    for regija in okuzenost:\n",
    "        okuzenost[regija] /= populacija[regija]\n",
    "\n",
    "    return okuzenost"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Komentarja je vreden klic `dict.fromkeys(populacija, 0)`. Ta sestavi slovar, katerega ključi so iz seznama/terke/ključev slovarja/niza/...česarkoli `populacija`, vse vrednosti pa so 0. Če te funkcije ne poznamo, takšen slovar pač sestavimo z\n",
    "\n",
    "```python\n",
    "okuzenost = {}\n",
    "for regija in populacija:\n",
    "    okuzenost[regija] = 0\n",
    "```\n",
    "\n",
    "Tipična napaka, ki so jo nekateri delali pri reševanju, je, da so delili število okuženih v regiji s skupnim številom prebivalcev občin, ki so imele vsaj eno okužbo, namesto s populacijo regije. Tega nisem kaznoval preveč strogo, kaznovati pa sem vendarle moral. Če ne bi imeli testov, bi lahko rekli, da niste dovolj natančno brali navodil; glede na to, da so testi povedali, da je nekaj narobe, pa bi morali odkriti, v čem je problem.\n",
    "\n",
    "\n",
    "## Položaj vrha\n",
    "\n",
    "Variacija na prvo nalogo. Tokrat imamo le seznam za en val. Zanima nas, na kateri dan je bilo največ okužb in koliko.\n",
    "\n",
    "Napiši **rekurzivno** funkcijo `argmax(s)`, ki za podani **neprazni** seznam vrne indeks in vrednost največjega elementa. Klic `argmax([5, 4, 7, 8, 5, 1])` vrne `(3, 8)`, ker se največji element, 8, pojavi na indeksu 3. Če je največjih elementov več, vrne indeks prvega od njih.\n",
    "\n",
    "Funkcija mora biti \"prava rekurzivna funkcija\": razen sebe naj ne kliče drugih funkcij, razen `len`, poleg tega naj ne vsebuje zank.\n",
    "\n",
    "### Rešitev\n",
    "\n",
    "Če ima seznam le en element, se največji element nahaja na indeksu 0, in sicer je to kar ničti element.\n",
    "\n",
    "Sicer poizvemo, kje se nahaja in kakšen je največji element ostanka. Če je večji od prvega, vrnemo le-tega, a z 1 večjim indeksom (ker je potrebno upoštevati še prvi element). Če je prvi element večji, pa je največji, očitno, prvi element."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(3, 8)"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def argmax(s):\n",
    "    if len(s) == 1:\n",
    "        return 0, s[0]\n",
    "    naj_idx, naj = argmax(s[1:])\n",
    "    if naj > s[0]:\n",
    "        return naj_idx + 1, naj\n",
    "    else:\n",
    "        return 0, s[0]\n",
    "\n",
    "argmax([5, 4, 7, 8, 5, 1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Sledilnik\n",
    "\n",
    "Napiši razred `Sledilnik`, ki ima\n",
    "\n",
    "- primeren konstruktor\n",
    "- in metodo `nov_dan`, ki kot argument sprejme število novookuženih v tekočem dnevu; predstavljaj si, da jo pokličemo vsak dan, ko vlada sporoči sveže podatke.\n",
    "\n",
    "Poleg tega naj ima atribute\n",
    "\n",
    "- `naj_dnevnih` vsebuje največje doslej zabeleženo število dnevnih okužb,\n",
    "- `tekoce_brez_okuzb` pove, koliko zadnjih dni že ni bilo nobene okužbe,\n",
    "- `naj_brez_okuzb` pove, kako dolgo je bilo najdaljše zaporedje dni brez okužb.\n",
    "\n",
    "Razen teh naj razred nima nobenih drugih atributov.\n",
    "\n",
    "Poleg tega napiši razred `Sledilnik2`, ki je izpeljan iz razreda `Sledilnik` in doda še atribut\n",
    "\n",
    "- `skupno_okuzenih`, ki shranjuje skupno število okuženih.\n",
    "\n",
    "`Sledilnik2` naj smiselno uporabi oz. spreminja podedovane metode in doda čim manj kode.\n",
    "\n",
    "Recimo, da izvedemo naslednji program.\n",
    "\n",
    "```python\n",
    "s = Sledilnik2()\n",
    "s.nov_dan(10)\n",
    "s.nov_dan(15)\n",
    "s.nov_dan(0)\n",
    "s.nov_dan(0)\n",
    "s.nov_dan(0)\n",
    "s.nov_dan(0)\n",
    "s.nov_dan(2)\n",
    "s.nov_dan(0)\n",
    "s.nov_dan(0)\n",
    "```\n",
    "\n",
    "Po tem je `s.naj_dnevnih` enak `15`, `s.tekoce_brez_okuzb` je `2`, `s.naj_brez_okuzb` je `4`. Ker gre za `Sledilnik2`, je `s.skupno_okuzb` enak `27`.\n",
    "\n",
    "Če bi program nadaljevali z\n",
    "\n",
    "```\n",
    "s.nov_dan(3)\n",
    "```\n",
    "\n",
    "je `s.naj_dnevnih` še vedno `15`, `s.tekoce_brez_okuzb` je `0`, `s.naj_brez_okuzb` je še vedno `4` in `s.skupno_okuzb` enak `30`.\n",
    "\n",
    "### Rešitev"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Sledilnik:\n",
    "    def __init__(self):\n",
    "        self.naj_dnevnih = 0\n",
    "        self.naj_brez_okuzb = 0\n",
    "        self.tekoce_brez_okuzb = 0\n",
    "\n",
    "    def nov_dan(self, okuzenih):\n",
    "        if okuzenih > 0:\n",
    "            self.tekoce_brez_okuzb = 0\n",
    "            if okuzenih > self.naj_dnevnih:\n",
    "                self.naj_dnevnih = okuzenih\n",
    "        else:\n",
    "            self.tekoce_brez_okuzb += 1\n",
    "            if self.tekoce_brez_okuzb > self.naj_brez_okuzb:\n",
    "                self.naj_brez_okuzb = self.tekoce_brez_okuzb\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "V konstruktorju nastavimo tri atribute na ustrezne začetne vrednosti.\n",
    "\n",
    "V `nov_dan` nas zanima, ali kdo okužen. Če je tako, je tekoče število dni brez okužb enako 0, poleg tega pa preverimo, ali gre morda celo za dnevni rekord.\n",
    "\n",
    "Če okuženih ni, povečamo tekoče število dni brez okužb, potem pa preverimo, ali je to slučajno rekord števila dni brez okužb.\n",
    "\n",
    "Drugi del naloge je preverjal, ali znate iz tega razreda izpeljati preprost razred in pravilno klicati podedovane metode."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Sledilnik2(Sledilnik):\n",
    "    def __init__(self):\n",
    "        super().__init__()\n",
    "        self.skupno_okuzenih = 0\n",
    "\n",
    "    def nov_dan(self, okuzenih):\n",
    "        super().nov_dan(okuzenih)\n",
    "        self.skupno_okuzenih += okuzenih"
   ]
  }
 ],
 "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
}