p1/domace-naloge/2022/05 funkcionalne ovire/resitev.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "9fec574b",
   "metadata": {},
   "source": [
    "Naloga se nanaša na nalogi prejšnjih dveh tednov (Šikaniranje, Lokacije ovir): večinoma je potrebno le preoblikovati to, kar ste programirali takrat, v funkcije. Pri reševanju smete uporabiti tudi objavljene rešitve prejšnjih dveh nalog.\n",
    "\n",
    "Napisati je potrebno naslednje funkcije:\n",
    "\n",
    "- `stevilo_ovir(ovire)` prejme ovire v obliki seznama trojk `(x0, x1, y)` in vrne število ovir.\n",
    "- `dolzina_ovir(ovire)` vrne skupno dolžino vseh ovir\n",
    "- `sirina(ovire)` vrne širino kolesarke steze, se pravi najbolj desno koordinato v seznamu ovir\n",
    "- `pretvori_vrstico(vrstica)` prejme vrstico v obliki niza, sestavljenega iz znakov `#` in `.` ter vrne seznam parov (x0, x1) (ogrevalni del domače naloge prejšnjega tedna)\n",
    "- `dodaj_vrstico(bloki, y)` prejme seznam, kakršnega vrača prejšnja funkcija in neko število `y`. Vrniti mora seznam, v katerem je vsakemu paru dodan `y`. Klic `dodaj_vrstico([(3, 4), (6, 8), (11, 11)], 3)` vrne `[(3, 4, 3), (6, 8, 3), (11, 11, 3)]`.\n",
    "- `pretvori_zemljevid(zemljevid)` dobi zemljevid v obliki seznama nizov in vrne seznam ovir (obvezna domača naloga prejšnjega tedna). Funkcija mora uporabiti prejšnji dve funkciji - testi bodo to preverili tako, da bodo začasno zamenjali tvojo funkcijo z neko drugo, ki vrača napačne številke in preverili, ali so številke res \"pravilno napačne\".\n",
    "- `globina(ovire, x)` prejme seznam ovir (v obliki trojk) in vrne vrstico, v kateri bi kolesar, ki se vozi po stolpcu `x`, naletel na oviro (naloga izpred dveh tednov).\n",
    "- `naj_stolpec(ovire)` vrne stolpec, v katerem kolesar pride najdlje in vrstico, do katere pride. Možno je tudi, da v kakem stolpcu ni ovire; v tem primeru vrne koordinato tega stolpca in `None`.\n",
    "- `senca(ovire)` vrne seznam, katerega elementa so `True` oz. `False` glede na to, ali stolpec vsebuje kako oviro ali ne. Če je širina poti 5 in sta drugi in zadnji stolpec brez ovir, vrne `[True, False, True, True, False]`.\n",
    "\n",
    "### Rešitev"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "262cd16d",
   "metadata": {},
   "outputs": [],
   "source": [
    "def stevilo_ovir(ovire):\n",
    "    return len(ovire)\n",
    "\n",
    "def dolzina_ovir(ovire):\n",
    "    dolzina = 0\n",
    "    for x0, x1, _ in ovire:\n",
    "        dolzina += x1 - x0 + 1\n",
    "    return dolzina\n",
    "\n",
    "def sirina(ovire):\n",
    "    najx = 0\n",
    "    for _, x1, _ in ovire:\n",
    "        if x1 > najx:\n",
    "            najx = x1\n",
    "    return najx\n",
    "\n",
    "def pretvori_vrstico(vrstica):\n",
    "    vrstica = \".\" + vrstica + \".\"\n",
    "    bloki = []\n",
    "    for i, znak in enumerate(vrstica):\n",
    "        if znak == \"#\":\n",
    "            if vrstica[i - 1] == \".\":\n",
    "                zacetek = i\n",
    "            if vrstica[i + 1] == \".\":\n",
    "                bloki.append((zacetek, i))\n",
    "    return bloki\n",
    "\n",
    "def dodaj_vrstico(bloki, y):\n",
    "    z_vrstico = []\n",
    "    for x0, x1 in bloki:\n",
    "        z_vrstico.append((x0, x1, y))\n",
    "    return z_vrstico\n",
    "\n",
    "def pretvori_zemljevid(zemljevid):\n",
    "    ovire = []\n",
    "    for y, vrstica in enumerate(zemljevid, start=1):\n",
    "        ovire += dodaj_vrstico(pretvori_vrstico(vrstica), y)\n",
    "    return ovire\n",
    "\n",
    "def globina(ovire, x):\n",
    "    najy = None\n",
    "    for x0, x1, y in ovire:\n",
    "        if x0 <= x <= x1 and (najy == None or y < najy):\n",
    "            najy = y\n",
    "    return najy\n",
    "\n",
    "def naj_stolpec(ovire):\n",
    "    naj_y = 0\n",
    "    for x in range(1, sirina(ovire) + 1):\n",
    "        g = globina(ovire, x)\n",
    "        if g == None:\n",
    "            return x, None\n",
    "        if g > naj_y:\n",
    "            naj_y = g\n",
    "            naj_x = x\n",
    "    return naj_x, naj_y\n",
    "\n",
    "def senca(ovire):\n",
    "    zaprti = []\n",
    "    for x in range(1, sirina(ovire) + 1):\n",
    "        zaprti.append(globina(ovire, x) == None)\n",
    "    return zaprti"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3d92726c",
   "metadata": {},
   "source": [
    "Komentar si zasluži le par funkcij.\n",
    "\n",
    "#### `pretvori_zemljevid`\n",
    "\n",
    "V `pretvori_zemljevid` dodamo vrstico z `+=` ne z `append`.\n",
    "\n",
    "```python\n",
    "# Tole ne deluje!\n",
    "    for y, vrstica in enumerate(zemljevid, start=1):\n",
    "        ovire.append(dodaj_vrstico(pretvori_vrstico(vrstica), y))\n",
    "```\n",
    "\n",
    "Metoda `append` bi dodala vrstico kot nov element seznama - se pravi vrstico, ne njenih elementov. Tako bi dobili seznam seznamov.\n",
    "\n",
    "Alternative so `extend`, ki naredi isto kot `+=`,\n",
    "\n",
    "```python\n",
    "    for y, vrstica in enumerate(zemljevid, start=1):\n",
    "        ovire.extend(dodaj_vrstico(pretvori_vrstico(vrstica), y))\n",
    "```\n",
    "\n",
    "ali pa dodajanje posamičnih elementov, kar pa je daljše, nepotrebno in počasnejše\n",
    "\n",
    "```python\n",
    "    for y, vrstica in enumerate(zemljevid, start=1):\n",
    "        for ovira in dodaj_vrstico(pretvori_vrstico(vrstica), y):\n",
    "            ovire.append(ovira)\n",
    "```\n",
    "\n",
    "V tej funkciji je zanimivo tudi, kako pridemo do številke vrstice. Lahko štejemo sami, s spremenljivko, ki jo sami povečujemo, lahko pa uporabimo `enumerate`. Če funkciji `enumerate` dodamo argument `start=1`, bo štela od `1`. Sicer pa pač šteje od `0` in kot številko vrstice uporabimo `y + 1`.\n",
    "\n",
    "#### `naj_stolpec`\n",
    "\n",
    "V tej funkciji je praktično, da takrat, ko najdemo prost stolpec, kar takoj vrnemo `x, None`. To prekine zanko, konča funkcijo, vrne rezultat.\n",
    "\n",
    "#### `senca`\n",
    "\n",
    "Dve stvari. Ta funkcija lahko kliče funkcijo `globina`. Pravzaprav je zelo koristno, da jo, saj sicer ponovimo večino kode te funkcije.\n",
    "\n",
    "Druga:\n",
    "\n",
    "```python\n",
    "zaprti.append(globina(ovire, x) == None)\n",
    "```\n",
    "\n",
    "in ne\n",
    "\n",
    "```python\n",
    "if globina(ovire, x) == None:\n",
    "    zaprti.append(True)\n",
    "else:\n",
    "    zaprti.append(False)\n",
    "```\n",
    "\n",
    "Seveda deluje tudi drugo, vendar ni smiselno, saj je `globina(ovire, x) == None` že vrednost, ki jo želimo dodati v seznam. (Zanimivo: študenti rezultat primerjanja stalno dojemajo kot *pogoj*, ki ga lahko uporabljajo v `if` in `while`, ne pa kot vrednost, ki jo lahko uporabijo, kjerkoli. Mogoče bi se to rešilo tako, da bi že eno predavanje, preden začnemo s pogoji, predstavil logične izraze, kot nekaj, kar pač vrne `True` ali `False`?!)"
   ]
  }
 ],
 "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
}