p1/advent of code/2020/16 Ticket Translation/resitev.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Day 16: Ticket Translation\n",
    "\n",
    "([Povezava na nalogo](https://adventofcode.com/2020/day/16))\n",
    "\n",
    "Naloga med študenti ni požela prevelikega navdušenja, zdela se jim je eno samo pisanje, eno samo dolgočasno preobračanje podatkov.\n",
    "\n",
    "Zanje imam slabo novico: dobrodošli v resničnem življenju.\n",
    "\n",
    "Naloga bo vseeno zanimiva: učili se bomo lepo po kosih vrteti te podatke. In še nevemkaterič videli, zakaj so izpeljani seznami in množice tako praktični.\n",
    "\n",
    "Imamo datoteko takšne oblike:\n",
    "\n",
    "```\n",
    "class: 1-3 or 5-7\n",
    "row: 6-11 or 33-44\n",
    "seat: 13-40 or 45-50\n",
    "\n",
    "your ticket:\n",
    "7,1,14\n",
    "\n",
    "nearby tickets:\n",
    "7,3,47\n",
    "40,4,50\n",
    "55,2,20\n",
    "38,6,12\n",
    "```\n",
    "\n",
    "Prvi blok opisuje podatke in možne interval vrednosti. (Vedno sta dva, vendar to v navodilih ni posebej omenjeno in se na to ne bomo zanašali, saj je splošna rešitev preprostejša.)\n",
    "\n",
    "Tretji del vsebuje vrstice. Vsaka vrstica ima vse te podatke, vendar ne vemo, v kakšen vrstnem redu. Vemo pa, da isti stolpec vedno ustreza istemu podatku.\n",
    "\n",
    "Vmesni del vsebuje naše podatke.\n",
    "\n",
    "Prvi del naloge je preprost: nekatera izmed števil v tretjem bloku se ne pojavijo v prav nobenem intervalu. V gornjem primeru so to 4, 55 in 12. Zanima nas njihova vsota.\n",
    "\n",
    "Drugi del je zabavnejši. Za vsak stolpec je potrebno ugotoviti, kateri del predstavlja. Za to najprej izločimo vse vrstice, ki vsebujejo kakšno številko, ki se ne pojavi v nobenem intervalu. Nato pa opazujemo, kateri stolpec bi, glede na podane številke, lahko predstavljal kateri podatek. Nekateri lahko ustrezajo več podatkom, a izkazalo se bo, da je rešitev, v kateri vsakemu stolpcu ustreza natančno eno pravilo, enolična.\n",
    "\n",
    "## Branje podatkov\n",
    "\n",
    "Preberemo datoteko in jo s `split(\"\\n\\n\")` razkosamo v tri bloke."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "rules_part, my_ticket, tickets = open(\"input.txt\").read().split(\"\\n\\n\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Pravila\n",
    "\n",
    "Prvi del, pravila bomo razstavili v slovar. Ne, ker bi v resnici potrebovali slovar, temveč ker bomo včasih potrebovali samo intervale, včasih pa tudi ime polja. Ključ bo polje, vrednosti pa bodo kar množica, ki vsebuje vsa dovoljena števila za to polje.\n",
    "\n",
    "S `splitlines()` razstavimo blok na vrstice. Vsako vrstico s `split(\":\")` razbijemo na ime polja in niz s seznam intervalov, `intervals`. (Kaj se zgodi na koncu, pa povem spodaj.)\n",
    "\n",
    "(Še tolažba: te vrstice so najbolj zapleteni del programa. :)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "rules = {}\n",
    "for rule in rules_part.splitlines():\n",
    "    field, intervals = rule.split(\":\")\n",
    "    rules[field] = set.union(*(set(range(int(f), int(t) + 1))\n",
    "                               for f, t in (p.split(\"-\") for p in intervals.split(\" or \"))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Zdaj recimo, da imamo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "intervals = \"1-3 or 5-7\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Razbijemo jih glede na `\" or \"`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['1-3', '5-7']"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "intervals.split(\" or \")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vsakega razbijemo glede na `\"-\"`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[['1', '3'], ['5', '7']]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[p.split(\"-\") for p in intervals.split(\" or \")]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Zdaj gremo z zanko čez to in sestavimo intervale."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[range(1, 4), range(5, 8)]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[range(int(f), int(t) + 1)\n",
    " for f, t in (p.split(\"-\") for p in intervals.split(\" or \"))]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pravzaprav nas ne zanimajo `range`-i, temveč množice."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[{1, 2, 3}, {5, 6, 7}]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[set(range(int(f), int(t) + 1))\n",
    " for f, t in (p.split(\"-\") for p in intervals.split(\" or \"))]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vse množice zložimo skupaj."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{1, 2, 3, 5, 6, 7}"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "set.union(*(set(range(int(f), int(t) + 1))\n",
    "            for f, t in (p.split(\"-\") for p in intervals.split(\" or \"))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "No, to smo spravili v slovar.\n",
    "\n",
    "### Vozovnica in ostale vozovnice\n",
    "\n",
    "To je trivialno."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "my_ticket = [int(x) for x in my_ticket.splitlines()[1].split(\",\")]\n",
    "\n",
    "tickets = [[int(x) for x in v.split(\",\")]\n",
    "           for v in tickets.splitlines()[1:]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Prvi del: vsota neveljavnih števil\n",
    "\n",
    "Tudi to je trivialno. Sestavimo množico vseh dovoljenih števil. Gremo čez vse vozovnice; za vsako izračunamo vsoto neveljavnih števil v njej in potem poračunamo vsoto te vsote."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "19060\n"
     ]
    }
   ],
   "source": [
    "all_valid = set.union(*rules.values())\n",
    "print(sum(sum(x\n",
    "              for x in ticket\n",
    "              if x not in all_valid)\n",
    "          for ticket in tickets))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Drugi del\n",
    "\n",
    "Ta je pa bolj zanimiv. Najprej sestavimo seznam, ki vsebuje le veljavne vozovnice, torej vozovnice, v kateri se ne pojavi nobena številka, ki je ni v nobenem intervalu. Ali so vse številke veljavne, preverimo tako, da ugotovimo, ali je množica teh številk podmnožica množice vseh veljavnih številk."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "valid_tickets = [ticket for ticket in tickets if set(ticket) <= all_valid]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Od tod naprej pa bomo preverjali, kateri stolpec bi lahko, glede na števila, ki jih vsebuje, ustrezal kateremu pravilu. Torej bomo delali s stolpci. Sestavimo seznam množic števil v vsakem stolpcu. Stolpcev je pa toliko kot pravil."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "columns = ({ticket[i] for ticket in valid_tickets}\n",
    "           for i in range(len(rules)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Stolpce bomo potrebovali samo enkrat, torej je vseeno, če jih ne tlačimo v seznam, temveč naredimo kar generator. Kot zanimivost povejmo še, da bi jih lahko naredili tudi z `columns = map(set, zip(*valid_tickets))` in v tem primeru bi lahko bili tudi `valid_tickets` kar generator. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "valid_tickets = (ticket for ticket in tickets if set(ticket) <= all_valid)\n",
    "columns = map(set, zip(*valid_tickets))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Zdaj pa sestavimo seznam, ki bo vseboval indeks stolpca in imena vseh pravil, ki bi jim stolpec lahko ustrezal. Stolpce torej oštevilčimo (`enumerate(columns)`) in za vsak par `i, column`, poiščemo vsa polja, za katera velja, da so števila v tem stolpcu podmnožica veljavnih števil tega polja."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "maybes = [(i, {field for field, valids in rules.items() if column <= valids})\n",
    "          for i, column in enumerate(columns)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Izvemo, da bi 15. stolpec lahko ustrezal trem različnim poljem."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(15, {'arrival platform', 'class', 'row'})"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "maybes[15]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nekateri ustrezajo tudi več poljem, nekateri pa manj. Preštejmo, koliko poljem ustreza kateri."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[16, 6, 18, 15, 19, 9, 4, 1, 20, 17, 2, 7, 5, 11, 10, 3, 14, 8, 13, 12]"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[len(maybe[1]) for maybe in maybes]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Če to reč uredimo, izvemo nekaj zanimivega."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sorted(len(maybe[1]) for maybe in maybes)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In zdaj pošpekuliratmo. Mogoče je stvar preprosta. Uredimo seznam `maybe` po številu polj. Za prvi stolpec vemo, kateremu pravilu ustreza. Temu pravilu ne more ustrezati noben drug stolpec. In če imamo srečo (izkazalo se bo, da jo res imamo) prav temu pravilu ustrezajo tudi vsi drugi stolpci. Potemtakem za drugi stolpec ostane le še eno možno pravilo. In tako naprej."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "maybes.sort(key=lambda x: len(x[1]), reverse=True)\n",
    "assignments = {}\n",
    "while maybes:\n",
    "    i, fields = maybes.pop()\n",
    "    field = (fields - set(assignments)).pop()\n",
    "    assignments[field] = i"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Seznam `maybes` smo uredili glede na število pravil. Zaradi lepšega ga uredimo padajoče. Potem vedno vzamemo zadnji stolpec, tisti, ki ustreza enemu samemu pravilu. Iz množice pravil, ki jim je ustrezal v začetku, odštejemo vsa pravila, ki so že zasedena. In nato zabeležimo, da to pravilo ustreza temu stolpcu.\n",
    "\n",
    "Naloga hoče, da izračunamo zmnožek tistih številk v naši vozovnici, ki ustrezajo podatkom, katerih ime se začne z *departure*."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "953713095011\n"
     ]
    }
   ],
   "source": [
    "from functools import reduce\n",
    "from operator import mul\n",
    "\n",
    "print(reduce(mul, (my_ticket[i]\n",
    "                   for field, i in assignments.items()\n",
    "                   if field.startswith(\"departure\"))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Celoten program\n",
    "\n",
    "Ker je bilo tole razreseno po celi beležki, zberimo celoten program še na enem mestu."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "19060\n",
      "953713095011\n"
     ]
    }
   ],
   "source": [
    "from functools import reduce\n",
    "from operator import mul\n",
    "\n",
    "\n",
    "# Branje podatkov\n",
    "\n",
    "rules_part, my_ticket, tickets = open(\"input.txt\").read().split(\"\\n\\n\")\n",
    "\n",
    "rules = {}\n",
    "for rule in rules_part.splitlines():\n",
    "    field, intervals = rule.split(\":\")\n",
    "    rules[field] = set.union(*(set(range(int(f), int(t) + 1))\n",
    "                               for f, t in (p.split(\"-\") for p in intervals.split(\" or \"))))\n",
    "\n",
    "my_ticket = [int(x) for x in my_ticket.splitlines()[1].split(\",\")]\n",
    "\n",
    "tickets = [[int(x) for x in v.split(\",\")]\n",
    "           for v in tickets.splitlines()[1:]]\n",
    "\n",
    "\n",
    "# Part 1\n",
    "\n",
    "all_valid = set.union(*rules.values())\n",
    "print(sum(sum(x\n",
    "              for x in ticket\n",
    "              if x not in all_valid)\n",
    "          for ticket in tickets))\n",
    "\n",
    "\n",
    "# Part 2\n",
    "\n",
    "valid_tickets = [ticket for ticket in tickets if set(ticket) <= all_valid]\n",
    "\n",
    "columns = ({ticket[i] for ticket in valid_tickets}\n",
    "           for i in range(len(rules)))\n",
    "\n",
    "maybes = [(i, {field for field, valids in rules.items() if column <= valids})\n",
    "          for i, column in enumerate(columns)]\n",
    "\n",
    "maybes.sort(key=lambda x: len(x[1]), reverse=True)\n",
    "assignments = {}\n",
    "while maybes:\n",
    "    i, fields = maybes.pop()\n",
    "    field = (fields - set(assignments)).pop()\n",
    "    assignments[field] = i\n",
    "    \n",
    "print(reduce(mul, (my_ticket[i]\n",
    "                   for field, i in assignments.items()\n",
    "                   if field.startswith(\"departure\"))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Drugi del: dve simpatični bližnjici\n",
    "\n",
    "`columns` je pravzaprav transponiran `valid_tickets`. Za transponiranje obstaja trik z `zip`-om."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1, 4, 7, 10), (2, 5, 8, 11), (3, 6, 9, 12)]"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = [(1, 2, 3), (4, 5, 6), (7, 8, 9), (10, 11, 12)]\n",
    "list(zip(*s))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Kako to deluje? Preprosto. Vse štiri terke postanejo argumenti `zip`-a, kot da bi napisali `zip((1, 2, 3), (4, 5, 6), (7, 8, 9), (10, 11, 12))`. `zip` gre vzporedno čez vse terke; najprej pobira prve elemente, nato druge, nato tretje.\n",
    "\n",
    "V našem primeru torej naredimo `zip(*valid_tickets)`. Iz vsake od dobljenih terk želimo narediti množico, torej jih premapiramo čez `map(set, ...)`.\n",
    "\n",
    "Na ta način `valid_tickets` potrebujemo le enkrat. Tako so `valid_tickets` lahko kar generator."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Še bolj kul pa je nadaljevanje. Vemo, da bomo polje najprej dodelili tistemu stolpcu, ki mu ustreza le eno pravilo, drugi stolpec tistemu, ki mu ustrezata dve in tako naprej. Po drugi strani pa vemo tudi, da bo najprej dodeljeno tisto pravilo, ki se pojavi le pri enem stolpcu, nato tisto, ki se pri dveh...\n",
    "\n",
    "Potemtakem lahko preprosto uredimo stolpce po številu ustrezajočih polj in polja po številu ustrezajočih stolpcev, pa se bodo natančno ujemali. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "953713095011\n"
     ]
    }
   ],
   "source": [
    "# Part 2\n",
    "\n",
    "from collections import Counter\n",
    "from itertools import chain\n",
    "from functools import reduce\n",
    "from operator import mul\n",
    "\n",
    "valid_tickets = (ticket for ticket in tickets if set(ticket) <= all_valid)\n",
    "columns = map(set, zip(*valid_tickets))\n",
    "\n",
    "maybes = [(i, {field for field, valids in rules.items() if column <= valids})\n",
    "          for i, column in enumerate(columns)]\n",
    "\n",
    "counts = Counter(chain(*(x[1] for x in maybes)))\n",
    "\n",
    "indices = (maybe[0] for maybe in sorted(maybes, key=lambda x: len(x[1])))\n",
    "fields = sorted(counts, key=counts.get, reverse=True)\n",
    "    \n",
    "print(reduce(mul, (my_ticket[i]\n",
    "                   for i, field in zip(indices, fields)\n",
    "                   if field.startswith(\"departure\"))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Pa če ne bi imeli takšne sreče?\n",
    "\n",
    "Kot vse podobne naloge je tudi ta zanimala vašega asistenta Tomaža Hočevarja. Hitro je našel članek, izrek, dokaz ... da bomo pri vsaki rešitvi, ki je enolična, gotovo imeli srečo. Sestavljalec naloge nam tu preprosto ni mogel otežiti življenja ... razen če bi bilo možnih različnih odgovorov več."
   ]
  }
 ],
 "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
}