kz/domače naloge/2021/11 Specops/resitev.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "30c557e4",
   "metadata": {},
   "source": [
    "# Specops\n",
    "\n",
    "<img style=\"float: right\" src=\"data:image/.png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAGYCAMAAABbMkSTAAAAGXRFWHRTb2Z0d2FyZQBBZG9iZSBJbWFnZVJlYWR5ccllPAAAADBQTFRF9pYi7CIqv7/BnZ2fB6hWBAQENTiK7u7u9IuPkpTC+8mOftGn4OHezs7X+sXH////iqVHMQAAABB0Uk5T////////////////////AOAjXRkAABPrSURBVHja7F2LlqMqEEzoFRID8f//dsW38UGjKOhUz94zrOulhbLsLhF4FLCk7IEuACAwAAJAYADkjwFiZJZlgnOmlpI455GtUYqAJ1YmpDSMKmsjZo2Z80TZmdO7INsesw+Qso7ystzXVSjrLWPUmNU1uqsk7om1f9Z9U10kr05hz3Mjl3VmGO2x95jYA4iurt0w2ipt70kOxFSfninnDaXqE1lXyiOyzIzHnSj4TxzhbLuuIaOF9jABafqY3F1NgnPW8IYWIU8U9n7gAMLuYCYzu4rJiTA1Z4odgDS9Idz3Mw82nxZ0l2BYTM45gGRcQDzxEO6Ke0DMdkBM64d1mx4CCLH60NbGAkRyH1jliUaEbE1zU5tdj6yui1nd5/nI4jzNNfFvBQYgwuYJJFgdXMV/qUIRpIpywp4pkgSEda4N1JlmEVlxAeF1c3lOnRLJcHSv89Cli4wMiObd+Dbtdef3WlaoMQBRjRpgZEQVaJoXSngh1iq65fbEBUSxQ7q9rdwJPhU8QDpCkbOHhUeTeASpvJY3z56gTn1QDwqI9Hi4Oc+tBBdR9UuEqbKLCazgYFgEaZ0uOPfOskxAQMpr0mxAnH1CvVhmZ27SeTcrn2jNcdt24ULa6K1DinCAEOuOYgNiRG1lvwjDvCGI125WkzQr8eiqFLsAaS6Idw8wAZFeePAfbz4xRDCbwmm45DZbrvUSExBVpRvMW5oHiFUWtblaQLoK/9x+ZgBSvZ1iZFlVu3XlXDNO1cznAqlKWO0I6tXdxHmTyQdk8MR3cjxbS9w3ACL4kaYadWCpIMlX/2ve2eMhuhQDxHvEEHHealcZEUn3yYrs6AWxH29Ezt4TVY28QEPMYROG20FXLrYHI4aJGQABIDAAAkBgAOTOgKharplOuOmmpGZLqinp1VKZZK6URu6mpTnHWmmmYxXW8eASQrZYLQOihdZWHeva+pL6LdHMsdmSvdBCdxWulIjl2FapOY5tNbTuuHcnDMdxdQuyHBdVDzEcK9tDa4CwRRhbV4avUuh4VR7XQwDkCoAow24B98QDqjQqXpXH9RCyLKS9MP+0F4+stB5ZCOrIsgAIAAEgAASAABAAEggQO+4uAEgqgCjp8QEm7HhhWH1kK4BIKoA08xq6z3+h1CMr9ebL1W56GWJI5BiSdRNDCYAkAEj3mXD7US4AiQtIN1MBgAAQAAJA0gdEA5DksiwxyrJgkYVhC0TGXrQIdiggjUQXUOqpjKlX0x/79SMQQyLHEItFNlhhBYDEBqRaeqOf2ghAogNyljsAAkAACAABIHcHBBZZGMISB0SxHwZswXpAlVrFq/K4HkIMQVAHIAAEgACQsIBQtayYoNrKyNSU1GxJNSWzWhLVymZLpZG7aWnOMWnDdExcx8Ry3JeCthgMwSMLgGwERLEzfP6J96ryON9Q6lDqUOpQ6gjqAASAABAAAkAACAABIAAESj1FpS4yn+05YQcrdVHtWA6lnoxSlxkNN4hBDIkdQ8oLIQCSVlAHIAAEgAAQAAJAAMgNAYFSj6/UfXalhx2u1MGQtBmCGIKgDkAACAABID6AmMFG8wAkAUDOcQdAAMgdAMGIYYTmrH3bC0tAqd9YVl9/fghiCII6AAEgAASAAJC7AELCvkgxojZ7cm3qt0S2pJpjeq1EZULeHJsr9e5o6NgsOa7q1hzHpRNiObZz+lmObYlYjgtRn+h0bOpfywzRurxXdGNWtNSmfks0c2y2ZC+06I5NS/2/0syx2aqF5ji2JWI51ravOI6rW5DluKh6aFjhguOqh6DUodRhUOpQ6siykPYCEAACQAAIAAEgAASAXAOQUDo0f7QGpZ6CUu/xUAXMT6kLKSWJsDq0wyNXUOp+Sl1ktQXdFGzMD8QQnxhismo55KDb5v08rwCIV1Cv2dIt5hDA3W/8ACAbsqxup8/97ibxHIBEBaTHox3Vy4VmGnFPFPlJVUYDhEI9sno8NhgFP3FvlbmKBEiooJ6f1M+Ps6rM4wBC7RNr517I+eMcOxG5qWg4eLfoOvcNtJu6etzN8vOVetmN3QNrt+nbIRIBEBVyRTmFGLI3hqjRGpi73alJW8wBOsQcX2W+wJDDlbocPa/2u5sgclFhmMdhiPpZIzaAu19ELg3I6QyRWWsUzF2PyBcM8Qaks3CA/HAEDNmg1AO7G3EEDNkDSCAdOuTIAdLWqOOrzCMq9QNM5a0VF7U8nlKHrbwnjQ0IvstKLIYAkFtmWWAIAAFDwBAAAoYAkPhKnUorL49qKxVsU1KzJdWUzGrJLpSwXBq5m5bmHAtlmI7Fdsd2eGv5EoK2+ASlDmEIpQ6ljhiCoI4sCwwBIGAIAAFDwBAAAoaAISEAgbkYAqX+55T6cIOdAz9yCVnleZ8B5Wc0Z/gZkJaD70gRQ+LHEMokkQy8kgOyrO2AaFPDkikAklKWlWUCgCSkQ1SWaQCSEEPkuTFEvZ6zRs9d9r0HQ8qsV3YEOQeQ514jNiIXZIjNeyX7ERDCvs+j7BZKnYiycBPVowLyuodSL6rFgMR5Sv1MhlxOqbePu3DrZbkful/P0DA1yWbIVXWIiADId2L0ZdprcmCJIVcdD4nBkJC992IwRL/5pqIxpH5yqpBrLsYDZLXKt/QxEW+eOglh0yx9c4YYBwK/eEVeyUGeKQyjMMSPIFKaWDFEU/f19a0ZshGQPzGm/g0vq1/OKlUohpwiDG8CyKpSN+93FSkW/tQ/fSgxiXz9fqJSDymrXwGrdDDk5KU1bqxDuFWmFUPuq0O2AZIDEDAEDJkDRHzBEDAEDEEMAUM8AVFC2E99jajNnlyb+i2RLanmmF4tlWn2sNSMQ7XHenc0dGyWHNuqlR47aaqcOl64hF8nw2NNDKnWxCZavAR3i4nl2FT/47JSr7cxUd2GJm1J7Sjputq2ZOqxwcExtVJiOakBeTkcT0tq5lgDSMOQIC12OV7ZT/24bRMZj6ztu0C+AlY5emS9TuwhxBBkWciykGWBIWAIAAFDwBAA8meV+gkbYy8Csr3KV8AqXSOGx27fHcPijKmzLbExdSh1x3gIlPpfjCHVeqXIspLJssS5CweAIQ5AVHYTQO4ypi4zAkOWGBJ829evE5ASDQGG8AHZu7WvcgCis0yHAUR9X7NGvwfa3lOfsdGHaZMTST7kU9aHddoMWX4KdvPURdEDskOHKt8ps+rfMfYJodRFftSG4Pm6Uic7RV2MN8Tdo5Y9APkcBMg/tasdDUO+5wEyVOqmmu05YMh2Heo9qfwoPP7pAErdFPl5DOmVepnxmhEgO2LIfoZQeEC2xxC7OabO1c+P/hrSX5W7f/SX9KgCrRkxpMx4q8+aSlzEXkA8l4r5FmZzjzuQM6uphyvzaCaBvpaM5g4qTg/lbkCygYViyOv3z+v3kP3PpuP632f0Qz9/X/qZOfHfP8ljiHtdjxqQAGtDTXwzGEJEkqpFF4nCMGQqzvQnuLRZ1CFuQNw8dgFC3HVWtjCke5kVIIYsAiLOAuS1B5CdDJmhyBaGhATkFR2QliFmAyDyuZMhXzAkKENeSTHESNqvQ5YYcsAQ2+KIoVuHPJ2pRzMvenpGcx5NDi4AYrgMWRsx3GEHrOrm+ZZghiELV/l1KnXt2/Cv+0SOUl9+peP9LmuRISd8yLIYQxS39yZfnbB9L1fJZsjKVyd/JIZ8OUqdOZpQHBBDgvReOllWqoDk5wIChoAhm3XIAYC8wJC0GPICQ1KJIS8w5A8x5BZK3TiV+nelSpcO0dyGh1Hq26eLtzfK3L8WK6UQ89SbPtENQ1YcNysMrDhuPnLgz05/tpPkXS1uGDJ1vDZPfftKDvSkp3zRdF0DmlvNYG5dgz0rOdh3sET0z/6YlZUc6he2tLqSg13nb97x7EoOr2fVcvdKDjk9qPzjtZLDpWPIE1kWdAiyLOgQMITFkCcYkgpDXmBIikodDPkbDIFS36rUnwcp9e12rzF14+/caX92TF2vVHnAmPoSQzCmnloM+b6az4teX+iQJLKs1/gzOmRZ0dPeMSIshphmMoK8EUNOBuS7okP62Q+ayRC7ikNp7Wa4YEhYQEYcYTGExvsSI4YEBmSAiM55gAjEkCMBGSDCYojMRunyjh2WFnVI+E2bDFuHsL9qM2wdYriAiOIHkcf6tlY1IO0muHdQ6s9nDcimGYHblTp7O3KWUq8yLJ+P7/e/QfizgDwZgNj9Fi0mARYwS2BMfQoIe/7Z/hjinvvGVuq6xETEyLI+//TBgDwjAvLcDIgN7TICQ8zPm9ntgGhPhhQhASmCMyTMBvfeDPkEWAfjhyITQCQ3hOwB5Oua2OuIITOAiACA+DLkM1l3YQcgZa9Ya9Zn+raW03fG1qv0B6Rx/mOd720MOf1d1me6EsagSvHm26Dv1oQht7otgKz10GsDIDo7/V2WmVm9p6/Sb/fzNwcQzw3VgwHSE+TLAcR+xGoXA5InK/XP3HpKok/7/EyPATEzVylkIEA8e2iAR5EzlHrz8p399A6k1D/LK1xV9Nnae8tj6u9QgGxTrFUiwVLqmkpT4Xy/tuDx24e3AeQ7SuzyDR85nBJDzMIqcBQeENoIyLsIEUN+hnBTHVOfX0luFpD3/J93V54FxKwB4q6y/G+lFzx6SHXLodSZdqpj6h8uIAwd4smQt5e0KQL3UKoMiQiIjApI4gxp1lH+fMCQJBiim9+f5ndAQAwY4s8Q3fbepzkAhjwC6NBNSv3T9NmnW6n9UwMiuIAsDoAvj6m/2VU6bEcPcZR6QGMr9U/TZYOl8z8VIAUXkMFAjp8wfBcxbcvX72co9Xac8DPYy+ATEhCzrNSjArJJqVO1QZig2sq+aUpqtqSakilL8iHpSWJ0rDZRrdg8U7LT/Mfu6lJzOy86Jt2Waqn37txVCwfo3nH7P4h3e2J/CSPH02Nqte1mpp2uFj/swgE00+JEvn6f7PZxfJYVN6in/vX7YYCkKgxTnx/yAUPAEDAkBkM0GAKGgCF/5F3WGUp9kSFQ6nGU+iJDjgfkekp9x6uzp++EnQlDjn+5+I76cvGx4eUiYgiyrL+T9kKHXJQhioJM2AFDAjGEqmmGBjEkEYbYTSUNYkgyDCn5oRFD0mGIqbeLhlJPRalXq86IVUy+L549tyn1f58ZK/vun5Qft9nT5L93+9frj6mXD6zRPHW1sLYl27yV+rEb3F9NqdvFmTKilfWylOeWsN4x5KQN7i8SQ0ooqtk6XWifuPu6d/PdCsi/oza4v3CW1QHRrmDGZ8gLDDmEIbJVh3LB3cuPIR4t0L8dKcMw5FNcmiEuQIrX/LbJj7mdlF/KpwXq82/0Q12x7dqFn9UTTVFclyE6a9YvW3xkLRo7pd/QAuHqPbOgQ5arvIpSb4BQ7dvFA9ZS2lClr1Jfmbz58/crKPUyzRLdakBpmK9SDzC5NhWlXr/rLWWI+hOAXGFMXdkvyEUAHRpQ2vqOqQdgyA3H1KPEkGDrAdxwTD0KIMorqK+EkBuOqUcBpOg215yaKX/ewvQH1vocDAkFSKCrBEP+ICBgCBgCQEIz5IwdvNxVugCJeZU7fD82bAp2NaV+Kdv09Xv4XSA3VOkCRKvgV8muckcPPTZsLKmF1tqeUltfUr8lmjk2WzL28dwdm5Z6J9SWmtfvi1ULzXFsS8RyXJaEcLa4LhnBclxUPVRV2B2rGSImHSzWgjoJ+8+tmrII1aZ+S2RLqpNcyyW7wkHRarWZUu+O2lKjr+cdV3VrhmPrhFiO7XILk2Nqvu1ELMdF1UNjx9VKDg8aOzb1L2RZ0CEABDoEDAEgYAiUOpQ6lDqUOpR6OkodMQRZFrIsAAKGABAeQ8zPJxkAJDJDZJaNtqECIJEZUi1GTHaWoQAgCcWQbqdPKPU0lLoMsnEelHoopd4RJHWlrkxlwujQV5mWUpchNrg/I4b0W4CKwFeZVAzpCZJ8UDfdN+3ieoCwlfoggiSfZWm/6WmXZIhop+JeIu01Xk+tSzJkmGJdQId4ceSKDNEDglxCGOpuXpS4JUNGGuQSSt2DIxdkiB6tKZeUDrGbRi38cOPIBXVIYmsG/ATuxJcCOECpq/EimEm9y2KZuNm7rB+CJBVDeKbvp9QvDYi4oVJPDhCPBRred3yXlR4gxXvd2FkWGHJGlfp9Zx1yPUB83p2AIcdXeft3WaF06AHSdjce1/+2N3nTl9ToHko9nA49QNqu4SEiXeXJ80MSjyHe/ECWdTAgzVcn7O67fpZlP2UsL49qKyNTU1KzJdWUzGpJ1F9ILpRG7qalH8fvN5U/2jAdE9cxuRz/lLa0OLfLBsy18+rCEPNDAAgAuSMgOQC5PkPSV+peshpKHfbHlHr8KqHUEdQBCNJeMASAgCEABAy5JEOEzDJJGoAkwpASjmpz4uZ60tiDyqmBVbwqD96DStT7s6X4CfzfVOr9xpLor8PtwQKkJlYLCGJI5BjSbEpMixvcA5Bzs6zyWSW13e5TAZA0sixdrZglkfamokNEicZgL1wAEpkholpKznSIAJDIgGRd2ksA5OjmqAoQtQaIbtPdNs2CUj+yOSrP8+UqH8VgYSaCVI+vG4ePqiytNf7+LCBWgVCd+yKoR2vO79veoRABILEBKUwZPmRiK8r9aUDOcgdAAAgAASAA5O6AQKlHaM5wTB2WmDCEJQ4IYgiCOgABIFcChIQQ/V5h9uTa1G+JbEl1O4qtlKhMIppjc6XeHQ0dmyXHVd2a47h0QizHdnY/y7EtEctxIeoTnY5N/Wsx7dWllTA01hwoTe0o9RWqmZJeL6ldl8B2rA5yrDktTn5zYmRZMAACAyCJ238BBgDW/YEaeiG4tAAAAABJRU5ErkJggg==\"/>\n",
    "\n",
    "Izkazalo se je, da Marsovci včasih tudi koga ugrabijo. V tej nalogi bomo vadili reševanje.\n",
    "\n",
    "Najprej celotna slika: čeprav so marsovske ladje okrogle, je smrdljivi kevder, v katerega zapirajo ugrabljene, pravokotne oblike. Vsaka soba (razen robnih) ima vrata v sosednje štiri. Vrata se vsakih deset sekund odprejo za trenutek, torej prehod skozi sobo vedno traja 10 sekund. (Ugrabljenci so omamljeni, zato kljub odpiranju vrat ne morejo nikamor.)\n",
    "\n",
    "Vsako polno uro se marsovski stražarji teleportirajo v določene sobe in prehodijo določeno poti. Vse je vedno enako. Točne podatke bomo dobili od MOSSAD-a, primer pa je na sliki.\n",
    "\n",
    "Kje so ugrabljenci, ne vemo zagotovo, prepričani pa smo, da v eni od sob, ki jih stražarji največkrat obiščejo. Na sliki sta dve takšni sobi, `(6, 4)` in `(4, 5)`; obiskani sta po trikrat.\n",
    "\n",
    "<p style=\"clear:both\">Reševalno operacijo bodo izvedli slovenski specialci. V istem trenutku, ko se v klet teleportirajo marsovci, se bodo tudi specialci teleportirali v sobo `(0, 0)`. Vsak bo šel po predvideni poti.</p>\n",
    "\n",
    "<img style=\"float: right\" src=\"data:image/.png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAGaCAMAAAAW+uWYAAAAGXRFWHRTb2Z0d2FyZQBBZG9iZSBJbWFnZVJlYWR5ccllPAAAADBQTFRFAwICDqpbOTuGmpqcv7/B7+7u8VRa5N7alJbH9YuP+blsfNClzs7Y95Qd7Rwk////gcFdnAAAABB0Uk5T////////////////////AOAjXRkAABjwSURBVHja7J2JgqQqDEVtIIVV0uP//+2IuxZLUESwQ78l49iKHEO4gFC1lLJKFRUBAaFEQAgIpWuBKFZVjGPOlAx3Hu+uWDHhPQ+GEwH5PJwx1El9EogL9vcXyAtinp27ixIHhOsyqSqOyL4+E/MidKfpkubYExXuxenO9J+lr6eTwD15xRTmrD4x7/vaPTN3nIcCIvuCU4gnYLr0MEA4H0vG9+pzfU/AXbSFCgWkQlfUuvgkvr5hfl/qH6R7Hn4GyFgc3F8qXTlzXNlNBShQJwpcGfKKo4Bgc8ix+UPncnwD7YWEes6xwhD+9xmHbY2aRwSiz0KcqLA57GqGAPdAPc2YPXEKiJweElnrXgAEVWWBLj8EEIG86ZA7oSI6yPTA56qsuYhRxRdYZWEeVzKUb/bZQxSKjqkMExo6wH385/Herg4aV66QeC8Q1LkVstk7XAwHBFXMSjctGWdIIuhq1fk8twKRqDqQ4YSIGrwIUSr6NMH8TVQ+NrE4zo9x1S/vBYT91DuBSGwE6Zu94C0PGdSk5d6IPZ+Byie6yaMGKieAiCWoRwXC8HrAf2v9Ouuk/6diXZIFPBKK2tRuE9a3AVMkagGiIgJh+A4RxFVZtSSBvL+fMf6RZJgmsN4cqUMEPmphgQTx8F9ViSF1eRUQx0PmMsa8/MgOijhAxstgoxbDXbMK4AHotmdIDAGcD2H6EwCnIaewZL9khSyO7m1GFiEOiO5CHV5q34kchs5miAVE6u4x3QuKafd2zSyFefkDFK7o23inuk6081bYHlcUkKV7tPKWSYXqcMUDme6NaznhVJDEdkdD5bkk0sElZ/2rimmTcY46aUqIOzPO0ZUb4lTeXxL1NMBxwyYCn0Ohb26/JI0YZpYICAGhREAICCUC8lwgMMi1qS9isaCVKEsOl7Ba7Wgpp2XMwjozuGxJwGVL+bKlkNk6VkbKAUQKKbtSAzmkxYK9xQ3HjJbOynKsdVh8toxZWCyOurHUPHDndfrEmcFVFoSwZmt7aSUwN4bhuR1A0CIMLYZk9EuiT7zzcQ7cm4DkDwTw0yywJyqIfkn0iXc+zoF7UyuLmr2UAoFQDKGgTkAISNFApu9R1M6qDMeMVoU8rzsTeR7jyPOUZOa/LRrIPL3mekshz2PYK0tm/lvykHs8RArj35YN5LySktEveS6G5A5kM5T/LS9Bqv4H1lb3P74/ZjlPNs3X38pUSl0qLJBslDowz7SY5mdI0mAp5986zrtVfvEqV0Ws89VV8VJPQRI+IMqJQQWd1xAQG5BxHv2cx++Kr6t2GikbgJ3Fu3/B+rcrqxFqe8zqIYl0SNYxZJnBqpIpKauHkDBcZoFP01NTPEFzs4fkDGSetz1Nyv2+imB1/yNXVq3/tzuGt3Q6+ruDxfd5qS1TPs1VVsZKXew/S/m+Sj0Lqnws9n2sfkYMQQAxvamK4Txk8CS2+13zb+h/FOp6Ww8Z8vKHgJyudL+UlLWVdfzeda2eAQQSADEE9XtbWVk3eydFaP8ISH6GJP0WMqsXKHWlgj5ZzFgYTiBMHwG9X+/uv5/fIUm/hQYSXanbYkh5QMbMzbFk3SP2+vfqPeS3/5Eeywrk6+VtTscQgQUC5XUu9l8gyrl3cV3xDUCw9TjYgKRQ6kGtrKyVev9p42qFleNAJBrIBUr9QUD65Y+WdRnTALnXQ4odU78KyPm39CSQUodwQ2PIBwhIRkDwT3DBeMhjlLr/Ktav+0mpJwHyLbnQq3gGCENS6lZh6Eq9Ur8ECCl1NJAvpW4FIrBASKkHKXVfULcCOd7sJaV+ppV1ARBS6tkBIaWeFRAShiFAhmXF+jXGeiDTUmPQKqcl+eejLdXCeMxsTRcUBouvLeGw+GwNWdCD6qZsKSkMWZgWlV2OCWe2hDsz7S4zfuurZG5W6g0p9byU+g8p9byUekNKnZQ6KXVS6qTUSRhmo9SBgOSl1BVjIc1eUupXK/VAIEUP4QrbRmU5jan/JSAXVLrxx9RlXUtS6ie6TkipO4FI1/aJRYypw5OUurTuGlaOUrfGkAKB8O2+0yCxrSyFBSLRSh1dqAoLBCQWCPreEq3UZfDj9LPfmVhvi1OmUg9rZeUtDOV2n6IylfqTgLR3ACGlnhUQEoZngJBSzwxIKUr9LwAhpZ4BEACsUgdsDAH0Sg5otQ1YpQ6ABYK/N8Q+cbm3Zz/kUalXuwlTNusfw53H2Q9DnYezxMOU+t5DvpX6sEUqmzdLDbUkHP9dhMUfptT9zd6zxbasZuz7jSo6kAcKQ3xLJ6DrJF4ri4DEUOpNcyuQspX6BUBiCsNDQP7GEK783KHUCUhmSn3QrfIPzX6/AAgp9QAgcFgt36PU+91cn6bUbWlYUQ79Mt4ypu6JIWUqdZu8dMeQPMbUH6nUI7WybhlTf6QwTA2kIaWeGxBS6lkBIWGYBMg9Y+rPB7JfOOD0R/HfCwd0OiTawgFjYqyWxoUD+JMWDrgqCib8Th1IqSMu2ZBSJ6VOSp2UOil1Eoak1Empk1IvQqkLUup5KfWasZaAnBCGscfUVV3/BSAnX2f4/Z03qLoshhwplLKUenjj2RJDrDzsHnJAh8xKPUALFKVDoil1O48LlLo1hhSo1PW6ARXj0tAB444h7r6sFQ95ZV+WB0h5fVl6GQc9mZxB1GbvwuOTQqmHtbKyFoayb8DH2DZvDWRTXyVQ6g8CsvfiKEC28SOBUg/UIQUodXESSFdf9kD6enNVX8kufZREJh5+YgdEdH9mzHLmx/TbVRVw7zKByF/QmxODdomFR4JUVf+Cf6eLmQFn7/sfUlVZ7CSQXxh3X03K45e9wn/nXxCQrlmSHghMu3gfjYJSxwuY/pN5CvOQ398bgCzfUB1U6jBt4w3zht6J0gEPeZ0CkkKp6yh3UqnDUt9+0sYQlthDrlbqGtBcYZ1Q6r2PDMc+mQf1cx5y/awTtWzeHWk85LNpoST4LPoiYShviSEbHmfGQ1ZvxOIjkKEwzBvIlkesAaq1j5Sr1O8A0vFgSugkYwJZ+0i5Q7h3AKnmxKMCWfkIAQkBsppBHhfIykeKHVOXtwnDS/qrP7beoGLG1HMAcnxM3UDkIz99AqSH5DamLu9S6pYUNqaOT8WMqcublLpNXoaNqeMVazFj6vIepW6t+K6bKEfC8FBQL2EvXAISBQgp9ayAkDAkIATEHdRJqQcA6We+wDwHZrJgb3HDMaMl1PpYK2UX1EdrOTZMxZktYxYWi0+W8mShf5z9307TgDbZ4vvMwAwE1lnoHsearW0WhPCVzGQ5lbru+O1eOTGkxYIuKxhLDpewWp227jxE6U0wxmMmy5iFxVKzNaS65ubMgDJkoQOyO2bJzNj5o9yZiVBGpNRJqZNSJ6VOwpCUOil1UuokDAkIASGlnimQSK9zuWu/ZzGmjh7XRt9Oodd+F+H3HsbUpXVMXWGBCCwQ9M7tB4qSlHr+Sn2d3DHkeLLqkMNAGKufA0QMq7eSUs8jhohhHum0bkChSt3qIeUB4RUXQi/nQEo9DyBDl6SYv2krUxiGeUgJzV7jV7ik1G8DIqsK0gHpdcj79S9GqrZ/fMMjgACbv6JKpdTf/65Jr/KBcM5WraxUSv11EZB/ULxS71fLElcrdfV6zVfTOiRW+XeZ3x5AvL+ZC0O1afZeptRfS32idUg8IP+eBqT3rggLmPliiI4a79QeUuwQrmUBs3+vl665hnTWmmPu4iFvKdXq5y22f7b+vGere5M+UjH2UvJRQCzrZXWpneNvFOs9trKM9cs5HYIAArVOeoMkf5L5ecg7hl9sPWRuJcQF0it1PxDB+qRbMYhU37NwwCQM+dU65L1RCXd4CExFjQPC5D0LB7BBiMiLgSwxvdchsYAMY+p1LRBAFAvyEFbf0tvLVss4XAhErfwjZgxZJTQQljOQfr67PCUvDyl1I5BzY+qmS24fp47hITeOqV+VfmweckRKuWPI7p2didTHgSQRhmlTY/OQw0CsrayDSj0jIKl2+rxHh2Af59YYkh5IE7GVFaRD0I9T/zUg93qIf0z9j3nIbUrdFUP+sofcpdTxQP6Yh9yl1MlDEsSQEKVOHpLAQzxKvXwg7bAcppgXxpwsaBXKUi04re4GHRA+lF5/TMxLcS6WMQsmq+8c7ZpNjMN8SV9mul/aHdtlYeymr/kARGAzc7SM7u46ia/UkV0nJSr1NJ2LTbTORU+z9+Dj1Pl0Lpap1KnrJDOlHigMSamXJgxJqWfQdTI0hEiHRFHqoo4ARA9lAyn1fJQ6Xz7tIw85qdSVbouGAPleFY4LwWYfyUmpJ0jxx9SDh3CHNEz931q9j9CYelIgwgWkd5GalHpKpQ6mlTbHKot5qyxS6tGbvZZL9kFdZtHKAvN36k9V6uZLrpu9dwd1lhbI3cLQfMlhad0sdIioGAFx9GVFT9INRO/dnRTIFWPqqiQgv9IJhFU8HhD5/kqv/QH+4u+59JpV+mmQyXjii3H2y3hvQ95APi4gei/1aEAC1wOQusV1SYJTj1PfCETppoWoQlZkczS9A7+hVfJswXctI+Pxc2vWjR4CiYBshCHT6wDFAiIDgcjmPBB2AZB6+5FhSiDDKicLkHNKPRiIOg/E8henHmf66nPZz2RJH4lMynTmxwRkpdRHErFiiAxeKeaqKuvH9Tjw9jQ9xi923u83oo0yJYnRIR9PDJm+7tL/iwfkhUv6G1DQlVZfcQ21V4P8z8/4ex2Pudpj/T+bKsv4OOBd+WbgEbqqxDsOkGrp+4wF5KC0jSIMP43XQ/xNQXaMCJwHMndIR62y7gQythNcHvL6d42HYESpzBFI/LXf10rd7yGvqzxEFuohF639vqmycvWQz9M95HtMHeshrubG6CEvdIoNBAS6vY4Rhp6z4q/9voohqvEKw5epTdSadQgyoYePP16lHjXhgFy09rvJQw4CqfMBEkWpbw8ax9TRl/ScaGv2No7HMQIRWA8xjqmjx/OlR6nHGOY6ENQvWfs9MIa8/b2958bbzsSQ1ECa64AobCvr7R8P+StAUgjDn6RAJAFBxpC0QNpCgeSh1GPGkMKBXKrUVd4eIp/uIceVeiEecmDPaV/GAK1DDm/fbdchgAUCWA8xXRL33FYgru272/0k5MmCjrjXGkcahmNyntW8trobdOUldF/NeMxkGbNgsvRGAkJ0hSfGCRbv0UMcWRj7slbH9lkYgSzHPJl5T+Mh3jIagchNtpTLQ4SUXanBOAS8WLC3hOnYWG1sfkOo9XmthK64Bms5NiSxjGGbsrBYarY6D5F6qfFaTis5jECGS4MyZH/0kM2xVqwyA9O8rPnYKgtCfWVreu5teShhKLcRyLbcxIOCeh5KnVpZmSn1woHkr9RrAlK2Uv+QDslLqb/RG5KRUk/iIYUDieYhclTqMrZSzwhIUUq9Un0M4exupW4EEkmpn0qJx9SrSu9BpZf5Y+LWMXUjkL5A5n2zXEBal4egm0QKC0SiPUQF3nueBcuYMscQ4+MYgSish0i0h8j1rFXpaGWp24N6pBiy8GC5trL2RPIL6mpsZakYQX3koVZAPpm1snZE/EBgWZg1CZCxqJqfGM1e1fNoVb4eMovGkYgfyLQSC0sFpCdiliLhOkT2GVfWGJJDs3fjI34gvB9QmPvkEwD5sTaDDghDpU3ZbwOZrQ5Z+wgGiEgaQxrHV5lJZ78nFIYrH/H3ZbFKpW1lOSZDHwUCK6U+jRiOu+tyw+668WOIbz798sXCBwEktVJvrJPTj957HUP+jZ8Zhn4ReEqpv/DfuXqVer8w/fmV3cKUerzPEb6BvIYPQEOBnFLqJ4G0WyDVshpnGqXeNpZXUx28dwwPOaXUTwJZK3U96aHfCxdSxZD9r6zc5WgM2QDhx4BE0CGHgXwr9Vi7RYcDkeuAcg7IK8xDIGIrC16RgZj3U08ARG6aXOeAjKWCjCHvNiIQ49oQqzUfFh7YvixxDxC5FSXngGyFzqnHCQZifLhvHfKCvIHI3eI920uqmtl+9n/EAhHIS8YFsuKB7u1lyfqyjDxGIptLChaUwCg8pWHjHHSKBOS14uEH0l8e+LxAakIg8muBK0O1EV56dg8BdgeQtX8ggPTDO91/VDqlbuTRE4ETQJjRQzb3FlGAoEtoOHHjH5YRw7VS5/3STLGkOk6pG3l8dadE8ZB97A9KIkKJbP3jyJh6Ig8xLbbY5OUhdXveQ3b+cWDWSaoYYlwFzhRDalPaHDUCMcUQ5bhi/X3Y8tznVrbOdm6vf+XKofTM3Vu1o5/D3soSW3KOS7rSXwLygwVi6HjCe0jAmNefA9KMrzMEegiP7yGJgMisgTTz6ww2DxHkIemANKvSg7MewsrwkJyBNJvXGcytrD/vIUlGDNt5fu/qdYYAD1HYGLJ5HKeHoEcrJVqHSCwQ19zeVEp9nsC4vM5gAoJwWJeHmJR6e2c6MPsd+526yXqbvlPfWuOX6M1gbT4ql836O/URiD8z9dTdOxzbfqe+/o2JnCNbNgtQn8/7ywiM36lLVwzh2JUcuOmYaSUHvl/JYbVkwli/jMf4eiWHaTUFU2b4OlszkCEz07ys/nZT/voszEC+VndQ4x5U1gUmVlng9jUdduXB7Ss5bLOQ0Ve42/qFX6tDqNkbAQjpkDuANPE95IeUOnkIeUiBfVkUQ0ip45S60UPUCaXOSKmfUupeWU1KfcSabNaJwUMA6yGA7ssCrIfgnxvOnChzHVOnGEKtLGplkYccByIFkIdkA0TouaSCPCQTIKBxzJNJi/WQQsbU/X1ZmoegGJKPh7DlC9yilfpTxtTF/GWIMxNh+/kFK/WfxvDD+p/G+/PTn/ez+nPJSl3vpy44V055CYE7XoYq9QtSrkrdN/sdqkpuVg44uL2yCwgihlyQCo0hom9hCe5eL+tVHpBSW1l8XDFATU2tGB7ywj+BTAmkBA+ZFwxg41IOxqtAmIvIgCe4ykWgUKXOp6pqMiw6xLlOwS5B0BOoZkk/K7sZGlm8MaXNiVNzbJ2MhVJIDEEBSfIE55S6UGr+Z06iXv2hLgAITDLEWWXdCASv1IO/Ds1TqY9LOHRBfbjPud2izZUSHLqky0NEfCDxH+fYbtHQb3PG5+WZ8kmhY+ongeSi1FvJemGYHQ+nhzwZiJ7PzTnE6e29JYaoKOsBPHMI95ZWVpiL1EBALvaQnogtAtf3Pc7f9RAHEBCZAZF/wkOUdWESKchDbvCQwEIhIFd7CCj1WCAFKnVnDLnxcYz3/viUer4pYFW3+ma1F1kYZg1EPQyIDAXyMB3ygKA+7A8m5p3CJgv6Lha/peZtxsxWO1rCYPG1NQprY2b4Jlt6JNCSGSlQ2RLObAlTFg6W0XtcOGCbBfIQavbepNQJCCl18pCilLokpU5KnZQ6KXVS6qTUUwEpL4bACASolZVHK6tjpoEAo1ZWHh4y7BkFjJGHZOIhrvlWBOQOD3kUED6/YLxQD5m2+lLPADJMJF0mkxao1MFBrtgqa/4soUSlDna9kp1Sl0ilPn9JVaRSh1q1hSSkMITp85AClDrMu3bJtryEBLI4SAExZNn9zu8XhcaQlYOU0MpaZrvLhwJZRZAiWll4HykTCKwWaCpDh6B9pMy+rHUTqxAdUiN9pEwPWa9gVopSR/pIkUA2GqQYpY7zkSKBbD7BzQ0IJslnAZnXn8lSGKJSMTodJQxz/EY9EAgrR7P7Z7/verFy61w89e15kdOA+sndZccQOw8aMYwIRMZYLIOAxAPSuXxt+6lrUSP8g4BEBeJI9Txw61lMhoCkAcIB5R80LysZEOxiS+QhSYBg/eMJQEpIkMliZBcp9YJ51O3zgeSj1KP4R/kf7JTS7D1TjxfWypJS6s1IhrRYsLe44ZjREmJ9rHVYfLaMWVgsjrpxZ/WPgzivKxRnBldZEMKare2llTDcbvSQ7W+4V3IQoiOrxJAWCzpWG4sbjnVJ6ixvLL451o6WMlh8toxZWCxuz9Y2M5NhyNba0gtM2LOlNlng9mxts8C5IVsTkE0WHqBDiq2ynqrUCQgBISCPBCKfqNRLTk9U6n8LSP5KPehEUuoUQyioExACkrQvi4CQhxCQDZBMd9j5q0DEdg8qAnIzEOhYgN5fcjwI+G2s0SdecMk7733p9t0tH0iIilR7kiT9G9wPjjUBAXT9gtbAEqJfEn3inY9jvLfRQ9QGSO8h0rmfOsWQdDGkq6uUnskxxRACcncri1cV49TKykiH9M3e+WtXAnJ3s7fjITirqMpKAwS8S/wN0ZxPiwcQkGuB9C7yaa1A5LQO0LivOgG5GkjXGobWDmQWhNPHuKTUr1Xq7ntXrdp7CKU7U6UVeg9C9XKElPrlSt1970pL9K6BRa2shDHEdW8dP9TQ/U46JBcg/QR7yOIJCAgN4RIQAkJACAgBiQiElPq9Sp1Sbko9J2lLSp1iCAV1AkJACm9l8S51d+VDWizo5wD7LTVcwmq1oyWcljELi6WQ2VKAy5bwZUugsnW0jMrYnJhaWZQICCUCQkAoERACQomAPDL9F2AAS+LBPr4sZQoAAAAASUVORK5CYII=\"/>\n",
    "\n",
    "- Če specialec sreča marsovca, ga prime za ušesa (ali antene, bogve, kaj imajo) in ga zadrži v tej sobi.\n",
    "- Če v sobi hkrati naletita na marsovca dva specialca, z njim ostane tisti specialec, ki je prej v seznamu. Ker vojska in hierarhija.\n",
    "- Na koncu (ko so vsi specialci bodisi zaposleni z marsovci bodisi so končali svoje poti) morajo biti vsi marsovci prijeti, poleg tega pa mora biti po en specialec v vsaki sobi, kjer bi lahko bil ugrabljenec. Morebitni dodatni specialci so nepomembni.\n",
    "\n",
    "Po koncu operacije teleportiramo specialce skupaj z ugrabljenci nazaj domov, pa še marsovce mimogrede ugrabimo. Zanalašč.\n",
    "\n",
    "Primer uspešno načrtovane akcije je na sliki.\n",
    "\n",
    "Simulacijo boste napisali za oceno 9. Za ostale ocene boste pisali funkcije, delno povezane s scenarijem; nekatere vam lahko pomagajo, nekatere morda tudi samo zato, da si znate kaj izpisati in izrisati.\n",
    "\n",
    "Poti v nalogah so opisane v obliki `\"vv^^^^>>v<\"`, pri čemer posamični znaki pomenijo premike. Kot kaže slika, koordinata y narašča v smeri `v` in pada v smeri `^`. Poti marsovcev na sliki so torej takšne:\n",
    "\n",
    "```python\n",
    "poti_s_slike = [\n",
    "    (0, 6, \">^^>^>>vv>^>>v>\"),  # rdeči\n",
    "    (2, 4, \">>vv<<^\"),  # zeleni\n",
    "    (5, 3, \">vv<v<^<vv>>\"),  # modri\n",
    "    (8, 8, \"^^^^<<^^<<<<<\"),  # oranžni\n",
    "]\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1fb4aff2",
   "metadata": {},
   "source": [
    "## Za oceno 6\n",
    "\n",
    "- Napiši funkcijo `koraki(x, y, pot)`, ki prejme začetni koordinati in pot ter vrne zaporedje koordinat polj, ki jih ta, ki gre po tej poti, obišče.\n",
    "\n",
    "    Klic `koraki(10, 80, \"vv>>>^<\")` vrne `[(10, 80), (10, 81), (10, 82), (11, 82), (12, 82), (13, 82), (13, 81), (12, 81)]`.\n",
    "\n",
    "- Napiši funkcijo `cilj(x, y, pot)`, ki vrne polje, na katerem se pot konča.\n",
    "\n",
    "    Klic `cilj(3, 6, \"<<v\")` vrne `(1, 7)`\n",
    "\n",
    "- Napiši funkcijo `cilji(opisi)`, ki prejme seznam terk `(x, y, pot)` in vrne seznam končnih lokacij.\n",
    "\n",
    "    Klic `cilji([(3, 6, \"<<v\"), (2, 1, \"vv\"), (5, 5, \"\")])` vrne `[(1, 7), (2, 3), (5, 5)]`.\n",
    "\n",
    "- Napiši funkcijo `najveckrat_obiskana(opisi)`, ki prejme podobne argumente kot `cilji` in vrne množico največkrat obiskanih polj. Če isti stražar obišče isto polje večkrat, se to šteje za več obiskov.\n",
    "\n",
    "    Klic `najveckrat_obiskana(poti_s_slike)`, kjer so `poti_s_slike` poti s slike, vrne `{(4, 5), (6, 4)}`.\n",
    "\n",
    "### Rešitev\n",
    "\n",
    "#### `koraki`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "71653d93",
   "metadata": {},
   "outputs": [],
   "source": [
    "def koraki(x, y, pot):\n",
    "    polja = [(x, y)]\n",
    "    for c in pot:\n",
    "        if c == \">\":\n",
    "            x += 1\n",
    "        elif c == \"<\":\n",
    "            x -= 1\n",
    "        elif c == \"v\":\n",
    "            y += 1\n",
    "        elif c == \"^\":\n",
    "            y -= 1\n",
    "        polja.append((x, y))\n",
    "    return polja"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6f03b1d1",
   "metadata": {},
   "source": [
    "Bolj zanimivo je tako:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "4f2ec129",
   "metadata": {},
   "outputs": [],
   "source": [
    "def koraki(x, y, pot):\n",
    "    polja = [(x, y)]\n",
    "    for c in pot:\n",
    "        x, y = {\">\": (x + 1, y), \"<\": (x - 1, y),\n",
    "                \"^\": (x, y - 1), \"v\": (x, y + 1)}[c]\n",
    "        polja.append((x, y))\n",
    "    return polja"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ab7f1709",
   "metadata": {},
   "source": [
    "#### `cilj`\n",
    "\n",
    "Funkcija `cilj` zgolj vrne zadnji element, ki ga pridela `korak`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "acfdce8b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def cilj(x, y, pot):\n",
    "    return koraki(x, y, pot)[-1]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cb54d6b1",
   "metadata": {},
   "source": [
    "#### `cilji`\n",
    "\n",
    "Funkcija `cilji` le pokliče `cilj` za vsak opis poti."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "6059a495",
   "metadata": {},
   "outputs": [],
   "source": [
    "def cilji(opisi):\n",
    "    return [cilj(x, y, pot) for x, y, pot in opisi]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "45fd086e",
   "metadata": {},
   "source": [
    "#### `najveckrat_obiskana`\n",
    "\n",
    "Pri tej funkciji se moramo izogniti pasti, da bi uporabili funkcijo `obiskana`. Ta je neuporabna, ker navodila pravijo: \"Če isti stražar obišče isto polje večkrat, se to šteje za več obiskov.\" V množici pa se večkratni obiski izgubijo.\n",
    "\n",
    "Tu povadimo stopnjevanje pridevnikov (emm, prislovov?). Uporabiti slovar bi bilo *praktično*. Uporabiti `defaultdict` bi bilo *bolj praktično*. Uporabiti `Counter` je najbolj *praktično*. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "b2be6d64",
   "metadata": {},
   "outputs": [],
   "source": [
    "def najveckrat_obiskana(opisi):\n",
    "    c = Counter()\n",
    "    for x, y, pot in opisi:\n",
    "        c.update(koraki(x, y, pot))\n",
    "    pogostosti = c.most_common()\n",
    "    naj = pogostosti[0][1]\n",
    "    return {polje for polje, f in pogostosti if f == naj}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a8a4114b",
   "metadata": {},
   "source": [
    "## Ocena 7\n",
    "\n",
    "Specialce označimo z velikimi črkami angleške abecede (A, B, C, D, E, F, G, H, I, J) in marsovce z malimi. Tako enih kot drugih je največ deset.\n",
    "\n",
    "- Napiši funkcijo `situacija(specialci, marsovci, sirina, visina)`, ki prejme seznam koordinat specialcev, seznam koordinat marsovcev. Vrniti mora seznam seznamov množic ter širino in višino zemljevida. Če se seznam recimo imenuje `s`, bo `s[y][x]` množica vseh, ki se nahajajo v sobi s koordinatama (x, y).\n",
    "\n",
    "    Klic \n",
    "    \n",
    "    ```python\n",
    "    situacija([(1, 0), (0, 2), (3, 1), (0, 2)],\n",
    "              [(2, 2), (3, 1), (3, 1), (1, 1)], 4, 3)\n",
    "    ```\n",
    "    \n",
    "    vrne\n",
    "\n",
    "    ```python\n",
    "    [[set(),       {'A'},  set(),     set()          ],\n",
    "     [set(),       {'d'},  set(),     {'C', 'c', 'b'}],\n",
    "     [{'D', 'B'},  set(),  {'a'},     set()          ]]\n",
    "    ```\n",
    "\n",
    "- Funkcija `znak(m)` prejme množico črk.\n",
    "\n",
    "    - Če je množica prazna, funkcija vrne `\".\"`.\n",
    "    - Če vsebuje en element, vrne ta element.\n",
    "    - Če vsebuje več kot en element, vrne niz s številom elementov. Če je velikost množice 3, vrne `\"3\"`. Predpostaviti smeš, da velikost ne bo večja od 9.\n",
    "\n",
    "- Funkcija `izris(polozaj)` prejme seznam seznamov množic, kakršnega vrne funkcija `situacija` in vrne niz z izpisom v naslednji obliki:\n",
    "\n",
    "    ```text\n",
    "    .A..\n",
    "    .d.3\n",
    "    2.a.\n",
    "    ```\n",
    "\n",
    "    Dejanski niz, ki ga vrne funkcija, je seveda, `\".A..\\n.d.3\\n2.a.\"`, tole zgoraj je že njegov izpis.\n",
    "\n",
    "    \n",
    "### Rešitev\n",
    "\n",
    "#### `situacija`"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "69cc0af1",
   "metadata": {},
   "source": [
    "Ta funkcija se je izkazala za kar zoprno. Recimo, da imamo:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "5710a400",
   "metadata": {},
   "outputs": [],
   "source": [
    "sirina = 5\n",
    "visina = 3"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dae1b5ca",
   "metadata": {},
   "source": [
    "Prvi problem je bil, da takale inicializacija seznama:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "75ee56b4",
   "metadata": {},
   "outputs": [],
   "source": [
    "polje = [[set()] * sirina] * visina"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1249dda3",
   "metadata": {},
   "source": [
    "izgleda pravilna"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "e4339e4f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[set(), set(), set(), set(), set()],\n",
       " [set(), set(), set(), set(), set()],\n",
       " [set(), set(), set(), set(), set()]]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "polje"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "998fa902",
   "metadata": {},
   "source": [
    "vendar ni:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "0286971a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[{'A'}, {'A'}, {'A'}, {'A'}, {'A'}],\n",
       " [{'A'}, {'A'}, {'A'}, {'A'}, {'A'}],\n",
       " [{'A'}, {'A'}, {'A'}, {'A'}, {'A'}]]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "polje[2][1].add(\"A\")\n",
    "\n",
    "polje"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "99e772e2",
   "metadata": {},
   "source": [
    "V vseh elementih `polje` se nahaja ena in ista množica. Temu smo posvetili večji del predavanj o imenskih prostorih ([zapiski](https://ucilnica.fri.uni-lj.si/mod/page/view.php?id=7769)).\n",
    "\n",
    "Polje je potrebno inicializirati z"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "216ef007",
   "metadata": {},
   "outputs": [],
   "source": [
    "polje = []\n",
    "for y in range(visina):\n",
    "    vrstica = []\n",
    "    for x in range(sirina):\n",
    "        vrstica.append(set())\n",
    "    polje.append(vrstica)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "fbb4c023",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[set(), set(), set(), set(), set()],\n",
       " [set(), set(), set(), set(), set()],\n",
       " [set(), set(), set(), set(), set()]]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "polje"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "9a01c97d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[set(), set(), set(), set(), set()],\n",
       " [set(), set(), set(), set(), set()],\n",
       " [set(), {'A'}, set(), set(), set()]]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "polje[2][1].add(\"A\")\n",
    "\n",
    "polje"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6cc1a91c",
   "metadata": {},
   "source": [
    "Ali s kakšno krajšo različico, kot je"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "a3bf0503",
   "metadata": {},
   "outputs": [],
   "source": [
    "polje = [[set() for _ in range(sirina)] for _ in range(visina)]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "66f45a16",
   "metadata": {},
   "source": [
    "Bistveno je, da `set()` ne pokličemo le enkrat, temveč tolikokrat, kolikor množic potrebujemo.\n",
    "\n",
    "Rešitev je potem"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "2acfe222",
   "metadata": {},
   "outputs": [],
   "source": [
    "def situacija(specialci, marsovci, sirina, visina):\n",
    "    polje = [[set() for _ in range(sirina)] for _ in range(visina)]\n",
    "    for znak, (x, y) in zip(\"ABCDEFGHIJ\", specialci):\n",
    "        polje[y][x].add(znak)\n",
    "    for znak, (x, y) in zip(\"abcdefghij\", marsovci):\n",
    "        polje[y][x].add(znak)\n",
    "    return polje"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bfde1156",
   "metadata": {},
   "source": [
    "Ne spreglejte, kako smo z `zip` poparili specialce in marsovce s črkami."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7d13b95b",
   "metadata": {},
   "source": [
    "Precej študentov je namesto tega sestavljalo množice za vsako sobo posebej in potem iskalo, kdo spada vanjo:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "ec816330",
   "metadata": {},
   "outputs": [],
   "source": [
    "def situacija(specialci, marsovci, sirina, visina):\n",
    "    polje = []\n",
    "    for y in range(visina):\n",
    "        vrstica = []\n",
    "        for x in range(sirina):\n",
    "            soba = set()\n",
    "            for znak, (x0, y0) in zip(\"ABCDEFGHIJ\", specialci):\n",
    "                if x0 == x and y0 == y:\n",
    "                    soba.add(znak)\n",
    "            for znak, (x0, y0) in zip(\"abcdefghij\", marsovci):\n",
    "                if x0 == x and y0 == y:\n",
    "                    soba.add(znak)\n",
    "            vrstica.append(soba)\n",
    "        polje.append(vrstica)\n",
    "    return polje"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c13e50ff",
   "metadata": {},
   "source": [
    "To je nerodnejše, daljše in počasnejše. Če se ne spomnimo na `zip`, da vsak marsovec in specialec dobi pravo črko, pa je potrebno še veliko akrobacij, da določimo pravo črko za vsakega.\n",
    "\n",
    "#### `znak`\n",
    "\n",
    "Ta funkcija ni nič posebnega; potrebujemo jo le, da bi naslednje stekle gladkeje."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "e6058df9",
   "metadata": {},
   "outputs": [],
   "source": [
    "def znak(s):\n",
    "    if not s:\n",
    "        return \".\"\n",
    "    if len(s) == 1:\n",
    "        return next(iter(s))\n",
    "    else:\n",
    "        return str(len(s))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8a864cb3",
   "metadata": {},
   "source": [
    "#### `izris`\n",
    "\n",
    "Tudi `izris` ni nič posebnega. Da ne telovadimo z nizi, pokažimo kar, kako se to naredi z generatorji in `join`-om:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "8e6a59ee",
   "metadata": {},
   "outputs": [],
   "source": [
    "def izris(polozaj):\n",
    "    return \"\\n\".join(\"\".join(znak(s) for s in vrstica) for vrstica in polozaj)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e5d488a7",
   "metadata": {},
   "source": [
    "## Za oceno 8\n",
    "\n",
    "- `prvo_srecanje(specialec, marsovec)` prejme dve trojki z začetnima koordinatama in potjo specialca in marsovca. Vrniti mora prvo polje, na katerem se srečata. Če se ne srečata nikoli, vrne `None`.\n",
    "\n",
    "    Klic `prvo_srecanje((2, 1, \">>\"), (1, 1, \">>>>>>\"))` vrne `(4, 1)`: specialec se premika pred marsovcev, potem pa ga pričaka v zasedi v `(4, 1)`.\n",
    "    \n",
    "### Rešitev\n",
    "\n",
    "Ni tako težko, če se je **lotimo sistematično**.\n",
    "\n",
    "Najprej sestavimo seznam polj, po katerih bosta hodila marsovec in specialec. Potem gremo po parih istoležnih elementov in če sta polje kdaj enaki, vrnemo koordinati.\n",
    "\n",
    "Nato je potrebno poskrbeti še za primer, ko sta poti različno dolgi. Če se prvi ustavi marsovec, se moramo vprašati, ali so njegove koordinate kje na ostanku specialčeve poti - preveriti moramo `korakis` od `len(korakim)` naprej. Če se prvi ustavi specialec, preverimo, ali bo marsovec naletel nanj na ostanku svoje poti. Katera pot je v resnici krajša, nam ni potrebno preverjati: ena od rezin bo pač vedno prazna."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "0ecf8a78",
   "metadata": {},
   "outputs": [],
   "source": [
    "def prvo_srecanje(specialec, marsovec):\n",
    "    korakis = koraki(specialec[0], specialec[1], specialec[2])\n",
    "    korakim = koraki(marsovec[0], marsovec[1], marsovec[2])\n",
    "    for koords, koordm in zip(korakis, korakim):\n",
    "        if koords == koordm:\n",
    "            return koords\n",
    "    if koordm in korakis[len(korakim):]:\n",
    "        return koordm\n",
    "    if koords in korakim[len(korakis):]:\n",
    "        return koords\n",
    "    return None"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b902ed15",
   "metadata": {},
   "source": [
    "Ker nam bo prišlo prav kasneje, omenimo, da bi lahko prvi dve vrstici napisali tudi tako:\n",
    "\n",
    "```python\n",
    "    korakis = koraki(*specialec)\n",
    "    korakim = koraki(*marsovec)\n",
    "```\n",
    "\n",
    "Zvezdica pred imenom pomeni, da želimo elemente tega seznama oziroma terke uporabiti kot argumente. Se pravi: kot argument ne podamo terke `specialec`, temveč elemente terke `specialec`."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "53ad16e3",
   "metadata": {},
   "source": [
    "Druga možnost je, da najprej rešimo nalogo za oceno 9 in v nalogi za oceno 8 le pokličemo to funkcijo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "deb96640",
   "metadata": {},
   "outputs": [],
   "source": [
    "def prvo_srecanje(specialec, marsovec):\n",
    "    return bingo([specialec], marsovec)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "97065ed3",
   "metadata": {},
   "source": [
    "## Za oceno 9\n",
    "- `bingo(specialci, marsovec)` prejme podobne argumente kot prejšnja funkcija, le da namesto opisa enega specialca prejme opise več specialcev. Funkcija vrne koordinate polja, kjer bo nek specialec ujel marsovca, oziroma `None`, če se bo mali zeleni izmaknil.\n",
    "\n",
    "    Klic \n",
    "    \n",
    "    ```python\n",
    "    bingo([(8, 12, \">>>>>>>>\"), (10, 14, \">>>>>>>>\"), (9, 13, \">>>>>>>>\")],\n",
    "          (12, 16, \"^>^>^>^>^>\"))\n",
    "    ```\n",
    "\n",
    "    vrne `(13, 14)`: marsovec bo po treh korakih na `(13, 14)` in ravno takrat se bo tam znašel specialec, ki začne na `(10, 14)` in se pomika desno.\n",
    "    \n",
    "### Rešitev\n",
    "\n",
    "Tudi ta ni tako težka, če se je **lotimo res sistematično**. Recimo takole:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "17a57963",
   "metadata": {},
   "outputs": [],
   "source": [
    "def bingo(specialci, marsovec):\n",
    "    korakiss = [koraki(*specialec) for specialec in specialci]\n",
    "    korakim = koraki(*marsovec)\n",
    "\n",
    "    for i, koordm in enumerate(korakim):\n",
    "        for korakis in korakiss:\n",
    "            if korakis[min(i, len(korakis) - 1)] == koordm:\n",
    "                return koordm\n",
    "    for korakis in korakiss:\n",
    "        if koordm in korakis[i:]:\n",
    "            return koordm\n",
    "    return None"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "93cc2490",
   "metadata": {},
   "source": [
    "Najprej si pripravimo seznam seznamov, ki vsebuje vse korake specialcev; poimenovali smo ga `korakiss`, kot množino `korakis` (slongleščina). `korakiss` je torej seznam senzamov, kakršen je bil `korakis`.\n",
    "\n",
    "Potem korakamo po marsovčevi poti in vemo tudi, na katerem koraku smo. Za vsak korak gremo čez vse `korakis`-e iz `korakiss` (se pravi čez vse specialce) in preverimo, če je specialec v tem, `i`-tem trenutku slučajno v isti sobi kot marsovec. Če, potem je ujet.\n",
    "\n",
    "Pomemben trik tule je, kako odkrijemo specialčevo polje: `korakis[min(i, len(korakis) - 1)]`. Zanima nas, kje je specialec v trenutku `i`. Če je `i` manjši od dolžine specialčeve poti, nas zanima element s tem indeksom, sicer pa zadnji element, saj je specialec že zaključil pot in preži tam.\n",
    "\n",
    "Če se ta zanke izteče neuspešno, je marsovec nekje obstal. Če bo kje ujet, bo ujet na tem polju. Gremo torej čez vse specialce in pogledamo, ali je v ostanku seznama katerega izmed specialcev (`korakis[i:]`, torej po `i`-tem koraku!) to marsovčevo polje. Če je, smo ga ujeli.\n",
    "\n",
    "Če ne, se je izmuznil."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7e1c4250",
   "metadata": {},
   "source": [
    "## Ocena 10\n",
    "\n",
    "Napiši funkcijo `simulacija(specialci, marsovci)`, ki prejme seznam poti specialcev (le nize, saj vsi specialci začnejo na `(0, 0)`!) in sezname s trojkami, ki opisujejo gibanje marsovcev. Vrniti mora `True`, če je reševalna akcija uspešna in `False`, če ni. Kako poteka akcija in kdaj je uspešna, je opisano v uvodu.\n",
    "\n",
    "### Rešitev\n",
    "\n",
    "Da ta ne bi bila težka, pa se je moramo lotiti **res res res sistematično.**\n",
    "\n",
    "Prejšnji dve funkciji sta nas naučili, da je potrebno sestaviti sezname korakov. Seznama `korakiss` in `korakims` bosta vsebovala vse poti vseh specialcev in marsovcev, ki so še aktivni. Ob ujetju marsovca bomo preprosto pobrisali pot specialca in marsovca iz seznama.\n",
    "\n",
    "V zanki bomo izvedli toliko korakov, kolikor je dolga najdaljša pot kateregakoli. Šli bomo prek vseh specialcev in znotraj tega prek vseh marsovcev. Naletivši na dva z enakimi koordinatami bomo pobrisali pripadajoča elementa `korakiss` in `korakims`. Za to brisanje bomo potrebovali indekse obeh. Indeksa marsovca (v notranji zanki) bomo pridobili z `enumerate`. Specialci bodo zahtevali zanko `while` - bomo videli, zakaj."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "a296fee5",
   "metadata": {},
   "outputs": [],
   "source": [
    "def simulacija(specialci, marsovci):\n",
    "    korakiss = [koraki(0, 0, specialec) for specialec in specialci]\n",
    "    korakims = [koraki(*marsovec) for marsovec in marsovci]\n",
    "    for i in range(max(len(x) for x in korakiss + korakims)):\n",
    "        speci = 0\n",
    "        while speci < len(korakiss):\n",
    "            korakis = korakiss[speci]\n",
    "            for marsi, korakim in enumerate(korakims):\n",
    "                if korakis[min(i, len(korakis) - 1)] == korakim[min(i, len(korakim) - 1)]:\n",
    "                    del korakims[marsi]\n",
    "                    del korakiss[speci]\n",
    "                    break\n",
    "            else:\n",
    "                speci += 1\n",
    "    return not korakims and najveckrat_obiskana(marsovci) <= {korakis[-1] for korakis in korakiss}\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f462629a",
   "metadata": {},
   "source": [
    "Brisanje marsovca je preprosto: `del korakims[marsi]`. S specialcem je podobno. Zanko prek marsovcev prekinemo z `break`. Znotraj ranks `for ... in korakims` preverjamo, ali bo specialec z indeksom `speci` ujel kakega marsovca. Če ga ujame, ne smemo pregledovati, ali bo morda še katerega drugega: ne bo, ker je že tega.\n",
    "\n",
    "Navidez smo se ujeli v past: znotraj zanke `for` prek nekega seznama ne smemo brisati elementov tega seznama, saj bo zanka, kot smo že nekoč spoznali, v tem primeru preskakovala elemente. V resnici tu te nevarnosti ni, saj smo zanko po brisanju tako ali tako prekinili.\n",
    "\n",
    "Pač pa moramo biti na to pozorni v zanki prek specialcev. To ne sme biti zanka `for`, ker bi po brisanju enega specialca zanka preskočila naslednjega. Zato tu uporabimo `while`: `speci` je indeks specialca. Zanka teče, dokler je indeks manjši od števila specialcev. Indeks se poveča le, če *ne pobrišemo* specialca - torej v primeru, da se zanka prek marsovcev ni končala z `break`.\n",
    "\n",
    "Akcija je uspešna, če na koncu ni več nobenega aktivnega marsovca in če je množica največkrat obiskanih polj podmnožica zadnjih koordinat vseh specialcev, ki so še aktivni.\n",
    "\n",
    "Ta rešitev je tako kratka po zaslugi nekaterih spretnosti. Najprej, prejšnje funkcije so nas naučile, da se splača delati sezname korakov. Odkrili smo trik, s katerim pridemo do `i`-tega elementa (indeksiranje z `min`). Predvsem pa je koristilo, da smo uporabili pravi zanki in se spomnili na `else` po zanki `for`. Brez teh trikov ... bi se funkcija pač zapletla."
   ]
  }
 ],
 "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.10.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}