p1/advent of code/2022/01 Calorie Counting/resitev.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "19a9e702",
   "metadata": {},
   "source": [
    "# Day 01: Calorie Counting\n",
    "\n",
    "Naloge imajo zgodbice. Tule bomo vedno vključili [povezavo na izvirno nalogo](https://adventofcode.com/2022/day/1), namesto opisa pa nalogo *kvečjemu* povzeli.\n",
    "\n",
    "## Prvi del\n",
    "\n",
    "V vsaki vrstici datoteke je zapisano celo število. Vrstice so ločene v skupine; med dvema skupinama je prazna vrstica. Sešteti moramo števila v vsaki skupini in na koncu izpisati največjo tako dobljeno vsoto.\n",
    "\n",
    "### Preprosta rešitev\n",
    "\n",
    "Z `open(\"input.txt\").read()` preberemo datoteko v niz. Razcepimo jo glede na prazne vrstice, `split(\"\\n\\n\")`. Potem se ukvarjamo z vsako skupino posebej: seštejemo in primerjamo vsoto z največjo doslej.\n",
    "\n",
    "To je nekaj, kar bi znati vsi študenti, ki so poslušali mesec in pol Programiranja 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "1e9088e1",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "67633\n"
     ]
    }
   ],
   "source": [
    "naj = 0\n",
    "for skupina in open(\"input.txt\").read().split(\"\\n\\n\"):\n",
    "    vsota = 0\n",
    "    for vrstica in skupina.splitlines():\n",
    "        vsota += int(vrstica)\n",
    "    if vsota > naj:\n",
    "        naj = vsota\n",
    "print(naj)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "22f529c5",
   "metadata": {},
   "source": [
    "### Izpeljani seznami - oziroma generatorji\n",
    "\n",
    "Seštevati se da tudi veliko hitreje. Za začetek: če imamo neko skupino, recimo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "f97839c6",
   "metadata": {},
   "outputs": [],
   "source": [
    "skupina = \"\"\"1500\n",
    "300\n",
    "200\n",
    "400\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9e903e25",
   "metadata": {},
   "source": [
    "lahko preprosto sestavimo seznam vrstic, pretvorjenih v številke."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "31172670",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1500, 300, 200, 400]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[int(vrstica) for vrstica in skupina.splitlines()]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8a9a1059",
   "metadata": {},
   "source": [
    "Vsota skupine je pač vsota tega seznama,"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "51d887ba",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2400"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum([int(vrstica) for vrstica in skupina.splitlines()])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "16eb813e",
   "metadata": {},
   "source": [
    "Namesto seznama lahko funkciji `sum` damo tudi kar generator - se pravi, izpustimo oglate oklepaje.\n",
    "\n",
    "Tako dobimo precej krajšo rešitev."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "ef5dd8e3",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "67633\n"
     ]
    }
   ],
   "source": [
    "naj = 0\n",
    "for skupina in open(\"input.txt\").read().split(\"\\n\\n\"):\n",
    "    vsota = sum(int(vrstica) for vrstica in skupina.splitlines())\n",
    "    if vsota > naj:\n",
    "        naj = vsota\n",
    "print(naj)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b434bf36",
   "metadata": {},
   "source": [
    "Zdaj pa pomislimo, da iščemo `max` vsot. Vse skupaj lahko torej zapakiramo v en sam `max`, ki bo šel prek vrstic in računal ... no, pač maksimum vsot."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "56efde4a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "67633\n"
     ]
    }
   ],
   "source": [
    "print(\n",
    "    max(sum(int(vrstica) for vrstica in skupina.splitlines())\n",
    "        for skupina in open(\"input.txt\").read().split(\"\\n\\n\")\n",
    "       )\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c1c4c8db",
   "metadata": {},
   "source": [
    "### Branje po vrsticah\n",
    "\n",
    "Zdaj pa naredimo malo drugače, bolj, recimo, C-jevsko: brali bomo vrstico za vrstico in seštevali. Ko naletimo na prazno vrstico, vemo, da je konec skupine. Primerjamo vsoto in če je večja od največje doslej, si jo zapomnimo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "2e5f60d8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "67633\n"
     ]
    }
   ],
   "source": [
    "naj = 0\n",
    "vsota = 0\n",
    "for vrstica in open(\"input.txt\"):\n",
    "    if vrstica.strip():  # vrstica vsebuje vsaj \\n, zato strip\n",
    "        vsota += int(vrstica)\n",
    "    else:\n",
    "        if vsota > naj:\n",
    "            naj = vsota\n",
    "        vsota = 0\n",
    "if vsota > naj:\n",
    "    naj = vsota\n",
    "\n",
    "print(naj)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "163f7411",
   "metadata": {},
   "source": [
    "Pogoj `if vrstica.strip()` preveri, ali je vrstica (po tem, ko odstranimo `\\n`) neprazna. Če je, prištejemo številko k trenutni vsoti, sicer postorimo, kar je potrebno postoriti, ko je konec skupine.\n",
    "\n",
    "Tisto zoprno preverjanje po zanki je potrebno za primer, da bi imela največjo vsoto ravno zadnja skupina, ki ji ne sledi več prazna vrstica.\n",
    "\n",
    "Prednost te rešitve je, da nikoli ne preberemo celotne datoteke v pomnilnik. Morda pa niti ne gre za datoteko: takole bi lahko dobivali, na primer, neke podatke z nekega spletnega strežnika, vsako minuto bi prišel nov podatek in mi bi morali v vsakem trenutku vedeti največjo vsoto *doslej*. V takem primeru je možna samo tale rešitev."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f6cfe62b",
   "metadata": {},
   "source": [
    "### Generator skupin\n",
    "\n",
    "Naredimo še nekaj zanimivega: napišimo funkcijo, ki kot argument dobi ime datoteke in nato vrača sezname, ki vsebujejo vse številke določene skupine. Ker bo zanimivo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "385704f6",
   "metadata": {},
   "outputs": [],
   "source": [
    "def skupine(ime):\n",
    "    skupina = []\n",
    "    for vrstica in open(ime):\n",
    "        if vrstica.strip():\n",
    "            skupina.append(int(vrstica))\n",
    "        else:\n",
    "            yield skupina\n",
    "            skupina = []\n",
    "    if skupina:\n",
    "        yield skupina"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e8042fce",
   "metadata": {},
   "source": [
    "Tale funkcija nekoliko spominja na prejšnjo rešitev. Razlika je le v tem, da je prejšnja takrat, ko je naletela na prazno vrstico, izračunala in primerjala vsoto, tale pa vrne (točneje: generira) sezname številk v skupinah.\n",
    "\n",
    "Uporabimo jo lahko tako:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "15d4082a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "67633\n"
     ]
    }
   ],
   "source": [
    "naj = 0\n",
    "for skupina in skupine(\"input.txt\"):\n",
    "    vsota = sum(skupina)\n",
    "    if vsota > naj:\n",
    "        naj = vsota\n",
    "print(naj)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0930dffd",
   "metadata": {},
   "source": [
    "Ali pa tako."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "c3a816d1",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "67633\n"
     ]
    }
   ],
   "source": [
    "print(max(sum(skupina) for skupina in skupine(\"input.txt\")))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ffd5e900",
   "metadata": {},
   "source": [
    "Oziroma, podobno ampak še boljše, tako."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "c4ea0a0b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "67633\n"
     ]
    }
   ],
   "source": [
    "print(max(map(sum, skupine(\"input.txt\"))))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4ee81292",
   "metadata": {},
   "source": [
    "Če bi generator namesto seznamov vračal kar vsote,"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "23a67437",
   "metadata": {},
   "outputs": [],
   "source": [
    "def skupine(ime):\n",
    "    skupina = []\n",
    "    for vrstica in open(ime):\n",
    "        if vrstica.strip():\n",
    "            skupina.append(int(vrstica))\n",
    "        else:\n",
    "            yield sum(skupina)\n",
    "            skupina = []\n",
    "    if skupina:\n",
    "        yield sum(skupina)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c62a6b41",
   "metadata": {},
   "source": [
    "pa bi lahko pisali celo kar"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "edf3f6b5",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "67633\n"
     ]
    }
   ],
   "source": [
    "print(max(skupine(\"input.txt\")))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3b0a8481",
   "metadata": {},
   "source": [
    "`skupine(\"input.txt\")` namreč generira vsote in `max` bo vrnil največjo zgenerirano stvar."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dd8ae612",
   "metadata": {},
   "source": [
    "## Drugi del\n",
    "\n",
    "Drugi del naloge hoče, da poiščemo največje tri vsote in jih seštejemo.\n",
    "\n",
    "To najpreprosteje naredimo tako, da zložimo vse vsote v seznam, ga uredimo in seštejemo največje tri.\n",
    "\n",
    "Rešitve bodo podobne prejšnjim, zato pokažimo le prvo in zadnjo. Vse ostale so pač med njima. :)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "876fd6cf",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "199628\n"
     ]
    }
   ],
   "source": [
    "vsote = []\n",
    "for skupina in open(\"input.txt\").read().split(\"\\n\\n\"):\n",
    "    vsota = 0\n",
    "    for vrstica in skupina.splitlines():\n",
    "        vsota += int(vrstica)\n",
    "    vsote.append(vsota)\n",
    "print(sum(sorted(vsote)[-3:]))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f9540245",
   "metadata": {},
   "source": [
    "`sorted` vrne urejen seznam. Vzamemo elemente od predpredzadnjega (`-3`) do konca in seštevamo.\n",
    "\n",
    "Pa še po vzoru zadnje rešitve:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "6791a3bd",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "199628\n"
     ]
    }
   ],
   "source": [
    "print(sum(sorted(skupine(\"input.txt\"))[-3:]))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b2784ec2",
   "metadata": {},
   "source": [
    "`sorted(skupine(\"input.txt\"))` uredi vse, kar zgenerira `skupine`. In potem spet vzamemo zadnje tri in seštejemo."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6d0e17b3",
   "metadata": {},
   "source": [
    "### Seznam treh\n",
    "\n",
    "Tule preberemo in urejamo vse. Urejanje je v splošnem počasna operacija. Nas zanimajo samo prvi trije.\n",
    "\n",
    "Lahko naredimo tako: najprej pripravimo seznam vsot. Lahko tako, kot v preprostejši rešitvi drugega dela (se pravi, obdržimo vse, kar je v zanki), lahko pa uporabimo generator iz drugega dela in napišemo kar"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "0b24380c",
   "metadata": {},
   "outputs": [],
   "source": [
    "vsote = list(skupine(\"input.txt\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "35dca0fc",
   "metadata": {},
   "source": [
    "Kakorkoli že, `vsote` zdaj vsebuje tri vsote. Nato poberemo tri največje."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "78238ae4",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "199628\n"
     ]
    }
   ],
   "source": [
    "vsota = 0\n",
    "for _ in range(3):\n",
    "    naj = max(vsote)\n",
    "    vsota += naj\n",
    "    vsote.remove(naj)\n",
    "print(vsota)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6f965801",
   "metadata": {},
   "source": [
    "Tole gre šestkrat čez celoten seznam - enkrat zaradi `max`, enkrat zaradi `remove`. Je to boljše, hitrejše od urejanja? Odvisno od tega, koliko skupin imamo. Ker sodobni jeziki uporabljajo hitre algoritme urejanja, bo do nekaj sto skupin hitreje, če urejamo. Od ondod do neskočnosti pa je hitreje takole. (Teorija: čas izvajanja gornjega programa je sorazmeren številu skupin - označimo ga z n. Za dvakrat več skupin porabi dvakrat več časa. Čas urejanja pa je (običajno, v praksi) sorazmeren $n \\log n$, torej narašča hitreje kot linearno, zato je od določenega števila skupin naprej gornji program hitrejši.)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "31a709f1",
   "metadata": {},
   "source": [
    "Če se želimo izogniti večkratnim prehodom čez vsot, ohranjujmo največje tri."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "e95d680a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "199628\n"
     ]
    }
   ],
   "source": [
    "vsote = list(skupine(\"input.txt\"))\n",
    "\n",
    "naj3 = []\n",
    "for vsota in vsote:\n",
    "    naj3 = sorted(naj3 + [vsota])[-3:]\n",
    "print(sum(naj3))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a7bb4a63",
   "metadata": {},
   "source": [
    "Tule je `naj3` seznam, ki vsebuje največje tri vsote (oziroma kakšno manj, v začetku). V vsakem koraku dodamo novo vsoto, ga uredimo in obdržimo le večje tri.\n",
    "\n",
    "Je to hitrejše? V teoriji je, saj `sorted` vedno kličemo le na seznamih s štirimi (ali, v začetku, celo manj) elementi. Torej čas izvajanja `sorted` ni odvisen od števila skupin.\n",
    "\n",
    "V praksi? Dvomim. In: komu mar. :)\n",
    "\n",
    "Tole bi se dalo še poljubno zaplesti, tako da bi namesto seznama uporabljali kopico. Ampak pustimo."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f3aee2de",
   "metadata": {},
   "source": [
    "## Kotlin\n",
    "\n",
    "Še enkrat poglejmo rešitev v eni vrstici."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "de12c9ec",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "67633\n"
     ]
    }
   ],
   "source": [
    "print(\n",
    "    max(sum(int(vrstica) for vrstica in skupina.splitlines())\n",
    "        for skupina in open(\"input.txt\").read().split(\"\\n\\n\")\n",
    "       )\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "80e757a3",
   "metadata": {},
   "source": [
    "Čeprav ji lahko priznamo učinkovitost, moramo potožiti, da ni ravno berljiva. Problem je v tem, da jo je potrebno brati ritensko. Preberimo kodo, od leve proti desni. Ta funkcija nekaj izpiše. In sicer maksimum. Maksimum česa? Vsot. Vsot česa? `int`-ov. `int`-ov iz česa? Vrstic skupin. Kakšnih skupin, takšnih, ki jih dobimo, če preberemo datoteko in dobljeni niz razcepimo po `\\n\\n`.\n",
    "\n",
    "Najprej se zgodi tisto, kar je napisano nazadnje, in potem se stvari dogajajo, no, od desne proti levi. V resnici razcepimo niz po `\\n\\n`, nato to razbijemo na vrstice, za vsako vrstico pokličemo `int`, nato zberemo vsote teh intov in izračunamo njihov maksimum. Če poskušate slediti temu stavku po kodi, boste videli, da smo zdaj prebrali kodo ritensko.\n",
    "\n",
    "Python ima zelo lepo sintakso generatorjev ter izpeljanih seznamov, množic in slovarjev, ko to zlagamo v večje strukture, pa gre vse v napačno smer.\n",
    "\n",
    "Poglejmo isti program v Kotlinu.\n",
    "\n",
    "```kotlin\n",
    "import java.io.File\n",
    "\n",
    "val vsote = File(\"input.txt\")\n",
    "    .readText()\n",
    "    .trim()\n",
    "    .split(\"\\n\\n\")\n",
    "    .map {\n",
    "        it.split(\"\\n\")\n",
    "        .map { it.toInt() }\n",
    "        .sum()\n",
    "    }\n",
    "\n",
    "\n",
    "println(vsote.maxOrNull()!!)\n",
    "println(vsote.sorted().takeLast(3).sum())\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "26d70600",
   "metadata": {},
   "source": [
    "```kotlin\n",
    "import java.io.File\n",
    "\n",
    "val chunks = File(\"input.txt\")\n",
    "    .readText()\n",
    "    .trim()\n",
    "    .split(\"\\n\\n\")\n",
    "    .map {\n",
    "        it.split(\"\\n\")\n",
    "            .sumOf { it.toInt() }\n",
    "    }\n",
    "\n",
    "\n",
    "println(chunks.maxOrNull()!!)\n",
    "println(chunks.sorted().takeLast(3).sum())\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6f2fb171",
   "metadata": {},
   "source": [
    "Vem, da Kotlina (večinoma) ne znamo, ampak koda je tako lepa, da jo lahko vseeno kar preberemo. Predvsem bomo videli, kako različna je od Pythonove.\n",
    "\n",
    "Odpremo datoteko. Preberemo besedilo. `trim()` je isto kot Pythonov `split`; tule ga potrebujemo, da odbijemo `\\n` na koncu datoteke, ki bi sicer povzročal težave kasneje. Dobljeno reč razbujemo glede na `\\n\\n`. Tako dobimo seznam skupin. Na vsaki skupini naredimo naslednje: razbijemo jo glede na `\\n`. Tako dobimo seznam vrstic. Na vsakem elementu pokličemo `toInt`. Dobimo seznam števil. Ta seštejemo.\n",
    "\n",
    "Tako pridemo do seznama vsot. Sledita `println`, ki izpišeta rešitev prvega in drugega dela naloge.\n",
    "\n",
    "Malo bolj lepo bi se sicer napisalo tako:"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3a654943",
   "metadata": {},
   "source": [
    "```kotlin\n",
    "import java.io.File\n",
    "\n",
    "val chunks = File(\"input.txt\")\n",
    "    .readText()\n",
    "    .trim()\n",
    "    .split(\"\\n\\n\")\n",
    "    .map {\n",
    "        it.lines()\n",
    "            .sumOf { it.toInt() }\n",
    "    }\n",
    "\n",
    "\n",
    "println(chunks.maxOrNull()!!)\n",
    "println(chunks.sorted().takeLast(3).sum())\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "86fef48d",
   "metadata": {},
   "source": [
    "In najbrž gre še lepše, ampak jaz nisem ravno veliko poznavalec Kotlina. In sploh je tule še nekaj tehničnih detajlov, ki jih ne razumemo, ker pač ne znamo Kotlina. (Predvsem: tisto v zavitih oklepajih so lambda-funkcije, ki jih podamo kot argument funkcijama `map` in `sumOf`; in če ima le-ta le en argument, ki ga ne navedemo eksplicitno, mu je ime `it`).\n",
    "\n",
    "Vendar to ni pomembno, pomembno je, da vidimo, kako to teče lepše od Pythona. Čeprav je ideja programa natančno ista, teče zelo lepo od začetka proti koncu, od zgoraj navzdol, tako kot ga beremo.\n",
    "\n",
    "Kotlin ni niti približno edini jezik, ki omogoča takšno pisanje programov (če ne drugega, je v tem kar močan tudi JavaScript), je pa eden močnejših. In, za moj okus, lep."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}