p1/domace-naloge/2020/11 sestavljanka/resitev.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Sestavljanka\n",
    "\n",
    "V tej nalogi bomo sestavljali sestavljanke. Takšne.\n",
    "\n",
    "```\n",
    "                                     /;    ;\\\n",
    "                                   __  \\\\____//\n",
    "                                  /{_\\_/   `'\\____\n",
    "                                  \\___   (o)  (o  }\n",
    "       _____________________________/          :--'\n",
    "   ,-,'`@@@@@@@@       @@@@@@         \\_    `__\\\n",
    "  ;:(  @@@@@@@@@        @@@             \\___(o'o)\n",
    "  :: )  @@@@          @@@@@@        ,'@@(  `===='\n",
    "  :: : @@@@@:          @@@@         `@@@:\n",
    "  :: \\  @@@@@:       @@@@@@@)    (  '@@@'\n",
    "  ;; /\\      /`,    @@@@@@@@@\\   :@@@@@)\n",
    "  ::/  )    {_----------------:  :~`,~~;\n",
    " ;;'`; :   )                  :  / `; ;\n",
    ";;;; : :   ;                  :  ;  ; :\n",
    "`'`' / :  :                   :  :  : :\n",
    "    )_ \\__;      \";\"          :_ ;  \\_\\       `,','\n",
    "    :__\\  \\    * `,'*         \\  \\  :  \\   *  8`;'*  *\n",
    "        `^'     \\ :/           `^'  `-^-'   \\v/ :  \\/\n",
    "```\n",
    "\n",
    "(Inspiracija prihaja iz [Advent of Code](https://adventofcode.com/), naloga [Jurassic Jigsaw](https://adventofcode.com/2020/day/20), vendar je narejena na novo.)\n",
    "\n",
    "Kako so videti posamezni koščki, si lahko pogledate v priloženih datotekah. V programu jih bomo zapisovali s terkami nizov. Košček\n",
    "\n",
    "```\n",
    "Qm55\n",
    "7 _H\n",
    "2o\\R\n",
    "H3cc\n",
    "```\n",
    "\n",
    "torej zapišemo kot "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "kos = (\"Qm55\", \"7 _H\", \"2o\\R\", \"H3cc\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Iz teh koščkov se da sestaviti sestavljanko, s tem da je potrebno koščke vrteti in celo zrcaliti. Ko jo sestavimo, bo potrebno še odbiti robove, ki niso del slike - od gornjega koščka bo ostal samo srednji kvadrat 2x2:\n",
    "\n",
    "```\n",
    " _\n",
    "o\\\n",
    "```\n",
    "\n",
    "A do tam pridemo šele pri oceni 10; šli pa bomo lepo počasi.\n",
    "\n",
    "1. **Pretvarjanje v terko:** če imamo seznam `s` in potrebujemo terko `s`, uporabimo `tuple(s)`. Toliko, da me ne boste spraševali vsak posebej. :)\n",
    "\n",
    "2. **Vzvratne poševnice:** V spodnjih izpisih so vzvratne poševnice zaradi preglednosti napisane z enim samim znakom. V testih sta po dve, ker, vemo, napišeš dve in dobiš eno.\n",
    "\n",
    "3. **Oblika sestavljank:** vsi koščki so kvadratni. Same sestavljanke pa so pravokotne, ne pa nujno kvadratne. Gornja krava je bolj dolga kot visoka.\n",
    "\n",
    "4. Naloga ni tako težka, zato ker jo bomo reševali po korakih in vse lepo sproti testirali. Držite se navodil in ko programirate določeno funkcijo, razmišljajte o tem, zakaj sem vam dal sprogramirati tiste prej. Ne uporabljajte pa jih vedno in na silo.\n",
    "\n",
    "## Testi\n",
    "\n",
    "Testi in datoteke: [sestavljanka.zip](https://github.com/janezd/predavanja/raw/master/p1/domace-naloge/2020/11%20sestavljanka/testi-sestavljanka.zip).\n",
    "\n",
    "\n",
    "## Za oceno 6\n",
    "\n",
    "-  Napiši funkcijo `zrcaljen_navp(kos)`, ki vrne navpično prezrcaljen košček. Za košček iz uvoda v nalogo vrne\n",
    "\n",
    "    ```\n",
    "    (\"H3cc\",\n",
    "     \"2o\\R\",\n",
    "     \"7 _H\",\n",
    "     \"Qm55\")\n",
    "    ```\n",
    "\n",
    "- Napiši funkcijo `zrcaljen_vod(kos)`, ki prejme košček in vrne vodoravno prezrcaljen košček. Za gornji košček vrne\n",
    "\n",
    "    ```\n",
    "    (\"55mQ\",\n",
    "     \"H_ 7\",\n",
    "     \"R\\o2\",\n",
    "     \"cc3H\")\n",
    "    ```\n",
    "\n",
    "-  Napiši funkcijo `obrnjen(kos)`, ki vrne košček, obrnjen za 90 stopinj v smeri urinega kazalca. Za košček iz uvoda v nalogo vrne\n",
    "\n",
    "    ```\n",
    "    ('H27Q',\n",
    "     '3o m',\n",
    "     'c\\_5',\n",
    "     'cRH5')\n",
    "     ```\n",
    "\n",
    "    V gornji vrstici se pojavi, kar je bil prej levi rob. Gornja vrstica je postala desni rob...\n",
    "\n",
    "-  Napiši funkcijo `obrnjen_n(kos, n)`, ki vrne košček, ki je n-krat obrnjen za 90 stopinj v smeri urinega kazalca. Košček in število obratov sta lahko tudi precej velika.\n",
    "\n",
    "- Napiši funkcijo `stranice(kos)`, ki vrne seznam s stranicami kosa v naslednjem vrstnem redu: gornja, desna, spodnja (od leve proti desni!), leva (od zgoraj navzdol) in nato še zrcaljena gornja, desna, spodnja in leva. Pozorno poglej tale primer: za košček iz primera,\n",
    "\n",
    "    ```\n",
    "    Qm55\n",
    "    7 _H\n",
    "    2o\\R\n",
    "    H3cc\n",
    "    ```\n",
    "\n",
    "    mora vrniti `['Qm55', '5HRc', 'H3cc', 'Q72H', '55mQ', 'cRH5', 'cc3H', 'H27Q']`.\n",
    "\n",
    "- Napiši funkcijo `obrati(kos)`, ki vrne množico vseh koščkov, ki jih je mogoče dobiti z obračanjem in zrcaljenjem podanega koščka. Za gornji košček vrne\n",
    "\n",
    "    ```\n",
    "    {('55mQ', 'H_ 7', 'R\\o2', 'cc3H'),\n",
    "     ('5HRc', '5_\\c', 'm o3', 'Q72H'),\n",
    "     ('H27Q', '3o m', 'c\\_5', 'cRH5'),\n",
    "     ('H3cc', '2o\\R', '7 _H', 'Qm55'),\n",
    "     ('Q72H', 'm o3', '5_\\c', '5HRc'),\n",
    "     ('Qm55', '7 _H', '2o\\R', 'H3cc'),\n",
    "     ('cRH5', 'c\\_5', '3o m', 'H27Q'),\n",
    "     ('cc3H', 'R\\o2', 'H_ 7', '55mQ')}\n",
    "    ```\n",
    "\n",
    "### Rešitev\n",
    "\n",
    "Prva naloga je bila naloga iz dela s seznami. Reševali pa jo bomo z izpeljanimi seznami; ker smo že dovolj stari.\n",
    "\n",
    "Za lažje opazovanje dogajanja si napišimo funkcijo, ki izpiše dva kosa: `izpisi(kos1, kos2)`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def izpisi(kos1, kos2):\n",
    "    for v1, v2 in zip(kos1, kos2):\n",
    "        print(v1, \"    \", v2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### `zrcali_navp`\n",
    "\n",
    "Tu je potrebno le obrniti terko vrstic."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def zrcaljen_navp(kos):\n",
    "    return kos[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Qm55      H3cc\n",
      "7 _H      2o\\R\n",
      "2o\\R      7 _H\n",
      "H3cc      Qm55\n"
     ]
    }
   ],
   "source": [
    "izpisi(kos, zrcaljen_navp(kos))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### `zrcaljen_vod`\n",
    "\n",
    "Tu pa je potrebno sestaviti seznam obrnjenih vrstic. Pravzaprav ne seznama, temveč terko."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def zrcaljen_vod(kos):\n",
    "    return tuple(x[::-1] for x in kos)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Qm55      55mQ\n",
      "7 _H      H_ 7\n",
      "2o\\R      R\\o2\n",
      "H3cc      cc3H\n"
     ]
    }
   ],
   "source": [
    "izpisi(kos, zrcaljen_vod(kos))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`x[::-1] for x in kos` je generator in ta generator podamo kot argument funkciji (tipu, konstruktorju, kakor mu že hočete reči) `tuple`, da iz generiranih elementov sestavi terko.\n",
    "\n",
    "#### `obrnjen`\n",
    "\n",
    "Ta je pa malo bolj sitna. Ne posebej imenitna rešitev je takšna."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def obrnjen(kos):\n",
    "    obrnjeni = ()\n",
    "    for stolpec in range(len(kos)):\n",
    "        nova_vrstica = \"\"\n",
    "        for vrstica in kos[::-1]:\n",
    "            nova_vrstica += vrstica[stolpec]\n",
    "        obrnjeni = obrnjeni + (nova_vrstica, )\n",
    "    return obrnjeni"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "V seznam `obrnjeni` nabiramo nove vrstice. V začetku bo to prazna terka, nato bomo vanjo z `obrnjeni = obrnjeni + (nova_vrstica, )` dodajali nove vrstice. Reč je kar sitna: terke so nespremenljive, torej nimajo metode `append`. Z `obrnjeni = ...` v bistvu priredimo imenu `obrnjeni` novo terko, ki je vsota tega, kar je bilo v tej terki doslej in terke, ki vsebujejo novo vrstico `(nova_vrstica, )`. Če bi pisali le `obrnjeni + nova_vrstica`, to ne bi delovalo, ker Python ne more sešteti terke `obrnjeni` in niza `nova_vrstica`. Če bi pisali `obrnjeni + (nova_vrstica)` (brez vejice) pa ne bi šlo, ker je `(nova_vrstica)` isto kot `nove_vrstica`, le da traja nanosekundo dlje, ker se Python vmes začudi, zakaj smo dali to ime v oklepaj.\n",
    "\n",
    "Drug način je, da je `obrnjeni` seznam, `obrnjeni = []`. Potem vrstice dodajamo kar s `obrnjeni.append(nova_vrstica)`, zadnjo vrstico pa spremenimo v `return tuple(obrnjeni)`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def obrnjen(kos):\n",
    "    obrnjeni = []\n",
    "    for stolpec in range(len(kos)):\n",
    "        nova_vrstica = \"\"\n",
    "        for vrstica in kos[::-1]:\n",
    "            nova_vrstica += vrstica[stolpec]\n",
    "        obrnjeni.append(nova_vrstica)\n",
    "    return tuple(obrnjeni)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Da, tako je morda še lažje.\n",
    "\n",
    "Novo vrstico pa sestavljamo tako, da pripravimo prazen niz. Nato gremo čez vse bodoče stolpce (za kar bi morali pravzaprav pisati `range(len(kos[0]))`, vendar so koščki kvadratni, zato je `len(kos)` vedno enako `len(kos[0])`. Pri vsakem stolpcu gremo čez vse vrstice obstoječega kosa, vendar od spodaj navzgor. Pobiramo črke na ustreznem stolpcu in jih zlagamo v niz."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Qm55      H27Q\n",
      "7 _H      3o m\n",
      "2o\\R      c\\_5\n",
      "H3cc      cRH5\n"
     ]
    }
   ],
   "source": [
    "izpisi(kos, obrnjen(kos))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Neneobičajna komplikacija, ki se je domislijo študenti, je takšna."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def obrnjen(kos):\n",
    "    obrnjeni = []\n",
    "    nova_vrstica = \"\"  # Zakaj že tu?!\n",
    "    \n",
    "    for stolpec in range(len(kos)):\n",
    "        nova_vrstica = \"\"\n",
    "        for vrstica in kos[::-1]:\n",
    "            nova_vrstica += vrstica[stolpec]\n",
    "        obrnjeni.append(nova_vrstica)\n",
    "        nova_vrstica = \"\"  # To moramo dodati za kazen...\n",
    "    return tuple(obrnjeni)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tu na začetku funkcije pripravimo prazno novo vrstico in jo pobrišemo po tem, ko jo uporabimo. Čeprav to deluje, je logika nekako ... izkrivljena. C-jevska. Pripravimo prostor, ga polnimo in praznimo. V gornji, preprostejši rešitvi, pa znotraj zanke `for stolpec ...` pripravimo vrstico in jo napolnimo.\n",
    "\n",
    "Zdaj pa skrajšajmo to funkcijo. Črke po stolpcih lahko poberemo z `vrstica[stolpec] for vrstica in kos[::-1]`. To damo metodi `\"\".join`, da jih združi, torej"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def obrnjen(kos):\n",
    "    obrnjeni = []\n",
    "    for stolpec in range(len(kos)):\n",
    "        nova_vrstica = \"\".join(vrstica[stolpec] for vrstica in kos[::-1])\n",
    "        obrnjeni.append(nova_vrstica)\n",
    "    return tuple(obrnjeni)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Qm55      H27Q\n",
      "7 _H      3o m\n",
      "2o\\R      c\\_5\n",
      "H3cc      cRH5\n"
     ]
    }
   ],
   "source": [
    "izpisi(kos, obrnjen(kos))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Odtod pa, očitno"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "def obrnjen(kos):\n",
    "    return tuple(\n",
    "        \"\".join(vrstica[stolpec] for vrstica in kos[::-1])\n",
    "        for stolpec in range(len(kos))\n",
    "    )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Qm55      H27Q\n",
      "7 _H      3o m\n",
      "2o\\R      c\\_5\n",
      "H3cc      cRH5\n"
     ]
    }
   ],
   "source": [
    "izpisi(kos, obrnjen(kos))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Radovedni pa bodo raziskali, kako deluje tole:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "def obrnjen(kos):\n",
    "    return zrcaljen_vod(map(\"\".join, zip(*kos)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Qm55      H27Q\n",
      "7 _H      3o m\n",
      "2o\\R      c\\_5\n",
      "H3cc      cRH5\n"
     ]
    }
   ],
   "source": [
    "izpisi(kos, obrnjen(kos))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### `obrnjen_n`\n",
    "\n",
    "Eden od testov je poskušal 10000000000000001-krat obrniti kos velikosti 100x100, kar namiguje na to, da si bo potrebno izmisliti bližnjico. V vprašanjih študentov sem videl kup zanimivih ugibanj, resnica pa je preprosta: če list papirja štirikrat obrnemo za 90 stopinj, bo obnjen tako, kot je bil v začetku. In če ga obrnemo n-krat, lahko preskočimo 4 * bogveliko vrtenj. Zanima nas le ostanek po deljenju s štiri. Ne liha in soda in podobno. Če ga obrnemo 10000000000000001-krat je to isto, kot če smo ga 1-krat. Če ga 10000000000000003-krat, je isto, kot če ga 3-krat. In če ga `n`-krat, je isto, kot če ga `n % 4`-krat.\n",
    "\n",
    "To sem potem videl sprogramirano na veliko zanimivih načinov -- pretežno z nekimi zankami `while` v temu duhu:\n",
    "\n",
    "```python\n",
    "while n != 0:\n",
    "    kos = obrnjen(kos)\n",
    "    n = n % 4 - 1\n",
    "```\n",
    "\n",
    "Ena in edina prava rešitev je"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "def obrnjen_n(kos, n):\n",
    "    for i in range(n % 4):\n",
    "        kos = obrnjen(kos)\n",
    "    return kos"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vseh druge rešitve te naloge je že davno, res davno, nekdo povsem pravilno pokomentiral z \"*kar je več, je od hudega*\".\n",
    "\n",
    "#### `stranice`\n",
    "\n",
    "Še ena vaja iz seznamov. In izpeljanih seznamov.\n",
    "- gornja: `kos[0]`;\n",
    "- desna: `vrstica[-1] for vrstica in kos`; združiti jim moramo v nov niz, torej `\"\".join(vrstica[-1] for vrstica in kos)`, seveda pa obstajajo tudi daljši načini;\n",
    "- spodnja: `kos[-1]`;\n",
    "- leva: `vrstica[0] for vrstica in kos`.\n",
    "Tako dobimo prve štiri. Damo jih v seznam; ostale štiri dobimo kot obrnjene elemente tega seznama."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "def stranice(kos):\n",
    "    t = [kos[0],\n",
    "         \"\".join(vrstica[-1] for vrstica in kos),\n",
    "         kos[-1],\n",
    "         \"\".join(vrstica[0] for vrstica in kos),\n",
    "         ]\n",
    "    return t + [x[::-1] for x in t]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Qm55      \n",
      "7 _H      \n",
      "2o\\R      \n",
      "H3cc      \n"
     ]
    }
   ],
   "source": [
    "izpisi(kos, [\"\"] * 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['Qm55', '5HRc', 'H3cc', 'Q72H', '55mQ', 'cRH5', 'cc3H', 'H27Q']"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "stranice(kos)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### `obrati`\n",
    "\n",
    "Še zadnja funkcija za oceno 6. Košček je potrebno štirikrat obrniti, zrcaliti in še štirikrat obrniti, ter vse pridno zlagati v množico."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "def obrati(kos):\n",
    "    vsi_obrati = set()\n",
    "    for i in range(2):\n",
    "        for j in range(4):\n",
    "            vsi_obrati.add(kos)\n",
    "            kos = obrnjen(kos)\n",
    "        kos = zrcaljen_navp(kos)\n",
    "    return vsi_obrati"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "V množici, ki jo dobimo, so res vsi obrati, v nekem naključnem vrstnem redu. Ker gre pač za množico.\n",
    "\n",
    "(S tem, kako deluje spodnji izpis, naj se zabavajo tisti, ki jih to zanima.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Qm55    H3cc    H27Q    cc3H    cRH5    5HRc    55mQ    Q72H\n",
      "7 _H    2o\\R    3o m    R\\o2    c\\_5    5_\\c    H_ 7    m o3\n",
      "2o\\R    7 _H    c\\_5    H_ 7    3o m    m o3    R\\o2    5_\\c\n",
      "H3cc    Qm55    cRH5    55mQ    H27Q    Q72H    cc3H    5HRc\n"
     ]
    }
   ],
   "source": [
    "for vrstice in zip(*obrati(kos)):\n",
    "    print(\"    \".join(vrstice))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Vse funkcije za oceno 6\n",
    "\n",
    "Da dolžina gornjih opisov ne bi pustila vtisa, da je bili potrebno za oceno 6 sprogramirati tisoč vrstic kode:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Funkcije za oceno 6\n",
    "\n",
    "def zrcaljen_vod(kos):\n",
    "    return tuple(x[::-1] for x in kos)\n",
    "\n",
    "\n",
    "def zrcaljen_navp(kos):\n",
    "    return kos[::-1]\n",
    "\n",
    "\n",
    "def obrnjen(kos):\n",
    "    return tuple(\"\".join(vrstica[i] for vrstica in kos[::-1])\n",
    "                 for i in range(len(kos)))\n",
    "\n",
    "\n",
    "def obrnjen_n(kos, n):\n",
    "    for i in range(n):\n",
    "        kos = obrnjen(kos)\n",
    "    return kos\n",
    "\n",
    "\n",
    "def stranice(kos):\n",
    "    t = [kos[0],\n",
    "         \"\".join(vrstica[-1] for vrstica in kos),\n",
    "         kos[-1],\n",
    "         \"\".join(vrstica[0] for vrstica in kos),\n",
    "         ]\n",
    "    return t + [x[::-1] for x in t]\n",
    "\n",
    "\n",
    "def obrati(kos):\n",
    "    vsi_obrati = set()\n",
    "    for i in range(2):\n",
    "        for j in range(4):\n",
    "            vsi_obrati.add(kos)\n",
    "            kos = obrnjen(kos)\n",
    "        kos = zrcaljen_navp(kos)\n",
    "    return vsi_obrati\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Za oceno 7\n",
    "\n",
    "- Napiši funkcijo `preberi_datoteko(ime_datoteke)`, ki prebere koščke iz podane datoteke. Vrniti mora seznam koščkov, torej seznam terk nizov, na primer\n",
    "\n",
    "    ```\n",
    "    [('bmq8', 'b__8', 'O__s', 'fyuX'),\n",
    "     ('Qm55', '7 _H', '2o\\R', 'H3cc'),\n",
    "     ('cj97', 'c  7', 'x \\m', 'KZ9K'),\n",
    "     ... in tako naprej\n",
    "    ```\n",
    "\n",
    "- Napiši funkcijo `zbirka_stranic(kosi)`, ki prejme seznam koščkov (tak, kot ga vrača gornja funkcija). Vrniti mora slovar, katerega ključi so vse možne stranice (vključno s prezrcaljenimi), pripadajoče vrednosti pa so množice koščkov, ki vsebujejo takšno stranico.\n",
    "\n",
    "    ```\n",
    "    {'bmq8': {('bmq8', 'b__8', 'O__s', 'fyuX'),\n",
    "              ('8J99', 'q_ k', 'm_ 2', 'bUee')},\n",
    "     '88sX': {('XH00', 's)_P', '8  H', '8v2H'),\n",
    "              ('bmq8', 'b__8', 'O__s', 'fyuX')},\n",
    "     'fyuX': {('bmq8', 'b__8', 'O__s', 'fyuX')},\n",
    "     'bbOf': {('o855', 'A__Y', 'X__j', 'fObb'),\n",
    "              ('bmq8', 'b__8', 'O__s', 'fyuX')},\n",
    "     ... in tako naprej\n",
    "    ```\n",
    "\n",
    "    Stranica `\"bmq8\"` je zgornja stranica koščka v prvi vrstici in zrcaljena leva stranica koščka v drugi vrstici (od leve proti desni preberemo prve črke nizov v drugi terki).\n",
    "\n",
    "    V množicah naj se koščki pojavljajo v svojih originalnih legah - takšnih, ko so v podanem seznamu - in ne obrnjeni ali zrcaljeni.\n",
    "\n",
    "    Vsak košček se pojavi v osmih različnih množicah - toliko, kolikor različnih stranih ima (skupaj z zrcaljenimi).\n",
    "\n",
    "    (Tale opis je dolg, sama funkcija pa ima pet vrstic, brez kakšnih fint z izpeljanim čemerkoli.)\n",
    "\n",
    "    Opazil(a) boš nekaj prijetnega: vsaka množica vsebuje le en ali dva koščka. Kaj to pomeni, razmisli sam(a). Še preden greš naprej.\n",
    "    \n",
    "### Rešitev\n",
    "\n",
    "#### `preberi_datoteko`\n",
    "\n",
    "Povsem običajna rešitev je takšna."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "def preberi_datoteko(ime_dat):\n",
    "    kosi = []\n",
    "\n",
    "    trenutni = []\n",
    "    for vrstica in open(ime_dat):\n",
    "        vrstica = vrstica.strip()\n",
    "        if not vrstica:\n",
    "            kosi.append(tuple(trenutni))\n",
    "            trenutni = []\n",
    "        else:\n",
    "            trenutni.append(vrstica)\n",
    "\n",
    "    kosi.append(tuple(trenutni))\n",
    "    return kosi"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`kosi` bo seznam kosov, ki ga bomo vrnili, v `trenutni` pa bomo med branjem nabirali vrstice trenutnega kosa.\n",
    "\n",
    "Gremo po vrsticah datoteke. Od-`strip`-amo `\\n` na koncu vrstice. Če je vrstica s tem prazna, je trenutni kos končan in ga (pretvorjenega v terko) dodamo v seznam kosov ter pripravimo nov `trenutni`. Če vrstica še ni prazna, pa dodamo vrstico v `trenutni` kos.\n",
    "\n",
    "Ko je zanka končana, s `kosi.append(tuple(trenutni))` dodamo še zadnji kos.\n",
    "\n",
    "Datoteka je oblikovana tako, da pred prvim in za zadnjim kosom ni praznih vrstic. Ako bi ne bilo tako, bi morali popaziti še na primere, kot je `trenutni` prazen.\n",
    "\n",
    "Zanimivo je, da smo tu naredili natančno tisto, o čemer sem pri `obrnjen` tožil, naj ne počnemo. Tam je bilo potrebno polniti in prazniti vrstico, če smo jo pripravili pred zanko. Tu se temu ne da izogniti, saj imamo le eno zanko."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('bmq8', 'b__8', 'O__s', 'fyuX'),\n",
       " ('Qm55', '7 _H', '2o\\\\R', 'H3cc'),\n",
       " ('cj97', 'c  7', 'x \\\\m', 'KZ9K'),\n",
       " ('KZ9K', 'K /K', 'a )O', 'OY04'),\n",
       " ('QRbK', 'Q= K', 'h_mO', '41K4'),\n",
       " ('8J99', 'q_ k', 'm_ 2', 'bUee'),\n",
       " ('ww2F', 'J  n', 'M  y', 'YYTq'),\n",
       " ('XH00', 's)_P', '8  H', '8v2H'),\n",
       " ('o855', 'A__Y', 'X__j', 'fObb'),\n",
       " ('qqzn', '6/_c', '2~_1', '558o'),\n",
       " ('Qm55', 'Ro/k', 'b \\\\C', 'Km77'),\n",
       " ('5vOO', 'Y_ V', 'j_ f', 'bUee'),\n",
       " ('YYTq', 'T  6', 'P  2', 'OOv5'),\n",
       " ('9J6c', '9 /c', 'J/ 3', '8v2H'),\n",
       " ('FF84', 'n  M', 'y (J', 'qqzn'),\n",
       " ('HHP0', '2=_E', '7ømw', 'QQh4')]"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "preberi_datoteko(\"muc-puzzle.txt\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Funkcijo se da napisati tudi precej preprosteje. Tu so bili v prednosti tisti, ki so morda brali moje [rešitve Advent of Code](https://github.com/janezd/predavanja/tree/master/p1/advent%20of%20code/2020). Tam smo letos pogosto srečali podatke, ločene s prazno vrstico. Prvič v nalogi [Password Processing](https://github.com/janezd/predavanja/blob/master/p1/advent%20of%20code/2020/04%20Passport%20Processing/resitev.ipynb). Trik je `open(ime_dat).read().split(\"\\n\\n\")`: preberemo celo vsebino datoteke in jo razdelimo glede na `\\n\\n`, dva znaka za novo vrstico. Poglejmo, kaj dobimo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "bloki = open(\"muc-puzzle.txt\").read().split(\"\\n\\n\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vzemimo prvi blok in si ga oglejmo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'bmq8\\nb__8\\nO__s\\nfyuX'"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "prvi = bloki[0]\n",
    "\n",
    "prvi"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To reč je potrebno le še razdeliti glede na `\\n` ali kar s `splitlines()` in spremeniti v terko."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('bmq8', 'b__8', 'O__s', 'fyuX')"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tuple(prvi.splitlines())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Rešitev naloge je potem"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "def preberi_datoteko(ime_dat):\n",
    "    return [tuple(kos.splitlines())\n",
    "            for kos in open(ime_dat).read().split(\"\\n\\n\")]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('bmq8', 'b__8', 'O__s', 'fyuX'),\n",
       " ('Qm55', '7 _H', '2o\\\\R', 'H3cc'),\n",
       " ('cj97', 'c  7', 'x \\\\m', 'KZ9K'),\n",
       " ('KZ9K', 'K /K', 'a )O', 'OY04'),\n",
       " ('QRbK', 'Q= K', 'h_mO', '41K4'),\n",
       " ('8J99', 'q_ k', 'm_ 2', 'bUee'),\n",
       " ('ww2F', 'J  n', 'M  y', 'YYTq'),\n",
       " ('XH00', 's)_P', '8  H', '8v2H'),\n",
       " ('o855', 'A__Y', 'X__j', 'fObb'),\n",
       " ('qqzn', '6/_c', '2~_1', '558o'),\n",
       " ('Qm55', 'Ro/k', 'b \\\\C', 'Km77'),\n",
       " ('5vOO', 'Y_ V', 'j_ f', 'bUee'),\n",
       " ('YYTq', 'T  6', 'P  2', 'OOv5'),\n",
       " ('9J6c', '9 /c', 'J/ 3', '8v2H'),\n",
       " ('FF84', 'n  M', 'y (J', 'qqzn'),\n",
       " ('HHP0', '2=_E', '7ømw', 'QQh4')]"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "kosi = preberi_datoteko(\"muc-puzzle.txt\")\n",
    "\n",
    "kosi"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### `zbirka_stranic`\n",
    "\n",
    "To je preprosto: za vsak kos pokličemo `stranice`, da izvemo vse njegove stranice. To bodo ključi slovarja. Vrednosti bodo množice; v te množice (torej: tiste, množice, ki kot vrednosti pripadajo tem stranicam) dodamo ta kos. Seveda bomo uporabili `defaultdict`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import defaultdict\n",
    "\n",
    "def zbirka_stranic(kosi):\n",
    "    vse_stranice = defaultdict(set)\n",
    "    for kos in kosi:\n",
    "        for stranica in stranice(kos):\n",
    "            vse_stranice[stranica].add(kos)\n",
    "    return vse_stranice"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{('8J99', 'q_ k', 'm_ 2', 'bUee'), ('bmq8', 'b__8', 'O__s', 'fyuX')}"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "po_stranicah = zbirka_stranic(kosi)\n",
    "\n",
    "po_stranicah[\"bmq8\"]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nekateri študenti so to funkcijo napisali tako, da je bila bistveno počasnejša. Kako, ne vem. Zna biti, da so najprej nabrali množico vseh možnih stranic, nato pa za vsako stranico gledali, kateri kosi jo vsebujejo. To bi potencialno lahko vodilo v rešitev v eni vrstici. Oziroma v rešitev, ki bi lepo demonstrirala, zakaj so rešitve v eni vrstici lahko tudi slaba ideja. Takšni programi so bili namreč zelo počasni.\n",
    "\n",
    "### Vse funkcije za oceno 7\n",
    "\n",
    "Spet pokažimo, koliko je bilo v resnici tega programiranja. Toliko. :)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [],
   "source": [
    "def preberi_datoteko(ime_dat):\n",
    "    return [tuple(kos.splitlines())\n",
    "            for kos in open(ime_dat).read().split(\"\\n\\n\")]\n",
    "\n",
    "def zbirka_stranic(kosi):\n",
    "    vse_stranice = defaultdict(set)\n",
    "    for kos in kosi:\n",
    "        for stranica in stranice(kos):\n",
    "            vse_stranice[stranica].add(kos)\n",
    "    return vse_stranice"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Za oceno 8\n",
    "\n",
    "Po razmisleku o gornjem napiši naslednje funkcije.\n",
    "\n",
    "- Funkcija `kotni(kosi)` prejme vse kose sestavljanke (kot jih vrne `preberi_datoteko`) in vrne množico kosov, ki so v vogalih. Kosi naj ne bodo obrnjeni ali zavrteni, temveč takšni, kot so v seznamu kosi.\n",
    "\n",
    "    Če nimaš pojma, kako to napisati, ponovno preveri zadnji odstavek zadnje funkcija naloge za oceno 7.\n",
    "\n",
    "- Funkcija `robni(kosi)` vrne množico kosov, ki so na robovih sestavljanke (vendar ne v kotih). Če nimaš pojma, kako to napisati, potem ne vem, kako ti je uspelo napisati prejšnjo funkcijo. :)\n",
    "\n",
    "- Funkcija `prvi_kot(kosi)` vrne tisti, kot, pri katerem je prva vrstica prva po abecedi. Uporabljaj Pythonovo urejenost (števke pred črkami, velike črke pred malimi; z drugimi besedami, samo uporabljaj Pythonove funkcije in vse bo dobro).\n",
    "\n",
    "(Funkcij, ki jih pišeš tu, morda ne potrebuješ, so pa uporabne, če želiš kaj izvedeti o sestavljanki. In za dodatno nalogo onstran one za oceno 10.)\n",
    "\n",
    "### Rešitev\n",
    "\n",
    "Na koncu naloge za oceno 7 sem namignil, da je zanimivo opazovati množice v slovarju, ki ga vrne `zbirka_stranic`. Nekatere imajo en sam kos, nekatere dva. Stranice z enim samim kosom so na robu sestavljanke, tiste z dvema, so notranje.\n",
    "\n",
    "Robni in vogalni kosi so tisti kosi, ki imajo zunanje stranice, torej, ki nastopajo v množicah z enim samim elementom. \n",
    "\n",
    "Vogalni kosi imajo dve takšni, unikatni stranici. Vendar vsako stranico gledamo dvakrat - enkrat tako, kot se pojavi in drugič zrcaljeno. Torej se vogalni kosi štirikrat pojavijo v množici z enim samim elementom.\n",
    "\n",
    "Robni kosi imajo eno unikatno stranico, torej se dvakrat pojavijo v množici z enim samim elementom.\n",
    "\n",
    "Funkciji `robni` in `vogalni` si bosta očitno zelo podobni, torej napišimo funkcijo `_po_enojnih(kosi, n)`, ki vrne množico vseh kosov, ki se `n`-krat pojavijo v množici z enim elementov. Za `n = 2` bomo dobili stranice, za `n = 4` pa vogale."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "def _po_enojnih(kosi, n):\n",
    "    enojnih = defaultdict(int)\n",
    "    for m_kosov in zbirka_stranic(kosi).values():\n",
    "        if len(m_kosov) == 1:\n",
    "            enojnih[m_kosov.pop()] += 1\n",
    "    return {kos for kos, stevec in enojnih.items() if stevec == n}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Naredimo torej `zbirka_stranic` in gremo čez množice, `values()`. V `enojnih` štejemo, kolikokrat posamični kos nastopa v množici z enim samim elementom: če ima množica (`m_kosov`) le en element, ga s `pop` poberemo iz množice in povečamo ustrezen števec. Na koncu v množico naberemo tiste ključe `enojnih`, pri katerih je števec enak `1`.\n",
    "\n",
    "Ljubitelji jedrnatega izražanja vedo, da lahko za štetje uporabimo `Counter` in napišejo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "\n",
    "def _po_enojnih(kosi, n):\n",
    "    enojnih = Counter(m_kosov.pop()\n",
    "                      for m_kosov in zbirka_stranic(kosi).values()\n",
    "                      if len(m_kosov) == 1)\n",
    "    return {kos for kos, enojnih in enojnih.items() if enojnih == n}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ali, na tiste dni, ko se jim res tlači brez potrebe,"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "def _po_enojnih(kosi, n):\n",
    "    return {kos\n",
    "            for kos, stevec in Counter(m_kosov.pop()\n",
    "                                       for m_kosov in zbirka_stranic(kosi).values()\n",
    "                                       if len(m_kosov) == 1).items()\n",
    "            if stevec == n}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Rešitve za oceno 8\n",
    "\n",
    "Če `_po_enojnih` sprogramiramo ... razumno, je celotna rešitev naloge za oceno 8 takšna."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [],
   "source": [
    "def _po_enojnih(kosi, n):\n",
    "    enojnih = Counter(m_kosov.pop()\n",
    "                      for m_kosov in zbirka_stranic(kosi).values()\n",
    "                      if len(m_kosov) == 1)\n",
    "    return {kos for kos, stevec in enojnih.items() if stevec == n}\n",
    "\n",
    "\n",
    "def kotni(kosi):\n",
    "    return _po_enojnih(kosi, 4)\n",
    "\n",
    "def robni(kosi):\n",
    "    return _po_enojnih(kosi, 2)\n",
    "\n",
    "def prvi_kot(kosi):\n",
    "    return min(kotni(kosi))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Za oceno 9\n",
    "\n",
    "- Funkcija `preobrni(kos, levo, gor, po_stranicah)` prejme kos sestavljanke, podatek o tem, kaj mora biti levo in zgoraj, ter slovar `po_stranicah`, ki je takšen, kot ga vrača funkcija `zbirka_stranic`. Vrniti mora kos, ki ga dobi z vrtenjem in/ali zrcaljenjem podanega kosa tako, da le-ta ustreza pogojema `levo` in `gor`.\n",
    "\n",
    "    Argumenta `levo` in `gor` povesta, kakšna morata biti leva in zgornja stranica vrnjenega kosa. Če je argument enak `1`, to pomeni, da mora biti `leva` oz `gor`-nja stranica robna stranica. Če je argument niz, pa pove, kakšna mora biti stranica.\n",
    "\n",
    "    Klic\n",
    "\n",
    "    ```\n",
    "    preobrni((\"Qm55\",\n",
    "              \"7 _H\",\n",
    "              \"2o\\R\",\n",
    "              \"H3cc\"), \"cc3H\", 1, po_stranicah)\n",
    "    ```\n",
    "\n",
    "    vrne\n",
    "\n",
    "    ```('cRH5',\n",
    "        'c\\_5',\n",
    "        '3o m',\n",
    "        'H27Q')\n",
    "    ```\n",
    "\n",
    "    To je namreč tista oblika tega koščka, pri katerem je leva stranica enaka `\"cc3H\"` (argument `leva`), zgornja, `\"cRH5\"` pa se v `po_stranicah` pojavi le enkrat (argument `gor`).\n",
    "\n",
    "    Funkcija sme predpostaviti, da je košček možno obrniti v zahtevano lego na natančno en način. Če razmisliš, to pomeni tudi, da je vsaj eden od argumentov vedno niz.\n",
    "\n",
    "- Funkcija `vzemi_kos(levo, gor, po_stranicah, uporabljeni)` prejme pogoja `levo` in `gor`, ki imata enak pomen kot pri prejšnji funkciji (in je vsaj eden od njiju niz); slovar `po_stranicah`, ki je prav tako enak onemu iz prejšnje funkcije; ter množico `uporabljeni`, ki vsebuje koščke, ki so že uporabljeni.\n",
    "\n",
    "    **Tako kot slovar `po_stranicah`, naj/bo tudi `uporabljeni` vsebuje koščke v njihovih originalnih legah.**\n",
    "\n",
    "    Funkcija `vzemi_kos` mora:\n",
    "    - vrniti košček, ki ustreza pogojema in še ni bil uporabljen; **košček mora biti obrnjen/zrcaljen tako, da sta levo in zgoraj stranici, ki ju predpisujeta argumenta**.\n",
    "    - poleg tega mora ta košček dodati v množico `uporabljeni`. (Footnote: to je grdo, ker funkcija vrača rezultat in hkrati nekaj spreminja. Vendar: če v Pythonu napišete `import this`, se med drugim izpiše tudi \"*practicality beats purity*\")\n",
    "\n",
    "    Ker je vaš profesor kljub temu, da vam daje takšne domače naloge, nekje globoko v srcu vseeno za silo prijazen človek, so stvari so organizirane tako, da bo v vsakem trenutku obstajal natančno en košček, ki bo ustrezal pogojem. (Tako je bilo tudi v nalogi v Advent of Code.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Rešitev\n",
    "\n",
    "Kos je potrebno preprosto vrteti, dokler ni tak, kot mora biti.\n",
    "\n",
    "Za vsak obrat (`for kos in obrati(kos)`) pokličemo `stranice(kos)` in si zabeležimo kakšna je gornja stranica tega kosa (`ta_gor`) in leva stranica (`ta_leva`). Dobili bi jih lahko z `ta_gor = stranice(kos)[0]`, `ta_levo = stranice(kos)[3]`, lahko pa preprosto razpakiramo terko; odvečno desno in spodnjo stranico razpakiramo v `_1` in `_2`, ostale štiri pa v `_` (pred katerega damo zvezdico, da bo pogoltnil vse odvečne stranice). \n",
    "\n",
    "Da je kos pravilno obrnjen, mora biti zahtevani `gor` enak `ta_gor`; če je `gor` slučajno število, pa mora biti enak številu kosov, pri katerih se pojavi takšna stranica `ta_gor`, torej `len(po_stranicah[ta_gor]`). Torej mora biti `gor` enak bodisi `ta_gor` bodisi `len(po_stranicah[ta_gor])`. Z `levo` pa je enako."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "def preobrni(kos, levo, gor, po_stranicah):\n",
    "    for kos in obrati(kos):\n",
    "        ta_gor, _1, _2, ta_levo, *_ = stranice(kos)\n",
    "        if gor in (ta_gor, len(po_stranicah[ta_gor])) \\\n",
    "                and levo in (ta_levo, len(po_stranicah[ta_levo])):\n",
    "            return kos"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Izkaže pa se, da je obrat kosa določen že s stranicami, ki so podane. Tega, ali gre za robno, niti ni potrebno preverjati. Še več, če sta podani dve stranici, je dovolj, da se ujema ena in ujemala se bo tudi druga. Tako so pač sestavljeni podatki; če bi bili bolj zapleteni, bi bilo programiranje težje. Spodnja funkcija torej ne sledi povsem navodilom, vendar preživi teste in bi jih preživela tudi za vsake druge podatke, ki ne bi neprimerno zapletli naloge."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [],
   "source": [
    "def preobrni(kos, levo, gor, po_stranicah):\n",
    "    for kos in obrati(kos):\n",
    "        ta_gor, _1, _2, ta_levo, *_ = stranice(kos)\n",
    "        if gor == ta_gor or levo == ta_levo:\n",
    "            return kos"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Zanimivo je, da argumenta `po_stranicah` torej niti ne potrebujemo. (Ob sestavljanju naloge se teh stvari nisem zavedal, čeprav sem preživel skoraj dva dni ob vrtenju teh koščkov. :)\n",
    "\n",
    "#### `vzemi_kos`\n",
    "\n",
    "Rešitev naloge je načelno takšna."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [],
   "source": [
    "def vzemi_kos(levo, gor, po_stranicah, uporabljeni):\n",
    "    stranica = levo if gor == 1 else gor\n",
    "    kos = (po_stranicah[stranica] - uporabljeni).pop()\n",
    "    uporabljeni.add(kos)\n",
    "    return preobrni(kos, levo, gor, po_stranicah)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Najprej si izberemo stranico, po kateri bomo iskali košček: to bo `leva` stranica, če je `gor` enak `1`, sicer pa zgornja. Lahko pa bi naredili tudi obratno.\n",
    "\n",
    "Iz slovarja `po_stranicah` dobimo množico kosov s to stranico. Odstranimo vse, ki so bili že uporabljeni. Naloga zagotavlja, da bo vedno obstajal natančno en košček s takšno stranico, torej vemo, da ima množica natančno en element. Vzamemo ga s `pop`. Dodamo ga med uporabljene in vrnemo ustrezen obrat tega kosa.\n",
    "\n",
    "Zdaj pa poškilimo malo naprej. V nalogi za oceno 10 bo potrebno sestaviti sestavljanko, pri čemer bomo kot argument dobili vse kose in gornji levi kos. Najprej bomo sestavili prvo vrstico (potem pa vsako naslednjo), tako da bomo začeli s prvim kosom vrstice in klicali `vzemi_kos` z desno stranico zadnjega kosa, da bi dobil kos z ustrezno levo stranico. Očitno bo veselja konec, ko pridemo do konca vrstice. Testi za oceno 9 sicer te funkcije nikoli ne pokličejo, ko ustreznega kosa ni (to nam zagotavlja besedilo naloge). Ob koncu vrstice pa bomo sami poklicali to funkcijo tako, da ne bo mogla vrniti ustreznega kosa. Torej je smiselno, da predvidimo še ta scenarij. V primeru, da je množica prazna, vrnimo `None`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [],
   "source": [
    "def vzemi_kos(levo, gor, po_stranicah, uporabljeni):\n",
    "    stranica = levo if gor == 1 else gor\n",
    "    kandidati = po_stranicah[stranica] - uporabljeni\n",
    "    if len(kandidati) != 1:\n",
    "        return None\n",
    "    kos = kandidati.pop()\n",
    "    uporabljeni.add(kos)\n",
    "    return preobrni(kos, levo, gor, po_stranicah)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Za oceno 10\n",
    "\n",
    "- Napiši funkcijo `sestavi_koscke(kosi, kos)`, ki dobi kose, kot jih vrne `preberi_datoteko` in za pomoč še kos, ki ga je potrebno postaviti v gornji levi kot. Ta košček je tudi pravilno obrnjen (glede na želeni končni izgled sestavljanke.)\n",
    "\n",
    "    Ta funkcija mora v bistvu sestaviti sestavljanko.\n",
    "\n",
    "    Vrniti mora seznam seznamov koščkov (vsak košček pa je terka nizov, torej funkcija vrača seznam seznamov terk nizov). Vsak seznam znotraj tega seznama predstavlja vrstico sestavljanke. Slika muca je sestavljena iz dveh vrstic in osmih stolpcev, torej mora funkcija vrniti seznam, ki vsebuje dva seznama s po osmimi seznami terk, takole:\n",
    "\n",
    "    ```\n",
    "    [\n",
    "        [('wJMY', 'w  Y', '2  T', 'Fnyq'), ('YTPO', 'Y  O', 'T  v', 'q625'),\n",
    "         ('OVfe', 'O  e', 'v__U', '5Yjb'), ('e2k9', 'e  9', 'U__J', 'bmq8'),\n",
    "         ('9J6c', '9 /c', 'J/ 3', '8v2H'), ('cRH5', 'c\\_5', '3o m', 'H27Q'),\n",
    "         ('5kC7', '5/\\7', 'mo m', 'QRbK'), ('79jc', '7  c', 'm\\ x', 'K9ZK')],\n",
    "        [('Fnyq', 'F  q', '8 (z', '4MJn'), ('q625', 'q/~5', 'z__8', 'nc1o'),\n",
    "         ('5Yjb', '5__b', '8__O', 'oAXf'), ('bmq8', 'b__8', 'O__s', 'fyuX'),\n",
    "         ('8v2H', '8  H', 's)_P', 'XH00'), ('H27Q', 'H=øQ', 'P_mh', '0Ew4'),\n",
    "         ('QRbK', 'Q= K', 'h_mO', '41K4'), ('K9ZK', 'K/ K', 'O) a', '40YO')]\n",
    "    ]\n",
    "    ```\n",
    "\n",
    "    Prvi košček v prvem seznamu je podani kotni košček (v podani legi). Ostali se z njim ujemajo (torej so po potrebi obrnjeni drugače kot v podatkih).\n",
    "\n",
    "    Če pozorno pogledamo, vidimo, da je desna stranica prvega koščka YYTq, in prav taka je leva stranica drugega. Prvi košček prve vrstice se konča z FNyq in z istim robom se začne prvi košček druge vrstice. In tako povsod drugje.\n",
    "\n",
    "    Funkcijo je najlažje napisati tako, da postavimo podani prvi košček in nato dokončamo prvo vrstico, tako da izbiramo ustrezne koščke za nadaljevanje. (Kako dolga je vrstica, vidimo sproti.) Pod prvo vrstico sestavimo drugo vrstico. Pod drugo dodamo tretjo. In tako naprej.\n",
    "\n",
    "    Če kaj pomaga (ni pa nujno potrebno): ko zaključimo prvo vrstico, vemo tudi, koliko vrstic bo.\n",
    "\n",
    "- Napiši funkcijo `slika(kosi)`, ki prejme kose, kot jih vrne prejšnja funkcija, in vrne niz s sliko: od vsakega koščka mora odstraniti rob, kar ostane, pa lepo zložiti. Med vrsticami niza so `\\n`. \n",
    "\n",
    "    `print(slika(kosi))`, kjer so `kosi` gornji seznam, bi izpisal\n",
    "\n",
    "    ```\n",
    "           /\\_/\\\n",
    "      ____/ o o \\\n",
    "    /~____  =ø= /\n",
    "    (______)__m_m)\n",
    "    ```\n",
    "\n",
    "- Napiši funkcijo `sestavljanka(kosi, kot)`, ki prejme enake argumente kot `sestavi_koscke` in vrne enak rezultat kot `slika`.\n",
    "\n",
    "### Rešitev\n",
    "\n",
    "Za oceno 10 pa je potrebno začeti programirati.\n",
    "\n",
    "Najprej si pripravimo zbirko stranic in množico uporabljenih kosov. V začetku je uporabljen vogalni kos, ki ga dobimo kot argument. Tu nas zamika napisati `uporabljeni = {kos}`, vendar to ne bo delovalo, ker ima množica `uporabljeni` kose v originalni legi, vogalni kos, ki ga dobi funkcija kot argument, pa je lahko obrnjen. Torej potrebujemo `uporabljeni = obrati(kos)` - za uporabljene razglasimo kar vse obrate tega kosa. Če hočemo biti \"pravilnejši\", pa napišemo `uporabljeni = obrati(kos) & set(kosi)`, tako da množica vsebuje le tisti obrat, ki se dejansko pojavi v originalnih podatkih.\n",
    "\n",
    "V `slika` bomo sestavljali sliko. Vanjo najprej dodamo (prazen) seznam `prva_vrstica`, ki ga potem v prvi zanki dopolnimo s kosi, ki jih vrača `vzemi_kos`. (Poglejte, kako smo jo obrnili!)\n",
    "\n",
    "Nato na podoben način dodamo preostale stranice."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sestavi_koscke(kosi, kos):\n",
    "    po_stranicah = zbirka_stranic(kosi)\n",
    "\n",
    "    uporabljeni = obrati(kos) & set(kosi)\n",
    "    prva_vrstica = []\n",
    "    slika = [prva_vrstica]\n",
    "\n",
    "    # Dopolni prvo vrstico\n",
    "    while kos:\n",
    "        prva_vrstica.append(kos)\n",
    "        levo = stranice(prva_vrstica[-1])[1]\n",
    "        kos = vzemi_kos(levo, 1, po_stranicah, uporabljeni)\n",
    "\n",
    "    # Dodaj ostale vrstice\n",
    "    N = len(prva_vrstica)\n",
    "    for i in range(len(kosi) // N - 1):\n",
    "        gor = stranice(slika[-1][0])[2]\n",
    "        vrstica = [vzemi_kos(1, gor, po_stranicah, uporabljeni)]\n",
    "        for i in range(1, N):\n",
    "            gor = stranice(slika[-1][i])[2]\n",
    "            levo = stranice(vrstica[-1])[1]\n",
    "            vrstica.append(vzemi_kos(levo, gor, po_stranicah, uporabljeni))\n",
    "        slika.append(vrstica)\n",
    "\n",
    "    return slika"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Obstaja tudi precej krajša rešitev.\n",
    "\n",
    "Za vsako stranico obstajata le dva koščka, ki ji ustrezata (ali eden, če gre za rob). To med drugim pomeni, da nam pri sestavljanju nadaljnjih vrstic ni potrebno opazovati prejšnje."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sestavi_koscke(kosi, kos):\n",
    "    po_stranicah = zbirka_stranic(kosi)\n",
    "    uporabljeni = obrati(kos) & set(kosi)\n",
    "    slika = [[kos]]\n",
    "    while len(uporabljeni) < len(kosi):\n",
    "        kos = vzemi_kos(stranice(slika[-1][-1])[1], 1, po_stranicah, uporabljeni)\n",
    "        if kos:\n",
    "            slika[-1].append(kos)\n",
    "        else:\n",
    "            slika.append([vzemi_kos(1, slika[-1][0][-1], po_stranicah, uporabljeni)])\n",
    "    return slika"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ta funkcija v sliko najprej vstavi kot. Nato izvaja zanko, dokler ne porabi vseh kosov. V vsakem koraku vzame kos, ki sledi (doslej) zadnjemu kosu v (doslej) zadnji vrstici. Ta kos je `slika[-1][-1]`, izmed njegovih stranic nas zanima desna (`stranice(kos[-1][-1])[1]`). Če tak kos obstaja, ga doda v to vrstico. Če ga ni, pa v sliko doda novo vrstico, ki se začne s koščkom, katerega zgornja stranica se ujema s spodnjo stranico prvega koščka v zadnji vrstici.\n",
    "\n",
    "**Ta funkcija deluje samo,** če v `preobrni_kos` ne preverjamo, ali je stranica, za katero podamo argument `1`, res robna. Uporabiti moramo torej ono različico s pogojem `if gor == ta_gor or levo == ta_levo`.\n",
    "\n",
    "Preostali funkciji sta v primerjavi s to trivialni."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [],
   "source": [
    "def slika(kosi):\n",
    "    bitmap = []\n",
    "    for vrsta_kosov in kosi:\n",
    "        for vrsta in zip(*(tile[1:-1] for tile in vrsta_kosov)):\n",
    "            bitmap.append(\"\".join(row[1:-1] for row in vrsta))\n",
    "    return \"\\n\".join(bitmap)\n",
    "\n",
    "\n",
    "def sestavljanka(kosi, kos):\n",
    "    return slika(sestavi_koscke(kosi, kos))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " Lepe praznike in še      ::::::    .-~~\\        ::::::     \n",
      " veliko programerskih     |::::|   /     \\ _     |::::|     \n",
      " uspehov v 2021! :) _     l~~~~!   ~x   .-~_)_   l~~~~!     \n",
      "               .-~   ~-.   \\  /      ~x\".-~   ~-. \\  /      \n",
      "        _     /         \\   ||    _  ( /         \\ ||       \n",
      "        ||   T  o  o     Y  ||    ||  T o  o      Y||       \n",
      "      ==:l   l   <       !  (3  ==:l  l  <        !(3       \n",
      "         \\\\   \\  .__/   /  /||     \\\\  \\  ._/    / ||       \n",
      "          \\\\ ,r\"-,___.-'r.//||      \\\\,r\"-,___.-'r/||       \n",
      "           }^ \\.( )   _.'//.||      }^\\. ( )  _.-//||       \n",
      "          /    }~Xi--~  //  ||     /   }~Xi--~  // ||\\      \n",
      "         Y    Y I\\ \\    \"   ||    Y   Y I\\ \\    \"  || Y     \n",
      "         |    | |o\\ \\       ||    |   | |o\\ \\      || |     \n",
      "         |    l_l  Y T      ||    |   l_l  Y T     || |     \n",
      "         l      \"o l_j      |!    l     \"o l_j     || !     \n",
      "          \\                 ||     \\               ||/      \n",
      "        .--^.     o       .^||.  .--^.     o       ||--.    \n",
      "             \"           ~  `'        \"           ~`'       \n"
     ]
    }
   ],
   "source": [
    "zadnji = preberi_datoteko(\"zadnji-puzzle.txt\")\n",
    "kot = next(kos for kos in zadnji if kos[0] == \"TTwADdOW\")\n",
    "print(sestavljanka(zadnji, zrcaljen_vod(obrnjen(kot))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Za dodatno zabavo\n",
    "\n",
    "- Spremeni funkcijo `sestavi_koscke` tako, da bo lahko argument `kos`, ki pove gornji levi kot, tudi `None`. To ustreza situaciji, ko preberemo datoteko in pravzaprav ne vemo, kateri košček bo levo zgoraj. Funkcija naj v tem primeru vzame enega od kotnih kosov (lahko kar `prvi_kot`) in ga ustrezno zasuka.\n",
    "\n",
    "    Dobljena sestavljanka bo sicer morda obrnjena in prezrcaljena. Vseeno pa je pomembno, da prvi kot pravilno zasukaš: če predpostavimo, da gre za gornji levi kot, mora biti košček obrnjen tako, da sta zgornja in leva stranica robni.\n",
    "\n",
    "    Tega v resnici sploh ni težko sprogramirati, samo testov se mi ne piše in naloga je že dovolj dolga. :)\n",
    "\n",
    "- Napiši program, ki prejme datoteko z ASCII artom in sestavi sestavljanko. Se pravi to, kar sem moral jaz početi s temi kravami in mačkami. :)\n",
    "\n",
    "### Rešitev\n",
    "\n",
    "Tole razreže sestavljanko, doda unikatne robove, prevrti in premeša koščke.\n",
    "\n",
    "```python\n",
    "from random import choice, shuffle, seed\n",
    "import string\n",
    "from functools import reduce\n",
    "from operator import add\n",
    "\n",
    "seed(0)\n",
    "\n",
    "#fn = \"muc\"\n",
    "#n = 2\n",
    "\n",
    "#fn = \"krava\"\n",
    "#n = 5\n",
    "\n",
    "fn = \"zadnji\"\n",
    "n = 6\n",
    "\n",
    "vrstice = [x.strip(\"\\n\") for x in  open(fn + \".txt\")]\n",
    "\n",
    "w, h = max(map(len, vrstice)), len(vrstice)\n",
    "\n",
    "hh = (h + n - 1) // n\n",
    "ww = (w + n - 1) // n\n",
    "print(hh, ww)\n",
    "pad_hor = \" \" * (n * ww - h)\n",
    "pad_ver = [\" \" * n * ww] * (ww * n - h)\n",
    "\n",
    "vrstice = [x + pad_hor for x in vrstice] + pad_ver\n",
    "\n",
    "allowed = string.ascii_letters + string.digits\n",
    "print(allowed)\n",
    "def rl():\n",
    "    return choice(allowed)\n",
    "\n",
    "sides = sorted({\"\".join(rl() for _ in range(n))\n",
    "     for _ in range(10 * (ww + 1) * (hh + 1))})\n",
    "shuffle(sides)\n",
    "sides = iter(sides)\n",
    "\n",
    "\n",
    "d = [[rl() for _ in range(ww + 1)] for _ in range(hh + 1)]\n",
    "vers = [[d[row][col] + next(sides) + d[row + 1][col]\n",
    "         for col in range(ww + 1)]\n",
    "        for row in range(hh)]\n",
    "hors = [[d[row][col] + next(sides) + d[row][col + 1]\n",
    "         for col in range(ww)]\n",
    "        for row in range(hh + 1)]\n",
    "\n",
    "def tile(x, y):\n",
    "    xs = slice(x * n, x * n + n)\n",
    "    left, right = vers[y][x:x + 2]\n",
    "    print(y * n + n - 1, len(vrstice))\n",
    "    return [hors[y][x],\n",
    "            *[left[yi] + vrstice[y * n + yi][xs] + right[yi] for yi in range(n)],\n",
    "            hors[y + 1][x]]\n",
    "\n",
    "def obrati(kos):\n",
    "    vsi_obrati = []\n",
    "    for i in range(2):\n",
    "        for j in range(4):\n",
    "            vsi_obrati.append(kos)\n",
    "            kos = [\"\".join(v[i] for v in kos)[::-1] for i in range(len(kos))]\n",
    "        kos = kos[::-1]\n",
    "    return vsi_obrati\n",
    "\n",
    "tiles = [[tile(x, y) for x in range(ww)] for y in range(hh)]\n",
    "print(\"\\n\".join(repr(x) + \",\" for x in tiles))\n",
    "\n",
    "flat_tiles = reduce(add, tiles)\n",
    "shuffle(flat_tiles)\n",
    "open(fn + \"-puzzle.txt\", \"wt\").write(\n",
    "    \"\\n\\n\".join(\"\\n\".join(choice(obrati(tile))) for tile in flat_tiles))\n",
    "```"
   ]
  }
 ],
 "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
}