p1/domace-naloge/2020/07 srečanja/rešitev.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Srečanja\n",
    "\n",
    "Dva tipa. Bluzita po New Yorku, v času viška korone. Zelo pametno. No, vsaj sledilno aplikacijo sta imela. Vsaj to.\n",
    "\n",
    "<table width=\"100%\"><tr>\n",
    "    <td align=\"center\"><font size=\"2\">Prvi je šel tako:<br/>^2 &gt;6 ^6 &lt;1 v3 &lt;6 v4</font></td>\n",
    "    <td align=\"center\"><font size=\"2\">Drugi - tako:<br/>&gt;4 ^3 &gt;4 ^3 &lt;6 v8 &gt;1 ^5</font></td>\n",
    "    <td align=\"center\"><font size=\"2\">Če narišemo oba skupaj, je to videti tako.</font></td>\n",
    "</tr>\n",
    "<tr><td align=\"center\"><img src=\"data:image/.png;base64,iVBORw0KGgoAAAANSUhEUgAAARoAAAE6CAMAAAD+wW2+AAAAGXRFWHRTb2Z0d2FyZQBBZG9iZSBJbWFnZVJlYWR5ccllPAAAAIRQTFRFxL/eTkCdiX+9YGBgICAgMDAwEBAQj4+PPzCNlI+uNTBPHhBt8O/3cHBwPzCVBQAfUFBQbGCtSkB+LiB9DgBdZWB/IhCEz8/PCgA+QkBQ08/maWCeKiBeOzB2pp/OMCCFOjBuDQBVR0Bud3Cflo++GRBOv7+/QEBAf39/EwB8AAAA////rMPU+wAAACx0Uk5T/////////////////////////////////////////////////////////wDH1gmMAAADZUlEQVR42uzdWU/bQBQG0KyQQBYIe1tKV5zl//+/tuQN+Y6lKd7g3NdPsa5PPE6k0cwMDiqoAQI0aNCgQYMGDRo0aBQaNGjQvO46UYsPTXO5S9Rq8YFpkjJvZ/OKZll0vx53FfWUc9VlFc3dc/drVkWzy7nqXRXNPn6+nos4227jrHjOy8JWhpU0b9Nmb2lWw7JC87fKfz/QoEGDBg0aNGjQoEGDBg0aNGjQoEGDBg0aNGjQdJQmnhSensTZZBJnJ9O8LGzl/OX2z0qzI01Wm5U08aTw6TTOxuM4m57mZfv0nPe8NEvPeSfbNKC8a9CgQYMGDRo0aNCgQYMGDRo0aNCgQYMGDRo0aNCg6QlND+r65fbXpdmRJuuynhoDCg0aNGjQoEGDBg0aNGjQoEGDBg0aNGjQoEGDpgWaxfdhWLPzOLu6irPzWV52HQW3bdAsVrveVLM0fZJpeMXuqEcytw+NrvPuEc3tp0OjA2rUe5maaS6DUy3mZ/GJFzc3cXY2z8vWcTR/OLRCM+r6/5pUK2jQoEGDBg0aNGjQoEGDBg0aNGjQoEGDBg0aNG3TbLblNZ5swyqKOJuM87J9HMWtHGmy2kTzPzQGFBo0aNCgQYMGDRo0aNCgQYMGDRo0aNCgQYMGDRo0aLpB86Xrh1anWql3MfPnrh9anWql3iXwBhQaNGjQoEGDBg0aNGjQoEGDBg0aNGjQoEGDBk0dNB3aHjVspR2ay/7sRtwwTY9kGp7zfuyRTMNz3rMeyfxqds572B+Zr4dm3zVHmlUXjpioOO3i56EVmkHX/9ekW0GDBg0aNGjQoEGDBg0aNGjQoEGDBg0aNGjQoEHTCs1gNLq/v1/vy+r6haY8ex+VPgU+8VV98KcGDRo0aNCgQYMGDRo0aNCgQYMGDRo0aNCgQYMGDRo0jdNEC1qPK3bnXd+lOt1K/ordfzTRMugfm2+/N5uHru9tnm4lf513PU/xu3/XoEGDBg0aNGjQoEGDBg0aNGjQoEGDBg0aNGjQoEGDphaabVjjSZwVRZxNxnlZDa0k20STT2NAoUGDBg0aNGjQoEGDBg0aNGjQoEGDBg0aNGjQoEGDphs0JnYjmsRnlxeJXhO3eLHMy2poJdnmXQWNQoMGDRo0aNCgQYNGoUGDBg2aluuPAAMAVYCyphlDC/kAAAAASUVORK5CYII=\"/>\n",
    "</td><td align=\"center\"><img src=\"data:image/.png;base64,iVBORw0KGgoAAAANSUhEUgAAARoAAAE6CAMAAAD+wW2+AAAAGXRFWHRTb2Z0d2FyZQBBZG9iZSBJbWFnZVJlYWR5ccllPAAAAIpQTFRFAAAA/0BA/7+//39/YGBgICAgMDAwoGBgEBAQ4CAgj4+P32BgoCAgv0BAbzAwzxAQz4+P7zAw/xAQ/zAwQAAAcHBw/2BggAAA/6+v/4+PUFBQgEBAz8/P/yAg/9/fvwAA/8/P/+/vUEBA/5+f/1BQUBAQj39/4EBAcEBAv7+/QEBAf39//wAA////JbAE0wAAAC50Uk5T////////////////////////////////////////////////////////////AIKPc1UAAANySURBVHja7N1rU+IwAAVQQR4iiIqIrO99r8X+/7+3yn416bZTQiPnfr2DpGeaykwm6VEpgRwhQIMGDRo0aNCgQYNG0KBBgwYNmixprotDzXUVzf3Loea+iiYyv16KcLfZhLvipVm3g6HUGyYaNGjQoEGDBg0aNGjQoEGDBg0aNGjQoEGDBg0aNGj2ShNeFB6dhLvhMNydjJp1OxhKdJiVNOFF4dNRuBsMwt3otFm3g6FEh2lCedagQYMGDRo0aNCgQYMGDRo0aNCgQYMGDRo0aLKiWc+mx8HEuptwNZ2Fu7OzZt1s+piY5vg1mywe09K8ZpRVnKblLHOi6SW9a/po0DSkeej6f6jV3mh6Xf9d00eDBg0aNGjQoEGDBg0aNGjQoEGDBg0aNGjQoGmHpuVtshfb77zs+o7di/+haXlz9Xz7nedd3+c9N6E8a9CgQYMGDRo0aNCgQYMGDRo0aNCgQYMGDRo0aNCgyYdmE8xgGO6KIlCMt985CX1uOAj/zbaHUj1MNE1pTCg0aNCgQYMGDRo0aNCgQYMGDRo0aNCgQYMGDZpPQbPsB3MxD3fjcYPuS0403xeHcahufZrnDp43nHAz87e7u5/zuz8fdrMO0iTcAh/rpvug+dGZCRXr9vKOgX5GNA+9j3N53gtmMmnWnV+uy4xojlP9rin38GISNGjQoEGDBg0aNGjQoEGDBg0aNGjQoEGDBg2aw6JJuOYd6/6tec9SHeD9fpZ4JU2n1rynqY59fz+B3oTyrEGDBg0aNGjQoEGDBg0aNGjQoEGDBg0aNGjQoEGDJhOalrPcXuJT7e5m290cJYy7xoRCgwYNGjRo0KBBgwYNGjRo0KBBgwYNGjRo0KDpGk2T41qvtpe4qN095EWT/gDgbtFEduymp+nWjt3IPu/0NN3a592pCbX2rAlkVeZCM2/8Wour2t1bls9l6XfNh0n5zhY0aNCgQYMGDRo0aNCgQYMGDRo0aNCgQYMGDZqWaDbBDIbhrigCxXh7+ZPa3VvaHkpFN0TTnMaEQoMGDRo0aNCgQYMGDRo0aNCgQYMGDRo0aNCgQZMNTSxoPgHNThZ2Y8lmYTfy2evbyFgHgeJXJc3v4HW0PJSK7va+xm3bSnpVNP2yq9k1zdfVIgZztS4PlibjoEGDBg0aNGjQoEGDRtCgaSF/BRgAC4SvTwtt99MAAAAASUVORK5CYII=\"/>\n",
    "</td><td align=\"center\"><img src=\"data:image/.png;base64,iVBORw0KGgoAAAANSUhEUgAAARoAAAE6CAMAAAD+wW2+AAAAGXRFWHRTb2Z0d2FyZQBBZG9iZSBJbWFnZVJlYWR5ccllPAAAAQJQTFRFQEBAv7+/AAAA/0BA/7+/xL/e/39/TkCdiX+9YGBgICAgxAAfTgBdoGBgMDAw4CAgEBAQPzCN8O/3PzCVlI+uoCAg32Bg/zAwj4+PbGCtQAAANTBPLiB9/xAQbzAwz4+PIhCExDBP/6+v/2Bg7zAwcHBwHhBtv0BATiB9gAAAxGB/ZWB/SkB+/yAgz8/PUFBQiQA+ThBtCgA+/4+PxI+uzxAQgEBABQAfTjCN08/mKiBeQkBQaWCe/8/PDgBd/9/fOzB2vwAAd3CfOjBucEBA4gAQR0BuUEBAlo++4EBAj39/pp/OMCCF/1BQ/5+f/+/vUBAQDQBVf39/EwB8/wAA////yyp8ygAAAFZ0Uk5T/////////////////////////////////////////////////////////////////////////////////////////////////////////////////wBKTWzZAAAEpklEQVR42uzdaVfaQBiGYWQHBWRxQ0EF9722alvr1n1fgPz/v1JMvtm8kyZOlpH7+fqcxJnrEOScOZlJWURICgJooIEGGmiggQYaaKAh0EADDTQPklOkMdE0S0NFmo0JplHK6LN5QLOZSn5uhx75HuSum140R1PJT92LZhjkrkdeNGn58zWlePYGA8XncipYJw6l4EmjZ5jG0jQLboFmnJxrBw000EADDTTQQAMNNNBAAw000EADDTTQQAMNNNBAA01CaeRF4eqs3JXLcjdbDdaJQ9myp7/s2jk0gYbpSSMvCi9W5a5UkrvqYrAurV7zbrl26jVv5TB5oPiugQYaaKCBBhpooIEGGmiggQYaaKCBBhpooIEGGmiMounNzefFqLpdqdixp7/n2jk00pXb26qh3ERMkx9pz4w9/WnXzqEJdt/OTbQ0I3NoRn01jea0TaLJRPqpyUIDTUCaw6T/h+rHRpNJ+u+aLDTQQAMNNNBAAw000EADDTTQQAMNNNBAAw000PxL0/hTEFPfkruVFaF4OXOfZ9J1W3X5ntdSsRYHTaM5NCbR0pgko/eN3VUvmqJBMmuXOt/z7j4hmrVXVqQPVNF4mZBploRTLVrL8okX+/tC8WL6PuvSdcst+Z4XctW6tGKhKSb9d41qKNBAAw000EADDTTQQAMNNNBAAw000EADDTTQQAMNNHHTHAzcUyoPxKRSQlGx/2ZNuq5cku+Zlit5KA5NwGFCE5yGBwoaaKCBBhpooIEGGmiggQYaaKCBBhpooIEGGmiggeYJ0LSzYla7UuPQSG2lIhTPTaL52Qm0L25Ym+omiOYq4OzCpXmt89Bq5y3hM9fu0/n57+75e9duLpE0b3QeWu28W77hu5uPg+ZHYh4oVZePgyZrEM1hxj0bZ0KRcWiktlbLiDnb6FkG0eSj+l1jeR1MAg000EADDTTQQAMNNNBAAw000EADDTTQQAMNNA/Go3t7VFW3Z3d7vndqjYdmyZzdiCOmMUgmNBr3Ne9bg2T8b+A9zux/0LivedcNkvnse2l+nGrgB6pgjsw3K9rvGoemqfOICVW3Y3c7QU67eGvFQpNL+u8a9fShgQYaaKCBBhpooIEGGmiggQYaaKCBBhpooIEGGmigiYUmVyyenp5epN1ybdO4d4q07Sne+e527W43HWGUNJZij4sJ/9RAAw000EADDTTQQAMNNNBAAw000EADDTTQQAMNNNBAEyrNut8tWRfsKXZ8d4fG0UyPIk2yaKQXWutx0Mzr3DD7UW/s3tNIr0F/PHh3cnLyIVqaOZ3brD/qPW9Lfa7DKPL0jPiuiYOmb5lC05WPw/A41mLBdzdO+8oyhibK/WtCGAo00EADDTTQQAMNNNBAAw000EADDTTQQAMNNNBAA00ENAMxpbLcpVJCUbGnX/PdjaN7KB5dGZrgNDxQ0EADDTTQQAMNNNBAAw000EADDTTQQAMNNNBAAw000BhDowo0T4AmlIVdVYxZ2FVcu3msGGtJKL560nwR56F5KB7d8ZEHjfZkvGiyVlITNs2vfkcFs9CzJpbG4EADDTTQQAMNNNBAAw00BBpoNOSvAAMAQns0MN89FUkAAAAASUVORK5CYII=\"/>\n",
    "</td>\n",
    "</tr></table>\n",
    "\n",
    "\n",
    "Vse ulice so pravokotne, vse razdalje so pozitivna cela števila. (Ker Manhattan.)\n",
    "\n",
    "Aplikacija za sledenje je zaznala, da sta se vsaj enkrat srečala. *Fun fact*: nikoli nista šla po isti poti: njune poti so se le križale. *Less fun fact*: aplikacija ne beleži ne koordinat ne časa, zato nimamo pojma, kje sta se srečala.\n",
    "\n",
    "## Testi\n",
    "\n",
    "\n",
    "[testi-srecanja.py](https://cdn.jsdelivr.net/gh/janezd/predavanja@master/p1/domace-naloge/2020/07%20srečanja/testi.py)\n",
    "\n",
    "\n",
    "## Obvezni del\n",
    "\n",
    "- Za začetek napiši funkcijo `v_pot(s)`, ki prejme niz, kot so gornji, in ga razbije v seznam terk: prvi element terke je smer, drugi razdalja. Klic `v_pot(\">100 ^42 <13\")` vrne `[(\">\", 100), (\"^\", 42), (\"<\", 13)]`.\n",
    "\n",
    "- Napiši funkcijo `odsek(x, y, smer, razdalja)`, ki prejme (celoštevilski) koordinati `(x, y)`, smer (`\"<\"`, `\">\"`, `\"^\"` ali `\"v\"`) in dolžino odseka (pozitivno celo število). Vrniti mora seznam terk, ki predstavljajo vse celoštevilske koordinate na tem odseku. Klic `odsek(2, 5, \"^\", 3)` vrne `[(2, 5), (2, 6), (2, 7), (2, 8)]`.\n",
    "\n",
    "- Nato napiši funkcijo `tocke(s)`, ki prejme gornji seznam terk in sestavi seznam vseh celoštevilskih koordinat, prek katerih gre pot. Klic `tocke([(\">\", 3), (\"v\", 2), (\">\", 2)])` vrne `[(0, 0), (1, 0), (2, 0), (3, 0), (3, -1), (3, -2), (4, -2), (5, -2)]`. Pot se vedno začne na koordinatah `(0, 0)`.\n",
    "\n",
    "- Končno, napiši funkcijo `presecisca(s, t)`, ki prejme dve poti *kot niz* in vrne seznam njunih presečišč, torej vseh točk potencialnih srečanj teh dveh ljudi. Upoštevaj, da so črte lahko tudi zelo dolge, veliko daljše kot v tem primeru. (Spet pa ne tako dolge, da seznam koordinat ne bi šel v pomnilnik.) Funkcija mora delo vseeno opraviti v nekaj sekundah. Če bo zahtevala več časa, ni pravilno napisana. (Ne boj se: če bo počasna, bo *res* počasna in boš vedel(a), da ni OK.)\n",
    "\n",
    "### Rešitev\n",
    "\n",
    "#### Funkcija `pot`\n",
    "\n",
    "Niz je potrebno razbiti na seznam nizov, kot je, na primer `\"^12\"`, nato pa iti prek tega razbitja ter njegove elemente predelati v terke in zlagati v seznam."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('>', 100), ('^', 42), ('<', 13)]"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def v_pot(s):\n",
    "    pot = []\n",
    "    for korak in s.split():\n",
    "        smer, razdalja = korak[0], int(korak[1:])\n",
    "        pot.append((smer, razdalja))\n",
    "    return pot\n",
    "\n",
    "v_pot(\">100 ^42 <13\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`smer` je prvi znak koraka (`korak[0]`) in `razdalja` je vse *razen* prvega znaka (`korak[1:]`), kar je potem potrebno pretvoriti še v `int`.\n",
    "Vrstici znotraj zanke bi seveda lahko združili v eno, `pot.append((korak[0], int(korak[1:])))`, vendar se mi zdi informativno poimenovati stvari, ki jih dajemo v seznam.\n",
    "\n",
    "#### Funkcija `odsek`\n",
    "\n",
    "Tole je nekaj, kar sem pogosto videval v študentskih rešitvah."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def odsek(x, y, smer, razdalja):\n",
    "    r = [(x, y)]\n",
    "    if smer == \"<\":\n",
    "        for i in range(razdalja):\n",
    "            x -= 1\n",
    "            r.append((x, y))\n",
    "    if smer == \">\":\n",
    "        for i in range(razdalja):\n",
    "            x += 1\n",
    "            r.append((x, y))\n",
    "    if smer == \"v\":\n",
    "        for i in range(razdalja):\n",
    "            y -= 1\n",
    "            r.append((x, y))\n",
    "    if smer == \"^\":\n",
    "        for i in range(razdalja):\n",
    "            y += 1\n",
    "            r.append((x, y))\n",
    "    return r"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Precej ponavljajoča se zadeva. Da bo očitneje, v čem je problem pojdimo v še večjo skrajnost."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def odsek(x, y, smer, razdalja):\n",
    "    if smer == \"<\":\n",
    "        r = [(x, y)]\n",
    "        for i in range(razdalja):\n",
    "            x -= 1\n",
    "            r.append((x, y))\n",
    "        return r\n",
    "    if smer == \">\":\n",
    "        r = [(x, y)]\n",
    "        for i in range(razdalja):\n",
    "            x += 1\n",
    "            r.append((x, y))\n",
    "        return r\n",
    "    if smer == \"v\":\n",
    "        r = [(x, y)]\n",
    "        for i in range(razdalja):\n",
    "            y -= 1\n",
    "            r.append((x, y))\n",
    "        return r\n",
    "    if smer == \"^\":\n",
    "        r = [(x, y)]\n",
    "        for i in range(razdalja):\n",
    "            y += 1\n",
    "            r.append((x, y))\n",
    "        return r"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To je očitno še malo slabše.\n",
    "\n",
    "No, to je bilo za karikaturo. Iti moramo seveda v drugo smer: znotraj `if`-ov bomo napisali le, tisto, po čemer se njihova vsebina razlikuje."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def odsek(x, y, smer, razdalja):\n",
    "    r = [(x, y)]\n",
    "    for i in range(razdalja):\n",
    "        if smer == \"<\":\n",
    "            x -= 1\n",
    "        if smer == \">\":\n",
    "            x += 1\n",
    "        if smer == \"v\":\n",
    "            y -= 1\n",
    "        if smer == \"^\":\n",
    "            y += 1\n",
    "        r.append((x, y))\n",
    "    return r"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Boljše, ne? (Namesto `if` - vseh razen zadnjega, seveda - bi lahko pisali tudi `elif`. Vendar je vseeno, če ne?)\n",
    "\n",
    "Gre krajše, boljše? Ti `if`-i so ... črevasti. Gre. S slovarjem."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def odsek(x, y, smer, razdalja):\n",
    "    smeri = {\"^\": (0, 1), \"v\": (0, -1), \"<\": (-1, 0), \">\": (1, 0)}\n",
    "    dx, dy = smeri[smer]\n",
    "    pot = [(x, y)]\n",
    "    for _ in range(razdalja):\n",
    "        x += dx\n",
    "        y += dy\n",
    "        pot.append((x, y))\n",
    "    return pot"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ključi slovarja `smeri` so različne smeri, vrednosti pa terke, ki povedo, kako je potrebno spremeniti `x` in `y`. Vzamemo ustrezno smer, razpakiramo in potem prištevamo. Oba pač, vendar je eden vedno enak 0.\n",
    "\n",
    "#### Funkcija `tocke`\n",
    "\n",
    "Vsekakor bi radi uporabili funkcijo `odsek`, saj bo sicer potrebno pisati vse od začetka. Se pravi nekaj takega."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def tocke(s):\n",
    "    # To (še) ne deluje\n",
    "    x, y = 0, 0\n",
    "    pot = []\n",
    "    for smer, razdalja in s:\n",
    "        pot += odsek(x, y, smer, razdalja)\n",
    "    return pot"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Funkcija ima dva problema.\n",
    "\n",
    "- Vrednosti `x` in `y` ves čas enaka 0. Funkcija `odsek` ju ne spremeni (in ne more spremeniti).\n",
    "- Funkcija `odsek` vrne celoten odsek, od prve do zadnje točke (ah, kako lepo je, da `range` in rezine ne vrnejo zadnjega elementa). Če bomo lepili odseke skupaj, se bo zadnja točka vsakega odseka vedno ponovila na začetku naslednjega.\n",
    "\n",
    "Lepota tega, kar bomo storili, je da reši oba problem v enem zamahu.\n",
    "- Koordinati `x` in `y` sta ravno zadnji element seznama `pot` po vsakem koraku zanke.\n",
    "- Zadnji element seznama `pot` je potrebno odstraniti, da se bo ponovil.\n",
    "- Seznami imajo metodo `pop`, ki vrne in odstrani zadnji element."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def tocke(s):\n",
    "    # To skoraj deluje\n",
    "    x, y = 0, 0\n",
    "    pot = []\n",
    "    for smer, razdalja in s:\n",
    "        pot += odsek(x, y, smer, razdalja)\n",
    "        x, y = pot.pop()\n",
    "    return pot"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tej, gotovo negrdi rešitvi, manjkata le še zadnji koordinati zadnjega odseka, saj za njim ni bilo nobenega odseka več. To nekateri rešujejo tako, da preverjajo, ali so že na koncu in v tem primeru ne od-`pop`-ajo zadnjega elementa. Za to so potrebni indeksi in `len` in bogvekaj še. Ne, ne, mi smo pametnejši. Kar smo odvzeli, bomo vrnili, pa bo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def tocke(s):\n",
    "    # To skoraj deluje\n",
    "    x, y = 0, 0\n",
    "    pot = []\n",
    "    for smer, razdalja in s:\n",
    "        pot += odsek(x, y, smer, razdalja)\n",
    "        x, y = pot.pop()\n",
    "    pot.append((x, y))\n",
    "    return pot"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Funkcija `presecisca`\n",
    "\n",
    "Naloga sprašuje po preseku. (Namig: naslov funkcije je ... *presečišča*.) Da izračunamo presek, je potrebno seznama točk (ki ju dobimo od funkcije `tocke`, ki ji podamo seznama, ki ju dobimo od funkcije `v_pot`) pretvoriti v množici. Nato izračunamo presek in ga pretvorimo nazaj v seznam."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def presecisca(s, t):\n",
    "    tocke1 = tocke(v_pot(s))\n",
    "    tocke2 = tocke(v_pot(t))\n",
    "    return list(set(tocke1) & set(tocke2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Dodatna naloga\n",
    "\n",
    "Izkazalo se je, da tole pravzaprav ni pot, ki sta jo prehodila, temveč pot, ki jo *nameravata* prehoditi. Poleg tega sta se dogovorila, da se morata nujno vsaj enkrat srečati.\n",
    "\n",
    "Da prehodita razdaljo dolžine 1, potrebujeta vsaj 1 minuto.\n",
    "\n",
    "Recimo, da bi se zmenila, da se bosta srečala na najbolj zgornji desni točki na sliki. Modri sicer lahko pride tja v 12 minutah, vendar bo moral tam počakati do rdečega, ki bo do tja potreboval 16 minut. Če se torej dogovorita za srečanje v oni točki, se bosta dobila čez 16 minut.\n",
    "\n",
    "Ker bi se rada srečala čimprej, si bosta raje izbrala kakšno točko, do katere lahko prideta ob čimprej -- pa čeprav ne nujno ob istem času. No, v primeru na sliki je to točka `(4, 2)`, do katere slučajno prideta ob hkrati, v šestih minutah.\n",
    "\n",
    "V splošnem pa točka srečanja *ni* točka, do katere potrebujeta enako časa, temveč točka, na kateri sta čimprej lahko oba.\n",
    "\n",
    "Napiši funkcijo `prvo_srecanje(s, t)`, ki prejme poti (kot niza) in vrne najkrajši možni čas do prvega srečanja in koordinati točke tega srečanja. V gornjem primeru vrne `(6, (4, 2))`.\n",
    "\n",
    "Začetna točka, (0, 0) ne šteje. Tam se ne smeta srečati, ker bi ju vsi videli.\n",
    "\n",
    "**Nasvet:** funkcija `tocke(s)` vrne le seznam točk. Ne pa tudi razdalj do njih. To ni dobro. Potrebno bo napisati kaj podobnega, a uporabnejšega.\n",
    "\n",
    "### Rešitev\n",
    "\n",
    "Kot svetuje nasvet, najprej pripravimo uporabnejšo različico funkcijo `tocke_koraki`, ki namesto seznama vrne slovar, katerega ključi so koordinate, vrednosti pa število korakov, ki jih potrebujemo do tja."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def tocke_koraki(s):\n",
    "    x, y = 0, 0\n",
    "    skupaj = 0\n",
    "    pot = {(x, y): skupaj}\n",
    "    for smer, razdalja in s:\n",
    "        podpot = odsek(x, y, smer, razdalja)[1:]\n",
    "        for skupaj, (x, y) in enumerate(podpot, start=skupaj + 1):\n",
    "            pot[(x, y)] = skupaj\n",
    "    return pot"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Lepota funkcije je predvsem v spremenljivki `skupaj`, ki vsebuje trenutno razdaljo. V začetku je skupna razdalja seveda 0. V `enumerate` ne bomo šteli od 0, temveč od `skupaj + 1`. Hm, kdo pa bo povečal skupaj? In, oho, kam je šel `x, y = pot.pop()`? Odsek prehodimo samo od prvega elementa naprej, `[1:]`. Se pravi, da ne bomo odbijali zadnjega elementa, temveč prvega; `pop`-a ne potrebujemo. Na koncu funkcije ni potrebno dodajati manjkajočega zadnjega elementa, pač pa na začetku dodamo prvega - slovar inicializiramo z `{(x, y): skupaj}`. Prav, še vedno pa ne vemo, kdo bo spremenil `skupaj`, `x` in `y`. Preprosto: zanka! Ko se zanka `for skupaj, (x, y) ...` izteče, bodo `skupaj`, `x` in `y` obdržali zadnje vrednosti. Se pravi zadnjo razdaljo in zadnje koordinate.\n",
    "\n",
    "Zdaj pa sestavimo takšna slovarja točk. Gremo čez prvega (uporabljali bomo `items`, da dobimo tako koordinato kot razdaljo) in za vsako točko preverimo, ali se pojavi tudi v drugem seznamu. Če je večje izmed teh dveh števil korakov najmanjšega, ki smo ga našli doslej, si ga zapomnimo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def prvo_srecanje(s, t):\n",
    "    tocke1 = tocke_koraki(v_pot(s))\n",
    "    tocke2 = tocke_koraki(v_pot(t))\n",
    "    del tocke1[(0, 0)]\n",
    "    prvo = None\n",
    "    prva_tocka = None\n",
    "    for tocka, korakov in tocke1.items():\n",
    "        if tocka != (0, 0) and tocka in tocke2:\n",
    "            cas = max(korakov, tocke2[tocka])\n",
    "            if prvo == None or cas < prvo:\n",
    "                prvo = cas\n",
    "                prva_tocka = tocka\n",
    "    return prvo, prva_tocka"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Krajše rešitve\n",
    "\n",
    "Ker se na predavanjih po tej nalogi učimo izpeljanih seznamov, slovarjev in množic ter generatorjev, se spodobi napisati še krajše rešitve. Nekako sodi k zapiskom.\n",
    "\n",
    "Ne bomo se trudili na silo pisati enovrstičnih funkcij, posebej če to bo zmanjšalo preglednost."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def v_pot(s):\n",
    "    return [(korak[0], int(korak[1:])) for korak in s.split()]\n",
    "\n",
    "def odsek(x, y, smer, razdalja):\n",
    "    dx, dy = {\"^\": (0, 1), \"v\": (0, -1), \"<\": (-1, 0), \">\": (1, 0)}[smer]\n",
    "    return [(x + i * dx, y + i * dy) for i in range(razdalja + 1)]\n",
    "\n",
    "def tocke(s):\n",
    "    x, y = 0, 0\n",
    "    pot = []\n",
    "    for smer, razdalja in s:\n",
    "        pot += odsek(x, y, smer, razdalja)\n",
    "        x, y = pot.pop()\n",
    "    pot.append((x, y))\n",
    "    return pot\n",
    "\n",
    "\n",
    "def presecisca(s, t):\n",
    "    return list(set(tocke(v_pot(s))) & set(tocke(v_pot(t))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Funkcija `v_pot` je očitna. Funkcija `presecisca` je že čisto kratka. Spraviti `tocke` v krajšo, celo enovrstično obliko bi se gotovo dalo, a najbrž ne bi bilo prav nič lepo. Zanimiva je samo `odsek`. Kar lepo, ni?\n",
    "\n",
    "Zdaj pa še dodatna naloga."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "def tocke_koraki(s):\n",
    "    x, y = 0, 0\n",
    "    dist = 0\n",
    "    pot = {(x, y): dist}\n",
    "    for smer, razdalja in s:\n",
    "        podpot = odsek(x, y, smer, razdalja)[1:]\n",
    "        for dist, (x, y) in enumerate(podpot, start=dist + 1):\n",
    "            pot[(x, y)] = dist\n",
    "    return pot\n",
    "\n",
    "def prvo_srecanje(s, t):\n",
    "    tocke1 = tocke_koraki(v_pot(s))\n",
    "    tocke2 = tocke_koraki(v_pot(t))\n",
    "    presecisca = set(tocke1) & set(tocke2) - {(0, 0)}\n",
    "    return min((max(tocke1[(xy)], tocke2[(xy)]), xy) for xy in presecisca)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Funkcije `tocke_koraki` se ne da preprosto zložiti v kaj bistveno lepšega. `prvo_srecanje` pa smo kar lepo stisnili. Kako, pa razmislite sami."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}