p1/izpiti/2023/1_resitev.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "1355d3a2",
   "metadata": {},
   "source": [
    "Kot v prvih domačih nalogah bodo ovire predstavljene s trojkami `(x0, x1, y)`, pri čemer se ovira razprostira od stolpca x0 do vključno x1, šteti pa začnemo z 1. Zemljevid na sliki bi opisali z `[(4, 7, 1), (1, 3, 2), (10, 14, 2), (4, 7, 4), (10, 14, 4), (4, 7, 6), (1, 3, 7), (6, 7, 7), (11, 15, 7)]`.\n",
    "\n",
    "```\n",
    "           1\n",
    "  123456789012345\n",
    "1 ...<-->........\n",
    "2 <->......<--->.\n",
    "3 ...............\n",
    "4 ...<-->..<--->.\n",
    "5 ...............\n",
    "6 ...<-->........\n",
    "7 <->..<>...<--->\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "877188f1",
   "metadata": {},
   "source": [
    "# 1. Nabava\n",
    "\n",
    "Zemljevidi vsebujejo ovire različnih dolžin. Gornji zemljevid, recimo, ima 1 oviro dolžine 2, 2 oviri dolžine 3, 3 ovire dolžine 4 in 3 ovire dolžine 5. Nekega dne se MOL odloči spremeniti razpored ovir na neki kolesarski poti, zato bo morda potrebno nabaviti nekaj novih ovir določenih dolžin (kar bo sicer strošek, vendar MOL takrat, ko gre za varnost kolesarjev, ne varčuje!)\n",
    "\n",
    "Napiši funkcijo `nabava(stari, novi)`, ki prejme dva seznama ovir in vrne slovar, katerega ključi so dolžine ovir, ki jih bo potrebno dokupiti, ker med obstoječimi ovirami ni (dovolj) ovir takšne dolžine. Pripadajoče vrednosti bodo število potrebnih novih ovir. Če je potrebno dokupiti 3 ovire dolžine 5 in sedem ovir dolžine 1, funkcija vrne `{5: 3, 1: 7}`.\n",
    "\n",
    "## Rešitev\n",
    "\n",
    "To je naloga iz slovarjev. Če se spomnimo nanje, je lahko čisto preprosta.\n",
    "\n",
    "Ena rešitev je lahko takšna, da v slovar preštejemo vse, kar potrebujemo (seveda bomo uporabili `defaultdict`. Nato od njega odštevamo, kar imamo. Na koncu vrnemo slovar, ki vsebuje le elemente s pozitivno vrednostjo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "5bfcc3fd",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import defaultdict \n",
    "\n",
    "def nabava(staro, novo):\n",
    "    ovire = defaultdict(int)\n",
    "    for x0, x1, _ in novo:\n",
    "        ovire[x1 - x0 + 1] += 1\n",
    "    for x0, x1, _ in staro:\n",
    "        ovire[x1 - x0 + 1] -= 1\n",
    "    return {k: v for k, v in ovire.items() if v > 0}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ca00c396",
   "metadata": {},
   "source": [
    "Kozmetični detajl: čez slovar gremo z `for x0, x1, _ in ...`. Koordinate razpakiramo že v slovarju in nepotrebno številko vrstice damo v spremenljivko z imenom `_`.\n",
    "\n",
    "Sitnost je v zadnji vrstici. Morda bi koga zamikalo napisati\n",
    "\n",
    "```python\n",
    "    for dolzina, stevilo in ovire.items():\n",
    "        if stevilo <= 0:\n",
    "            del ovire[dolzina]\n",
    "    return ovire\n",
    "```\n",
    "\n",
    "Vendar bi ga čakalo razočaranje: če gremo z zanko čez slovar, znotraj te zanke ne moremo spreminjati (dolžine) tega slovarja. Tu moramo narediti nov slovar, kot smo ga zgoraj ali pa, po daljši poti z\n",
    "\n",
    "```python\n",
    "    kupiti = {}\n",
    "    for dolzina, stevilo in ovire.items():\n",
    "        if stevilo > 0:\n",
    "            kupiti[dolzina] = stevilo\n",
    "    return kupiti\n",
    "```\n",
    "\n",
    "Druga možnost je, da zanke ne poženemo pred slovarja temveč prek seznama, ki vsebuje vse, kar je v tem slovarju:\n",
    "\n",
    "```python\n",
    "    for dolzina, stevilo in list(ovire.items()):\n",
    "        if stevilo <= 0:\n",
    "            del ovire[dolzina]\n",
    "    return ovire\n",
    "```\n",
    "\n",
    "Vseeno - najboljše je prvo.\n",
    "\n",
    "Daljša rešitev je, da ločeno preštejemo, kaj potrebujemo in kaj imamo, potem pa sestavimo nov slovar, v katerega dajemo razliko med obema."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "c4b12ce5",
   "metadata": {},
   "outputs": [],
   "source": [
    "def nabava(staro, novo):\n",
    "    potrebe = defaultdict(int)\n",
    "    for x0, x1, _ in novo:\n",
    "        potrebe[x1 - x0 + 1] += 1\n",
    "    imamo = defaultdict(int)\n",
    "    for x0, x1, _ in staro:\n",
    "        imamo[x1 - x0 + 1] += 1\n",
    "    kupiti = {}\n",
    "    for dolzina, stevilo in potrebe.items():\n",
    "        if stevilo > imamo.get(dolzina, 0):\n",
    "            kupiti[dolzina] = stevilo - imamo.get(dolzina, 0)\n",
    "    return kupiti"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "00e66a8f",
   "metadata": {},
   "source": [
    "# 2. Rekonstrukcija\n",
    "\n",
    "Napiši funkcijo `rekonstrukcija(kocke)`, ki dobi seznam polj, ki jih pokrivajo ovire. Seznam je podan v obliki parov `(y, x)` (pazi: najprej y, potem x, saj to olajša nalogo!), ki pa niso nujno urejeni. Funkcija mora vrniti seznam dejanskih ovir v obliki običajnih trojk. Vrnjeni seznam mora biti urejen po vrsticah in znotraj vrstic po stolpcih.\n",
    "\n",
    "Klic `rekonstrukcija([(2, 3), (1, 1), (2, 2), (2, 4), (1, 2), (3, 4)])` vrne `[(1, 2, 1), (2, 4, 2), (4, 4, 3)]`.\n",
    "\n",
    "## Rešitev\n",
    "\n",
    "Vsak izpit ima (ali vsaj naj bi imel) nalogo, pri kateri je potrebno malo vozlati zanke in pogoje. Na tem izpitu je to ta."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "8e251815",
   "metadata": {},
   "outputs": [],
   "source": [
    "def rekonstrukcija(kocke):\n",
    "    ovire = []\n",
    "    prvi_x = zadnji_x = zadnji_y = None\n",
    "    for y, x in sorted(kocke):\n",
    "        if prvi_x is None:\n",
    "            prvi_x = x\n",
    "        elif y != zadnji_y or x != zadnji_x + 1:\n",
    "            ovire.append((prvi_x, zadnji_x, zadnji_y))\n",
    "            prvi_x = x\n",
    "        zadnji_x, zadnji_y = x, y\n",
    "    if prvi_x is not None:\n",
    "        ovire.append((prvi_x, zadnji_x, zadnji_y))\n",
    "    return ovire"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b1efd89b",
   "metadata": {},
   "source": [
    "`ovire` je očitno seznam, v katerega zložimo ovire in ga na koncu vrnemo.\n",
    "\n",
    "Seznam kock je potrebno urediti. Brez tega ... bo težka. Imeli bomo torej zanko `for y, x in sorted(kocke)`. V tej zanki moramo za vsako novo kocko vedeti, ali je del obstoječe ovire, ali pa je ovire, ki smo jo pregledovali v zadnjih korakih zanke, zdaj konec in jo je potrebno shraniti. Potrebujemo torej naslednje spremenljivke\n",
    "\n",
    "- `prvi_x` je začetek tekoče ovire. V začetku je `None` in vsakič, ko naletimo na novo oviro, ga postavimo na začetek le-te.\n",
    "- `zadnji_x` in `zadnji_y` sta `x` in `y` iz prejšnjega koraka zanke. Trenutna kocka nadaljuje prejšnjo oviro, če je trenutni `x` za `1` večji od zadnjega, trenutni `y` pa je enak zadnjemu.\n",
    "\n",
    "V zanki se dogaja to: če je `prvi_x` enak `None`, gre za prvi korak zanke. Ta kocka je začetek prve ovire.\n",
    "\n",
    "Sicer preverimo, ali se s trenutno kocko začenja nova ovira. Kdaj je to, smo opisali zgoraj. V tem primeru shranimo v seznam oviro, ki se je s prejšnjim korakom zanke končala in si zapomnimo trenutni `x` kot začetek nove ovire.\n",
    "\n",
    "Na koncu shranimo trenutna `x` in `y` kot `zadnji_x` in `zadnji_y`, da nam bosta dostopna v naslednjem koraku.\n",
    "\n",
    "Po zanki je še zoprna zafrkancija: ker se prejšnja ovira ni končala z novo kocko, jo je potrebno dodati posebej. Seveda, če obstaja - če je `prvi_x` še vedno `None`, na stezi ni nobenih ovir.\n",
    "\n",
    "Seveda obstaja še veliko drugih rešitev, ena je recimo ta:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "58d58676",
   "metadata": {},
   "outputs": [],
   "source": [
    "def rekonstrukcija(kocke):\n",
    "    if not kocke:\n",
    "        return []\n",
    "    ovire = []\n",
    "    prvi_x = None\n",
    "    kocke = sorted(kocke)\n",
    "    for (y, x), (nasl_y, nasl_x) in zip(kocke, kocke[1:] + [(0, 0)]):\n",
    "        if prvi_x is None:\n",
    "            prvi_x = x\n",
    "        if nasl_y != y or nasl_x != x + 1:\n",
    "            ovire.append((prvi_x, x, y))\n",
    "            prvi_x = nasl_x\n",
    "    return ovire"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fa25169d",
   "metadata": {},
   "source": [
    "Zanimiva - in kar kratka in razumljiva - je tale: vse kocke spremenimo v ovire. Potem gremo po seznamu teh \"ovir\" in ovire, ki se stikajo, združimo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "273b5852",
   "metadata": {},
   "outputs": [],
   "source": [
    "def rekonstrukcija(kocke):\n",
    "    ovire = [(x, x, y) for y, x in sorted(kocke)]\n",
    "    i = 1\n",
    "    while i < len(ovire):\n",
    "        if ovire[i - 1][2] == ovire[i][2] and ovire[i - 1][1] + 1 == ovire[i][0]:\n",
    "            ovire[i - 1] = (ovire[i - 1][0], ovire[i][1], ovire[i][2])\n",
    "            del ovire[i]\n",
    "        else:\n",
    "            i += 1\n",
    "    return ovire"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e4a0a86b",
   "metadata": {},
   "source": [
    "Pogoje preverja, ali se i-ta ovira stika s prejšnjo. Če se, ju združi in pobriše i-to. Sicer pa poveča `i`.\n",
    "\n",
    "Pa še ena: mislim, da bi jo imeli matematiki radi zaradi \n",
    "\n",
    "```python\n",
    "        vrstica = [x - i for i, x in enumerate(sorted(vrstica))]\n",
    "        dolzine = Counter(vrstica)\n",
    "```\n",
    "\n",
    "Nadebudnjši študenti lahko razmislijo, zakaj in kako to deluje."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "132e850f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def rekonstrukcija(kocke):\n",
    "    ovire = []\n",
    "    vrstice = defaultdict(list)\n",
    "    for y, x in kocke:\n",
    "        vrstice[y].append(x)\n",
    "    for y, vrstica in sorted(vrstice.items()):\n",
    "        vrstica = [x - i for i, x in enumerate(sorted(vrstica))]\n",
    "        dolzine = Counter(vrstica)\n",
    "        n = 0\n",
    "        for x, dolzina in sorted(dolzine.items()):\n",
    "            ovire.append((x + n, x + n + dolzina - 1, y))\n",
    "            n += dolzina\n",
    "    return ovire"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a19175a4",
   "metadata": {},
   "source": [
    "# 3. Spet nov format\n",
    "\n",
    "Napiši funkcijo `dekodiraj_vrstico(vrstica)`, ki dobi eno vrstico zemljevida v obliki, kot ga vidiš na vrhu izpita. Vrne seznam začetkov in koncev ovir: `dekodiraj_vrstico(\"..<-->...<---->..<>\")` vrne `[(3, 6), (10, 15), (18, 19)]`. Ovir dolžine 1 ni. Je Angelca rekla, da so čisto brez zveze.\n",
    "\n",
    "Napiši funkcijo `preberi(ime_datoteke)`, ki prejme ime datoteke, v kateri je shranjen zemljevid v takšni obliki. Vrne naj seznam ovir (urejen po vrsticah, znotraj po stolpcih). Za zemljevid z gornje slike mora vrniti seznam iz besedila ob njej.\n",
    "\n",
    "## Rešitev\n",
    "\n",
    "Tretja naloga preverja, kako smo kaj domači z nizi in datotekami. In ne bi smela biti pretežka.\n",
    "\n",
    "Najočitnejša rešitev prvega dela je"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "a7130710",
   "metadata": {},
   "outputs": [],
   "source": [
    "def dekodiraj_vrstico(vrstica):\n",
    "    ovire = []\n",
    "    for x, c in enumerate(vrstica, start=1):\n",
    "        if c == \"<\":\n",
    "            prvi = x\n",
    "        elif c == \">\":\n",
    "            ovire.append((prvi, x))\n",
    "    return ovire"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "67106555",
   "metadata": {},
   "source": [
    "Malo bolj zabavno je pobrati indekse vseh `<` in vseh `>` ter jih zipniti v en seznam."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "c7187f1a",
   "metadata": {},
   "outputs": [],
   "source": [
    "def dekodiraj_vrstico(vrstica):\n",
    "    return list(zip((i for i, c in enumerate(vrstica, start=1) if c == \"<\"),\n",
    "                    (i for i, c in enumerate(vrstica, start=1) if c == \">\")))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d9dbf50d",
   "metadata": {},
   "source": [
    "Da preberemo datoteko, zgolj pokličemo to funkcijo za vse vrstice ter v seznam ovir dodajamo trojke, ki vsebujeta začetek in konec ovire ter številko vrstice."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "5ae3ac5e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def preberi(ime_datoteke):\n",
    "    ovire = []\n",
    "    f = open(ime_datoteke)\n",
    "    for y, vrstica in enumerate(f, start=1):\n",
    "        ovire += ((x0, x1, y) for x0, x1 in dekodiraj_vrstico(vrstica))\n",
    "    return ovire"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "aeddd8fe",
   "metadata": {},
   "source": [
    "# 4. Sodobna umetnost\n",
    "\n",
    "V sklopu konference Velocity je potekala tudi umetniška razstava z inštalacijo iz ovir. Naložili so jih, kot kaže slika na desni: na zelo široki oviri `d` stojita oviri `a` in `b`. Na `a` stojita `c` in `r` ... in tako naprej. Takšno postavitev predstavimo s slovarjem `{\".\": \"dh\", \"d\": \"ab\", \"h\": \"tef\", \"a\": \"cr\", \"b\": \"uv\", \"t\": \"xy\", \"f\": \"qm\", \"c\": \"w\", \"r\": \"i\", \"u\": \"o\", \"v\": \"p\", \"x\": \"s\", \"q\": \"g\", \"m\": \"n\", \"w\": \"j\", \"o\": \"l\", \"s\": \"z\", \"g\": \"B\", \"n\": \"A\", \"l\": \"T\"}`. Ovira je vrh, če na njej ni nobene druge ovire. V primeru na sliki so vrhovi j, i, T, p, z, y, e, B, A.\n",
    "\n",
    "Napiši funkcijo `vrhovi(skladovnica, ovira, visina)`, ki prejme takšen slovar, neko oviro in neko višino. Vrniti mora množico imen vrhov, ki so nad to oviro in so za vsaj visina višji od nje. Funkcija naj bo seveda splošna in naj ne deluje le za ovire v tej umetnini. Seveda pa predpostavimo, da je ime ovire vedno podano z eno samo črko. Klic `vrhovi(skladovnica, \"a\", 3)` vrne `{\"j\"}`, in `vrhovi(skladovnica, \"a\", 2)` vrne `{\"j\", \"i\"}`.\n",
    "\n",
    "Namig: višina je lahko tudi negativna. V tem primeru funkcija vrne vse vrhove nad oviro. (To ti bo v pomoč!)\n",
    "\n",
    "## Rešitev\n",
    "\n",
    "To je seveda naloga iz naše ljube rekurzije."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "c957bce1",
   "metadata": {},
   "outputs": [],
   "source": [
    "def vrhovi(skladovnica, ovira, visina):\n",
    "    ovire = set()\n",
    "    if ovira not in skladovnica:\n",
    "        if visina <= 0:\n",
    "            ovire.add(ovira)\n",
    "    else:\n",
    "        for nadovira in skladovnica[ovira]:\n",
    "            ovire |= vrhovi(skladovnica, nadovira, visina - 1)\n",
    "    return ovire"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b3ba20da",
   "metadata": {},
   "source": [
    "Pripravimo si množico, ki jo bomo vrnili. Če ovire ni v slovarju, ki opisuje, kaj je na čem, jo dodamo, vendar le, če je dovolj visoko (`visina <= 0`). Sicer pa v množico ovir dodamo vse ovire, ki stojijo na tej oviri in so visoke vsaj `visina - 1`."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0e03c12d",
   "metadata": {},
   "source": [
    "# 5. Potapljanje ovir\n",
    "\n",
    "Napiši razred Ovire.\n",
    "\n",
    "- Konstruktor sprejme množico ovir, podanih s trojkami (x0, x1, y).\n",
    "- Metoda strel(x, y) prejme koordinate nekega polja. Če je tam ovira, vrne True, sicer False.\n",
    "- Metoda zadetkov() vrne število strelov, ki so zadeli kako oviro.\n",
    "- Metoda vse_ovire() vrne ovire, ki še obstajajo. Ovira, ki je trikrat zadeta (lahko trikrat v isto točko, lahko v različne), se razblini (v celoti, ne le tam, kjer je bila zadeta).\n",
    "- Metoda zmaga() vrne True, če ni ostala nobena ovira več. Sicer pa False.\n",
    "\n",
    "## Rešitev\n",
    "\n",
    "Pri objektnem programiranju je - vsaj pri osnovnih nalogah, ki jih rešujemo pri Programiranju 1 - \"najtežji\" korak, da se odločimo, kako bomo shranjevali podatke. Tule očitno potrebujemo število zadetkov in nekaj, kamor bomo shranili vse ovir, ki še obstajajo. Ker moramo za vsako oviro vedeti tudi, kolikokrat je bila zadeta, bomo ovire shranjevali v slovar - ovire bodo ključi, pripadajoče vrednosti pa število zadetkov."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "6782168f",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Ovire:\n",
    "    def __init__(self, ovire):\n",
    "        self.zadetkov_ = 0\n",
    "        self.ovire = dict.fromkeys(ovire, 0)\n",
    "\n",
    "    def strel(self, x, y):\n",
    "        for ovira in self.ovire:\n",
    "            if ovira[0] <= x <= ovira[1] and ovira[2] == y:\n",
    "                self.zadetkov_ += 1\n",
    "                self.ovire[ovira] += 1\n",
    "                if self.ovire[ovira] == 3:\n",
    "                    del self.ovire[ovira]\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "    def zadetkov(self):\n",
    "        return self.zadetkov_\n",
    "\n",
    "    def vse_ovire(self):\n",
    "        return set(self.ovire)\n",
    "\n",
    "    def zmaga(self):\n",
    "        return not self.ovire"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "67f66475",
   "metadata": {},
   "source": [
    "Slovar smo naredili z `dict.fromkeys(ovire, 0)`. Kaj naredi, je najbrž očitno. Če tega ne poznamo, pač  pišemo\n",
    "\n",
    "```\n",
    "    self.ovire = {}\n",
    "    for ovira in ovire:\n",
    "        self.ovire[ovira] = 0\n",
    "```\n",
    "\n",
    "Edina metoda, s katero imamo v resnici kaj dela, je `strel`. Ta gre čez slovar ovir in če ugotovi, da smo kaj zadeli, poveča število zadetkov v splošnem ter število zadetkov te ovire. Če je ovira s tem zadeta tretjič, jo odstranimo in vrnemo `True`.\n",
    "\n",
    "Tule bi lahko kdo rekel - kaj pa je s tistim, da znotraj zanke čez slovar ne smemo spreminjati tega slovarja? To še vedno velja, vendar smo tule zanko prekinili, torej ne bo nič narobe.\n",
    "\n",
    "Ostale metode zgolj vrnejo, kar morajo.\n",
    "\n",
    "Omenimo le še, da smo atribut s številom zadetkov poimenovali `zadetkov_`, da se njegovo ime ne tepe z imenom metode `zadetkov`."
   ]
  }
 ],
 "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
}