p1/izzivi/03 dovoljena stevila/resitev.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Dodatni izziv\n",
    "\n",
    "Naloga je nadaljevanje domače naloge [Prepovedana števila](https://github.com/janezd/predavanja/blob/master/p1/domace-naloge/2020/03%20prepovedani%20intervali/resitev.ipynb), v kateri je bil podan seznam intervalov števil, ki so prepovedana, recimo,"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "prepovedani = [\n",
    "    (12, 18),\n",
    "    (2, 5),\n",
    "    (3, 8),\n",
    "    (0, 4),\n",
    "    (15, 19),\n",
    "    (6, 9),\n",
    "    (13, 17),\n",
    "    (4, 8)\n",
    "]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Naloga: napiši program, ki pove, koliko je vseh dovoljenih števil med 0 in največjo zgornjo mejo. V gornjem primeru mora izpisati 2, saj sta dovoljeni dve števili, 10 in 11.\n",
    "\n",
    "Za začetek lahko poskušaš z manjšim številom intervalov, kot je recimo seznam iz \"redne\" domače naloge. Potem pa se spopadi z intervali iz datoteke *intervali.txt*, ki je v priponki naloge.\n",
    "\n",
    "Branja datotek se še nismo učili. Lahko se potrudiš sam(a), lahko pa uporabiš naslednjo vrstico:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "intervali = [tuple(int(x) for x in vrstica.split(\"-\")) for vrstica in open(\"intervali112.txt\")]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Še en zanimiv izziv je naslednji: recimo, da tvoj računalnik ne bi imel niti toliko pomnilnika, da bi lahko shranil celotno tabelo intervalov. Če hočeš večkrat prek tabele, moraš večkrat odpreti datoteko in jo brati. Z drugimi besedami: nimamo seznamov (ali terk, slovarjev, množic ...), le posamične int-e in datoteke (ter, očitno, niz s posamično vrstico, ki jo dobiš iz datoteke, ter seznam z dvema nizoma, ki ga vrne `split` te vrstice). Napiši program, ki kljub tem omejitvam v doglednem času reši nalogo. Recimo tako, da čim manjkrat prebere datoteko.\n",
    "\n",
    "## Rešitev\n",
    "\n",
    "\n",
    "### Naivna rešitev: množice, prečrtavanje\n",
    "\n",
    "Pa začnimo z naivno strategijo: pripravimo množico vseh prepovedanih števil. (Če še ne veste za množice, se ne vznemirjajte: pri tej nalogi nas ne bodo pripeljale nikamor.) Za mali nabor intervalov. Dovoljeno je potem vse, kar ni prepovedano.\n",
    "\n",
    "V spremenljivki `prepovedani` imamo še vedno mali seznam intervalov. Velikega smo naložili v `intervali`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n"
     ]
    }
   ],
   "source": [
    "prep_st = set()\n",
    "for od, do in prepovedani:\n",
    "    for i in range(od, do + 1):\n",
    "        prep_st.add(i)\n",
    "print(max(prep_st) + 1 - len(prep_st))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "K `max(prep_st)`, to je, največji zgornji meji, smo prišteli 1. Če je zgornja meja 5, se pogovarjamo o šestih številih, namreč 0, 1, 2, 3, 4 in 5.\n",
    "\n",
    "Naredimo lahko tudi obratno. Seznam, katerega i-ti element bo `True`-jev, če je število dovoljeno. V začetku so v intervalu sami `True`-ji, potem pa gremo čez intervale in črtamo vse, kar je v njih. Na koncu preprosto seštejemo elemente seznama, saj je `True` enak `1` in `False` enak 0."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n"
     ]
    }
   ],
   "source": [
    "meja = 0\n",
    "for od, do in prepovedani:\n",
    "    if do > meja:\n",
    "        meja = do\n",
    "        \n",
    "dovoljeni = [True] * (meja + 1)\n",
    "for od, do in prepovedani:\n",
    "    for i in range(od, do + 1):\n",
    "        dovoljeni[i] = False\n",
    "print(sum(dovoljeni))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Zdaj pa lahko poskusite pognati isti program na velikem seznamu intervalov. Se vidimo drugo leto.\n",
    "\n",
    "Aha, pa kakšnih 32 GB pomnilnika boste potrebovali, ker Pythonov `int` ni tako majhna zadeva.\n",
    "\n",
    "Seveda se bo tu kdo domislil `numpy`-ja."
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "import numpy as np\n",
    "\n",
    "meja = max(do for _, do in intervali)\n",
    "dovoljeni = np.ones(meja + 1, dtype=np.byte)\n",
    "for od, do in intervali:\n",
    "    dovoljeni[od:do + 1] = False\n",
    "print(sum(dovoljeni))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ne `dtype=np.byte` ne `dtype=bool` nas ne bosta rešila. S prvim bi porabili \"le\" 4 GB pomnilnika in z drugim 500 MB. A tudi numpy ne more tako hitro zapisovati v pomnilnik tisoč ogromnih intervalov.\n",
    "\n",
    "### Urejeni intervali\n",
    "\n",
    "Trik, ki ga je potrebno uporabiti, je relativno očiten: intervale uredimo. Nato bomo v spremenljivko `prvo_dovoljeno` bomo beležili, katero je prvo število, ki bi utegnilo biti dovoljeno (ker v resnici je ali pa še nismo naleteli na interval, ki bi ga prepovedoval). Sprehodimo se po intervalih. Pri vsakem preverimo, ali je med `prvo_dovoljeno` in spodnjo mejo naslednjega prepovedanega intervala kaj prostora. Če je, so ta števila dovoljena. Nato pa `prvo_dovoljeno` dvignemo onstren gornje meje intervala - razen, če je `prvo_dovoljeno` že zdaj višja od te meje."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "112\n"
     ]
    }
   ],
   "source": [
    "prvo_dovoljeno = 0\n",
    "dovoljenih = 0\n",
    "\n",
    "for od, do in sorted(intervali):\n",
    "    if od > prvo_dovoljeno:\n",
    "        dovoljenih += od - prvo_dovoljeno\n",
    "    if do >= prvo_dovoljeno:\n",
    "        prvo_dovoljeno = do + 1\n",
    "        \n",
    "print(dovoljenih)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Na enak način bi lahko tudi hitro našli prvo dovoljeno število."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "22887907\n"
     ]
    }
   ],
   "source": [
    "prvo_dovoljeno = 0\n",
    "\n",
    "for od, do in sorted(intervali):\n",
    "    if od > prvo_dovoljeno:\n",
    "        print(prvo_dovoljeno)\n",
    "        break\n",
    "    if do >= prvo_dovoljeno:\n",
    "        prvo_dovoljeno = do + 1\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Najpočasnejši del tega programa je urejanje. Časovna zahtevnost je sorazmerna $k\\ln k$, kjer je $k$ število intervalov."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Pometanje\n",
    "\n",
    "Tole pa je prisrčen trik, ki se ga je spomnil - pozabil sem kdo, morda eden od asistentov morda eden od študentov Pedagoške fakultete, ki jih včasih morim s to nalogo. Recimo, da bi za vsako število radi vedeli, kolikokrat je prepovedano."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(0, 1), (2, 1), (3, 1), (4, 1), (5, -1), (6, 0), (9, -2), (10, -1), (12, 1), (13, 1), (15, 1), (18, -1), (19, -1), (20, -1)]\n"
     ]
    }
   ],
   "source": [
    "from collections import defaultdict\n",
    "\n",
    "deltas = defaultdict(int)\n",
    "for od, do in prepovedani:\n",
    "    deltas[od] += 1\n",
    "    deltas[do + 1] -= 1\n",
    "\n",
    "deltas = sorted(deltas.items())\n",
    "print(deltas)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tole pove, da imamo začetke intervalov pri 0, 2, 3 in 4 - število 4 je torej prepovedano kar štirikrat. Pri 4 je enega intervala konec, vendar se tam takoj začne naslednji, torej je sprememba enaka 0. Pri 5 se en interval konča, torej je 6 prepovedano samo trikrat. Pri  (zato `(5, -1)`), torej je 5 prepovedana samo trikrat. Potem se en interval zaključi pri 5, vendar se pri 6 začne novi, tako da je sprememba pri 6 enaka 0. Pri 8 se končata dva intervala (torej je 9 prepovedana samo še enkrat) in pri 9 se konča še en interval - torej je število 10 dovoljeno! Pa 11 tudi, saj je naslednja prepoved šele pri 12.\n",
    "\n",
    "Gornje lahko tudi narišemo - program za risanje pa naj razume, kdor hoče."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[<matplotlib.lines.Line2D at 0x113a06e50>]"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAk0AAADFCAYAAABJhsbEAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi40LCBodHRwOi8vbWF0cGxvdGxpYi5vcmcv7US4rQAADjZJREFUeJzt3W+MZWddB/Dvz7bEP7AiFnXYdl0whGQgcWkmLBUlBIkpFbvqC1vWPySSbEkkgajRGhKEF75AIzEaol1DAyqFagC3NiVCFEJI2pVt3ZZ2yp9CSul2bBeNDMRELTy+mLvJOJ2782w7586ZO59PcjN37nnunN9vn3vO/d5z7r1brbUAAHB+37XTBQAA7AZCEwBAB6EJAKCD0AQA0EFoAgDoIDQBAHQQmgAAOghNAAAdhCYAgA4XD/FHL7300nbw4MEh/jQAwLa66667vt5ae+5W4wYJTQcPHsypU6eG+NMAANuqqr7aM87pOQCADkITAECH7tBUVRdV1b9W1W1DFgQAMEYXcqTpLUkeGKoQAIAx63ojeFVdluRnk/xBkt8ctCJ2pZtPPpwTp8/MZF1HDu3P0cMHZrIuADin90jTnyT5nSTfmTagqo5V1amqOnX27NltKY7d48TpM1leWR18PcsrqzMLZwCw3pZHmqrqdUkeb63dVVWvmjautXY8yfEkWVpaattWIbvG4sK+3HL9lYOu49ob7xj07wPAND1Hml6R5JqqeijJh5K8uqr+ZtCqAABGZsvQ1Fr7vdbaZa21g0muS/LPrbVfGbwyAIAR8T1NAAAdLui/UWmtfSrJpwapBABgxBxpAgDoIDQBAHQQmgAAOghNAAAdhCYAgA5CEwBAB6EJAKCD0AQA0EFoAgDoIDQBAHQQmgAAOghNAAAdhCYAgA5CEwBAB6EJAKCD0AQA0EFoAgDoIDQBAHQQmgAAOghNAAAdhCYAgA5CEwBAB6EJAKCD0AQA0EFoAgDoIDQBAHQQmgAAOghNAAAdtgxNVfXdVfUvVXVPVd1fVe+cRWEAAGNycceY/07y6tbat6rqkiSfqaqPtdbuHLg2AIDR2DI0tdZakm9Nfr1kcmlDFsX2uvnkwzlx+syg61heWc3iwr5B17F+XdfeeMdM1kWfI4f25+jhAztdBnNoFvuveWN7HE7Xe5qq6qKqOp3k8SSfaK2d3GTMsao6VVWnzp49u9118jScOH0myyurg65jcWFfjhzaP+g6krWdwazCGX2WV1Y9qTGYWey/5ontcVg9p+fSWvt2kkNV9ewkH62ql7TW7tsw5niS40mytLTkSNTILC7syy3XX7nTZTxtRw8f8ApqZBz1Y2jzsv+aBdvjsC7o03Ottf9M8qkkVw1SDQDASPV8eu65kyNMqarvSfKaJJ8fujAAgDHpOT23kOT9VXVR1kLW37bWbhu2LACAcen59Ny9SV46g1oAAEbLN4IDAHQQmgAAOghNAAAdhCYAgA5CEwBAB6EJAKCD0AQA0EFoAgDoIDQBAHQQmgAAOghNAAAdhCYAgA5CEwBAB6EJAKCD0AQA0EFoAgDoIDQBAHQQmgAAOghNAAAdhCYAgA5CEwBAB6EJAKCD0AQA0EFoAgDoIDQBAHQQmgAAOghNAAAdhCYAgA5bhqaquryqPllVD1TV/VX1llkUBgAwJhd3jHkiyW+11u6uqmcluauqPtFaWx64NgCA0dgyNLXWVpKsTK5/s6oeSLI/idC0DW4++XBOnD4z6DqWV1azuLBv0HUA4zKLfcss2H9duOWV1Vx74x2Dr+fIof05evjA4OsZkwt6T1NVHUzy0iQnN1l2rKpOVdWps2fPbk91e8CJ02eyvLI66DoWF/blyKH9g64DGJdZ7Ftmwf7rwhw5tH8mIXN5ZXUuQvmF6jk9lySpqmcm+XCSt7bWnrQlttaOJzmeJEtLS23bKtwDFhf25Zbrr9zpMoA5Y9+y9xw9fGAmR39mcSRrjLqONFXVJVkLTB9orX1k2JIAAMan59NzleS9SR5orb17+JIAAMan50jTK5L8apJXV9XpyeXqgesCABiVnk/PfSZJzaAWAIDR8o3gAAAdhCYAgA5CEwBAB6EJAKCD0AQA0EFoAgDoIDQBAHQQmgAAOghNAAAdhCYAgA5CEwBAB6EJAKCD0AQA0EFoAgDoIDQBAHQQmgAAOghNAAAdhCYAgA5CEwBAB6EJAKCD0AQA0EFoAgDoIDQBAHQQmgAAOghNAAAdhCYAgA5CEwBAB6EJAKDDlqGpqm6qqser6r5ZFAQAMEY9R5rel+SqgesAABi1i7ca0Fr7dFUdHL6Ufu/8h/uz/OjqTpexLZZXVrO4sG+ny4CnZXllNdfeeMfg6zlyaH+OHj4w+HqGdPPJh3Pi9JnB12PfwtBmsd0vPm9ffv/nXjzoOi7ElqGpV1UdS3IsSQ4c2N07tVlaXNiXI4f273QZ8JTN6vG7vLL2Qmm3h6YTp8/MJNDYtzCkvfrYqtba1oPWjjTd1lp7Sc8fXVpaaqdOnXp6lQGsc+4V7S3XX7nDlTw989IHzJOququ1trTVOJ+eAwDoIDQBAHTo+cqBDya5I8mLquqRqnrj8GUBAIxLz6fnXj+LQgAAxszpOQCADkITAEAHoQkAoIPQBADQQWgCAOggNAEAdBCaAAA6CE0AAB2EJgCADkITAEAHoQkAoIPQBADQQWgCAOggNAEAdBCaAAA6CE0AAB2EJgCADkITAEAHoQkAoIPQBADQQWgCAOggNAEAdBCaAAA6CE0AAB2EJgCADkITAEAHoQkAoIPQBADQoSs0VdVVVfWFqnqwqm4YuigAgLHZMjRV1UVJ3pPktUkWk7y+qhaHLgwAYEwu7hjzsiQPtta+kiRV9aEkR5IsD1kYwEbLK6u59sY7drqMp2V5ZTWLC/t2ugzgKegJTfuTfG3d748kObxxUFUdS3IsSQ4cOLAtxQGcc+TQ/p0uYVssLuybm15gr+kJTbXJbe1JN7R2PMnxJFlaWnrScoCn4+jhAzl62AsyYOf0vBH8kSSXr/v9siSPDlMOAMA49YSmzyZ5YVU9v6qekeS6JLcOWxYAwLhseXqutfZEVb05yT8muSjJTa21+wevDABgRHre05TW2u1Jbh+4FgCA0fKN4AAAHYQmAIAO1dr2fztAVZ1N8tVt/8P/36VJvj7wOsZqL/ee7O3+93Lvyd7uX+97117uf1a9/2hr7blbDRokNM1CVZ1qrS3tdB07YS/3nuzt/vdy78ne7l/ve7P3ZG/3P7benZ4DAOggNAEAdNjNoen4Thewg/Zy78ne7n8v957s7f71vnft5f5H1fuufU8TAMAs7eYjTQAAMyM0AQB0GH1oqqqrquoLVfVgVd2wyfKqqj+dLL+3qq7YiTq3W1VdXlWfrKoHqur+qnrLJmNeVVXfqKrTk8vbd6LWoVTVQ1X1uUlvpzZZPq9z/6J1c3q6qlar6q0bxszV3FfVTVX1eFXdt+6251TVJ6rqS5OfPzDlvufdR4zdlN7/qKo+P3lcf7Sqnj3lvufdRsZuSu/vqKoz6x7bV0+5766e92Rq/7es6/2hqjo95b67fe43fY4b/XbfWhvtJWv/QfCXk7wgyTOS3JNkccOYq5N8LEkleXmSkztd9zb1vpDkisn1ZyX54ia9vyrJbTtd64D/Bg8lufQ8y+dy7jf0eFGSf8vaF6/N7dwneWWSK5Lct+62P0xyw+T6DUneNeXf57z7iLFfpvT+M0kunlx/12a9T5addxsZ+2VK7+9I8ttb3G/Xz/u0/jcs/+Mkb5/Tud/0OW7s2/3YjzS9LMmDrbWvtNb+J8mHkhzZMOZIkr9qa+5M8uyqWph1oduttbbSWrt7cv2bSR5Isn9nqxqduZz7DX46yZdba0N/w/6Oaq19Osl/bLj5SJL3T66/P8nPb3LXnn3EqG3We2vt4621Jya/3pnkspkXNgNT5r3Hrp/35Pz9V1Ul+aUkH5xpUTNynue4UW/3Yw9N+5N8bd3vj+TJwaFnzK5WVQeTvDTJyU0WX1lV91TVx6rqxTMtbHgtycer6q6qOrbJ8rmf+yTXZfpOc57nPkl+uLW2kqztYJP80CZj9sJj4NezdkR1M1ttI7vVmyenJm+acnpmL8z7TyV5rLX2pSnL52buNzzHjXq7H3toqk1u2/gdCT1jdq2qemaSDyd5a2ttdcPiu7N22ubHk/xZkr+fdX0De0Vr7Yokr03yG1X1yg3L533un5HkmiR/t8nieZ/7XvP+GHhbkieSfGDKkK22kd3oz5P8WJJDSVaydopqo7me94nX5/xHmeZi7rd4jpt6t01um8n8jz00PZLk8nW/X5bk0acwZleqqkuy9mD6QGvtIxuXt9ZWW2vfmly/PcklVXXpjMscTGvt0cnPx5N8NGuHZNeb27mfeG2Su1trj21cMO9zP/HYudOtk5+PbzJmbh8DVfWGJK9L8stt8kaOjTq2kV2ntfZYa+3brbXvJPnLbN7T3M57klTVxUl+Mckt08bMw9xPeY4b9XY/9tD02SQvrKrnT151X5fk1g1jbk3ya5NPUr08yTfOHdrbzSbns9+b5IHW2runjPmRybhU1cuyNp//Prsqh1NV31dVzzp3PWtvjL1vw7C5nPt1pr7SnOe5X+fWJG+YXH9DkhObjOnZR+w6VXVVkt9Nck1r7b+mjOnZRnadDe9L/IVs3tNczvs6r0ny+dbaI5stnIe5P89z3Li3+1m9U/6pXrL2CakvZu2d8m+b3PamJG+aXK8k75ks/1ySpZ2ueZv6/smsHW68N8npyeXqDb2/Ocn9WfvkwJ1JfmKn697G/l8w6eueSY97Zu4nvX1v1kLQ96+7bW7nPmvhcCXJ/2btVeQbk/xgkn9K8qXJz+dMxj4vye3r7vukfcRuukzp/cGsvWfj3Lb/Fxt7n7aN7KbLlN7/erI935u1J8KFeZz3af1Pbn/fuW193dh5m/tpz3Gj3u79NyoAAB3GfnoOAGAUhCYAgA5CEwBAB6EJAKCD0AQA0EFoAgDoIDQBAHT4P587T6c03PhlAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 720x216 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "%matplotlib inline\n",
    "\n",
    "import numpy as np\n",
    "from matplotlib import pyplot\n",
    "pyplot.rcParams[\"figure.figsize\"]=10,3\n",
    "\n",
    "\n",
    "x, delta = np.array(deltas).T\n",
    "y = np.cumsum(delta)\n",
    "x = np.vstack((x[:-1], x[1:])).T.flatten()\n",
    "y = np.vstack((y, y)).T.flatten()[:-2]\n",
    "pyplot.plot(x, y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Prvo dovoljeno število je 10\n"
     ]
    }
   ],
   "source": [
    "prepovedanost = 0\n",
    "for x, delta in deltas:\n",
    "    prepovedanost += delta\n",
    "    if prepovedanost == 0:\n",
    "        print(\"Prvo dovoljeno število je\", x)\n",
    "        break"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Če želimo izvedeti število vseh dovoljenih števil, pa imamo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n"
     ]
    }
   ],
   "source": [
    "dovoljenih = 0\n",
    "prepovedanost = 0\n",
    "for (x, delta), (x1, _) in zip(deltas, deltas[1:]):\n",
    "    prepovedanost += delta\n",
    "    if prepovedanost == 0:\n",
    "        dovoljenih = x1 - x\n",
    "print(dovoljenih)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vse to lahko preskusimo tudi na velikem seznamu velikih intervalov."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "109\n"
     ]
    }
   ],
   "source": [
    "intervali = [tuple(int(x) for x in vrstica.split(\"-\")) for vrstica in open(\"intervali.txt\")]\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "deltas = defaultdict(int)\n",
    "for od, do in intervali:\n",
    "    deltas[od] += 1\n",
    "    deltas[do + 1] -= 1\n",
    "\n",
    "deltas = sorted(deltas.items())\n",
    "\n",
    "dovoljenih = 0\n",
    "prepovedanost = 0\n",
    "for (x, delta), (x1, _) in zip(deltas, deltas[1:]):\n",
    "    prepovedanost += delta\n",
    "    if prepovedanost == 0:\n",
    "        dovoljenih += x1 - x\n",
    "\n",
    "print(dovoljenih)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Rešitev ima enako časovno zahtevnost kot prejšnja. Prej smo uredili $k$ intervalov, zdaj uredimo $2k$ meja. To je isto."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Naj drugi delajo namesto mene\n",
    "\n",
    "Takole se je lotil eden od študentov: našel je modul python-intervals. Spodnje je bistvo njegovega programa (z nekaj kozmetičnimi spremembami).\n",
    "\n",
    "```python\n",
    "# Za to, da lahko uvozimo ta modul, moramo namestiti knjižnico python-intervals\n",
    "from intervals import closed as interval\n",
    "\n",
    "prepovedani = interval(intervali[0][0], intervali[0][1])\n",
    "for od, do in intervali:\n",
    "    prepovedani = prepovedani | interval(od, do)\n",
    "\n",
    "dovoljeni = interval(0, prepovedani.upper) - prepovedani\n",
    "count = 0\n",
    "for i in dovoljeni:\n",
    "    count += i.upper - i.lower - 1\n",
    "```\n",
    "\n",
    "V prvem delu sestavimo \"interval\" (tak, po odsekih), ki združuje vse prepovedane intervale. V drugem delu izračunamo njegov komplement in seštejemo dolžine njegovih kosov.\n",
    "\n",
    "Še krajše je, če si pomagamo s par funkcijami drugih Pythonovih modulom in znanjem, ki ga bomo dobili čez par tednov.\n",
    "\n",
    "```python\n",
    "from intervals import closed as interval, Interval\n",
    "from functools import reduce\n",
    "\n",
    "prepovedani = reduce(Interval.union, (interval(od, do) for od, do in intervali))\n",
    "dovoljeni = (~prepovedani)[1:-1]\n",
    "count = sum(i.upper - i.lower - 1 for i in dovoljeni)\n",
    "```\n",
    "\n",
    "To je seveda odličen pristop. Če dobimo (zanesljiv) modul, si seveda prihranimo delo, tako da ni potrebno pisati nam. Seveda gre tu za različna znanja: avtor te rešitve ni programiral, pač pa se je naučil poiskati in uporabiti nekaj, kar že obstaja. Tudi to je dobro. Pozdravljam idejo.\n",
    "\n",
    "### Numpy\n",
    "\n",
    "Glede na to, da smo si na dodatnih predavanjih ogledali `numpy`, napišimo še rešitev z njim."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "109\n"
     ]
    }
   ],
   "source": [
    "from collections import defaultdict\n",
    "import numpy as np\n",
    "\n",
    "deltas = defaultdict(int)\n",
    "for od, do in intervali:\n",
    "    deltas[od] += 1\n",
    "    deltas[do + 1] -= 1\n",
    "\n",
    "deltas = sorted(deltas.items())\n",
    "x, delta = np.array(deltas).T\n",
    "y = np.cumsum(delta)\n",
    "\n",
    "cs = np.flatnonzero(y == 0)[:-1]\n",
    "dovoljenih = np.sum(x[cs + 1] - x[cs])\n",
    "print(dovoljenih)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Začetek že poznamo. `x` in `y` vsebujeta tisto, kar kaže oni graf. S `cs = np.flatnonzero(y == 0)` dobimo indekse elementov v `y`, pri katerih `y == 0` vrne `True` - torej indekse elementov `y`, ki so enaki 0. Te indekse uporabimo v `x`: `x[cs]` so `x`-i, pri katerih je `y` enak 0 - torej začetki regij dovoljenih števil. `x[cs + 1]` so elementi `x` z naslednjimi indeksi, torej tisti elementi `x`, ki sledijo elementom `x[cs]`. Zato so `x[cs + 1] - x[cs]` širine regij dovoljenih števil. Te širine moramo sešteti, pa dobimo število dovoljenih števil.\n",
    "\n",
    "Čemu `[:-1]` pri `flatnonzero`? Zato ker se `y` vedno konča z 0, vendar to ustreza največji zgornji meji in od tam naprej je tako ali tako vse dovoljeno, tako da te, zadnje meje ne upoštevamo več."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Rešitev, če nimamo dovolj pomnilnika"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ozadje tega dodatka je takšno: Advent of Code sem tisto leto reševal na mikrokontrolerju Arduino Uno. Tale [dolgočasni video](https://www.youtube.com/watch?v=XgQm8j2wXA4&list=PLm-JYoU3uw-aIWvjuzHk2KOQSjLQT6Ac-&index=30&ab_channel=JanezDemsar) kaže, kako Arduino rešuje tale dodatni izziv.\n",
    "\n",
    "Arduino ima 2 KB RAM-a, poleg tega pa še 32 KB EEPROMa, v katerega lahko shranimo program in podatke. Problem: 1005 intervalov, torej 2010 4-bajtnih števil, zahteva 8040 bajtov pomnilnika. To seveda gre v EEPROM. Vendar lahko Arduinov program spreminja le vsebino RAM-a. Vsebino EEPROMa zapišemo, ko na Arduina naložimo program. To pomeni, da na Arduinu ni mogoče sortirati seznama intervalov. Seveda bi lahko intervale sortiral prej, preden jih naložim na Arduina. Vendar tega ne bi počel ročno, temveč v Pythonu. In to bi bila goljufija: če rešujemo na Arduinu, ne moremo polovice narediti prej na računalniku. Potrebno je bilo torej sestaviti postopek, ki deluje sorazmerno hitro tudi z neurejenimi intervali.\n",
    "\n",
    "Kar se tiče hitrosti programa samega: Arduina sicer programiramo v C-ju oz. C++ (in v ničemer drugem, pozabite na Python in podobna udobja). Vendar je njegov procesor zelo zelo počasen.\n",
    "\n",
    "V dodatni izziv sem sicer napisal, da podatke vedno znova beremo iz datoteke. Tako sem se \"izrazil\", ker nisem hotel napisati, da jih ne smete urejati, saj bi vam s tem izdal, da je urejanje smiselno in tako pokvaril prvi del naloge. V rešitvi pa jih ne bomo vsakič znova brali iz datoteke, temveč bomo vedno znova prehajali prek istega, neurejenega seznama. Saj ni razlike.\n",
    "\n",
    "Ideja bo relativno preprosta. Najprej poiščimo prvo dovoljeno število. Predpostavimo, da je 0 dovoljeno. Če naletimo na interval, ki to število prepoveduje, predpostavimo, da je dovoljeno število, ki je za 1 večje od zgornje meje tega intervala. Spet pregledamo intervale; če naletimo na interval, ki ga prepoveduje ... in tako naprej."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "22887907\n"
     ]
    }
   ],
   "source": [
    "kandidat = 0\n",
    "while True:\n",
    "    for od, do in intervali:\n",
    "        if od <= kandidat <= do:\n",
    "            kandidat = do + 1\n",
    "            break\n",
    "    else:\n",
    "        break\n",
    "\n",
    "print(kandidat)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Število dovoljenih števil poiščemo tako, da za vsakega kandidata za dovoljeno število poiščemo, kateri interval ima najmanjšo zgornjo mejo, ki je nad njim. Če se vmes izkaže, da je kandidat prepovedan, potem pač nadaljujemo z naslednjim. Če je kandidat v resnici dovoljeno število, pa k številu dovoljenih števil prištejemo razliko med tem številom in prvim naslednjim prepovedanim intervalom."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "109\n"
     ]
    }
   ],
   "source": [
    "kandidat = 0\n",
    "dovoljenih = 0\n",
    "while True:\n",
    "    zgoraj = None\n",
    "    for od, do in intervali:\n",
    "        if od <= kandidat <= do:\n",
    "            kandidat = do + 1\n",
    "            break\n",
    "        elif kandidat < od and (zgoraj == None or od < zgoraj):\n",
    "            zgoraj = od\n",
    "            naprej = do + 1\n",
    "    else:\n",
    "        if zgoraj == None:\n",
    "            break\n",
    "        dovoljenih += zgoraj - kandidat\n",
    "        kandidat = naprej\n",
    "print(dovoljenih)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Koliko časa zahteva ta program? Zanka `for` gre čez `k` intervalov. Vsakič poveča vrednost `kandidat` na neko višjo gornjo mejo, zato se bo `while` obrnila največ `k` krat. Čas izvajanja je torej sorazmeren $k^2$."
   ]
  }
 ],
 "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
}