p1/domace-naloge/2023/10 Kontrola/resitev.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "5f8c3d2d",
   "metadata": {},
   "source": [
    "Na MOL-ovem Oddelku za motorni promet in gospodarske dejavnosti na vsako opozorilo o neprijetnostih na kolesarskih poteh odgovorijo, da bodo *preverili in ukrepali skladno s svojimi pristojnostmi*. Še več, njihovi uslužbenci vsakodnevno, praktično 24/7, kolesarijo po Ljubljani in identificirajo nevarne točke, da jih čimprej odpravijo. Funkcije, ki jih boste napisali tu, jim bodo pomagale še boljše in vestnejše opravljati njihovo delo.\n",
    "\n",
    "Da bo naloga lažja, bomo predpostavili, da ima mesto pravokotno mrežo.\n",
    "\n",
    "Zemljevidi so zapisani v datotekah s takšno vsebino:\n",
    "\n",
    "```\n",
    ".r......c..c\n",
    "r.b.........\n",
    ".p...r......\n",
    "............\n",
    ".s.....l....\n",
    ".ad......a..\n",
    "............\n",
    "..gl......g.\n",
    "```\n",
    "\n",
    "Za lažje sledenje navodilom, je tule zemljevid z oštevilčenimi stolpci in vrsticami. V datoteki teh številk ni.\n",
    "\n",
    "```\n",
    "            11\n",
    "  012345678901 \n",
    "0 .r......c..c\n",
    "1 r.b.........\n",
    "2 .p...r......\n",
    "3 ............\n",
    "4 .s.....l....\n",
    "5 .ad......a..\n",
    "6 ............\n",
    "7 ..gl......g.\n",
    "```\n",
    "\n",
    "- Koordinate zapisujemo tako, da navedemo številko stolpca, nato številko vrstice. Štejemo od 0. Koordinata polja s črko `b` je `(2, 1)`.\n",
    "- Razdalje merimo tako, da štejemo koliko vodoravnih in navpičnih korakov je potrebno narediti med črkama. Razdalja med `a` in `g` je `3`, ker moramo en korak desno in dva dol. Razdalja med `p` in `b` je `2`.\n",
    "- Katere črke se pojavljajo v zemljevidu, ne vemo vnaprej. V nekem mestu kolesarji morda vozijo po poteh, sestavljenih iz `$#!?@@!##!`. Vemo le, da `.` pomeni, da na polju ni ničesar posebnega."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d450772a",
   "metadata": {},
   "source": [
    "## Ocena 6\n",
    "\n",
    "### 1. `preberi_zemljevid(ime_dat)`\n",
    "\n",
    "Napiši funkcijo `preberi_zemljevid(ime_dat)`, ki dobi ime datoteke z zemljevidom in vrne zemljevid, shranjen na poljuben način, ki se ti zdi smiseln. Vse nadaljnje funkcije, ki jih bo potrebno napisati, bodo dobile zemljevid v takšni obliki, kot ga boš sestavil v tej funkciji.\n",
    "\n",
    "**Nasvet**: preberi ostale naloge in razmisli, kako si shraniti zemljevid, da ti bo z njim udobno delati.\n",
    "\n",
    "Funkcija lahko vrne, karkoli želiš - seznam, slovar, ime datoteke, množico, seznam nizov ... ali celo terko, v kateri sta slovar in niz. Testi bodo preverjali samo, da funkcija vrne nekaj, kar ni `None`, zato sam skrbno preveri, da funkcija res vrača, kar si si zamislil, naj vrne.\n",
    "\n",
    "#### Rešitev\n",
    "\n",
    "V naslednjih nalogah - pravzaprav že kar v naslednji funkciji - bomo pogosto iskali najbližji tak in tak znak, redkeje pa nas ne bo zanimalo, kaj je na nekih koordinatah. Torej je smiselno zemljevid organizirati okrog znakov, ne okrog koordinat. Naša funkcija `preberi_zemljevid` bo zato vrnila slovar, katerega ključi bodo znaki, pripadajoče vrednosti pa množice koordinat, na katerih se ta znak pojavi."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "16135e40",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import defaultdict\n",
    "\n",
    "def preberi_zemljevid(ime_dat):\n",
    "    lokacije = defaultdict(set)\n",
    "    for v, vrstica in enumerate(open(ime_dat)):\n",
    "        for s, c in enumerate(vrstica):\n",
    "            if c not in \".\\n\":\n",
    "                lokacije[c].add((s, v))\n",
    "    return lokacije"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "39888ab5",
   "metadata": {},
   "source": [
    "Čez datoteko gremo s `for v, vrstica in enumerate(open(ime_dat))`. Poleg vsebine vrstice bomo potrebovali tudi njeno številko, da bomo lahko zapisovali koordinate.\n",
    "\n",
    "Tudi čez vrstico gremo z `enumerate`: `s` bo stolpec, `c` (kot *character*) pa znak.\n",
    "\n",
    "Zanimajo nas le znaki, ki niso pike, mimogrede pa se znebimo še `\\n`. V `lokacije[c]`, ki beleži lokacije znakov `c`, dodamo par s stolpcem in vrstico. Ker so `lokacije` `defaultdict(set)` in ne običajen slovar, se bodo novi ključi pojavljali sami od sebe, kadar bo potrebno."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a30999ff",
   "metadata": {},
   "source": [
    "### 2. `najblizji(x, y, c, zemljevid)`\n",
    "\n",
    "Napiši funkcijo `najblizji(x, y, c, zemljevid)`, ki prejme\n",
    "\n",
    "- koordinate neke točke (`x`, `y`),\n",
    "- iskani znak ali prazen niz (`c`),\n",
    "- in zemljevid v obliki, v kateri ga vrača tvoja funkcija `preberi_zemljevid` (`zemljevid`).\n",
    "\n",
    "Delovanje funkcije je odvisno od argumenta `c`:\n",
    "\n",
    "- Če `c` vsebuje znak, mora funkcija vrniti koordinate polja, ki vsebuje črko `c` in je najbližje podanemu polju (vendar **ni enako podanemu** polju!), ki vsebuje črko `c`. Klic `najblizji(8, 2, \"r\", zemljevid)` vrne `(5, 2)`. Klic `najblizji(1, 5, \"a\", zemljevid)` vrne `(9, 5)`; `a` je sicer tudi ravno na točki `(1, 5)`, vendar funkcija ne sme vrniti iste točke.\n",
    "\n",
    "- Če je `c` prazen niz, funkcija vrne koordinato najbližjega polja (ki ni trenutno polje) in vsebuje poljuben znak (razen, seveda pike).\n",
    "\n",
    "Kadar je enako oddaljenih koordinat več, vrne tisto v bolj levem stolpcu. Če je tudi teh več (= 2, se mi zdi :), vrne tisto, ki je višje.\n",
    "\t\n",
    "Če iskana črka ne obstaja, funkcija vrne `None`.\n",
    "    \n",
    "#### Rešitev\n",
    "\n",
    "Začnimo z dolgo rešitvijo, potem pa jo bomo skrajšali."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ae0d1346",
   "metadata": {},
   "outputs": [],
   "source": [
    "def najblizji(x, y, c, zemljevid):\n",
    "    if c:\n",
    "        kandidati = zemljevid[c]\n",
    "    else:\n",
    "        kandidati = set()\n",
    "        for koordinate in zemljevid.values():\n",
    "            kandidati |= koordinate\n",
    "\n",
    "    najkoord, najrazdalja = None, None\n",
    "    for koord in kandidati:\n",
    "        razdalja = abs(koord[0] - x) + abs(koord[1] - y)\n",
    "        if koord != (x, y) and (\n",
    "                najrazdalja is None\n",
    "                or razdalja < najrazdalja\n",
    "                or razdalja == najrazdalja and koord < najkoord):\n",
    "            najkoord, najrazdalja = koord, razdalja\n",
    "    return najkoord"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5c39e92e",
   "metadata": {},
   "source": [
    "Prvi del funkcije sestavi seznam koordinat, ki vsebujejo iskani znak ali pa, če ta ni podan, katerikoli znak. Če je `c` neprazen niz, je stvar preprosta: koordinate najdemo v `zemljevid[c]`. Sicer pa sestavimo prazno množico in vanjo priunijamo vse, kar najdemo v `zemljevid.values()`.\n",
    "\n",
    "Sledi klasična zanka, s katero iščemo nek minimum prek nečesa. Tokrat gremo prek koordinat, za vsako izračunamo razdaljo do koordinat, podanih kot argument. Trenutne koordinate so boljše od najboljših, če niso enake podanim in bodisi nismo videli še nobenih(`najrazdalja is None`) bodisi je ta razdalja krajša od najkrajše doslej, bodisi ji je enaka, vendar so koordinate \"manjše\".\n",
    "\n",
    "Če iskanega znaka ni, se zanka ne bo izvedla nikoli, `najkoord` bo ostal `None` in funkcija bo vrnila `None`, kot hočejo navodila.\n",
    "\n",
    "Zdaj pa krajša različica. Iz rokava, točneje, iz modula `itertools` privlečemo funkcijo `chain`. Tej lahko podamo seznam nekih stvari, pa jih bo spela skupaj."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "d925cd3f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a\n",
      "b\n",
      "1\n",
      "3\n",
      "4\n"
     ]
    }
   ],
   "source": [
    "from itertools import chain\n",
    "\n",
    "for x in chain(\"ab\", [1, 3, 4]):\n",
    "    print(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "938810b9",
   "metadata": {},
   "source": [
    "Naslednji trik, ki ga najbrž že poznamo, je razpakiranje argumentov. Če imamo, recimo, nek seznam ali karkoli, čez kar je možno iterirati, in bi radi njegove elemente uporabili kot argumente funkcije, ga podamo kot argument tako, da predenj dodamo zvezdico."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "209ed727",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 2 3 4\n",
      "0 1 2 a b\n"
     ]
    }
   ],
   "source": [
    "def f(a, b, c, d, e):\n",
    "    print(a, b, c, d, e)\n",
    "    \n",
    "s = [1, 2, 3]\n",
    "f(0, *s, 4)\n",
    "\n",
    "s = \"ab\"\n",
    "f(0, 1, 2, *s)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "398f7343",
   "metadata": {},
   "source": [
    "Tako lahko celoten prvi del funkcije nadomestimo z\n",
    "\n",
    "```python\n",
    "kandidati = zemljevid[c] if c else chain(*zemljevid.values())\n",
    "```\n",
    "\n",
    "Sledi drugi del. Iščemo minimimum prek vseh kandidatov, razen tistega, ki je enak podanim koordinatam, ` for k in kandidati if k != (x, y)`. Koordinate primerjamo glede na razdalje od izbrane; če bo razdalja enaka, pa hočemo primerjati koordinate same. Ključ za primerjavo bo torej `(abs(k[0] - x) + abs(k[1] - y), k)` - najprej razdalja, če je ta enaka, koordinate. Končno, če kandidatov ni, mora `min` vrniti `None`; to mu povemo z argumentom `default`. Skrajšana funkcija je"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "c5144f0d",
   "metadata": {},
   "outputs": [],
   "source": [
    "def najblizji(x, y, c, zemljevid):\n",
    "    kandidati = zemljevid[c] if c else chain(*zemljevid.values())\n",
    "    return min((k for k in kandidati if k != (x, y)),\n",
    "               key=lambda k: (abs(k[0] - x) + abs(k[1] - y), k),\n",
    "               default=None)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0c388fb3",
   "metadata": {},
   "source": [
    "### 3. `najpogostejsi(x, y, d, zemljevid)`\n",
    "\n",
    "Napiši funkcijo `najpogostejsi(x, y, d, zemljevid)`, ki vrne najpogostejšega med znaki, ki so za največ `d` korakov oddaljen od trenutnega polja. Upoštevaj tudi trenutno polje. Če je takih znakov več (če so na razdalji `d`, recimo po trije znaki `b`, `l` in `r`), naj vrne tistega, ki je prej po abecedi (v tem primeru `\"b\"`). Če na tej razdalji ni nobenega znaka, vrne `None`.\n",
    "\n",
    "#### Rešitev\n",
    "\n",
    "Poškilimo naprej in vidimo, da bomo pisali funkcijo, ki vrne množico vseh najpogostejših znakov. Ta naloga pravi, da moramo vrniti tistega med njimi, ki je prvi po abecedi. Poiskal nam ga bo `min`. Povedati mu moramo le še, kaj naj vrne, če je množica prazna - `None`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "df308049",
   "metadata": {},
   "outputs": [],
   "source": [
    "def najpogostejsi(x, y, d, zemljevid):\n",
    "    return min(vsi_najpogostejsi(x, y, d, zemljevid),\n",
    "               default=None)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "21803616",
   "metadata": {},
   "source": [
    "### 4. `vsi_najpogostejsi(x, y, d, zemljevid)`\n",
    "\n",
    "Napiši funkcijo `vsi_najpogostejsi(x, y, d, zemljevid)`, ki je podobna prejšnji funkciji, vendar vrne množico najpogostejših črk. V gornjem primeru torej namesto `\"b\"` vrne `{\"b\", \"l\", \"r\"}`. Če je najpogostejši le eden, vrne množico z enim elementom. Če ni nobenega, vrne prazno množico.\n",
    "\n",
    "#### Rešitev\n",
    "\n",
    "Na tem mestu podvomimo, ali je bila naša odločitev, da bo zemljevid slovar znakov in ne slovar koordinat, pravilna. Stisnimo zobe in sprogramirajmo. Spet najprej na dolgo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "4c6e5e8e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def vsi_najpogostejsi(x, y, d, zemljevid):\n",
    "    pojavitve = defaultdict(int)\n",
    "    for c, koords in zemljevid.items():\n",
    "        for x0, y0 in koords:\n",
    "            if abs(x0 - x) + abs(y0 - y) <= d:\n",
    "                pojavitve[c] += 1\n",
    "\n",
    "    maxpojav = max(pojavitve.values(), default=0)\n",
    "    pogosti = set()\n",
    "    for c, pojavitev in pojavitve.items():\n",
    "        if pojavitev == maxpojav:\n",
    "            pogosti.add(c)\n",
    "    return pogosti"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "36a6a434",
   "metadata": {},
   "source": [
    "V prvem delu gremo čez vse znake in znotraj tega čez vse koordinate. Število pojavitev beležimo v `pojavitve`. Če je znak znotraj zahtevane razdalje, k številu njegovih pojavitev prištejemo 1.\n",
    "\n",
    "V drugem delu ugotovimo največje število pojavitev. Če na podani razdalji ni nobene ovire (v Ljubljani je to seveda možno, le razdalja mora biti zelo majhna), naj bo največje število pojavitev enako `0` - lahko pa bi bilo karkoli, saj se zanka, ki sledi in v kateri dejansko uporabimo to spremenljivko, tako ali tako ne bo izvedla nikoli.\n",
    "\n",
    "Nato gremo čez preštete pojavitve in v množico zložimo vse znake, ki se pojavijo tolikokrat, kolikorkrat se pojavi najpogostejši.\n",
    "\n",
    "Nekoliko daljša, a morda učinkovitejša različica drugega dela je\n",
    "\n",
    "```python\n",
    "   maxpojav = 0\n",
    "    pogosti = set()\n",
    "    for c, pojavitev in pojavitve.items():\n",
    "        if pojavitev > maxpojav:\n",
    "            maxpojav = pojavitev\n",
    "            pogosti = {c}\n",
    "        elif pojavitev == maxpojav:\n",
    "            pogosti.add(c)\n",
    "```\n",
    "\n",
    "Tu največjega števila pojavitev ne ugotovimo pred zanko, temveč kar v zanki sestavljamo množico z znaki, ki imajo največje število pojavitev doslej. Če se pojavi pogostejši znak, začnemo množico sestavljati od začetka.\n",
    "\n",
    "V Pythonu takšna rešitev najbrž ni bistveno hitrejša od prve, saj je iskanje maksimuma s funkcijo `max` hitra operacija. V kakem hitrejšem jeziku in pri večjem številu podatkov pa bi utegnila biti druga različica hitrejša.\n",
    "\n",
    "Zdaj pa še krajša, bolj Pythonovska rešitev."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6e7ef8ae",
   "metadata": {},
   "outputs": [],
   "source": [
    "def vsi_najpogostejsi(x, y, d, zemljevid):\n",
    "    pojavitve = {c: sum((abs(x0 - x) + abs(y0 - y) <= d\n",
    "                          for x0, y0 in koords))\n",
    "                  for c, koords in zemljevid.items()}\n",
    "    maxpojav = max(pojavitve.values(), default=0)\n",
    "    return {k for k, v in pojavitve.items() if v == maxpojav > 0}\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ed57065a",
   "metadata": {},
   "source": [
    "Slovar `pojavitve` sestavimo z generatorjem. Generator bo seveda tekel prek `zemljevid`. Ključi zemljevida bodo tudi ključi slovarja `pojavitve`, pripadajoče vrednosti pa bodo število pojavitev znaka. Te dobimo tako, da za vsake koordinate ugotovimo ali so znotraj podane razdalje; `True`-je preštejemo s `sum`.\n",
    "\n",
    "Nato, tako kot prej, ugotovimo, kolikokrat se pojavi najpogostejši znak. Ker bodo `pojavitve` vsi ključi zemljevida, je `default=0` tule skoraj nepotreben, saj bomo v takšni situaciji le, če na celem zemljevidu ni niti ene ovire, to pa je, vemo, realno nemogoče.\n",
    "\n",
    "Nato vrnemo množico, v katero zložimo vse ključe slovarja `pojavitve` (= vse znake), za katere je pripadajoča vrednost (= število pojavitev) enaka maksimalni. Zraven pa zvito dodamo pogoj, da mora biti `maxpojav > 0`. Če ni, to pomeni, da znotraj podane razdalje ni bilo nobenega znaka in v tem primeru bo množica prazna."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0e417aad",
   "metadata": {},
   "source": [
    "## Ocena 7\n",
    "\n",
    "### 1. `najblizji(x, y, c, zemljevid, prepovedani)`\n",
    "\n",
    "Spremeni obstoječo funkcijo `najblizji` tako, da bo sprejemala dodatni argument, množico `prepovedani`. Funkcija `najblizji(x, y, c, zemljevid, prepovedani)` naj vrne enak rezultat kot `najblizji`, vendar ignorira polja, našteta v `prepovedani`.\n",
    "\n",
    "(Ne skrbi za teste. To ni tvoj problem. Samo dodaj argument. :)\n",
    "\n",
    "#### Rešitev\n",
    "\n",
    "Da ne bi ponovno pisali dolge različice funkcije, le povejmo, kaj moramo spremeniti: v glavo funkcije dodamo zahtevani argument `prepovedani`, pogoj\n",
    "\n",
    "```python\n",
    "        if koord != (x, y) and (\n",
    "```\n",
    "\n",
    "pa dopolnimo v\n",
    "\n",
    "\n",
    "```python\n",
    "        if koord != (x, y) and koord not in prepovedani and (\n",
    "```\n",
    "\n",
    "Podobno dopolnimo krajšo različico, ki se spremeni v"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "927da26a",
   "metadata": {},
   "outputs": [],
   "source": [
    "def najblizji(x, y, c, zemljevid, prepovedani):\n",
    "    kandidati = zemljevid[c] if c else chain(*zemljevid.values())\n",
    "    return min((k for k in kandidati if k != (x, y) and k not in prepovedani),\n",
    "               key=lambda k: (abs(k[0] - x) + abs(k[1] - y), k),\n",
    "               default=None)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "196e277a",
   "metadata": {},
   "source": [
    "### 2.. `angelca(x, y, znamenitosti, zemljevid)`\n",
    "\n",
    "Angelca meni, da je potrebno stvari delati sistematično. (To vedno ponavlja tudi županu!) Zato za vsakega nadzornika pripravi dnevni načrt: začetno točko (ta je vedno \"prazna\", `.`) in spisek mestnih kolesarskih znamenitosti (robniki, stopnice, bolt ipd).\n",
    "\n",
    "    Nadzornik opravlja vožnjo tako, da obišče znamenitosti v vrstnem redu, ki ga je določila Angelca, pri čemer gre v vsakem koraku k znamenitosti, ki je najbližja trenutni poziciji (v smislu funkcija `najblizji`), pri čemer pa nikoli ne gre na znamenitost, ki jo je že obiskal, \"*saj to,*\" je rekla Angelca, \"*ne bi imelo nobenega smisla*\".\n",
    "\n",
    "\tRecimo, da začne kar na `(0, 0)` in mora prevoziti spisek `rprbr`.\n",
    "\n",
    "\t- Najprej gre na `r` na koordinatah `(0, 1)`. Pot je dolga `1`.\n",
    "\t- Nato gre na `p` na `(1, 2)`. To zahteva `2` koraka.\n",
    "\t- Nadaljuje na `r` na `(1, 0)` (na prejšnjem `r` je bil, torej se ne vrača tja). Tudi to je dolgo `2` koraka.\n",
    "\t- Nato gre na `b` na `(2, 1)`. Spet `2` koraka.\n",
    "\t- Konča na `r` na `(5, 2)` (dva bližja `r`-ja je že obiskal). To je dolgo `4` korake.\n",
    "\n",
    "\tSkupno je naredil 1 + 2 + 2 + 2 + 4 = 11 korakov.\n",
    "\n",
    "\tNek drug nadzornik začne na `(0, 5)` in mora obiskati `asalag`.\n",
    "\n",
    "\t- Gre na `a` na `(1, 5)`: `1` korak.\n",
    "\t- Gre na `s` na `(1, 4)`: `1` korak.\n",
    "\t- Gre na `a` na `(9, 5)`: `9` korakov.\n",
    "\t- Gre na `l` na `(7, 4)`: `3` koraki.\n",
    "    - Tu bi moral obiskati `a`, vendar se ustavi, ker ni več nobenega `a`-ja, ki ga še ni obiskal. Tako do `g`-ja sploh ne pride.\n",
    "\n",
    "\tSkupno je naredil 1 + 1 + 9 + 3 = 14 korakov.\n",
    "\n",
    "\tNapiši funkcijo `angelca(x, y, znamenitosti, zemljevid)`, ki vrne število korakov, ki jih bo naredil nadzornik, ki začne poti v `(x, y)` in mora obiskati `znamenitosti` na `zemljevid`.\n",
    "\n",
    "#### Rešitev\n",
    "\n",
    "Funkcija je dokaj \"mehanska\" - nobenih eksotičnih podatkovnih struktur, trikov in posebej \"pythonovskih\" rešitev. Korakoma korakamo po korakih, seštevamo razdalje in prepovedujemo polja, ki jih obiščemo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "aa995fba",
   "metadata": {},
   "outputs": [],
   "source": [
    "def angelca(x, y, znamenitosti, zemljevid):\n",
    "    prepovedani = set()\n",
    "    korakov = 0\n",
    "    for znamenitost in znamenitosti:\n",
    "        nasl = najblizji(x, y, znamenitost, zemljevid, prepovedani)\n",
    "        if not nasl:\n",
    "            break\n",
    "        xn, yn = nasl\n",
    "        korakov += abs(xn - x) + abs(yn - y)\n",
    "        x, y = xn, yn\n",
    "        prepovedani.add((x, y))\n",
    "    return korakov"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e58e39bc",
   "metadata": {},
   "source": [
    "## Ocena 8\n",
    "\n",
    "Ko je Angelca na dopustu, jo zamenja Johanca. Ta deluje drugače. Nadzornik dobi začetno točko (na kateri ni ničesar, le `.`) in niz z opisom premikov. \n",
    "\n",
    "Na primer, da začne na `(1, 1)` in mora slediti poti `><>4v^12^13v1<2^>>>>>>2v^4v4<^`\n",
    "\n",
    "- `>`: Najprej gre desno. Vidi `b`.\n",
    "- `<`: Gre levo. Tam ni ničesar.\n",
    "- `>`: Gre desno. Tam je `b`, vendar ga je že videl, zato ga ne zabeleži.\n",
    "- `4v`: Nato gre za `4` dol. Vidi `d`.\n",
    "- `^`: Gre gor. Tam ne vidi ničesar.\n",
    "- `12^`: Gre še 12-krat gor. Tam ne vidi sploh ničesar, saj tega niti ni na zemljevidu.\n",
    "- `13v`: Gre 13-krat dol, torej je spet tam, kjer je bil `d`. Ker je ta `d` že videl, ne šteje.\n",
    "- `1<`: Gre za 1 levo. Tam vidi `a`.\n",
    "- `2^`: Gre za 2 gor. Tam ni ničesar. **`s`, ki ga je preskočil, spregleda!**\n",
    "- `>>>>>>`: Nato gre šestkrat `>`. Ničesar.\n",
    "- `2v`: Gre za 2 dol, pri čemer preskoči `l`.\n",
    "- `^` Gre gor in vidi `l`, ki ga je prej preskočil.\n",
    "- `^v`: Gre dol in gor. Ponovno vidi `l`, vendar ga ne zabeleži, ker je tam že bil.\n",
    "- `4v4<^`: v nadaljevanju se spusti pod zemljevid, gre levo in ko se vrne gor, naleti na (drug) `l` ter ga zabeleži.\n",
    "\n",
    "Napiši funkcijo, `johanca(x, y, pot, zemljevid)`. Funkcija mora vrniti niz z zaporedjem znamenitosti, ki jih je videl kolesar. V gornjem primeru vrne `bdall`.\n",
    "\n",
    "Pot je, kot kaže gornji primer, sestavljena iz zaporedja znakov `v`, `^`, `<` in `>`.\n",
    "- Če je pred znakom številka (ki ima lahko poljubno število mest), to pomeni, da naredi več korakov v tisto smer. Ker brezglavo divja, ne vidi znamenitosti, ki so vmes. Tako je, recimo, pri \"*Gre za `2` gor.\n",
    "- Če pot vodi ven iz zemljevida, se pač vozi tam - le da tam pač ne vidi ničesar.\n",
    "- Ko vidi nekaj, kar je že videl (kot recimo `d` v gornjem primeru), to ignoriramo.\n",
    "- Gornje velja le za znamenitosti na *istih* koordinatah. Ko v gornjem primeru naleti na nov `l`, ga zabeleži.\n",
    "\n",
    "#### Rešitev\n",
    "\n",
    "Tegoba te naloge je, kajpak, v tem, da moramo brati zoprni niz. Osnovna ideja bo takšna: gremo čez niz. Vsakič, ko naletimo na števko, jo dodamo v niz `stevilka`. Ko naletimo na smer, se premaknemo za toliko, kolikor piše v `stevilka`, ali za `1`, če je številka prazen niz. Po premiku nastavimo `stevilka` nazaj na prazen niz.\n",
    "\n",
    "```python\n",
    "def johanca(x, y, pot, zemljevid):\n",
    "    ...\n",
    "    stevilka = \"\"\n",
    "    for c in pot:\n",
    "        if c in \"<>^v\":\n",
    "            # premakni se za `stevilka` (ali 1, če je `stevilka` prazna) polj v smer `c`\n",
    "            ...\n",
    "            \n",
    "            stevilka = \"\"\n",
    "        else:\n",
    "            stevilka += c\n",
    "    ...\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3aca5358",
   "metadata": {},
   "source": [
    "K temu okostju dodamo še detajle. `znamenitosti` bo niz z obiskanimi znamenitostmi, ki ga bomo vrnili na koncu funkcije. `obiskane` bo množica obiskanih koordinat; potrebna je, da preprečimo, da bi večkrat zabeležili isto znamenitost."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "97dcfca7",
   "metadata": {},
   "outputs": [],
   "source": [
    "def johanca(x, y, pot, zemljevid):\n",
    "    znamenitosti = \"\"\n",
    "    obiskane = set()\n",
    "    stevilka = \"\"\n",
    "    for c in pot:\n",
    "        if c in \"<>^v\":\n",
    "            stev = int(stevilka or 1)\n",
    "            x, y = {\"<\": (x - stev, y), \">\": (x + stev, y), \"v\": (x, y + stev), \"^\": (x, y - stev)}[c]\n",
    "            if (x, y) not in obiskane:\n",
    "                obiskane.add((x, y))\n",
    "                for z, koord in zemljevid.items():\n",
    "                    if (x, y) in koord:\n",
    "                        znamenitosti += z\n",
    "            stevilka = \"\"\n",
    "        else:\n",
    "            stevilka += c\n",
    "    return znamenitosti"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0d7b207f",
   "metadata": {},
   "source": [
    "Izraz `stevilka or 1` bo imel vrednost `stevilka`, če je niz `stevilka` resničen, torej neprazen, in `1`, če je neresničen, prazen. To pretvorimo v `int`, pa imamo razdaljo.\n",
    "\n",
    "Nove koordinate bi lahko dobili z zaporedjem `if c == \"<\"` in tako naprej. Ker smo leni, raje sestavimo slovar, ki za vsak možen premik vsebuje nove koordinate, potem pa s `[c]` izberemo ustrezne.\n",
    "\n",
    "Po premiku preverimo, ali smo na tem polju že bili. Če nismo, dodamo polje med obiskana polja in po zemljevidu pobrskamo, ali polje vseubje kakšno znamenitost."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dc515894",
   "metadata": {},
   "source": [
    "## Ocena 9\n",
    "\n",
    "- Angelca ima sestrično v nekem velemestu in ta ima podobno velik vpliv na tamkajšnjega župana. Zato moraš poskrbeta, da bo funkcija `angelca` delovala tudi na bistveno večjem zemljevidu. Testi bodo preverjali, da se funkcija izvede v doglednem času - biti mora dovolj hitra, da preživi teste. Če si jo že prej napisal učinkovito, ti ni potrebno storiti ničesar. Če nisi - razmisli in popravi.\n",
    "\n",
    "- Johanca tudi. :)\n",
    "\n",
    "- Ker želijo tudi v teh, velikih mestih, pritegniti kolesarje k ogledu kolesarskih znamenitosti, napiši še funkcijo `najboljsa_cetrt(a)`. Ta poišče kvadrat s stranico `a`, ki vsebuje največ znamenitosti. Funkcija vrne koordinate njegovega zgornjega levega oglišča. Tudi ta funkcija se mora končati v doglednem času.\n",
    "\n",
    "    Če je enako dobrih kvadratov več, vrne najbolj levega, med enako dobrimi najbolj levimi pa najbolj zgornjega.\n",
    "\n",
    "#### Rešitev\n",
    "\n",
    "Ob prvih dveh smo hvaležni sami sebi, da smo zemljevid zapisali na način, na katerega smo ga zapisali. Ob tretji se za to odločitev nase razjezimo, zavihamo rokave in programiramo. Ker gre tu vendarle za oceno 9, bomo kar takoj pokazali zaresno rešitev, ne kakšnih neskončnih zank. (Pač pa se bo, spoiler, pokazalo, da je ta rešitev za zemljevide s pregosto posejanimi ovirami lahko počasna.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "0ce4044c",
   "metadata": {},
   "outputs": [],
   "source": [
    "def najboljsa_cetrt1(a, zemljevid):\n",
    "    tocke = set().union(*zemljevid.values())\n",
    "    maxx = max(x for x, _ in tocke)\n",
    "    maxy = max(y for _, y in tocke)\n",
    "    maxn = 0\n",
    "    for x in range(max(1, maxx - a + 2)):\n",
    "        for y in range(max(1, maxy - a + 2)):\n",
    "            n = sum(x <= tx < x + a and y <= ty < y + a for tx, ty in tocke)\n",
    "            if n > maxn:\n",
    "                maxn = n\n",
    "                xx, yy = x, y\n",
    "    return xx, yy"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b042d946",
   "metadata": {},
   "source": [
    "Najprej sestavimo množico s koordinatami vseh znamenitosti. Množica, `set` ima metodo `union`, ki vrne unijo te množice in vseh množic, ki jih podamo kot argument. Sestavimo torej prazno množico in kot argument podamo vse množice v zemljevidu - zvezdice poskrbi, da argument ne bo en sam, namreč, `zemljevid.values()`, temveč bo argumento v več, namreč, argumenti bodo vsi elementi `zemljevid.values()`.\n",
    "\n",
    "Nato poiščemo velikost zemljevida, največjo koordinato točke + 1, ker štejemo od `0`.\n",
    "\n",
    "Zdaj gremo prek vseh možnih levih in gornjih vogalov. Z vsakega gremo prek vseh točk (`for tx, ty in tocke`) in preštejemo, koliko od teh točk se nahaja znotraj kvadrata z gornjim levim ogliščem v `(x, y)`. Če jih je več kot največ doslej, bingo.\n",
    "\n",
    "Tule je malo skrajšana rešitev - vedno mi gre na živce, ko moram ročno programirati `max`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6a0285f3",
   "metadata": {},
   "outputs": [],
   "source": [
    "def najboljsa_cetrt(a, zemljevid):\n",
    "    tocke = set().union(*zemljevid.values())\n",
    "    maxx = max(x for x, _ in tocke) + 1\n",
    "    maxy = max(y for _, y in tocke) + 1\n",
    "    return max(((x, y)\n",
    "                for x in range(max(1, maxx - a + 1)) for y in range(max(1, maxy - a + 1))),\n",
    "               key=lambda k: sum(k[0] <= tx < k[0] + a and k[1] <= ty < k[1] + a for tx, ty in tocke))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "245b5a99",
   "metadata": {},
   "source": [
    "Preštevanje znamenitosti znotraj kvadrata se da tudi obrniti. Namesto da gremo čez seznam točk in preverjamo ali so znotraj kvadrata, lahko sestavimo množico točk v kvadratu in preverimo velikost njenega preseka z množico znamenitih točk."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "aaa8210b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def najboljsa_cetrt(a, zemljevid):\n",
    "    tocke = set().union(*zemljevid.values())\n",
    "    maxx = max(x for x, _ in tocke) + 1\n",
    "    maxy = max(y for _, y in tocke) + 1\n",
    "    maxn = 0\n",
    "    for x in range(max(1, maxx - a + 1)):\n",
    "        for y in range(max(1, maxy - a + 1)):\n",
    "            n = len({(tx, ty) for tx in range(x, x + a) for ty in range(y, y + a)}\n",
    "                    & tocke)\n",
    "            if n > maxn:\n",
    "                maxn = n\n",
    "                xx, yy = x, y\n",
    "    return xx, yy"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c7f5a461",
   "metadata": {},
   "source": [
    "Ali, različica, v kateri uporabimo `max`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "da3e4d18",
   "metadata": {},
   "outputs": [],
   "source": [
    "def najboljsa_cetrt(a, zemljevid):\n",
    "    tocke = set().union(*zemljevid.values())\n",
    "    maxx = max(x for x, _ in tocke) + 1\n",
    "    maxy = max(y for _, y in tocke) + 1\n",
    "    return max(((x, y)\n",
    "                for x in range(max(1, maxx - a + 1)) for y in range(max(1, maxy - a + 1))),\n",
    "               key=lambda k: len({(tx, ty) for tx in range(k[0], k[0] + a) for ty in range(k[1], k[1] + a)}\n",
    "                                 & tocke))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "260a77a2",
   "metadata": {},
   "source": [
    "Ker Python hitro sestavlja množice in računa njene preseke, je ta rešitev hitrejša od gornje - predvsem za mesta z veliko znamenitostmi.\n",
    "\n",
    "Ob sestavljanju naloge sem imel v mislih drugačno rešitev: rešitev, v kateri izračunamo le število znamenitosti v kvadratu na levem robu, nato pa s tem kvadratom drsimo proti desni in vsakič odštejemo znamenitosti, ki smo jih izgubili na levi strani ter prištejemo znamenitosti na desni. Če so kvadrati res veliki, bo sprejemljivo hiter le takšen postopek. V tej nalogi se je izkazalo, da kljub velikim zemljevidom to ni potrebno."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "45f90dbb",
   "metadata": {},
   "source": [
    "## Ocena 10\n",
    "\n",
    "Kljub veliki skrbi za popisovanje nevarnih točk, nekatere vseeno ostajajo. Problem se utegne skrivati tule. Angelco in Johanco so dali za nekaj časa izpolnjevati stolpce v Excelu in nadzorniki se vozijo po drugačnem postopku.\n",
    "\n",
    "### Prvi del\n",
    "\n",
    "Vsak nadzornik ima pri sebi `n` obrazcev. Pot začne v neki predpisani točki (`x`, `y`), ki je gotovo prazna. V vsakem koraku si izbere neko znamenitost, ki je oddaljena največ `d`. Popiše jo. Nato izbere naslednjo točko, oddaljeno `d`. Popiše in gre do naslednje. To počne toliko časa, dokler mu ne zmanjka obrazcev. K znamenitostim, ki jih je že popisal, se nikoli ne vrača.\n",
    "\n",
    "Napiši funkcijo `dosegljive(x, y, d, n, zemljevid)`, ki vrne množico točk, ki jih lahko doseže nadzornik. To ne pomeni, da lahko nadzornik obišče *vse* točke, temveč, da lahko obišče *vsako*. \n",
    "\n",
    "#### Rešitev\n",
    "\n",
    "Funkcija `dosegljive` bo sestavila množico vseh točk in poklicala funkcijo `doseg`, ki bo imela enake argumente kot `dosegljive` in še enega dodatnega: točke, v katere je nadzorniku dovoljeno iti. V začetku bodo to kar vse točke.\n",
    "\n",
    "`doseg` bo rekurzivna funkcija, ki bo v vsakem koraku preverila, ali ima nadzornik še kak obrazec ter v tem primeru dodala vse točke, ki so dosegljive iz trenutne točke, ter (zdaj pride rekurzije) vse točke, ki so dostopne iz teh, dosegljivih točk, če ima nadzornik en obrazec manj in če je ta točka zdaj prepovedana."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "1a666650",
   "metadata": {},
   "outputs": [],
   "source": [
    "def dosegljive(x, y, d, n, zemljevid):\n",
    "    def doseg(x, y, obr, dovoljene):\n",
    "        dos = set()\n",
    "        if obr:\n",
    "            for xn, yn in dovoljene:\n",
    "                if 0 < abs(xn - x) + abs(yn - y) <= d:\n",
    "                    dos.add((xn, yn))\n",
    "                    dos |= doseg(xn, yn, obr - 1, dovoljene - {(xn, yn)})\n",
    "        return dos\n",
    "\n",
    "    tocke = set().union(*zemljevid.values())\n",
    "    return doseg(x, y, n, tocke)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6e99827d",
   "metadata": {},
   "source": [
    "### Drugi del\n",
    "\n",
    "Na točkah, označenih z `*`, so MOL-ove izpostave. Če nadzornik obišče izpostavo, tam dobi nove obrazce, tako da jih ima spet `n`.\n",
    "\n",
    "- Tudi izpostave, ki jih obišče, smejo biti od trenutne pozicije oddaljene največ `d`.\n",
    "- Isto izpostavo sme obiskati večkrat.\n",
    "- Izpostave ne sme obiskati, če ima še vedno pri sebi `n` obrazcev. Kot pravi Angelca, to ne bi imelo nobenega smisla.\n",
    "\n",
    "Dopolni funkcijo `dosegljive`, da bo upoštevala še ta pravila.\n",
    "\n",
    "Nadzornik, ki nadzira spodnji zemljevid in začne pot na `(11, 5)`, dela korake dolžine do `3` ter ima pri sebi največ `2` obrazca, lahko obišče `{(7, 4), (11, 0), (10, 7), (8, 0), (9, 5)}`.\n",
    "\n",
    "```\n",
    "            11\n",
    "  012345678901 \n",
    "0 .r..*...c..c\n",
    "1 r.b.........\n",
    "2 .p...r...*..\n",
    "3 .*..........\n",
    "4 .s.....l....\n",
    "5 .ad......a..\n",
    "6 ..*.........\n",
    "7 ..gl......g.\n",
    "```\n",
    "\n",
    "Predlog: nalogo je možno rešiti rekurzivno ali iterativno. Rekurzivna rešitev bo najbrž preprostejša in bližja temu, kar smo se učili. Čez teden bom bistveno dopolnil zapiske o rekurziji. V drugem delu bo rekurzija eksplodirala, če je ne boste ukrotili s trikom, ki sem ga pokazal na predavanju (in bo seveda tudi v zapiskih).\n",
    "\n",
    "Če se boste naloge lotili rekurzivno: funkcija `dosegljive` skoraj gotovo ne bo rekurzivna, pač pa bo poklicala, drugo, rekurzivno funkcijo, katere ime in argumente si zamislite sami.\n",
    "\n",
    "Vzpodbuda: če razumete rekurzijo in se je znate lepo lotiti, je naloga za oceno 10 lahka in prijetna, rešitev pa kratka in elegantna. Ni pa ravno čisto trivialna.\n",
    "\n",
    "#### Rešitev\n",
    "\n",
    "Gornjo funkcijo bo potrebno malo obdelati. :)\n",
    "\n",
    "- V `izpostave` shranimo vse izpostave, `izpostave = zemljevid[\"*\"]`. Ker je funkcija `doseg` znotraj funkcija `dosegljive`, ni potrebno, da bi bile `izpostave` argument funkcije `doseg`.\n",
    "\n",
    "- Med dovoljenimi točkami ni več tistih, ki vsebujejo zvezdice. Rokohitrski način, da jih poiščemo, je `tocke = set().union(*(v for k, v in zemljevid.items() if k != \"*\"))`. Če ne znate tako, je očitno možno tudi z navadno zanko.\n",
    "\n",
    "- Znotraj funkcije bomo imeli poleg rekurzivnih klicev na nove znamenitosti (če ima nadzornik še kak `obr`) tudi rekurzivne klice na izpostave (če je nadzornik od zadnjega obiska na izpostavi porabil vsaj en obrazec, `obr < n`). Tako kot točka mora biti tudi izpostava dovolj blizu, rekurzivni klic pa je drugačen: namesto, da bi imel nadzornik po obisku izpostave `obr - 1` obrazcev, jih ima `n`. Poleg tega ostanejo `dovoljene` točke seveda enake.\n",
    "\n",
    "- Zadnja - in najbolj zoprna - komplikacija: ker funkcija zelo zelo zelo velikokrat obišče isto točko (ne v okviru ene rekurzivne veje, temveč ker poskuša iste točke obiskovati v zelo veliko vrstnih redih), bo funkcija prepočasna. Dodati je potrebno `@cache`. To bi bilo trivialno, če si ne bi kot argument podajali množice `prepovedani` - `cache` shranjuje že videne argumente v slovar, zato se slabo razume s spremenljivimi argumenti. Množico zato uredimo in pretvorimo v terko - brez urejanja bi se nam zgodilo, da bi imeli dve množici, ki sta enaki, vendar imata različen vrstni red elementov (navidez, saj množice sploh ne poznajo koncepta vrstnega reda) in bi za dve množici, ki sta v bistvu enaki, dobili različne terke."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "b18942f0",
   "metadata": {},
   "outputs": [],
   "source": [
    "def dosegljive(x, y, d, n, zemljevid):\n",
    "    @cache\n",
    "    def doseg(x, y, obr, dovoljene):\n",
    "        dos = set()\n",
    "        if obr:\n",
    "            for xn, yn in dovoljene:\n",
    "                if 0 < abs(xn - x) + abs(yn - y) <= d:\n",
    "                    dos.add((xn, yn))\n",
    "                    dos |= doseg(xn, yn, obr - 1, tuple(sorted(set(dovoljene) - {(xn, yn)})))\n",
    "        if obr < n:\n",
    "            for xn, yn in izpostave:\n",
    "                if 0 < abs(xn - x) + abs(yn - y) <= d:\n",
    "                    dos |= doseg(xn, yn, n, dovoljene)\n",
    "        return dos\n",
    "\n",
    "    izpostave = zemljevid[\"*\"]\n",
    "    tocke = set().union(*(v for k, v in zemljevid.items() if k != \"*\"))\n",
    "    return doseg(x, y, n, tuple(sorted(tocke)))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "24ec5e69",
   "metadata": {},
   "source": [
    "Obvoz okrog zadnje težave je, da argument `dovoljene` odstranimo. Pred rekurzivnim klicem iz `tocke` umaknemo trenutno koordinato in jo po klicu dodamo nazaj. To je v resnici tudi precej hitrejše, saj se izognemo vsem kopiranjem, pretvarjanjem in urejanjem."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "834df9d3",
   "metadata": {},
   "outputs": [],
   "source": [
    "def dosegljive(x, y, d, n, zemljevid):\n",
    "    @cache\n",
    "    def doseg(x, y, obr):\n",
    "        dos = set()\n",
    "        if obr:\n",
    "            for xn, yn in tocke:\n",
    "                if 0 < abs(xn - x) + abs(yn - y) <= d:\n",
    "                    dos.add((xn, yn))\n",
    "                    tocke.remove((xn, yn))\n",
    "                    dos |= doseg(xn, yn, obr - 1)\n",
    "                    tocke.add((xn, yn))\n",
    "        if obr < n:\n",
    "            for xn, yn in izpostave:\n",
    "                if 0 < abs(xn - x) + abs(yn - y) <= d:\n",
    "                    dos |= doseg(xn, yn, n)\n",
    "        return dos\n",
    "\n",
    "    izpostave = zemljevid[\"*\"]\n",
    "    tocke = set().union(*(v for k, v in zemljevid.items() if k != \"*\"))\n",
    "    return doseg(x, y, n)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "15bc2ffd",
   "metadata": {},
   "source": [
    "## Rešitev z zemljevidom v obliki vrstic\n",
    "\n",
    "Predpostavljam, da je večina študentov prebrala zemljevid kar v seznam vrstic. Pri sestavljanju naloge te različice, priznan, nisem poskusil. Izkaže se, da ni tako grozna."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "951952d0",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 6\n",
    "\n",
    "def preberi_zemljevid(ime_dat):\n",
    "    zemljevid = []\n",
    "    for v, vrstica in enumerate(open(ime_dat)):\n",
    "        zemljevid.append(vrstica.strip())\n",
    "    return zemljevid\n",
    "\n",
    "\n",
    "def najblizji(x, y, c, zemljevid, prepovedani):\n",
    "    najkoord, najrazdalja = None, None\n",
    "    for v, vrstica in enumerate(zemljevid):\n",
    "        for s, znak in enumerate(vrstica):\n",
    "            if znak == c or c == \"\" and znak != \".\":\n",
    "                razdalja = abs(s - x) + abs(v - y)\n",
    "                if (s, v) != (x, y) and (s, v) not in prepovedani and (\n",
    "                        najrazdalja is None\n",
    "                        or razdalja < najrazdalja\n",
    "                        or razdalja == najrazdalja and (s, v) < najkoord):\n",
    "                    najkoord, najrazdalja = (s, v), razdalja\n",
    "    return najkoord\n",
    "\n",
    "\n",
    "def vsi_najpogostejsi(x, y, d, zemljevid):\n",
    "    pojavitve = defaultdict(int)\n",
    "    for v in range(max(0, y - d), min(len(zemljevid), y + d + 1)):\n",
    "        for s in range(max(0, x - d + abs(y - v)),\n",
    "                       min(len(zemljevid[0]), x + d + 1 - abs(y - v))):\n",
    "            pojavitve[zemljevid[v][s]] += 1\n",
    "    pojavitve[\".\"] = 0\n",
    "    maxpojav = max(pojavitve.values(), default=0)\n",
    "    return {k for k, v in pojavitve.items() if v == maxpojav > 0}\n",
    "\n",
    "\n",
    "def najpogostejsi(x, y, d, zemljevid):\n",
    "    return min(vsi_najpogostejsi(x, y, d, zemljevid),\n",
    "               default=None)\n",
    "\n",
    "\n",
    "# 7\n",
    "\n",
    "def angelca(x, y, znamenitosti, zemljevid):\n",
    "    prepovedani = set()\n",
    "    korakov = 0\n",
    "    for znamenitost in znamenitosti:\n",
    "        nasl = najblizji(x, y, znamenitost, zemljevid, prepovedani)\n",
    "        if not nasl:\n",
    "            break\n",
    "        xn, yn = nasl\n",
    "        korakov += abs(xn - x) + abs(yn - y)\n",
    "        x, y = xn, yn\n",
    "        prepovedani.add((x, y))\n",
    "    return korakov\n",
    "\n",
    "\n",
    "# 8\n",
    "\n",
    "def johanca(x, y, pot, zemljevid):\n",
    "    znamenitosti = \"\"\n",
    "    obiskane = set()\n",
    "    stevilka = \"\"\n",
    "    for c in pot:\n",
    "        if c in \"<>^v\":\n",
    "            stev = int(stevilka or 1)\n",
    "            x, y = {\"<\": (x - stev, y), \">\": (x + stev, y), \"v\": (x, y + stev), \"^\": (x, y - stev)}[c]\n",
    "            if (x, y) not in obiskane:\n",
    "                obiskane.add((x, y))\n",
    "                if 0 <= y < len(zemljevid) and 0 <= x < len(zemljevid[0]) and zemljevid[y][x] != \".\":\n",
    "                    znamenitosti += zemljevid[y][x]\n",
    "            stevilka = \"\"\n",
    "        else:\n",
    "            stevilka += c\n",
    "    return znamenitosti\n",
    "\n",
    "\n",
    "# 9\n",
    "\n",
    "def najboljsa_cetrt(a, zemljevid):\n",
    "    maxn = 0\n",
    "    for x in range(max(1, len(zemljevid[0]) - a + 1)):\n",
    "        for y in range(max(1, len(zemljevid) - a + 1)):\n",
    "            n = sum(len(vrstica[x:x+a].replace(\".\", \"\")) for vrstica in zemljevid[y:y+a])\n",
    "            if n > maxn:\n",
    "                maxn = n\n",
    "                xx, yy = x, y\n",
    "    return xx, yy\n",
    "\n",
    "# 10\n",
    "\n",
    "# Te pa se mi ne da narediti na ta način. :)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "192ad9dc",
   "metadata": {},
   "source": [
    "Zanimivo je predvsem, da je Angelca - vsaj na mojem računalniku - dovolj hitra tudi na ta način. Sicer je desetkrat počasnejša od one v gornjih rešitvah (pri meni potrebuje 1,2 s namesto 0,12 s), vendar je to vsaj pri meni še vedno v okviru omejitev."
   ]
  }
 ],
 "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
}