p1/domace-naloge/2021/12 Specops/resitev.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "d6fd2620",
   "metadata": {},
   "source": [
    "<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": "97b7005e",
   "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 `obiskana(x, y, pot)`, ki vrne množico vseh obiskanih polj.\n",
    "\n",
    "    Klic `obiskana(4, 4, \"^^>vv<<\")` vrne `{(4, 4), (4, 3), (4, 2), (5, 2), (5, 3), (5, 4), (3, 4)}`.\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": "01fc28bd",
   "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": "a5fdfe36",
   "metadata": {},
   "source": [
    "Ob tej nalogi je najprej vredna omembe naslednja pogosta slaba navada:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "ebde61d5",
   "metadata": {},
   "outputs": [],
   "source": [
    "def koraki(x, y, pot):\n",
    "    polja = [(x, y)]\n",
    "    for c in pot:\n",
    "        if c == \">\":\n",
    "            x += 1\n",
    "            polja.append((x, y))\n",
    "        elif c == \"<\":\n",
    "            x -= 1\n",
    "            polja.append((x, y))\n",
    "        elif c == \"v\":\n",
    "            y += 1\n",
    "            polja.append((x, y))\n",
    "        elif c == \"^\":\n",
    "            y -= 1\n",
    "            polja.append((x, y))\n",
    "    return polja"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "715dd2d9",
   "metadata": {},
   "source": [
    "To ni kul. Če v vsakem primeru dodamo terko `(x, y)`, naj bo ta `append` na koncu, za `if`-om.\n",
    "\n",
    "Nekateri so si zaželeli (in želja se je izpolnila), da bi lahko reševali v Pythonu 3.10 in uporabili `switch`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "a18b2119",
   "metadata": {},
   "outputs": [],
   "source": [
    "def koraki(x, y, pot):\n",
    "    polja = [(x, y)]\n",
    "    for c in pot:\n",
    "        match c:\n",
    "            case \">\":\n",
    "                x += 1\n",
    "            case \"<\":\n",
    "                x -= 1\n",
    "            case \"v\":\n",
    "                y += 1\n",
    "            case \"^\":\n",
    "                y -= 1\n",
    "        polja.append((x, y))\n",
    "    return polja"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1c6e0380",
   "metadata": {},
   "source": [
    "Prav, čeprav - meh. Neke velike prednosti ni. `switch` zasije, ko z njim počnemo kaj bolj zapletenega.\n",
    "\n",
    "Bolj zanimivo je tako:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "81f2b267",
   "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": "c60327a9",
   "metadata": {},
   "source": [
    "To, da se da početi takšne stvari, je, ugibam, eden od razlogov, zakaj se Pythonu ni mudilo z uvajanjem `switch` oziroma `match`.\n",
    "\n",
    "#### `cilj`\n",
    "\n",
    "Funkcija `cilj` zgolj vrne zadnji element, ki ga pridela `korak`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "b71e32cd",
   "metadata": {},
   "outputs": [],
   "source": [
    "def cilj(x, y, pot):\n",
    "    return koraki(x, y, pot)[-1]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "723882e7",
   "metadata": {},
   "source": [
    "#### `cilji`\n",
    "\n",
    "Funkcija `cilji` le pokliče `cilj` za vsak opis poti."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "cb0aad9e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def cilji(opisi):\n",
    "    return [cilj(x, y, pot) for x, y, pot in opisi]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1011598e",
   "metadata": {},
   "source": [
    "#### `obiskana`\n",
    "\n",
    "Obiskana polja so množica polj, čez katera vodijo koraki."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "1ff25b0e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def obiskana(x, y, pot):\n",
    "    return set(koraki(x, y, pot))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "202d6767",
   "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": 8,
   "id": "ddcf2f9d",
   "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": "63d7dc22",
   "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",
    "- Funkcija `animacija0(x, y, pot, sirina, visina)` prejme začetne koordinate in pot ter vrne seznam nizov, ki predstavljajo situacije v posameznih časovnih korakih. Akter je predstavljen z znakom A (kot da gre za specialca). Parametra `sirina` in `visina` vsebujeta dimenzija kleti.\n",
    "\n",
    "    Klic `animacija0(1, 1, \"<^>>\", 3, 3)` vrne `['...\\n.A.\\n...', '...\\nA..\\n...', 'A..\\n...\\n...', '.A.\\n...\\n...', '..A\\n...\\n...']`.\n",
    "    \n",
    "### Rešitev\n",
    "\n",
    "#### `situacija`"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f1ec97aa",
   "metadata": {},
   "source": [
    "Ta funkcija se je izkazala za kar zoprno. Recimo, da imamo:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "99f19db1",
   "metadata": {},
   "outputs": [],
   "source": [
    "sirina = 5\n",
    "visina = 3"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5aa9ecbe",
   "metadata": {},
   "source": [
    "Prvi problem je bil, da takale inicializacija seznama:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "e7a395d1",
   "metadata": {},
   "outputs": [],
   "source": [
    "polje = [[set()] * sirina] * visina"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "84029e18",
   "metadata": {},
   "source": [
    "izgleda pravilna"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "75b55860",
   "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": "markdown",
   "id": "39f25f49",
   "metadata": {},
   "source": [
    "vendar ni:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "9c1bfa72",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[{'A'}, {'A'}, {'A'}, {'A'}, {'A'}],\n",
       " [{'A'}, {'A'}, {'A'}, {'A'}, {'A'}],\n",
       " [{'A'}, {'A'}, {'A'}, {'A'}, {'A'}]]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "polje[2][1].add(\"A\")\n",
    "\n",
    "polje"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9bb30fd8",
   "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": 13,
   "id": "d7961fda",
   "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": 14,
   "id": "d5b54faa",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[set(), set(), set(), set(), set()],\n",
       " [set(), set(), set(), set(), set()],\n",
       " [set(), set(), set(), set(), set()]]"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "polje"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "028b3448",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[set(), set(), set(), set(), set()],\n",
       " [set(), set(), set(), set(), set()],\n",
       " [set(), {'A'}, set(), set(), set()]]"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "polje[2][1].add(\"A\")\n",
    "\n",
    "polje"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3764c62d",
   "metadata": {},
   "source": [
    "Ali s kakšno krajšo različico, kot je"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "d7d3e5a2",
   "metadata": {},
   "outputs": [],
   "source": [
    "polje = [[set() for _ in range(sirina)] for _ in range(visina)]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a89c25b5",
   "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": 17,
   "id": "9da312b4",
   "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": "6233d5b1",
   "metadata": {},
   "source": [
    "Ne spreglejte, kako smo z `zip` poparili specialce in marsovce s črkami."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "82157d1b",
   "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": 18,
   "id": "cd087ffa",
   "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": "b8a00480",
   "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": 19,
   "id": "0853ebe4",
   "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": "e663aaca",
   "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": 20,
   "id": "6b8c90b6",
   "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": "15b3e334",
   "metadata": {},
   "source": [
    "#### `animacija`\n",
    "\n",
    "Tudi animacijo je preprosto narediti z izpeljanim seznamom. Brez njega pa tudi ni bistveno bolj zapleteno, le izris kličemo za vsak korak na poti. Seznam specialcev vsebuje trenutne koordinate, seznam marsovcev pa je prazen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "d294807e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def animacija0(x, y, pot, sirina, visina):\n",
    "    return [izris(situacija([(x, y)], [], sirina, visina))\n",
    "            for x, y in koraki(x, y, pot)]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9b6dcd82",
   "metadata": {},
   "source": [
    "## Za oceno 8\n",
    "\n",
    "- Funkcija `dopolnjeno(s, n)` prejme seznam `s`. Vrniti mora nov seznam dolžine `n` (pri čemer je `n` večji ali enak `len(s)`). Vrnjeni seznam vsebuje vse elemente `s`, ki jim sledi toliko ponovitev zadnjega elementa `s`, da je skupna dolžina enaka zahtevani, `n`.\n",
    "\n",
    "    Klic `dopolnjeno([\"Ana\", \"Berta\", \"Cilka\"], 5)` vrne `[\"Ana\", \"Berta\", \"Cilka\", \"Cilka\", \"Cilka\"]`.\n",
    "\n",
    "- Funkcija `razporedi(specialci, marsovci)` prejme dva seznama, enega za specialce enega za marsovce. Vsak seznam je sestavljen iz trojk `(x, y, pot)`, ki opisuje gibanje enega od specialcev ali marsovcev. Funkcija vrne dva seznama enakih dolžin: njuna dolžina ustreza najdaljši poti, ki jo naredi katerikoli izmed specialcev ali marsovcev. Vsak element seznama ustreza eni časovni točki in vsebuje koordinate vseh specialcev oz. marsovcev v podanem trenutku.\n",
    "\n",
    "    Za ilustracijo poglejmo klic\n",
    "    \n",
    "    ```python\n",
    "    razporedi([(0, 2, \">>>\"), (3, 3, \"<v\"), (4, 2, \"\")],\n",
    "              [(1, 2, \"^^<>>\"), (1, 1, \">>\")])\n",
    "    ```\n",
    "\n",
    "    Vrniti mora\n",
    "\n",
    "    ```python\n",
    "    ([[(0, 2), (3, 3), (4, 2)],\n",
    "      [(1, 2), (2, 3), (4, 2)],\n",
    "      [(2, 2), (2, 4), (4, 2)],\n",
    "      [(3, 2), (2, 4), (4, 2)],\n",
    "      [(3, 2), (2, 4), (4, 2)],\n",
    "      [(3, 2), (2, 4), (4, 2)]],\n",
    "     [[(1, 2), (1, 1)],\n",
    "      [(1, 1), (2, 1)],\n",
    "      [(1, 0), (3, 1)],\n",
    "      [(0, 0), (3, 1)],\n",
    "      [(1, 0), (3, 1)],\n",
    "      [(2, 0), (3, 1)]])\n",
    "    ```\n",
    "\n",
    "    Najprej opazujmo prvi seznam iz para. Njegov prvi element vsebuje začetne položaje vseh specialcev, `[(0, 2), (3, 3), (4, 2)]`. Naslednji element vsebuje položaje specialcev po prvem koraku, `[(1, 2), (2, 3), (4, 2)]`: prvi se je premaknil desno, drugi levo, tretji nikamor, saj je njegova pot prazna. Tretji element vsebuje koordinate po drugem koraku in četrti element po tretjem. Peti in šesti element sta potem enaka četrtemu, saj se specialci premaknejo le trikrat (in še to le prvi); v zadnjih treh korakih se premikajo samo še marsovci.\n",
    "\n",
    "    Drugi seznam iz para vsebuje enake podatke za marsovce.\n",
    "\n",
    "- Funkcija `animacija(specialci, marsovci, sirina, visina)` prejme enake argumente kot `razporedi`, poleg tega pa še dimenzije kleti. Funkcija vrne animacijo v podobni obliki kot `animacija0`, vendar za vse specialce in marsovce.\n",
    "\n",
    "    Klic \n",
    "    \n",
    "    ```python\n",
    "    \n",
    "    animacija([(0, 2, \">>>\"), (3, 3, \"<v\"), (4, 2, \"\")],\n",
    "              [(1, 2, \"^^<>>\"), (1, 1, \">>\")], 5, 5)\n",
    "    ```\n",
    "\n",
    "    vrne seznam, ki vsebuje naslednje nize\n",
    "\n",
    "    ```text\n",
    "    .....\n",
    "    .b...\n",
    "    Aa..C\n",
    "    ...B.\n",
    "    .....\n",
    "    ```\n",
    "\n",
    "    ```text\n",
    "    .....\n",
    "    .ab..\n",
    "    .A..C\n",
    "    ..B..\n",
    "    .....\n",
    "    ```\n",
    "\n",
    "    ```text\n",
    "    .a...\n",
    "    ...b.\n",
    "    ..A.C\n",
    "    .....\n",
    "    ..B..\n",
    "    ```\n",
    "\n",
    "    ```text\n",
    "    a....\n",
    "    ...b.\n",
    "    ...AC\n",
    "    .....\n",
    "    ..B..\n",
    "    ```\n",
    "\n",
    "    ```text\n",
    "    .a...\n",
    "    ...b.\n",
    "    ...AC\n",
    "    .....\n",
    "    ..B..\n",
    "    ```\n",
    "\n",
    "    ```text\n",
    "    ..a..\n",
    "    ...b.\n",
    "    ...AC\n",
    "    .....\n",
    "    ..B..\n",
    "    ```\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",
    "- `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",
    "#### `dopolnjeno`\n",
    "\n",
    "Funkcijo `dopolnjeno` je prišla prav v nadaljevanju, za `razporedi`. Poleg tega pa sem si zaželel, da jo sprogramirate zato, da malo povadimo tisto mantro, da funkcija ne sme kar tako, nepooblaščeno, spreminjati argumentov.\n",
    "\n",
    "Tole je narobe:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "d744c174",
   "metadata": {},
   "outputs": [],
   "source": [
    "def dopolnjeno(s, n):\n",
    "    while len(s) < n:\n",
    "        s.append(s[-1])\n",
    "    return s"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c6baa958",
   "metadata": {},
   "source": [
    "Funkcija mora vrniti podaljšani seznam, ne da bi podaljševala podani seznam.\n",
    "\n",
    "Tole je prav:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "579a4cf5",
   "metadata": {},
   "outputs": [],
   "source": [
    "def dopolnjeno(s, n):\n",
    "    return s + [s[-1]] * (n - len(s))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "365694f9",
   "metadata": {},
   "source": [
    "Lahko pa tudi tako:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "a88ec891",
   "metadata": {},
   "outputs": [],
   "source": [
    "def dopolnjeno(s, n):\n",
    "    return s + s[-1:] * (n - len(s))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "989e3c10",
   "metadata": {},
   "source": [
    "#### `razporedi`\n",
    "\n",
    "Tale je bila kar zoprna, ker je bilo treba malo manipulirati z več seznami.\n",
    "\n",
    "Najprej se je lotimo na dolgo - brez kakršnihkoli izpeljanih seznamov in podobnih trikov. Bistvene pripombe so napisane kar v komentarjih."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "df0f5622",
   "metadata": {},
   "outputs": [],
   "source": [
    "def razporedi(specialci, marsovci):\n",
    "    # Ugotovimo največje število korakov; ta je za 1 daljše od najdaljše poti\n",
    "    cas = 0\n",
    "    for x, y, pot in specialci + marsovci:\n",
    "        if len(pot) > cas:\n",
    "            cas = len(pot)\n",
    "    cas += 1\n",
    "    \n",
    "    # Pripravimo sezname koordinat, podaljšane do dolžine najdaljše\n",
    "    spec_koraki = []\n",
    "    for x, y, pot in specialci:\n",
    "        spec_koraki.append(dopolnjeno(koraki(x, y, pot), cas))\n",
    "\n",
    "    mars_koraki = []\n",
    "    for x, y, pot in marsovci:\n",
    "        mars_koraki.append(dopolnjeno(koraki(x, y, pot), cas))\n",
    "\n",
    "    # Obrnemo seznama - stolpci (koordinate v posameznem trenutku)\n",
    "    # postanejo vrstice\n",
    "    spec = []\n",
    "    mars = []\n",
    "    for t in range(cas):\n",
    "        if spec_koraki:  # \"napaka\" v testih; glej besedilo\n",
    "            spec_koord = []\n",
    "            for specialec in spec_koraki:\n",
    "                spec_koord.append(specialec[t])\n",
    "            spec.append(spec_koord)\n",
    "\n",
    "        if mars_koraki:  # \"napaka\" v testih; glej besedilo\n",
    "            mars_koord = []\n",
    "            for marsovec in mars_koraki:\n",
    "                mars_koord.append(marsovec[t])\n",
    "            mars.append(mars_koord)\n",
    "\n",
    "    return spec, mars"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9bd83fec",
   "metadata": {},
   "source": [
    "Testi so bili ... ne ravno napačni temveč vsaj nerodni. Kaj naj bi vrnil tale klic?\n",
    "\n",
    "```python\n",
    "razporedi([(0, 2, \">>>\"), (3, 3, \"<v\"), (4, 2, \"\")], []))\n",
    "```\n",
    "\n",
    "Tole?\n",
    "\n",
    "```text\n",
    "([[(0, 2), (3, 3), (4, 2)],\n",
    "  [(1, 2), (2, 3), (4, 2)],\n",
    "  [(2, 2), (2, 4), (4, 2)],\n",
    "  [(3, 2), (2, 4), (4, 2)]],\n",
    " [[],\n",
    "  [],\n",
    "  [],\n",
    "  []]),\n",
    "```\n",
    "\n",
    "Ali tole?\n",
    "\n",
    "```text\n",
    "([[(0, 2), (3, 3), (4, 2)],\n",
    "  [(1, 2), (2, 3), (4, 2)],\n",
    "  [(2, 2), (2, 4), (4, 2)],\n",
    "  [(3, 2), (2, 4), (4, 2)]],\n",
    " [])\n",
    "```\n",
    "\n",
    "Navodila o tej situaciji niso govorila. Bolj logično bi bilo prvo, saj imajo Marsovci še vedno štiri časovne točke, le seznami znotraj njih so dolgi toliko, kolikor je pač Marsovcev, torej 0. Testi pa so predpostavili drugo. Zakaj? V bistvu zato, ker je moja prva rešitev vrnila takšen rezultat (in rešitve, ki so jih napisali asistenti, najbrž tudi), sam pa se s tem vprašanjem nisem ukvarjal. Študenti so pisali zaradi vseh mogočih drugih stvari, ta pa ni zmotila nikogar, zato o tem nisem začel razmišljati do trenutka, ko sem pripravil gornjo rešitev in bil prisiljen vanjo dodati dva nepotrebna `if`-a.\n",
    "\n",
    "Skrajšajmo to rešitev."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "ed0235ed",
   "metadata": {},
   "outputs": [],
   "source": [
    "def razporedi(specialci, marsovci):\n",
    "    cas = 1 + max((len(pot) for x, y, pot in specialci + marsovci), default=0)\n",
    "    spec_koraki = [dopolnjeno(koraki(x, y, pot), cas) for x, y, pot in specialci]\n",
    "    mars_koraki = [dopolnjeno(koraki(x, y, pot), cas) for x, y, pot in marsovci]\n",
    "    return ([list(x) for x in zip(*spec_koraki)],\n",
    "            [list(x) for x in zip(*mars_koraki)])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5a81459a",
   "metadata": {},
   "source": [
    "Prva vrstica, očitno, najde najdaljšo pot. Drugi dve sestavita dopolnjena seznama, zadnja obrne stolpce v vrstice. Naj razume, kdor če.\n",
    "\n",
    "Kar napredek, ne? V zadnji me neskončno iritira, da ne morem napisati kar `return zip(*spec_koraki), zip(*mars_koraki)`. To je pač zato, ker `zip` vrača terke,, naloga pa hoče terke.\n",
    "\n",
    "#### `animacija`\n",
    "\n",
    "`animacija`, je funkcija z dolgim opisom in kratko rešitvijo: izrisati je potrebno vse situacije."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "11bc794e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def animacija(specialci, marsovci, sirina, visina):\n",
    "    spec_razp, mars_razp = razporedi(specialci, marsovci)\n",
    "    return [izris(situacija(spec, mars, sirina, visina))\n",
    "            for spec, mars in zip(spec_razp, mars_razp)]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "43aba7ac",
   "metadata": {},
   "source": [
    "#### `prvo_srecanje`\n",
    "\n",
    "Najprej trivialna rešitev: pokličemo funkcijo `bingo`, ki pričakuje seznam specialcev in marsovca. Seznam specialcev je pač seznam, ki vsebuje (edinega) specialca."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "e4cd3072",
   "metadata": {},
   "outputs": [],
   "source": [
    "def prvo_srecanje(specialec, marsovec):\n",
    "    return bingo([specialec], marsovec)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "aaedd6d1",
   "metadata": {},
   "source": [
    "Po tem moramo seveda napisati še funkcijo `bingo`. To nam sicer tako ali tako ne uide, vseeno pa za začetek napišimo `prvo_srecanje`. Ta funkcija je namreč lažja kot `bingo` in lahko služi kot \"ogrevanje\" zanjo.\n",
    "\n",
    "Naprej si bomo pripravili seznam vseh koordinat, ki jih prehodita specialec in marsovec. To lahko storimo tako\n",
    "\n",
    "```python\n",
    "    # Prva dva argumenta sta koordinati, drugi je pot\n",
    "    korakis = koraki(specialec[0], specialec[1], specialec[2])\n",
    "    korakim = koraki(marsovec[0], marsovec[1], marsovec[2])\n",
    "```\n",
    "\n",
    "ali tako\n",
    "\n",
    "```python\n",
    "    x, y, pot = specialec\n",
    "    korakis = koraki(x, y, pot)\n",
    "\n",
    "    x, y, pot = marsovec\n",
    "    korakim = koraki(x, y, pot)\n",
    "```\n",
    "\n",
    "Drugo je boljše, ker ne potrebuje komentarja. Lepa koda brez komentarja je vedno boljša od grde kode, ki jo je potrebno razložiti.\n",
    "\n",
    "OK, popustil bi pri tem:\n",
    "\n",
    "```python\n",
    "    korakis = koraki(*specialec)\n",
    "    korakim = koraki(*marsovec)\n",
    "```\n",
    "\n",
    "Je pa le toliko krajše, da se splača. V naslednjih funkcijah bomo torej delali tako. Če se še nismo naučili poprej: `koraki(specialec)` pomeni, da podamo kot argument (terko) `specialec`, `koraki(*specialec)` pa pomeni, da podamo kot argumente vse elemente (terke) `specialec`.\n",
    "\n",
    "Rešitev je takšna. 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": 29,
   "id": "70c95e3e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def prvo_srecanje(specialec, marsovec):\n",
    "    korakis = koraki(*specialec)\n",
    "    korakim = koraki(*marsovec)\n",
    "    for koords, koordm in zip(korakis, korakim):\n",
    "        if koords == koordm:\n",
    "            return koordm\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": "fbb6ad63",
   "metadata": {},
   "source": [
    "#### `bingo`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "f72d6c95",
   "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": "d2f7afd6",
   "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": "80a3e549",
   "metadata": {},
   "source": [
    "## Ocena 9\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",
    "\n",
    "Funkcije, ki ste jih napisali do sem, so bile priprava za simulacijo. Morda pridejo prav, morda pa nam pomagajo razmišljati.\n",
    "\n",
    "Funkcija `prvo_srecanje` je marsikoga zavedla - mislil je, da jo je pametno uporabiti za simulacijo. Ni. Simulacijo je potrebno poganjati po korakih, prvo srečanje med nekim specialcem in marsovcem pa se lahko zgodi tudi, ko je ta specialec v resnici že zaseden z drugim marsovcem. Podobno je z `bingo`. Tidve sta uporabni za zgled; simulacijo je možno sprogramirati v podobnem slogu.\n",
    "\n",
    "Funkcijo bomo rešil z `razporedi` in brez nje. Osnovni problem bo obakrat, kako vedeti, kdo je še aktiven.\n",
    "\n",
    "Najprej z `razporedi`. Tam je brisanje \"deaktiviranih\" specialcev in marsovcev iz seznamov zoprno, ker se ne nahajajo v vrsticah (kar bi bil en seznam) temveč v stolpcih (istoležni elementi več seznamov). Zato je vsaj meni tu lažje vzdrževati seznam `bool`-ov, ki vsebuje `True`, če je pripadajoči specialec ali marsovec aktiven, in `False`, če ni."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "0ee51e3c",
   "metadata": {},
   "outputs": [],
   "source": [
    "def simulacija(specialci, marsovci):\n",
    "    spec_poz, mars_poz = razporedi([(0, 0, spec) for spec in specialci],\n",
    "                                   marsovci)\n",
    "    spec_aktivni = [True] * len(specialci)\n",
    "    mars_aktivni = [True] * len(marsovci)\n",
    "    for specs, marss in zip(spec_poz, mars_poz):\n",
    "        for speci, spec in enumerate(specs):\n",
    "            for marsi, mars in enumerate(marss):\n",
    "                if spec_aktivni[speci] and mars_aktivni[marsi] and spec == mars:\n",
    "                    spec_aktivni[speci] = mars_aktivni[marsi] = False\n",
    "\n",
    "    return not any(mars_aktivni) and \\\n",
    "           najveckrat_obiskana(marsovci) <= {poz for poz, aktiven in zip(specs, spec_aktivni) if aktiven}\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "50cda4c8",
   "metadata": {},
   "source": [
    "Najprej pokličemo `razporedi` in pripravimo seznama `True`-jev, ki odražata, da so vsi specialci in marsovci aktivni.\n",
    "\n",
    "Potem gremo vzporedno prek koordinat marsovcev in specialcev. V notranjih dveh zankah gremo prek koordinat specialcev in marsovcev. Če sta specialec in marsovec aktivna in na istih koordinatah, postanega neaktivna. Specialce in marsovce oštevilčimo, da lahko beremo (in tudi spreminjamo) njuno aktivnost.\n",
    "\n",
    "Operacija je uspešna, če ni aktivnih marsovcev in so največkrat obiskana polja podmnožica končnih polj aktivnih specialcev.\n",
    "\n",
    "Rešitev brez `razporedi` zahteva nekoliko več spretnosti.\n",
    "\n",
    "Funkciji `prvo_srecanje` in `bingo` 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": 32,
   "id": "fa40d0a1",
   "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": "aa9575cf",
   "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."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3fbed9f3",
   "metadata": {},
   "source": [
    "\n",
    "## Ocena 10\n",
    "\n",
    "Napiši funkcijo `strategija(marsovci)`, ki vrne optimalno strategijo operacije. Argument so poti marsovcev. Rezultat mora biti seznam poti vseh specialcev.\n",
    "\n",
    "- Operacija mora biti uspešna.\n",
    "- Vsakega marsovca je potrebno zgrabiti čimprej. (Ideja: za vsakega marsovca je zadolžen en specialec in ta ga mora zgrabiti, čim je mogoče.)\n",
    "- Tudi do vseh ugrabljenih je potrebno priti čimprej.\n",
    "- Specialcev naj bo le toliko, kot jih potrebujemo.\n",
    "- Poti specialcev naj nimajo nepotrebnih repov. Pri prejšnji nalogi smo ignorirali morebitno predvideno pot specialca po tem, ko sreča marsovca in obstani z njim; v strategiji, ki jo vrne ta funkcija, naj odvečnih repov ne bo.\n",
    "\n",
    "Testi bodo uporabljali vašo funkcijo `simulacija`, zato mora biti ta pravilno napisana. Ko bomo testirali vašo strategijo, pa bomo zamenjali simulacijo s svojo. Lahko se vam torej zgodi, da bodo testi poročali, da je naloga uspešno rešena za oceno 10, v resnici pa boste dobili oceno 9. (Taki situaciji se poskuašmo izogniti, a resnici na ljubo pri večini predmetov pravzaprav nikoli ob oddaji izdelka ne veste, ali je vaša rešitev res pravilna in kakšno oceno boste dobili.)\n",
    "\n",
    "###  Rešitev\n",
    "\n",
    "Gremo po poti vsakega marsovca. Če je v nekem trenutku `t` za `t` korakov od (0, 0), je to polje, kjer ga bomo ujeli; zanko prekinemo. Če pride zanka do konca, ga bomo ujeli (šele) na polju, kjer se ustavi. Med specialce dodamo nekoga, ki bo šel ponj.\n",
    "\n",
    "Nato dodamo specialce, ki gredo po ugrabljence.\n",
    "\n",
    "Na koncu specialce uredimo po dolžini. Tako preprečimo, da bi se specialec, ki ima daljšo pot predčasno ustavil, ker se znajde na polju, kamor je poslan specialec z daljšo nalogo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "43b034cf",
   "metadata": {},
   "outputs": [],
   "source": [
    "def strategija(marsovci):\n",
    "    specialci = []\n",
    "    for marsovec in marsovci:\n",
    "        for t, (x, y) in enumerate(koraki(*marsovec)):\n",
    "            if x + y <= t:\n",
    "                break\n",
    "        specialci.append(\"v\" * y + \">\" * x)\n",
    "        \n",
    "    specialci += [\"v\" * y + \">\" * x for x, y in najveckrat_obiskana(marsovci)]\n",
    "    \n",
    "    return sorted(specialci, key=len)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8f4bcbb6",
   "metadata": {},
   "source": [
    "## Celotna rešitev\n",
    "\n",
    "Za pregled in vtis je tu še rešitev celotne naloge."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "dece8fe2",
   "metadata": {},
   "outputs": [],
   "source": [
    "## Za oceno 6\n",
    "\n",
    "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\n",
    "\n",
    "\n",
    "def cilj(x, y, pot):\n",
    "    return koraki(x, y, pot)[-1]\n",
    "\n",
    "\n",
    "def cilji(opisi):\n",
    "    return [cilj(x, y, pot) for x, y, pot in opisi]\n",
    "\n",
    "\n",
    "def obiskana(x, y, pot):\n",
    "    return set(koraki(x, y, pot))\n",
    "\n",
    "\n",
    "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}\n",
    "\n",
    "\n",
    "## Za oceno 7\n",
    "\n",
    "def situacija(specialci, marsovci, sirina, visina):\n",
    "    polje = [[set() for _ in range(sirina)] for _ in range(visina)]\n",
    "    for znaki, pozicije in ((\"ABCDEFGHIJ\", specialci), (\"abcdefghij\", marsovci)):\n",
    "        for c, (x, y) in zip(znaki, pozicije):\n",
    "            polje[y][x].add(c)\n",
    "    return polje\n",
    "\n",
    "\n",
    "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))\n",
    "\n",
    "    \n",
    "def izris(polozaj):\n",
    "    return \"\\n\".join(\"\".join(znak(s) for s in vrstica) for vrstica in polozaj)\n",
    "\n",
    "\n",
    "def animacija0(x, y, pot, sirina, visina):\n",
    "    return [izris(situacija([(x, y)], [], sirina, visina))\n",
    "            for x, y in koraki(x, y, pot)]\n",
    "\n",
    "\n",
    "## Za oceno 8\n",
    "\n",
    "def dopolnjeno(polja, n):\n",
    "    return polja + polja[-1:] * (n - len(polja))\n",
    "\n",
    "def razporedi(specialci, marsovci):\n",
    "    spec_koraki = [koraki(x, y, pot) for x, y, pot in specialci]\n",
    "    mars_koraki = [koraki(x, y, pot) for x, y, pot in marsovci]\n",
    "    cas = max((len(x) for x in spec_koraki + mars_koraki), default=0)\n",
    "    spec_koraki = [dopolnjeno(k, cas) for k in spec_koraki]\n",
    "    mars_koraki = [dopolnjeno(k, cas) for k in mars_koraki]\n",
    "    return list(map(list, zip(*spec_koraki))), list(map(list, zip(*mars_koraki)))\n",
    "\n",
    "def animacija(specialci, marsovci, sirina, visina):\n",
    "    return [izris(situacija(spec, mars, sirina, visina))\n",
    "            for spec, mars in zip(*razporedi(specialci, marsovci))]\n",
    "\n",
    "def prvo_srecanje(opis1, opis2):\n",
    "    return bingo([opis1], opis2)\n",
    "\n",
    "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\n",
    "\n",
    "\n",
    "## Za oceno 9\n",
    "\n",
    "def simulacija(specialci, marsovci):\n",
    "    spec_poz, mars_poz = razporedi([(0, 0, spec) for spec in specialci],\n",
    "                                   marsovci)\n",
    "    spec_aktivni = [True] * len(specialci)\n",
    "    mars_aktivni = [True] * len(marsovci)\n",
    "    for specs, marss in zip(spec_poz, mars_poz):\n",
    "        for speci, spec in enumerate(specs):\n",
    "            for marsi, mars in enumerate(marss):\n",
    "                if spec_aktivni[speci] and mars_aktivni[marsi] and spec == mars:\n",
    "                    spec_aktivni[speci] = mars_aktivni[marsi] = False\n",
    "\n",
    "    return not any(mars_aktivni) and \\\n",
    "           najveckrat_obiskana(marsovci) <= {poz for poz, aktiven in zip(specs, spec_aktivni) if aktiven}\n",
    "\n",
    "\n",
    "## Za oceno 10\n",
    "\n",
    "def strategija(marsovci):\n",
    "    specialci = []\n",
    "    for marsovec in marsovci:\n",
    "        for i, (x, y) in enumerate(koraki(*marsovec)):\n",
    "            if x + y <= i:\n",
    "                break\n",
    "        specialci.append(\"v\" * y + \">\" * x)\n",
    "    specialci += [\"v\" * y + \">\" * x for x, y in najveckrat_obiskana(marsovci)]\n",
    "    return sorted(specialci, key=len)"
   ]
  }
 ],
 "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
}