p1/domace-naloge/2022/08 ovire v vrstici/resitev.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "50d95ee6",
   "metadata": {},
   "source": [
    "Tokratna naloga bo zelo kratka. V vsaki funkciji bo potrebno napisati samo eno vrstico. Točneje, tokratna naloga bo krajša, ko bi si želeli: v vsaki funkciji boste *smeli* napisati samo eno vrstico.\n",
    "\n",
    "Spet se vračamo k isti nalogi, ki smo jo reševali že dvakrat: prvič smo jo imenovali Šikaniranje, drugič pa [Funkcijske ovire](https://ucilnica.fri.uni-lj.si/mod/url/view.php?id=50701).\n",
    "\n",
    "Tokrat jih bomo reševali s pomočjo izpeljanih seznamov. Če vam kaj pomaga (najbrž vam vsaj malo) imate poleg testov že napisane funkcije, ki rešijo naloge ... le predolge so. :)\n",
    "\n",
    "## Obvezna naloga\n",
    "\n",
    "Napišite funkcije\n",
    "\n",
    "- `stevilo_ovir(ovire)`,\n",
    "- `dolzina_ovir(ovire)`,\n",
    "- `sirina(ovire)`,\n",
    "- `dodaj_vrstico(bloki, y)`\n",
    "- `globina(ovire, x)`\n",
    "- `senca(ovire)`\n",
    "\n",
    "tako, da bodo vsebovale samo stavek `return` in ... kar je pač potrebno, da izračunate, kar morajo izračunati.\n",
    "\n",
    "### Rešitev\n",
    "\n",
    "Število ovir je že napisano v vrstici. Daljše skoraj ne gre. :)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "f38fa016",
   "metadata": {},
   "outputs": [],
   "source": [
    "def stevilo_ovir(ovire):\n",
    "    return len(ovire)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0acc0371",
   "metadata": {},
   "source": [
    "**`dolzina_ovir(ovire)`** mora vrniti vsoto dolžin vseh ovir. Dolžina ovire `(x0, x1, y)` je `x1 - x0 + 1`, vsota tega je `sum(x1 - x0 + 1 ... za vsako oviro`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "59f57423",
   "metadata": {},
   "outputs": [],
   "source": [
    "def dolzina_ovir(ovire):\n",
    "    return sum(x1 - x0 + 1 for x0, x1, _ in ovire)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c60c807f",
   "metadata": {},
   "source": [
    "Ker `y` ne potrebujemo, tretjo vrednost iz trojke poimenujemo kar `_`.\n",
    "\n",
    "**`sirina(ovire)`** je enaka največjemu (po angleško: maksimalnemu) `x1`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "c7770a46",
   "metadata": {},
   "outputs": [],
   "source": [
    "def sirina(ovire):\n",
    "    return max(x1 for _, x1, _ in ovire)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e76e3f26",
   "metadata": {},
   "source": [
    "**`dodaj_vrstico(ovire, y)`** gre čez seznam parov in jih zlaga v seznam trojk, ki poleg `x1` in `x0` vsebujeta še `y`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "42088185",
   "metadata": {},
   "outputs": [],
   "source": [
    "def dodaj_vrstico(bloki, y):\n",
    "    return [(x0, x1, y) for x0, x1 in bloki]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ca981833",
   "metadata": {},
   "source": [
    "Če hočemo poudariti, da je `y` dodan k tistemu, kar smo imeli prej, pa"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "be657309",
   "metadata": {},
   "outputs": [],
   "source": [
    "def dodaj_vrstico(bloki, y):\n",
    "    return [blok + (y, ) for blok in bloki]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ac83dbca",
   "metadata": {},
   "source": [
    "Ne spreglejte: ne `blok + (y)`, temveč `blok + (y, )`. `(y)` bi bila samo številka, ne terka."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "88f2b499",
   "metadata": {},
   "source": [
    "**`globina(ovire, x)`** mora vrniti najmanjši `y` med vsemi `x0, x1, y`, za katere velja, da je `x` med `x0` in `x1`, torej `x0 <= x <= x1`.\n",
    "\n",
    "To bi lahko bilo tole:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "a200f8b5",
   "metadata": {},
   "outputs": [],
   "source": [
    "def globina(ovire, x):\n",
    "    return min(y for x0, x1, y in ovire if x0 <= x <= x1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e1a8b388",
   "metadata": {},
   "source": [
    "vendar ne deluje v primeru, da v stolpcu ni nobene ovire. Tedaj `(y for x0, x1, y in ovire if x0 <= x <= x1)` ne zgenerira ničesar in `max` ne ve, kaj vrniti. Pogledši [dokumentacijo funkcije `min`](https://docs.python.org/3/library/functions.html#min) izvemo, da ji lahko podamo še argument `default`, s katero predpišemo vrednost, ki naj jo vrne v takšnem primeru. V naši nalogi želimo, da tedaj vrne `None`, torej"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "be8442aa",
   "metadata": {},
   "outputs": [],
   "source": [
    "def globina(ovire, x):\n",
    "    return min((y for x0, x1, y in ovire if x0 <= x <= x1), default=None)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3abc7901",
   "metadata": {},
   "source": [
    "**`senca(ovire)`** mora sestaviti seznam s toliko elementi, kolikor je stolpcev in vsak vsebuje `True`, če `globina` za ta stolpec vrne `None` in `False`, če ne."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "0a8f47f2",
   "metadata": {},
   "outputs": [],
   "source": [
    "def senca(ovire):\n",
    "    return [globina(ovire, x) is None for x in range(1, sirina(ovire) + 1)]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fd5e815f",
   "metadata": {},
   "source": [
    "## Dodatna naloga\n",
    "\n",
    "Napišite funkcijo `indeksi(s, subs)`, ki prejme niza `s` in `subs` ter vrne seznam indeksov znotraj `s`, na katerih se pojavi `subs`. Klic `indeksi(\"pepelka peče prepelice\", \"pe\")` vrne `[0, 2, 8, 16]`, saj se `pe` pojavi na indeksih 0, 2, 8 in 16. Tudi ta funkcija sme seveda obsegati samo `return`.\n",
    "\n",
    "Potem napišite v eni vrstici funkcijo\n",
    "\n",
    "- `pretvori_vrstico(vrstica)`."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7a41696c",
   "metadata": {},
   "source": [
    "### Rešitev\n",
    "\n",
    "Funkcijo `indeksi` so nekateri študenti zelo zapletli, ker so si poskušali pomagati z zanko, v kateri bi klicali `index`. To je zelo težko. Veliko preprosteje je pomisliti drugače: kaj hoče funkcija? Kaj moramo vrniti? Vse tiste indekse, za katere velja, da se na njih začenja podniz `subs`. Kako torej preverimo, ali se na `i`-tem mestu `s`-ja začenja `subs`? `s[i:i + len(subs)] == subs`. Lahko pa uporabimo tudi metodo `startswith`, ki pove, ali se niz začne s podanim nizom: `s[i:].startswith(subs)`.\n",
    "\n",
    "Funkcija `indeksi` je torej:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "0b944fc5",
   "metadata": {},
   "outputs": [],
   "source": [
    "def indeksi(s, subs):\n",
    "    return [i for i in range(len(s)) if s[i:].startswith(subs)]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d051b262",
   "metadata": {},
   "source": [
    "Zdaj pa pretvorimo vrstico. Zanima nas, kje so začetki ovir. Ovire za začnejo tam, kjer najdemo `.#`. Da bomo našli tudi ovire, ki bi bile čisto na začetku, na začetek prištejemo piko. Ovire se torej začenjajo na `indeksi(\".\" + s, \".#\")`. Vendar bodo ti indeksi žal za 1 premajhni: če imamo `s = \"#\"`, se ovira začne na `1` (ker v teh nalogah pač štejemo od 1). Klic `indeksi(\".\" + s, \".#\")`, ali, konkretneje, `indeksi(\".#\", \".#\")` bo vrnil `[0]`. Nič hudega: indeksom bi sicer lahko prištevali 1 kdaj kasneje, a preprosteje, če nizu `s` namesto ene same pike prištejemo dve, pa se bodo vsi indeksi povečali za `1`. Stolpci, v katerih se začenjajo ovire, so torej `indeksi(\"..\" + s, \".#\")`.\n",
    "\n",
    "Pa konci? Zdaj iščemo `\"#.\"`. Da pravilno zaznamo tudi oviro, ki bi bila čisto na koncu niza, nizu prištejemo še `\".\"`. Da povečamo indekse za `1`, dodamo piko na začetku (namesto pike bi lahko na začetek dodali tudi karkoli drugega). Konci ovir so torej na `indeksi(\".\" + s  + \".\", subs)`.\n",
    "\n",
    "Funkcija mora vrniti pare začetkov in koncev."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "936fee14",
   "metadata": {},
   "outputs": [],
   "source": [
    "def pretvori_vrstico(vrstica):\n",
    "    return list(zip(indeksi(\"..\" + vrstica, \".#\"), indeksi(\".\" + vrstica + \".\", \"#.\")))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "20aa0085",
   "metadata": {},
   "source": [
    "## Čisto dodatna naloga (ki ne šteje nikamor)\n",
    "\n",
    "Še preostali dve:\n",
    "\n",
    "- `pretvori_zemljevid(zemljevid)` (tule boste verjetno potrebovali `reduce` in `add`),\n",
    "- `naj_stolpec(ovire)`.\n",
    "\n",
    "### Rešitev\n",
    "\n",
    "Ni tako težko.\n",
    "\n",
    "Generator `(dodaj_vrstico(pretvori_vrstico(vrstica), y) for y, vrstica in enumerate(zemljevid, start=1))` gre čez vrstice; za vsako poišče začetke in konce vrstic ter v pare doda številke vrstic, `y`. Problem je, da tako dobimo sezname seznamov ovir v vrsticah. Vse \"podsezname\" je potrebno sešteti v en sam seznam. To lahko storimo s funkcijo `sum`, če ji podamo začetni element. Funkcija `sum` privzeto začne prištevati k `0`, mi želimo, da prišteva k praznemu seznamu."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "4365f606",
   "metadata": {},
   "outputs": [],
   "source": [
    "def pretvori_zemljevid(zemljevid):\n",
    "    return sum((dodaj_vrstico(pretvori_vrstico(vrstica), y)\n",
    "                for y, vrstica in enumerate(zemljevid, start=1)), start=[])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "380bc1a2",
   "metadata": {},
   "source": [
    "Funkcija `naj_stolpec` je pa bolj zoprna. Iščemo nekakšen `max(((x, globina(ovire, x)) for x in range(1, sirina(ovire) + 1)`, pri čemer pa moramo pare primerjati po drugem elementu.\n",
    "\n",
    "Ena možnost je, da uporabimo `key`, ki mu podamo lambda-funkcijo. Ta prejema elemente, katerih maksimum iščemo in za vsakega vrne ključ, glede na katerega ga primerjamo. V našem primeru imamo pare, ki jih primerjamo po drugem elementu, torej"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "cb29d4de",
   "metadata": {},
   "outputs": [],
   "source": [
    "def naj_stolpec(ovire):\n",
    "    return max(((x, globina(ovire, x)) for x in range(1, sirina(ovire) + 1)),\n",
    "               key=lambda x: x[1])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a2dcceea",
   "metadata": {},
   "source": [
    "Če lambd ne poznamo (vsaj letos smo se o njih učili le na dodatnih predavanjih), se znajdemo tako, da zamenjamo vrstni red elementov v paru: namesto `(x, globina(ovire, x))` sestavljamo pare `(globina(ovire, x), x)`. Funkcija `max` jih bo primerjala po prvem elementu in tako izbrala pravi največji element -- a funkcija mora vrniti par, v katerem je na prvem mestu `x`, ne globina. Nič hudega, ga pač obrnemo pred vračanjem, tako da na konec dodamo `[::-1]`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "490037e2",
   "metadata": {},
   "outputs": [],
   "source": [
    "def naj_stolpec(ovire):\n",
    "    return max((globina(ovire, x), x)\n",
    "               for x in range(sirina(ovire) + 1) if globina(ovire, x) is not None)[::-1]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f4a7dfb7",
   "metadata": {},
   "source": [
    "Žal nas zafrknejo stolpci brez ovir. Tam `globina` vrne `None`. Funkcija mora v tem primeru vrniti ta stolpec ... a namesto tega vrne napako, da poskušamo primerjati `None` in število.\n",
    "\n",
    "Če delamo z lambdami, to rešimo tako, da funkcija, ki računa ključ, v primeru, da je drugi element enak `None` vrne 1000. Recimo, da tako daleč ne bo nobene ovire. Če nas to moti, pa lahko vrača tudi neskončno, `float(\"inf\")`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "a89aa4e9",
   "metadata": {},
   "outputs": [],
   "source": [
    "def naj_stolpec(ovire):\n",
    "    return max(((x, globina(ovire, x)) for x in range(1, sirina(ovire) + 1)),\n",
    "               key=lambda x: float(\"inf\") if x[1] is None else x[1])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cf745563",
   "metadata": {},
   "source": [
    "Rešitev brez lambde pa je zabavna. Takole storimo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "9bb6141b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def naj_stolpec(ovire):\n",
    "    return ([(x, None)\n",
    "             for x in range(1, sirina(ovire) + 1) if globina(ovire, x) is None]\n",
    "            + [max((globina(ovire, x), x)\n",
    "                   for x in range(sirina(ovire) + 1) if globina(ovire, x) is not None)[::-1]]\n",
    "           )[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "83219ef3",
   "metadata": {},
   "source": [
    "Seštevamo dva seznama. Prvi seznam vsebuje pare `(x, None)` za vse tiste `x`, kjer ni ovir. Drugi seznam pa vsebuje samo en element, namreč maksimalni element, ki ga dobimo natančno tako, kot smo opisali zgoraj, vendar upoštevamo le tiste `x`, pri katerih ovire obstajajo.\n",
    "\n",
    "Oba seznama torej seštejemo in nato vrnemo prvi element seznama, ki ga dobimo kot vsoto. Če obstaja kak stolpec brez ovir, bodo te v prvem seznamu in vrnili bomo prvo med njimi. Če stolpcev brez ovir ni, pa bo prvi seznam prazen in vrnili bomo prvi (in edini) element drugega. :)"
   ]
  }
 ],
 "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.9.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}