kz/domače naloge/2022/06 razbiranje ovir/resitev.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "f3430bff",
   "metadata": {},
   "source": [
    "Izvedši, da je njihov zemljevid s pikami in lojtrami neuporaben in živcira študente računalništva, kognitivne znanosti, upravne informatike in digitalnega jezikoslovja, so začali na Oddelku za gospodarstvo in motorizirani promet Mestne občine Ljubljana pripravljati podatke v drugačni obliki. Zato bo potrebno napisati nove funkcije za njihovo branje.\n",
    "\n",
    "Ovire so zapisane v večvrstičnem nizu:\n",
    "\n",
    "```\n",
    "4: 5-6\n",
    "13: 90-100, 5-8, 9-11\n",
    "5: 9-11, 19-20, 30-34\n",
    "4: 9-11\n",
    "13:  22-25, 17-19\n",
    "```\n",
    "\n",
    "To pomeni, da je v 4. vrstici ovira od 5 do 6. V 13. vrstici so ovire od 90 do 100, od 5 do 8 in od 9 do 11. V 5. so od ... In potem so se spomnili, da je v 4. vrstici še ena ovira. In v 13. še dve.\n",
    "\n",
    "Oblika vsake posamične vrstice je torej takšna: imamo številko vrstice, ki ji sledi dvopičje, temu pa pari koordinat `(x0, x1)`. Med koordinatama je `-`, med pari pa vejice. Kot vidimo zgoraj.\n",
    "\n",
    "## Kako iz/do večvrstičnih nizov\n",
    "\n",
    "Če je `s` večvrstični niz, ga razbijemo v seznam posamičnih vrstic tako, da pokličemo `s.splitlines()`.\n",
    "\n",
    "Če imamo niza `prva = \"Prva vrstica\"` in `druga = \"Druga vrstica\"`, ga zložimo v dvovrstični niz, tako da seštejemo `prva + \"\\n\" + druga`. Kombinacija `\\n` pomeni prehod v novo vrstico.\n",
    "\n",
    "## Obvezna naloga\n",
    "\n",
    "Napiši naslednje funkcije.\n",
    "\n",
    "- `vrstica(s)` prejme niz z eno vrstico in vrne seznam trojk `(x0, x1, y)`, ki predstavljajo ovire v tej vrstici.\n",
    "\n",
    "    Klic `vrstica(\"4: 1-3, 5-11, 15-33\")` vrne seznam `[(1, 3, 4), (5, 11, 4), (15, 33, 4)]`.\n",
    "\n",
    "- `preberi(s)` celoten, večvrstični niz z ovirami in vrne seznam ovir. Ovire naj bodo shranjene v takšnem vrstnem redu, v kakršnem se pojavljajo.\n",
    "\n",
    "    Če jo pokličemo z gornjim nizom, vrne\n",
    "\n",
    "    ```\n",
    "    [(5, 6, 4),\n",
    "     (90, 100, 13), (5, 8, 13), (9, 11, 13),\n",
    "     (9, 11, 5), (19, 20, 5), (30, 34, 5),\n",
    "     (9, 11, 4),\n",
    "     (22, 25, 13), (17, 19, 13)]\n",
    "    ```\n",
    "  \n",
    "- `intervali(xs)` prejme seznam parov `(x0, x1)` in vrne seznam nizov, ki opisujejo te intervale.\n",
    "\n",
    "    Klic `intervali([(6, 10), (12, 16), (20, 22), (98, 102)])` vrne\n",
    "    `[\"6-10\", \"12-16\", \"20-22\", \"98-102\"]`.\n",
    "\n",
    "- `zapisi_vrstico(y, xs)` prejme številko vrstice in seznam parov `(x0, x1)`. Vrniti mora opis ene vrstice.\n",
    "\n",
    "    Klic `zapisi_vrstico(5, [(6, 10), (12, 16)]))` vrne niz\n",
    "    `\"5: 6-10, 12-16\"`. Pazi: nobenih odvečnih ali manjkajočih presledkov ali vejic!\n",
    "    \n",
    "### Rešitev\n",
    "\n",
    "### `vrstica`\n",
    "\n",
    "Vrstico moramo najprej razdeliti glede na `\":\"`. Ker vemo, da bo samo eden, bomo rezultat funkcije takoj razpakirali na dva dela, niz s številko vrstice (`ys` - `s` kot \"string\") in niz s koordinatami x (`xs`). `ys` nato razbijemo glede na `\", \"` in čez dobljene kose poženemo zanko `for`; vsak kos, končno, razbijemo še po `-` da dobimo začetek in konec ovire. Trojke z začetkom in koncem ovire ter koordinato `y` vestno zlagamo v seznam."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "a7755d8c",
   "metadata": {},
   "outputs": [],
   "source": [
    "def vrstica(s):\n",
    "    ovire = []\n",
    "    ys, xs = s.split(\":\")\n",
    "    y = int(ys)\n",
    "    for x0x1 in xs.split(\", \"):\n",
    "        x0s, x1s = x0x1.split(\"-\")\n",
    "        ovire.append((int(x0s), int(x1s), y))\n",
    "    return ovire"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f703cf4b",
   "metadata": {},
   "source": [
    "Dve opazki. `ys` pretvorimo v `int` kar pred zanko, namesto da bi to počeli vsakič posebej. Program je zaradi tega za vrstico daljši, je pa za (pri tako malo podatkih neopazno) malenkost hitrejši.\n",
    "\n",
    "Druga: trojko s koordinatami sestavimo kar ob klicu funkcije `append`.\n",
    "\n",
    "### `preberi`\n",
    "\n",
    "Tu ni kaj: celoten niz razbijemo v vrstice s `splitlines`, čez dobljeni seznam poženemo zanko `for` in za vsako vrstico pokličemo `vrstica` ter njene rezultate zlagamo v seznam."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "5543485b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def preberi(s):\n",
    "    ovire = []\n",
    "    for v in s.splitlines():\n",
    "        ovire += vrstica(v)\n",
    "    return ovire"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "de4dd647",
   "metadata": {},
   "source": [
    "### `intervali`\n",
    "\n",
    "Pripravimo prazen seznam. Gremo čez ovire in za vsako v seznam dodamo niz. Sestavljanje niza je nekoliko okorno - `str(x0) + \"-\" + str(x1)`. Nekoč se bomo naučili, da gre tudi lažje."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "6c74631f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def intervali(xs):\n",
    "    intv = []\n",
    "    for x0, x1 in xs:\n",
    "        intv.append(str(x0) + \"-\" + str(x1))\n",
    "    return intv"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d226117b",
   "metadata": {},
   "source": [
    "### `zapisi_vrstico`\n",
    "\n",
    "Naloga preverja, ali znamo poklicati `join`. :) Potrebno je vzeti številko vrstice in dvopičje, k temu pa dodati z vejico združeni seznam, ki nam ga pripravi prejšnja funkcija."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "7944c03b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def zapisi_vrstico(y, xs):\n",
    "    return str(y) + \": \" + \", \".join(intervali(xs))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0009deb3",
   "metadata": {},
   "source": [
    "## Dodatna naloga\n",
    "\n",
    "Napiši funkcijo `zapisi(ovire)`, ki prejme seznam ovir in vrne niz, ki vsebuje opis ovir v novi obliki. \n",
    "\n",
    "Klic\n",
    "\n",
    "```python\n",
    "zapisi([(5, 6, 4), (9, 11, 4),\n",
    "        (9, 11, 5), (19, 20, 5), (30, 34, 5),\n",
    "        (5, 8, 13), (9, 11, 13), (17, 19, 13), (90, 100, 13)])\n",
    "```\n",
    "\n",
    "vrne niz\n",
    "\n",
    "```python\n",
    "4: 5-6, 9-11\n",
    "5: 9-11, 19-20, 30-34\n",
    "13: 5-8, 9-11, 17-19, 90-100\n",
    "```\n",
    "\n",
    "Spet: niz mora biti v točno takšni obliki, brez odvečnih ali manjkajočih presledkov ali vejic.\n",
    "\n",
    "### Rešitev\n",
    "\n",
    "Tole gre na kup načinov. Eden, ki ne uporablja prejšnjih funkcij, je tale:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "6a4ec896",
   "metadata": {},
   "outputs": [],
   "source": [
    "def zapisi(ovire):\n",
    "    yvrste = None\n",
    "    zemljevid = \"\"\n",
    "    for x0, x1, y in ovire:\n",
    "        if y != yvrste:\n",
    "            if yvrste != None:\n",
    "                zemljevid += vrsta + \"\\n\"\n",
    "            vrsta = str(y) + \": \" + str(x0) + \"-\" + str(x1)\n",
    "            yvrste = y\n",
    "        else:\n",
    "            vrsta += \", \" + str(x0) + \"-\" + str(x1)\n",
    "    zemljevid += vrsta\n",
    "    return zemljevid"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0d10f20c",
   "metadata": {},
   "source": [
    "Osnovni problem je, da ne vemo, koliko ovir je v posamezni vrstici. \n",
    "\n",
    "V `vrsta` bomo nabirali vsebino trenutne vrstice. V `yvrste` bo shranjena številka trenutne vrstice.\n",
    "\n",
    "Zato za vsako oviro pogledamo, ali je v isti vrstici kot te, ki jih trenutno sestavljamo. Če ni, se začenja nova vrstica: trenutno vrstico dodamo v `zemljevid` (razen, če je `yvrste` enak `None`, kar pomeni, da je to šele prva vrstica. Nato v spremenljivko `vrsta` zapišemo začetek te vrstice (koordinato y in trenutni par koordinat) in v `yvrste` shranimo številko trenutne vrstice.\n",
    "\n",
    "Če pa je ta ovira v vrstici, ki jo trenutno sestavljamo (`else`), pa le dodamo oviro v vrstico.\n",
    "\n",
    "Na koncu, po zanki, dodamo v zemljevid še zadnjo vrstico, saj ni bilo nobene ovire, ki bi jo \"zaključila\".\n",
    "\n",
    "Če hočemo, lahko pišemo tudi naravnost v `zemljevid`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "00ac59c7",
   "metadata": {},
   "outputs": [],
   "source": [
    "def zapisi(ovire):\n",
    "    prejy = None\n",
    "    zemljevid = \"\"\n",
    "    for x0, x1, y in ovire:\n",
    "        if y != prejy:\n",
    "            if prejy != None:\n",
    "                zemljevid += \"\\n\"\n",
    "            zemljevid += str(y) + \": \" + str(x0) + \"-\" + str(x1)\n",
    "            prejy = y\n",
    "        else:\n",
    "            zemljevid += \", \" + str(x0) + \"-\" + str(x1)\n",
    "    return zemljevid\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c150a510",
   "metadata": {},
   "source": [
    "Lepše pa je, seveda, če uporabimo funkcije, ki smo si jih pripravili zgoraj. Recimo tako, da je `vrsta` seznam ovir v neki vrsti. Ko je vrste konec, jih dodamo z `zapisi_vrstico`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "c0658496",
   "metadata": {},
   "outputs": [],
   "source": [
    "def zapisi(ovire):\n",
    "    prejy = None\n",
    "    zemljevid = \"\"\n",
    "    for x0, x1, y in ovire:\n",
    "        if y != prejy:\n",
    "            if prejy != None:\n",
    "                zemljevid += zapisi_vrstico(prejy, vrsta) + \"\\n\"\n",
    "            vrsta = []\n",
    "            prejy = y\n",
    "        vrsta.append((x0, x1))\n",
    "    zemljevid += zapisi_vrstico(prejy, vrsta) + \"\\n\"\n",
    "    return zemljevid"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5d45270b",
   "metadata": {},
   "source": [
    "Pa če ovire ne bi bile podane po vrsti? Ubogi študenti na FRI rešujejo problem, kjer so ovire v seznamu poljubno pomešane, izpisati pa jih morajo po vrsti...\n",
    "\n",
    "Takole: pripravimo seznam seznamov, ki ima za elemente toliko praznih seznamov, kolikor je vrstic. Vsak, očitno, pripada eni vrstici. Nato gremo čez seznam ovir in vsako oviro vržemo v pripadajoči seznam. Na koncu se zapeljemo čez te sezname in vsakega, ki ni prazen, izpišemo v zemljevid."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "5fbf2c2e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def zapisi(ovire):\n",
    "    # Poišči število vrstic\n",
    "    visina = 0\n",
    "    for _, _, y in ovire:\n",
    "        if y > visina:\n",
    "            visina = y\n",
    "\n",
    "    # Pripravi seznam seznamov; vrstice[i] bo seznam ovir v i-ti vrstici\n",
    "    # Na začetek pa damo še en prazen seznam, da se bodo indeksi začeli z 1.\n",
    "    vrstice = [[]]\n",
    "    for _ in range(visina):\n",
    "        vrstice.append([])\n",
    "\n",
    "    # Vsako oviro v pripadajoči seznam\n",
    "    for x0, x1, y in ovire:\n",
    "        vrstice[y].append((x0, x1))\n",
    "\n",
    "    # In zdaj le še izpišemo sezname v zemljevid\n",
    "    zemljevid = \"\"\n",
    "    for y, vrstica in enumerate(vrstice):\n",
    "        if vrstica:\n",
    "            zemljevid += zapisi_vrstico(y, vrstica) + \"\\n\"\n",
    "    return zemljevid"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "517ec15a",
   "metadata": {},
   "source": [
    "Ni tako grozno, ne?\n",
    "\n",
    "Še lepše gre s slovarji. Konkretno, z `defaultdict`-om. Te smo, ah, smola, spoznali šele na naslednjih predavanjih, po roku za oddajo naloge. Vseeno poglejmo rešitev."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "247a3f6a",
   "metadata": {},
   "outputs": [],
   "source": [
    "def zapisi(ovire):\n",
    "    vrstice = defaultdict(list)\n",
    "    for x0, x1, y in ovire:\n",
    "        vrstice[y].append((x0, x1))\n",
    "\n",
    "    zapis = \"\"\n",
    "    for y, vrstica in sorted(vrstice.items()):\n",
    "        zapis += zapisi_vrstico(y, sorted(vrstica)) + \"\\n\"\n",
    "    return zapis"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3d9ebca7",
   "metadata": {},
   "source": [
    "Vzeli smo `defaultdict(list)`: če uporabimo nek ključ, ki ga ni v slovarju, se ta sam od sebe pojavi, pripadajoča vrednost pa je prazen slovar.\n",
    "\n",
    "V prvem delu funkcije gremo čez ovire in dodajamo pare `(x0, x1)` v pripadajoče vrstice `y`.\n",
    "\n",
    "V drugem delu gremo čez slovar. Vzamemo vse pare (ključ, vrednost), ki jih dobimo z `items`. S `sorted` jih uredimo; ker gre za terke, jih bo `sorted` uredil po prvem elementu, če sta prva elementa enaka, pa po drugem. (Da bi bila prva elementa enaka, se tu ne more zgoditi. Razmisli, zakaj!). Za vsako vrstico dodamo v `zapis` zapis te vrstice, ki ga dobimo tako, da pokličemo funkcijo `zapisi_vrstico` z urejenim seznamom ovir v tej vrstici. Preverjanje, ali je vrstica morda brez ovir, zdaj ni več potrebno, saj takih vrstic v slovarju ne bo."
   ]
  }
 ],
 "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
}