p1/izpiti/2021/4_resitev.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "b2e9802b",
   "metadata": {},
   "source": [
    "## 1. Točni vlaki Slovenskih železnic (hipotetični, miselni eksperiment)\n",
    "\n",
    "Napiši funkcijo `tocni(redi, dejanski)`, ki prejma dva seznama seznamov. Vsak element se nanaša na en vlak; istoležni elementi se nanašajo na iste vlake. Prvi seznam vsebuje predvidene čase prihoda na postaje, drugi pa dejanske prihode. Časi so podani v minutah od polnoči. Funkcija naj vrne število vlakov, ki niso na nobeni postaji zamujali več kot dvajset minut (kar uporabniki Slovenskih železnic štejemo za praktično točen prihod). Klic\n",
    "\n",
    "```python\n",
    "tocni([[570, 590, 616, 620], [1200, 1500], [800, 900, 1000], [700, 800]],\n",
    "      [[570, 611, 622, 630], [1200, 1510], [810, 910, 1000], [800, 900]]))\n",
    "```\n",
    "\n",
    "vrne 2: \"točna\" sta bila drugi in tretji vlak. Prvi in četrti sta vsaj enkrat zamudila več kot 20 minut.\n",
    "\n",
    "**Namig:** če želiš, si lahko napišeš tudi pomožno funkcijo tocen(red, dejansko), ki prejme seznam za en sam vlak in vrne True, če je bil točen in False, če je kje zamudil za več kot 20 minut. (Če je ne napišeš, ignoriraj teste zanjo.)\n",
    "\n",
    "### Rešitev\n",
    "\n",
    "Ubogajmo, napišimo funkcijo `tocen`. Gremo čez vse pare predvidenih in dejanskih časov; če naletimo na zamudo, vrnemo `False`, sicer, na koncu, po zanki, vrnemo `True`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "f805e140",
   "metadata": {},
   "outputs": [],
   "source": [
    "def tocen(red, dejansko):\n",
    "    for cas_red, cas_dejansko in zip(red, dejansko):\n",
    "        if cas_dejansko - cas_red > 20:\n",
    "            return False\n",
    "    return True"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9b83c639",
   "metadata": {},
   "source": [
    "Naprej je preprosto: gremo čez vse vlake in za vsakega, ki je bil točen, prištejemo 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "d1458533",
   "metadata": {},
   "outputs": [],
   "source": [
    "def tocni(red, dejansko):\n",
    "    tocnih = 0\n",
    "    for r, d in zip(red, dejansko):\n",
    "        if tocen(r, d):\n",
    "            tocnih += 1\n",
    "    return tocnih"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d20f7202",
   "metadata": {},
   "source": [
    "Če znamo uporabljati izpeljane sezname (in če vemo, da je `False` isto kot `0` in `True` isto kot `1`), sta funkciji lahko tudi takšni:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "af754603",
   "metadata": {},
   "outputs": [],
   "source": [
    "def tocen(red, dejansko):\n",
    "    return all(d - r <= 20 for r, d in zip(red, dejansko))\n",
    "\n",
    "def tocni(redi, dejanski):\n",
    "    return sum(tocen(red, dejansko) for red, dejansko in zip(redi, dejanski))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1718755f",
   "metadata": {},
   "source": [
    "Brez dodatne funkcije je malo bolj zoprno. Ena od za silo elegantnih rešitev je `else` po `for`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "822d9a04",
   "metadata": {},
   "outputs": [],
   "source": [
    "def tocni(red, dejansko):\n",
    "    tocnih = 0\n",
    "    for red1, dejansko1 in zip(red, dejansko):\n",
    "        for predviden, prisel in zip(red1, dejansko1):\n",
    "            if prisel > predviden + 20:\n",
    "                break\n",
    "        else:\n",
    "            tocnih += 1\n",
    "    return tocnih"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6fddf66f",
   "metadata": {},
   "source": [
    "Obstajajo pa seveda tudi druge."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a1297830",
   "metadata": {},
   "source": [
    "Kdor je prelen za pisanje dodatne funkcije, zna pa uporabljati izpeljane sezname, pa zbaše vse skupaj v"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "90443a68",
   "metadata": {},
   "outputs": [],
   "source": [
    "def tocni(red, dejansko):\n",
    "    return sum(\n",
    "        all(prisel <= predviden + 20 for prisel, predviden in zip(pri, pre))\n",
    "        for pri, pre in zip(red, dejansko)\n",
    "    )"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "fa710e49",
   "metadata": {},
   "source": [
    "## 2. Enake linije\n",
    "\n",
    "Dve liniji sta \"enaki\", če vsebujeta iste postaje **ali** pa imata isto začetno in končno postajo ter ena od njiju vsebuje vse postaje, ki jih vsebuje druga; v tem primeru je druga hitrejša različica prve. Noben vlak ne ustavi večkrat na isti postaji.\n",
    "\n",
    "Napiši funkcijo `enaki(linija1, linija2)`, ki prejme seznama imen postaj in vrne `True`, če sta liniji enaki in `False`, če ne. Funkcija naj ignorira vrstni red (razen prve in zadnje postaje, ki morata biti enaki): liniji Ljubljana - Sevnica - Trebnje - Novo mesto in Ljubljana - Trebnje - Sevnica - Novo mesto sta enaki.\n",
    "\n",
    "- Liniji Ljubljana - Kresnice - Jevnica - Litija - Zagorje - Zidani most in Ljubljana - Jevnica - Zidani most sta enaki.\n",
    "- Liniji Ljubljana - Kresnice - Zidani Most in Ljubljana - Zagorje - Zidani most nista enaki, ker vsaka vsebuje kakšno postajo, ki je druga nima.\n",
    "- Liniji Kresnice - Zagorje in Ljubljana - Kresnice - Zagorje nimata enake začetne postaje.\n",
    "\n",
    "### Rešitev\n",
    "\n",
    "Študent naj bi razmislil, kaj pomeni, da ima ena linija vse postaje, ki jih ima druga: gre za podmnožice. Seznama torej pretvorimo v množice in preverimo ali je ena podmnožica druge oziroma obratno. Poleg tega pa preverimo še prvo in zadnjo postajo, torej:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "b9abc1fa",
   "metadata": {},
   "outputs": [],
   "source": [
    "def enaki(linija1, linija2):\n",
    "    return linija1[0] == linija2[0] \\\n",
    "        and linija1[-1] == linija2[-1] \\\n",
    "        and (set(linija1) <= set(linija2)\n",
    "             or set(linija2) <= set(linija1))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3ea58b29",
   "metadata": {},
   "source": [
    "Ne spreglejte oklepajev. Imamo tri stvari: prvi postaji sta enaki IN zadnji sta enaki IN (prva je podmnožica druge ali pa je druga podmnožica prve). Brez teh oklepajev rešitev ni pravilna, ker ima `and` prednost pred `or`."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "06109cd9",
   "metadata": {},
   "source": [
    "## 3. Čisto enake linije\n",
    "\n",
    "Napiši funkcijo `enaki_red(linija1, linija2)`, ki poleg tega zahteva, da se postaje pojavljajo v enakem vrstnem redu.\n",
    "\n",
    "- Liniji Ljubljana - Zalog - Laze - Kresnice - Jevnica - Litija - Zagorje in Ljubljana - Jevnica - Kresnice - Laze - Zagorje bi bili v prejšnji nalogi enaki, tu pa nista, ker imata različen vrstni red postaj (drugi se iz Jevnice vrača v Laze).\n",
    "\n",
    "**Namig 1**: nalogi sta dovolj različni, da ti ena funkcija najbrž ne bo praktično nič pomagala pri drugi.\n",
    "\n",
    "**Namig 2**: če liniji nista enako dolgi, je hitrejša tista, ki je krajša. Na začetku funkcije se ti morda splača napisati \n",
    "\n",
    "```python\n",
    "if len(linija1) < len(linija2):\n",
    "    linija1, linija2 = linija2, linija1\n",
    "```\n",
    "\n",
    "### Rešitev\n",
    "\n",
    "Tole je pa \"ta težja\" naloga izpita. Najprej preverimo prvo in zadnjo postajo. Potem poskrbimo, da je `linija1` tista, ki gre čez več postaj (kot pravi namig).\n",
    "\n",
    "Zdaj si predstavljajte, da greste s prstoma čez seznam postaj. Z enim čez počasni vlak in ga primerjate s prstom, ki kaže na hitri vlak. Kadar počasni vlak pride na postajo, na kateri ustavlja tudi hitri, premaknete prst na hitrem vlaku za eno postajo naprej. Ko je \"počasni\" prst na koncu, mora biti na koncu tudi hitri vlak.\n",
    "\n",
    "Z zanko gremo čez počasnejši vlak, kje je prst na drugem, pa bo shranjeno v indeksu (`i2`, v spodnjem programu). Indeks se poveča, ko se imeni postaj ujemata."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "405730b6",
   "metadata": {},
   "outputs": [],
   "source": [
    "def enaki_red(linija1, linija2):\n",
    "    if linija1[0] != linija2[0] or linija1[-1] != linija2[-1]:\n",
    "        return False\n",
    "    i2 = 0\n",
    "    if len(linija1) < len(linija2):\n",
    "        linija1, linija2 = linija2, linija1\n",
    "    for postaja1 in linija1:\n",
    "        if i2 < len(linija2) and linija2[i2] == postaja1:\n",
    "            i2 += 1\n",
    "    return i2 == len(linija2)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "4c594aa1",
   "metadata": {},
   "source": [
    "## 4. Kopičenje zamud\n",
    "\n",
    "Napiši funkcijo `zamujenih(vlak, cakajoci)`, ki prejme niz s kodo vlaka, ki zamuja in slovar, katerega ključi so kode vlakov, vrednosti pa množice vseh vlakov, ki morajo čakati, kadar ta vlak zamuja. Funkcija naj vrne število vseh zamujenih vlakov. Pri tem upoštevaj, da bodo zamujali tudi vlaki, ki čakajo zamujene vlake, ki čakajo zamujene vlake ...\n",
    "\n",
    "V primeru iz testov je tako: če zamuja LP3682, bosta zaradi tega zamujala tudi LP8524 in IC021. Ker zamuja LP8524 bodo morali čakati tudi EN123, IC521 in LP6316, zaradi IC021 pa LP222 in IC204. Zaradi EN123 ne čaka nihče, zaradi IC521 pa ... in tako naprej. Skupno zaradi LP3682 zamudi 14 vlakov.\n",
    "\n",
    "Vlaki se nikoli ne čakajo v krogu: če A čaka B in B čaka C, potem ne B ne C ne čakata na A.\n",
    "\n",
    "### Rešitev\n",
    "\n",
    "Vrniti morate velikost \"rodbine vlakov\" - kar je prva naloga iz rekurzije, ki smo jo delali na predavanjih..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "b7e6a800",
   "metadata": {},
   "outputs": [],
   "source": [
    "def zamujenih(vlak, cakajoci):\n",
    "    zamud = 1\n",
    "    for vlak1 in cakajoci[vlak]:\n",
    "        zamud += zamujenih(vlak1, cakajoci)\n",
    "    return zamud"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "157365fe",
   "metadata": {},
   "source": [
    "Malo hitreje pa je tako:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "25cf6365",
   "metadata": {},
   "outputs": [],
   "source": [
    "def zamujenih(vlak, cakajoci):\n",
    "    return 1 + sum(zamujenih(vlak1, cakajoci) for vlak1 in cakajoci[vlak])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8512995e",
   "metadata": {},
   "source": [
    "Kdor ve kaj več, je opazil, da ni tako preprosto: lahko bi se zgodil, da bi na A čakala B in C, potem pa bi na oba, torej na B in na C, čakal nek vlak D. Tale program bi D štel dvakrat. To bi lahko rešili tako, da bi namesto preštevanja našteli vsa imena v rodbini in pogledali, koliko jih je."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "41e51729",
   "metadata": {},
   "source": [
    "## 5. Robotski sprevodnik\n",
    "\n",
    "Ker se potniki jezijo na sprevodnike namesto na šefe SŽ, bodo uvedli robotske sprevodnike. Napiši razred `Sprevodnik`:\n",
    "\n",
    "- konstruktor prejme začetno postajo in cenik v obliki slovarja, katerega ključi so pari imen postaj, vrednosti pa cena prevoza med tem parom;\n",
    "- `postaja(ime)` se bo poklicala, ko vlak pride na postajo s podanim imenom;\n",
    "- `potnik(kam)` proda vstopivšemu potniku vozovnico od trenutnega kraja do kraja s podanim imenom;\n",
    "- `blagajna()` vrne trenutni izkupiček od prodanih vozovnic;\n",
    "- `potnikov()` vrne trenutno število potnikov na vlaku.\n",
    "\n",
    "**Namig:** Sprevodnik mora poznati trenutno postajo in število potnikov, ki izstopijo na posamezni od prihodnjih postaj.\n",
    "\n",
    "### Rešitev\n",
    "\n",
    "Kot je pri nalogah iz objektnega programiranja običajno, moramo le razmisliti, kaj si bo moral zapomniti sprevodnik in kako to shraniti. Potem metode le spreminjajo te podake.\n",
    "\n",
    "Zapomniti si bo moral\n",
    "- cenik (to bo `self.cenik`),\n",
    "- koliko ima v blagajni (to bi lahko bilo `self.blagajna`, vendar se atribut ne more imenovati kot metoda, torej recimo temu `self.zasluzak`),\n",
    "- trenutno postajo, kot prijazno pove namig (`self.trenutna_postaja`) in\n",
    "- število potnikov, ki bodo izstopili na posamezni postaji (`self.potniki`). To bomo shranjevali v slovarju, katerega ključi bodo potniki, vrednosti pa število potnikov, ki tam izstopijo.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "d88668d3",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Sprevodnik:\n",
    "    def __init__(self, zacetna, cenik):\n",
    "        self.cenik = cenik\n",
    "        self.trenutna_postaja = zacetna\n",
    "        self.zasluzek = 0\n",
    "        self.potniki = defaultdict(int)\n",
    "\n",
    "    def postaja(self, postaja):\n",
    "        self.trenutna_postaja = postaja\n",
    "        if self.trenutna_postaja in self.potniki:\n",
    "            del self.potniki[self.trenutna_postaja]\n",
    "\n",
    "    def potnik(self, kam):\n",
    "        self.zasluzek += self.cenik[self.trenutna_postaja, kam]\n",
    "        self.potniki[kam] += 1\n",
    "\n",
    "    def blagajna(self):\n",
    "        return self.zasluzek\n",
    "\n",
    "    def potnikov(self):\n",
    "        return sum(self.potniki.values())"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d705ef17",
   "metadata": {},
   "source": [
    "Kaj dela konstruktor, je očitno.\n",
    "\n",
    "- `postaja`: ko pridemo na postajo, si zapomnimo, da je to trenutna postaja. Če na taj postaji kdo izstopi, preprosto pobrišemo ta ključ iz slovarja.\n",
    "- `potnik`: ko potnik vstopi in pove, kam gre, povečamo zaslužek in povečamo število potnikov, ki izstopijo na njegovi ciljni postaji.\n",
    "- `blagajna` vrne zaslužek, ki smo si ga shranili v `self.zasluzek`.\n",
    "- `potnikov` vrne število potnikov, ki bodo izstopili na kateri od prihodnjih postaj. Natančno toliko jih je namreč na vlaku."
   ]
  }
 ],
 "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
}