p1/izpiti/2022/2_resitev.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "4500de29",
   "metadata": {},
   "source": [
    "<img style=\"float: left; margin-right: 20px\" src=\"data:image/.png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAGRCAMAAAB8PRVbAAAAGXRFWHRTb2Z0d2FyZQBBZG9iZSBJbWFnZVJlYWR5ccllPAAAAYBQTFRFxsbGpqam7u7uNjY22dnZ4uLiZWVl3d3d5OTkj4+POTk539/fkZGR6OjoFBQUQEBAKSkpsLCw0tLSMDAw0NDQdnZ2Q0NDaGhouLi4nJycLS0tfHx8dHR0WVlZhoaGjIyMtra2Pj4+ycnJgICApKSkzs7OysrKiIiIqqqqrKyseXl5goKChISEDQ0NbW1tISEhlpaWJSUlRkZGVVVVqKion5+fioqK1NTUoqKiGhoaXV1denp6mZmZkpKSREREmpqaoKCgYmJirq6uHR0dSkpKlJSUtLS0cHBwSEhIbm5uUFBQcnJyOzs7BAQETU1NCQkJYGBgTk5OampqU1NTf39/v7+/7Ozs9vb2/Pz89PT0zMzM29vb6+vr+/v79fX14eHh1tbWwcHBu7u7wsLC9/f38/Pzs7Oz5+fnvr6+xcXF+vr6srKy19fXzc3N/f39vLy8+fn55ubmvb29+Pj48fHx7e3t8vLyxMTEw8PD8PDw2traurq6wMDA////AAAA////0HRaPQAAAIB0Uk5T/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////wA4BUtnAAAtdElEQVR42uyd6UPaTBPA1SgqPoZLEEFQpFUUIwK1glcfCy0+lEhfC1Vbb61a23rXq7r519/shptdDcil3fnQrrmTH8nOzM7O1AlUakrq6COgQKhQIBQIFQqEAqFCgVAgVCgQCkSurIwwn3HLez9FgdJ4gFkzZuB5VQfhcE417uQNIUal0o3u4PbYn40y2rylGwpxD1UkuJW/Q9tHnjfcYg/FAE5/nbv0pWX2N9rvE4iOZN7rcpdnFDWWNj2KrF2aFeEW8b+LAROIdq5nrDgeDNrF/w61YT9Qt2bu0q6f+ZloNtr0xQOZjnLgBLeC0W/te0AfZo3FefvKpb7BHq7eD95jFjerPdZYNw7vjgUojNrlvOUtU0OxWA/DGvPWaE2m3i0DZoVQz070d7nCOb8FPQDMnti4sZniXVww40B+wH6AjT0v4JmMXdZ6QDTwVWz0B3xXXQFTxlNXA9Yi/n/mm+3985H3pVas+qJctD9xS2owVzyQ0f0e0IJbcb0knpfVf8Pv1gU2cYtbmCCvwSz/oTQSzq8IbJMvrlk3kb+wFbLocy/krTgJquD7y45lLd0b08RcEMg090W83ehpak2j87t6BF116x+vOmOX8xf1XRwEsgTfNiP/J7Xmd/eGzpv843MG+wOHrxdIQA6GTCrPY/qQaTwQJAHLb/yKKbYftzhsmY6+xb04qjj+OPvZ732ODAR68xdauT94IHG1Ff6q1Z05yxe7IZCWefgS9Lu6M18290iCWlidtcvZOwQEyU/QlfmFzwDiDmWsWNJIQA7rwG2kXEDOWOsidsV3bqEB24FsbPE4IE6T4p+6M8yKblvMA9zGAl4Q8Znqmpdm1fk/CGMAAmlk5rFAtAzsJtY9M4UCMfJ9WCBNE/42DJCWgHWpbEDs/Aa2ewHAi+t3frrqhR9YIG9UHhZY9vJXfARBzeYccGBP3xP14Rb36wAIYM7SplKKWsMg8GKB1LlgT9tkYAoE0m7IWpUAcvAKADZLsUkAOe70CGflAtIfHcC+IF8upwLKZgyo2JqgwQKBMgQG8rWviEkLe575FdwLwgTPMYsPQqx1NMAO5q/xAZ11wu8eKiWQxZ5oHwaI0H5qDEc1eUCW6tmdsgHZc6vaSTuts0N53b2V1RlmTMBlJuylUrXlAWEs8DAf1Vqceh0Yw6ohLvELd8NEMN/M7bCqdVrddc8nq20+XBCQ1cFoTBDwfcjyApcHZC3qUqlsHOvRlh7IfTwEwTSf99E6dZpjVgsID17jd/mfrjFfC1A1QSA6jBJ97pnDvSAXXoTCyuK1s1W9X0vo1JWoy7cXAmTVkcMjE8iqg+/IBXI8GYvFzAHXcFPJgey5DffwWPdje3Xhnk9Wm6t7NW/hMCu+9i262VXMC8KOYo8zooZcQ+5G7NpXXO4XKwFk1crmqL0PA8nnkfOGNOR36nDvcnyyTtT8f/aY+Z/8X3uf4s1mr5rTCvKBNMfG+n1qjGIkNBjYN99ncFbeeZBpxp+BU/3oC0UHMAfrGwwDhYAHIozrdMZWf9bqB4CsDgLXQCzm1OQB+dat//7nP+AUygHkbQTnOumdt0HXhSX/LTkJiRbuDMl18t2A+ZQ0hTgQDf/Ebd8+EgWRfcyK7WA94RSX81GgfoFZccpxExi0Z6OSNdVhAFwsS/dutkwnDD5ztoJ9oAmKv9JzK3TfqGYy2Tco4DtzNqYDvDLLhDq8VCVv8GCk++k6F898c4aub9S5WCvSZAAmF7CsUCA1IjHQenfXDd5QILUhx58+Nd3dNdoU3yiQmpCGYOe3u7uGeQqEAqFAKBCyhHjAQTNjhgdQlGLTwKKmHzpEujjYnIVm6NcAbE6sCMbwDFoahaq5J4B21BnE/dRR2ERueg3aeB56rPaUsMlewrN50ZGRVdGDjlG/0dooxNVosQQEXQU0bY7QUg55f81oAzNsOtB+n+AVdaAjm66gedaJtjCMQ7se7dcDN75FtyLab72hb3OwiQYMF+2wGYBG3o4V3QkaZ/0uPQHYvHHBpguao58n0MbQoXPchY481hAUhHXY5C3IcjGhG4QbtKInwCFfrx5tAYcBBKO4WisTSFgCgZM2wi4+lrjLwA7BvRLeIhxM0/mF8Ia8HvmM3+XzSA/hYF86fxDWdDGEFcuts4Q1G4afhDVfOcKKRf0AYc2SapMCeZpABqOkhztHeB7CgZq0CxcnGeHaBsKalcYLApCmmwPC+W+aCAe7aCRd88kv0pNqaiSsWetYIz130tj/YfM66Tl3XMsE8osjPV3FOWkfHWkXv5Z26o/t1CkQCoQCyepe9w8pkNoB0qTgwWLBnToMlEv+Szv1knbqHtUnsFao2mt2oSGooLedqr2lVnsbBGvhQP6w0Mz8BMzfKJDS2yFFABG2WHY8zYMCqToQkQhI86BAqg9EUIHoS+o6qQiQHqKWpU5HmYSBhUuHrza7SLvwg4Trua5vJqxp3D0hALnsXSTcdu93ki61S1KZXnYRVhzXaUj6n480vP/bSlixunVF0r/G2mQCkWOHhEFsaZ9NE6F2SAkNwyKAfASxZUE44mx7FEhNAGkcRM+od52+IbUBhLpOqC/rL/b20hFDOoRLgVAgFAgFQoE8EyAhIhAODgP9ssZisSENfM6/W81i8+2acOsnAvGY7forOCetEW1cD0dlvnVNOkPuTmRVOvTi4UJIF6sbFrcINf5qbRTa3k3GnHq3BIQZcg51Qa/NriXkjJmtMPRN2O8W9+tGk3nGB7oZj/0VvKL2rqFYbHIU2kfH78UjOztn4ThURygWMw8j90rbgHgSvUM0okaEF3DjNxD3QVw8nLkVulmWTm26gZgTJWhoCsFJgcjH8rnV7FxwmaGeufZ2CG4M5/ksvYSXb+1oDwrCNWzaURTf4qh4kthreBXvwnaxOQznoS39gUvtyJfSbI7p5AbKkdXekoprsgULZHzRk9omHbn4gPgVZiwQsxVNW8YBEd9ALJDVPm/hN8NNEYAIZ1NmPBC7T6gtIHMk5+LnIoDoShmwfFockLLZIRQIBUKBUCBPCMg9am8phSVdx766cCDcWOnUXmk+QqEqSnXsEAqk7ECaFC4Q0B9QILUCxBkevB0GWUQqDeRKi9z/xg0KBBpH8J9O/04VgXgADIR4EU2mPaN9iDCQNWZYaSBatUiknnN/wb8hF5Mop0ieeFzPF0ineqeaaq/WxE34Uzxy1V6iNHueq9p7wltXq2qHaHXA9EUoFMhdF/9MgTBZL0gVgPj8IDqIA+L5eh+Qeu55Aunk6qprqfs43b9KMIgBAkIXfx+QTq6vuq4TH6f+JfYjKSKZQIgPoP7ZAlHk8rhngKq04yHJXmMe9eda10QiT3a/rnAgrINws42tpKjf3k7CitV3RdyNinCwsylS6rulEHaASgHm4aDYTRXV3hNpBtveeb7aKxvI81F7PUinj/Qd1qTr5C8EUtvORQqEAqFAKJDik8+UVGykqU3rtsKBqPcJBytinrqgKfxmombCscqbfKbiQ7h/ox1CgTwFIIQUf2rYVKPF/ojYZtDHjYVNz30p/lzi4QwmaWOlQWVQwo25ORSBaIe7qI9QzNycuJ36j9DNGHRoYz/cL4LOzTEGeGTY5NVBNZsA4hLV9hnxijgdgyZpNy+Ih1POQpNrsVUHL1cxDOMX0U3MwmbIIx404rWah+uu9XDjTmiPnv2rg0th0sHjeujX5wPikQ2Sicp5UvcaFS9fJV0Rulcb6u949/yuILTD882gjO/ns/ABotoXawrYnIPf54NR2DSgPOj9NlW3XCAX2/v9KInJZVyUrWMUrXkLm2gS7snVfjx+9BP6hxfrYHMDDTf2n8bjp3VoluzXTXGxEX0hV+AWf9YPUVPcYksL/ZjHv47Ejb+jLca3xCMb0ZGbtuF+aJiqoU/c+M8NvIxVrbjF0S8U39tsFPe7ahd8fgTEr0cdxMoVPPI4vKJvL8UjH/XDIy/d/InHr4xh4mffKkhHhjd42CZuvF8HJ9kersPmJnp/r8XzxU9RZ7MIL3+/D17+wcYR3Bjd64l4iP0rdM074n7xW/QrO+gX7ySOckouoeb2BepPYPMWdSq/9+MdcoH4Gg8Ja4YJRcCEfiNpkpOmj5AvRsa06DxJTYtOAkkm3SdPi24hx4WOEHap+rToXPHsrhLWRL8SVoyG9ghrZluXCbrUw9HveZKKfs8FQo5+31ARgXwi7FJz0e8UCAVCgVAgNQtk3Rfr+kyB1AyQXt6kYqN1VMuqFS2rTXwsJ6zlWHhSkguELMsj99ghNSL5fYhHeUaB1BCQE9a6SoHUCpAmZzfXeSBQILUCRDtjANn1CDtIIwjC9iKp6/xK6oQam5bwK2Tk7c2TVN7eXCDkvL2fZ0lA+CGS+lP1ZPwt2aGLVO2tumFoBHWHFEhNAemlQGoESIf4JV9j/PSTVStAFMCWa6lTIFX9ZG3bY4PZalV3HUExEuZaSM9wmuRUeT1IyAbUbiY99stWkpbzavocD+R8mhTb2xwkAvlI2GXH8Zqwpu0DSWVqCRJWFBzb+zTlubtOKBAKhAKhQCgQCqQ0QOasW1+wcVkveTimhIvLGg39fomNyzoILxg3cXFZlw7ltHTk3Lis5V5R7cXHZbV6NVe4uKw6zafOPmxcVp2PPB3Li4/LEhoVwZfYuKyrf3UOeJL8uKyVZo4Ql7WoV1zi47KOdHLH1Od1EQVyooXhXB4G3bNzBoYkAniV74M2lUo5AM/Q4hWbjPVaBHLQGVGpIhbk43sHgwNNUtY+k8um0tXDe770ilswQ/DR/15QGpScCuXSyItcvNoXgXR8VKpUulZ4zyhxALMATz3lFpuR4H4SCMuiNHm384zfpcRGLhp07gkrNnLR6gkK+MhFH+v32DwoNnTcJO6nXEC/FktExXBhePnnVnE/mxfe60EvvPygsYkjRC7uhAIGQuQiuy0TyLMyDJ9DVlIKhAKhQO6TZ+U6KWJaNHWdlFPtfQpSdSCHf3o+2SITrzcoEDwQq63vsHKnb9azALhUEQ4AxrhEgeQD6eWzBgzLLO9YoJxeQfmurH7gaaZAcoEssqHKAbn2AubPUjKdz7GVZXspkBwgXtttNpAyalkXHjB0nZlhyeiKblEtK/sTwrXXZQMpnx0i8phezc55dalWjlM7JBMtaxQqBmSBz+VxdzfN6tcokLQwk6sVA6IJdK4kMGiPjMnmBHhPgaSfJG9TqXTA1HlcASA2/xeJwa4JhnKaf0tsdBN7FEhStu2xmF0BLG9Wyw9klO2SeNijLufmCzcYaUB/hsAuBZKtdlVG7f2fW4sAvGGl6ksKUJ94RTobqNpbeSD96u5z+PxvdDpJr2qP6CRCYdMvCiRTxlWVcJ2Mskb0+BUgOYVvjJ1GS0bZQQqk8jIrdenLSkvKvPRENqRvln6NAqm4eMLrKPuxP226DvG96BWZn7mhQO6527JMiz7R6VEXEmOlecJwWvSVehgZih/Y20xvRymnRZ/skvwwL7sIK/6S5DMnOucifPjBRJcOh3AXVZ+a8jsRqvZWBMi+awx9noLzbSkgwidTB1y25Z6iQCoNRBMwSn26YiUNxBq4QiMjysxenQLJkeCEeQolEngdE0WPegcHrLA7gALlcMWJpyy7PWZYebZ3Mx6/7LKjLcTm9nulZ9I+6Tu97bNKWu8e89F4ZewxO0Pu2d6OEKeBC1dUQc1V/NLnRPtZJzpQceKY/j106OzU68WlqDjxO1u3M2Z2OrSTUoo/dr7+ezx+5bB2M57hd1ub8e1deEXm15rt+O3RG/EQwwrVQF/8sn5IPLLTdylekQYW3DW/q+vXq7/8A5s9xs347enYJLx8h7jffpeh4OLE2jaOUAt3sVvlxNfCNbu2ywfknvLdaUkAyV7oQN8xS3Zi+w0CkDGOlASzpMJHagtIEfPUD9TFAvkHA4QYBX2krggQdx/h/JWap14C0RULZGgNLn2dlbu5i6iw6yoCRNfy9A1D2UDughQIBUKBYMWBA/KxXTJEKJCktMGpOKeHFejUE5Z69kJPcz6Qv7tTt6K84IuPMwxlqb0SEMXDQFSkGNMKqb1RfTUNQ6/l4PGWegFAYlH5QBzop7qnafybgBiGVqsJRHJmaXU4IF/UgUvRMJwAPX8TEPbVYTWBsFeS7wT7hgyyrj5hAgwd4IForWY7RpyTzFMGInYhpqGD2gQiEjHp0jxygRBlNfR0gVzfxn94QVbSxSIGqJpdpQTy33Im6VD65/HDJQ/I3Q/2MUD8g9UeoLKAkwrYIVggoDcfSNoOEfsP4N7G2CFg6F4gviduGD4+DkgOkMQQbhRjLhKAiDxeO9jANgaIv2uJzOOb4okDeQU2KvCGSEEOWCDZ7t4kkB0LmDwQ3rKBzXwgRDF9f9pA4HeshXl0ZuuyAFlnRmDf5nCP/kVAvJzNANSPzdsry3WCB4IZEJHhOikrkKq6Ts5/2GOOpYrYIXggkrvXUqDrpKxAqmuHlCTI4dFAsvzvFAgFQoGkk7WuUyA1BcTzlQJ5AEgR06Jv/bKB7LpwQLL87xbSaV6xFQHCThPO/4SSz+hKCUTGEO7ztUMw8osDOlTBQ/o9IjeXBY0rvoB2Whf6bszCWWhfUbHgiRVBUKgeKk7sYZNATB5UnBjw4hYel7tPAqKe8bjQfmpdryDEkcXRCYP0GuZhUwkrx341oP3UM+LhJK7J4sTwdx0xqAwMJwER/7Cht5Z3i1t4pBLCLlRvWNoYNpVS2WNYb9iGDhc1pZvos/UdnUQJmzdosQuGCn6egM0AnEJx3IUOgX5C6+gkFuRrNKGTwOYF+hFx/XBjPdoCmVlGAGbKGeQgQzxJIFnBttbApgRktDRnaZWABBuEpyO1CGRF1b1GgVAgTwNImeap5wBJ5Fz8l32VC0TGdIRcSU9HyAVC54cUCMToQkB2PJY9CqSGgNxNGBopkIS88LJZ4yFPH8hqiPn1ZIEsM9zk0a/DagFpZvRrJQdy9496+8kC8WSPTpUdyBRrzASyEpGAdJq+UCCSLVopLTgBJObKGo9LAukJ7JdO7c0A8uTUXoWqlQHKSuQ6oUBkAWG44NEuE92oFhAhLHkXKZCE8MpjQdjhO4+rBcQrAZliHRQIAoKC3z3KnSoDOXK/oEDQJwtND/EEM4CUKW9vDpBkdQSvcjwHiIy8vbmSztubC+TJ5e3Vc+3wk2U9qJTamwSSrB+S8C5mAPm71d5lVu3YZfx75bdDIpaTe4BomdgqBQKlycuDucbyG4bJ9EwEIBnu3r8cSKWci0Qg7BYFUktAjO5XFMj9UkSwdctXkh3T2LSEB3KmbcgEcve/cHJC0UrjBeFgTTcH+BUHN00EIBeNpLs5IeWmXWoiaXlPKPnMw5ILJClJIBnu3r/aDqkBIF0USC0BWbHlDYhQINlysb3fjy1OvIVGTnDFiUXpxxYnXoFboOLESSAW3TgsTixu/B1tcamWgNj9lw2oODEKzMMXJxaajXFUnDjRjBtRCauVK1j2GBUnFiZTQFBx4v1t5FzYM8Im6mcaLtHGyCTHFic+XIdNXHFicXEf9DvkFydG14wtTiwsoSamOHG8Qy6QHoZQnNgWhheMK07cbxQU+OLEugeSz8DJoJL/PZo5LRpfnHjDopOKE4syBusGm8ZgM6M48Xo4BQQVJ1YxI/BhGdXi1c8h90pHGNZItgvCy3+X8cWJX5AjiHlSceKVaBETtZqqofbqow8CmWjPAUKMfq+M2rtjJT5DF6moXFsxqR23qwzkn1U8kMSACAVSaSDYjHIpIBoXBVIjQEwvJXcvBUKB1CAQLVRt4/vN5XKd/MvK/GRNsQ/PU6+M60TQkGcDEa0sf+FAmHMcEE9C9Twok9Ez6M8BonpY7e2qsmF4Sp5bRdqlXV04kHsm7Dw+1wletK96vOl5mtb2w/xEykmt924CPCUgx8i6O/x9Xh4gbkvpg04aHIhFlDGo4OyxxCQ2y0gg+6oC/5xLpdqYpwSkPeyGFmKHP1wWIPWlf0HiFg6wwZ7NtVTKJH2gdXRhXpp+mOrWIl0NidUZX6wnAGTVAUztgpZlt8oCxD13XNrxkA4Vz4eNO1k5rPSufpT73T0xZY1ZLbNmc+vRRWptnUlO8pna6dRFIjqjP8WjhJ06ekGy05c9Wu01c9xQQ25SsSQQl34xP+MYPitpLau9q4MAsEflsUNys2U9Eki7lw+O5z/z+4Bkp+19GnZIBwu/WuUAUgeMhyUE8lsJ9A13RCC7vC93zXlnjqv0KQDpYNkh3rRXDiCeyPE9lnr/giESaioAyATvy6yZ3nGELM+j9hF3AsjbbBxt1rzP7xMAIvLYFwaBeq/0QL6D0SUykOEoiDB84EY2EDPXnXw/Vv8oTBlKFa/zdvsufVlAmluVfP6V1j6QzxbuFPYj/GzpgXj8ufkWM/L2bnO2tru795xFUggeLiypdQVbpGe9bGVFtdZsSRmGrE1KnWGyfYzZ7fbh/+ZNhFGdjLy92ZIqLJkr6cKSuUCKKCwpkJPMqpM/1W9oNHCnI3mlTaUboLptvkcj9/I3aNiVbZepwof5K4mHww9Uow2ZrpNwk6hNnXbKyLBEXSdEUZvQ92eUG5e3/VWg+xrxaOVckqqQDSTLh0iBFA7Eq0NAtGy9POfjSFSqkN7FKptznYsSkFiUAnkEEH10BT7FJnZoWdb2OqkHWVerb/K8vZ2fKZBHA5mONqJfvL/zQpZ31zV9hhxTnCPf/Y5P/U6BFDRiqGUdyKjwW67lqL31LLI17pTK5vwRQ/lA6BDug0AsuhU5QMycVvpixb6RgFgABVIokHldKlCO4d8co8fIRWDuPlQLFxcoNxo66IyoPH4X0pK/u1y2/EA5UlgWFgg+UG7KzRQYKGcwKaEHEBco1xURShcot1dOIHPWrS+JUNJ+dmQZAXHD2s8vefhUcKGko6HfL0/jvz65byQb5F1dIpT0ILxg3IShpJqAI11O/fjX0aVDOS0FqW7BkFBk5zShUNLl3s4vhFDSVq/mChdKWqf51NmHDSWtG7X0CvhQ0i6lgA0lFRoVwZfYUNKrf3UOeJL8UNKVZo4QSrqoV1ziQ0mPdMVM2EkCkffJGkkCSc98TU7YSZRTT9W3T03YwQxH0Ak72ZIxLfqaNa9lAHloWjQGSHJadBKIKgkkOS0a4yD5q6dFP6DHZnfqD9qFSSDGfGSBRLFo+6JQTnnm80OSQJSRzwUA0bp78hJDDHBXFEjpgMg0DBNA1tX5QCZdvygQWUCuPICzkJy5PzjjUgFApiTD8B4gNzoK5H4g33nL6XtWvUNynbQX4jpJWOqHutkVApBd13uBArkPiNd0DBOR1x1itawEEC07eiZHy0q5TrwnuVrWDNOYDYRqWXgty5MPJMMO8bp+Z7rfH7JD3vv/Xc0BkrRDZiTvexoItUPwdkgv3/m5hQke4w3DxHjIe653SQ6QNrfk7VXONRGATLF/KJD7DcNeHuSUzcsAwtiupRFD6VslF0jIvZELRJUYn3L1UyD3AllmTIN6PotIBhB2ZK0wIM5lPJCW1Cx1CuR+IArYh/zk9Qf3AbG4VmQBERhLOwXyOCD35lzsYF+fSZ4TWYZ6CkgPl6vaJIEEVV+p2nuv2utGORfdljM8kKQrqzAgmd5FSU5dY9nOXgqEAMQKFk6vPBx+jC4JRC23PkrY1IwHkud9p0BIrpMXDABBQmbrjpQr65u8Q4+4kfnXG3DggSwrFSsUSPHOxWKB5DuzRtl9uOKk3L7FZwkk7TrJBfJg3t4R/3gOkITrJOHKygBCXSeyB6jSam8ukAfV3nq2LwdIQu1NAPmi7lktr9o7GtA84ySYxQK5Y1LOrASQj34E5Efa2VsmIBr/m78ASND0uTAgylwgCVcWBfJYIImwLJ1MIFeB1rP7gKR9ixRIUXl7E66ToeiJPCBtbgnIXCqWNAFEKQExpzwnFIh8IINRwNlUKtUMD8DEN/gc6zkOTX6ag88DV5x4RxVJTMSRgHyIZhUndjOcFXlOzFFWaUjmdWDRLCQv2g2pIj1o8b9C4wWhOPEByr8hRXKb0X5m2HRwGcWJOQSE03mk4sQgCksgY4oTz6g5VQmLE2+TihNrXaTixMR56rnyK2OSkykxP0T6S3FO2icVMSpN2PmQF1ItAfFmLJlrLqEqP5i6ZgnIcyvfnRZpTF0tG4jkzMoHMo20gzkK5LFAJDVrKFoYEEfeVGeUcZ8CeTyQiYuMb9ZjgSwrKZAigGQm5gEcmtN2Z0FdoZoUv9WcymDpasQD+S55TjJvW0s4WOPuCcmpQpoWLaSndJQAiH+QcJYVH8k1+puUMGd164qw5nCsDQ9EazffZPvQs+byv1rNeEVIvnMfmw2kzpV7jx1wcWNmzh+2rnRq78XHUgKRNKxqqb0KYNNlJ3PIBhKREjNIvYhcIE1qLJAfAQrkISCjsPTqQFYGs2wgoO5QGlriZQHhtVgghmYKRB4QqWxeVpBDDhDT77sUkRSQRReaQXaUqDScBgL6sEAwWQMoELlBDjlAwBQyvu8OO6PAmaowEwYikVOW7cACuVPmZrrckwx1CuQhIFKQA5MJpCfXqvuZyN1zqePZgeUUEasmySNDy0oYHEqsoZ4FpJxaFkl+/1fzWpYVWJe+dQLPGcEOyejX4WC5iGQoESb6iQdsR54dknBm4YFk2oVltUOI0tBZ63bIN4X4gfrPldmH5AEBwXSKOBEJsLXCKx5kwcg1CYg35wiDd7UB5K6n9g3D9XjDz6w0mPlAwEBGhtGOD6LVp9P3cG4GmL8RgOQ6s6QPma0CQMDszj082sJPwlKf8+8I9wLJfEdEuTXbYMfP8SkiaSCKzzggt3mGetmAAKXdacfIpG/t7u7G8wSAtHhBXc54SL5EmrN+ae1+/7+tE+JTcCCT8iCt5krOLDv3kKEObKTYkiLqGApTMlKoGFZkAnH3Ec5SkTqGHgPwZ6clDfPYRBADa5lEBmBJAw1r2MtVe7HeRYyhXi61twRAqus6cfbk3j4eiPgmd+V+nTWs9IJkAomsY4AkQhwokKKGcElAxGf4UXOWCcSbHGTPAIJ190pAejgKpLRAUMby4KRdL3UoZ+7wCgHIeHau6oXPeXYhBVIKIH1vh4IsCnFAVYr8b47zgGC9i5JdOAsokGKAhIhAOMlIb/SPoXCtMTaZrPQ24wuF8y7mj6iLr1IJY3uPu0sJhJ0mnL9Ksb2/iKl1E0O4SSAK7mu+pY4FItmFBlARO+TRQGp6TB0HpIv7gh6wQr0uEwjGLqRASgXkV8989KsExB+yx2JDb9ceAoKzC4FrEt23Qx+LxaS3t27YLDZfoo/Du8lYTP8edlE79eIWQ11oOP9PdyxmtqIP5b7YjHWjbH/j1mFvKQ1D/wdnzIliXptC4knMKEvq51bx4sytMD5w7e0QbMIZGEsv4eVbUc65a9i0oyi+xVFx49hr6ZsFm8PwXpf+wKYduX+bzXafXCAn1lgPrGlwNRyDl2O8jce3R8UnHxvaPiAB6b/sgddrjcfYBBDV4La4n8Mai/WYJCCagMVqnjZuxjeNaOPXTVgg44tyHlruM1TY321txrd30WN7rdmO3x69EZnGnC8u4/HL+iH7pFICYuqBN/WuLi5exj9w4x7xim5Pxybh5TvE/U59aD8MELuZmDGSmyIB+V3SvL146eIkIE4uv/d9kwSSMYfKIJkhmoBR1uE/FwFE9+BNLYcgkDW96hFz6s5G7wNCGCkpad7eHEnYgX/Yt0uSlpV8wulyFSF3IuykSzrIbOuiYEtEWmcpuuRg6/0ikhJzY4SDpYKt84AUEWzd7CInkCXsshMqad5ePJD2gB0lbGh3JZ29aSAzOfNwZ1tX93SJ8cIsRZcCKWEtXIY5Qd8sD9ucA6RBLbnfW7m+JJDDG7UExMNsUCDlARLjpLxYPjZhqqeA1LPS2KDCtZEEImj8Ggnf/DoF8gCQdfsR8ry3KFSWRvlA2gOS7+SOiX7JBmKTXFnpSYYikBfsKTJDdJ0rFMi9QC4UPBiC/vOfbCTGRJOWfEZGudyRxaTF9JFHczjvvvgN6MEnp0XXs1I6oDpXUsl6PShMSnnmTnTOzJgR8rTofl3hQFgHKYQlOS06D0gR06KbbOT06IRdjlvJ15znOtGqbnkExKM8E85Y745s/a/Rn3hFnJwqI2bnKpB4QT5EMwbdFlwJM0RmGYqnrPYedyA1Z81XrNqLgJzwMLZ3kvsm/9JmE6+ISMTvS4KcZhOTcA916ZRyohliaCvEDHnSQMaBB9rsQd73GCC9KLTXCLRCAa8Ik6jG9tYN2IkX+1eObhfQdUjLYlzmF8QWbpFGQzafP5BFq0jkPAhmDh8DxArg2H0f+LEk/9paOfO3RLnCVwbJX8/UJ0bd19WZL0iLzrqTb4Y8V0t9xwqUFuA5FCoNRAjzg+mKnv2np3XpErcGkKlAbaglIB5V818ABBLhPcW7ThCQ0QSQ7UO5WpYoeyYwuIoNRpvgW9Pqwes/9YFTyQz5X9boznPVshqCWUAK0rKSQOpQ4OIUuJBrh0hP1ASSX61MObPwHzLSnc2O+QIJM0SfNdz3TO0QkYfKmvHJKtRSl9ReND1kTrlWEBBhOcwzidk8GYGmOpDJAwFB9aFf+LOf2fMEIvLwCGcD6U69OCBDXK/4grxYLQyIcNjKAU/fUgaOxoloNLsG5ey75Qj74viuRef/9RcA+Y4+VzvW1MMuDogAJ9laD4QCgYga1EQUuMy7knalfcfwYCJniGS2VfjiBrogC14IfwGQ1Wb03V9qe6xzUbv/uQDnYoY0vEYlupk5OO4b6M5TpGDymTWnQenN7cKpL0u2t7dQad8a0AcjFr1v/KAkx6MjhjUmFAgFQoFQIBTI0wXiazwkrBn+TfJ2GEmue00foae/rie5tsaZwoG4dgkHO9ltJAB5SRqeOa7TENasEEsr8xOEXVbfkidqNckEklGcWBQG6cPOGRnFiVURCzrHO4+4OFGc2OSyqXT1cOT90gurAg/BCMTfC0qDkpOKQtthdV81rCAsOObE/dRXfUqTR4ciEf3i34aIlIiPgZn6kFuZV4sX45E0UJi1b0ZczKul4sTNC7De8Cw8t1ScWKfr6Yv3iU1bQALCRQziFgu/+j/MEIoT+1i/x+ZBP/lxWAFZuYD8WJaIionep/a262BeRCfc+HwW5kgMp9VeHt6lTZqw5IKP1VRccWJRtqQSwrfxh4sTx0+lgr1fN2GR4ezixLCEMKwKrIV+x/IVJ/728kjcuB+eWypO7NNlhZKu6dPP0PsUixM/aBhKko7LwhmGWClTVtJc2VARgXwq2DCsfppYCoQCoUDypINYTmeblPul5esxaYCoiTDadaYlFYkpYp76wU0TSYeeJQHhh0hPqok0g6si89SfuSyPkIBErbVyjWkgTQopUE5o6QT6Awqk2kC0vCoRuSg2KJDqA7mOJwaozsVGNwVS/U9WasRQyARCO/Uqduo4IFTtraLaS4FQIBQIBUKBUCClBFLtAaoi8vYu9pLKR7Z4iUBGCLvcM0BV/ry9OCDUDqmiHZKY9CkIzj9LFEgNAHn2QoFQICUHQl0nNTYeQtVeOoRLgVAgFAgFUiyQMJ8uTgyLDYhNQyIvL7QtccWJx9Q2tDQKA/Q8AbRjRnFiF4xANKHmw8WJHVciEHxx4jG0AaE48Sd4RR2okowJWsffOhPZuK2xgXAuEHWP9VP0vuLEfABVMpYCdz0wghNdfhRuLMVSonu1SWWP1YyfUJw4EbmIK04sO3Lxwby9+XLrLyIct4R5e8+nC58WbQSlFFLymYrk7cVIEVPLS5omVoZBkguk2VNCHuTo9xLYIRQIBUKBUCC1CSSR4q9p2GAbWKFAqg0kmeJvkQ/Guln1WlrtJcnDtXALyBdTwnIVZDuEPE99sKRalqsUdkgqxV+H+Jr08b5V2UCulzL/o0BKBETIGDGEY4bHsoEEPXAWU7trYI0CKReQM35a/hsS4w3tMD+TY5UCKReQAdBUQB9i5z1aXYoHBVJ6II2s/riQTh1WjhxcpZ16uYAsKtWLBam97QHAtFC1t+SGYQLIIqM+Kcgw3FNH53nVHgVSHiBZPOQAOVGDt4IzgwgFUkoga0rOEY/vfzmUDUQH3or9hxMsXFMgZQBiTSRCXpQNxPj9DP439ZW+IRVwLtIBqhoboKK+rCqqvRQIBUKBUCAUCAVSSiCDxLxpc6Qw7IMich/bSLpUSYOtLxo/E4BodSXkETUTzl+KYOuHihNbYVlcDcwM9xtWns0tTiz7N1XC4sTifvpX8Irau4ZisclR+BCO3+vhxqgYVkcoUQt3Te/SO8WNHWWwQ6pWnBgHJFmcuHczHr/sQhtrNhPFiWOTvtPb+JUDPjYZxYkrBWRRu3tPcWJ712U8vqkZgk+gpy4ev+2FJ4kNwI3/oMdt7RUfzGk9bDrrv5+UEcjzlFKkiS2TUCBPDMizmhZd2ry95Z8WjZNnNR2hpOUqKjgdYfN0iQKpPpBkir9O0RSMjq5SIFUGkkrx90+/sBhMRZ1QINUCkkrxByVdV5ICqYXkM8JU6g15VvPUya6Tk1+kJ1UDKf6021ZudJXaIdW3QxJAgjxgfj5vw3DVzGifDhDxBbZwV4fPmohPffSUgAiC2rtDgdQSkFQt3OfZqecBqeVOHT6axtT8kOep9uYBqWG194SdgFPaWoS/AYiyuaaBSJM+62dV8+lJn88ZyF29+09NA8EJBUKBUCD36ofPcoAqD8jTGaB6znZIBpDatEMoEAqEAqFAnjiQxqBtHoV/wcx2qsiQXWx6UbMTLu2EdYptFrM9ZtfPoeakuIV13iY25/Ric3jCAEv6huB+C/AYuOLE4tHCKDourzhxL3IrfBS30LXCPvxiUtyCWUAqwBQsIRxE0XFjsG6waQw2b4OwMLJXvCJndxheRjDkjNnNlghMTqgYhtesVM2oJSBR3Qzc2BoTL/+TuIXtf+Ll280fYdMzAvebRU1ccWJVxAL1jXOreEU2L/TWHPTCyw++h1tgixMLawrYnIOqxcEobBpeIDXIpuqWC+SeYOsiRFGJ4sS7czKuRAIiY0PeUlvFiUsLZGCnAnbIxcdSAonqa8sOoUAoEAqEAqlNIOupgi7LzjdJH0eopEC6CI6xdnMJp0Ufd5cSCDtNOH/bh3XCmpYgYUVB06KTKf6gLKTyBtwzYacI8WsrosoPciUEomupkh2SSvEnCEbWpKRAqg1ESI2p77BdM8khdQqkBoB4gkKQAqkdIKOBvXTQCQVSdSAbcMp4GgjVsqqlZSWBMCZzzOkO6Bufvx2SWdClJg1DBMSDSrZwyrrDZw2E67m7aws/BSBI0p+s5woEcN2DKkCB1A4Q2XkyKBAK5D55rmqvbKmm2kuBUCAUCAVCgVAgpQTyXF0n8pMPVtF18jcN4T5Ztfe5xmXJllqLy3ozo6pm5OJRy+4JIXJxXKEsOnJRbM7CZshjK33kYu+alRC5uPo+qCJELn5alwmEilBbnToVCoQCoUKBUKFAKBAqFAgFQoUCoUCoUCB/sfxfgAEAhr1pWRr2QVIAAAAASUVORK5CYII=\"/>\n",
    "\n",
    "Slika kaže razpored ovir v testih. Funkcije morajo delovati za poljuben razpored ovir (predpostaviti pa smete, da se ovire ne prekrivajo) in velikost steze.\n",
    "\n",
    "Ovire so podane kot seznam terk `(y, x0, x1)`, kjer je `y` številka vrstice, `x0` in `x1` pa skrajni levi in desni stolpec ovire. Seznam ovir ni urejen ne po vrsticah ne kakorkoli drugače. "
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "4dfe663d",
   "metadata": {},
   "source": [
    "## 1. Prehodi\n",
    "\n",
    "Prehodi so prosta polja, ki imajo na sosednjem levem in desnem polju oviro. Na sliki so označena s križci. Napiši funkcijo `prehodi(ovire)`, ki vrne množico koordinat prehodov v obliki parov `(y, x)`.\n",
    "\n",
    "### Rešitev\n",
    "\n",
    "Lahko gremo prek seznama vseh parov ovir in za vsak par preverimo, ali je med njima stisnjen prehod. Ker ovire niso urejene, bo potrebno narediti dvojno, gnezdeno zanko:\n",
    "\n",
    "```\n",
    "    for ya, xa0, xa1 in ovire:\n",
    "        for yb, xb0, xb1 in ovire:\n",
    "```\n",
    "\n",
    "Za vsak preverimo, ali sta v isti vrstici in ali se druga ovira začne dve polji po koncu prve ovire. Če je tako, dodamo vmesno polje v množico."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "ec3b5a66",
   "metadata": {},
   "outputs": [],
   "source": [
    "def prehodi(ovire):\n",
    "    preh = set()\n",
    "    for ya, xa0, xa1 in ovire:\n",
    "        for yb, xb0, xb1 in ovire:\n",
    "            if ya == yb and xb0 == xa1 + 2:\n",
    "                preh.add((ya, xa1 + 1))\n",
    "    return preh"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "adddf635",
   "metadata": {},
   "source": [
    "Če smo čisto strogi, to ni čisto prava rešitev: kaj, če bi bila na polju med tema ovirama zagozdena še ena ovira dolžine 1? Tega sicer nikoli nismo videvali: ovire se nikoli niso stikale. Če bi nas to skrbelo, bi lahko odšteli še vse ovire dolžine 1,\n",
    "\n",
    "```\n",
    "    return pref - {(y, x0) for y, x0, x1 in ovire if x0 == x1}\n",
    "```\n",
    "\n",
    "Vendar na to možnost nisem pomislil niti pri sestavljanju nalog, niti pri sestavljanju testov, zato ne bomo nikomur zamerili, če je rešil tako, kot zgoraj.\n",
    "\n",
    "Še manjši detajl: spremenljivk `xa0` in `xb1` v resnici ne potrebujemo, zato bi ju lahko zamenjali s `_`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "bf4e584e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def prehodi(ovire):\n",
    "    preh = set()\n",
    "    for ya, _, xa1 in ovire:\n",
    "        for yb, xb0, _ in ovire:\n",
    "            if ya == yb and xb0 == xa1 + 2:\n",
    "                preh.add((ya, xa1 + 1))\n",
    "    return preh"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2bff6d77",
   "metadata": {},
   "source": [
    "Zdaj pa kakšna boljša rešitev. Lahko, recimo, najprej razmečemo ovire po vrsticah. Sestavimo slovar, katerega ključi so številke vrstic, `y`, vrednosti pa pari začetkov in koncev ovir v teh vrstici, torej `(x0, x1)`.\n",
    "\n",
    "```python\n",
    "    vrstice = defaultdict(list)\n",
    "    for y, x0, x1 in ovire:\n",
    "        vrstice[y].append((x0, x1))\n",
    "```\n",
    "\n",
    "Vemo, da je lahko prehod le med dvema zaporednima ovirama. Gremo torej čez vrstice. Seznam ovir v vsaki vrstici uredimo in zdaj vemo, da je lahko ovira le med zaporednim parom. Pa imamo:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "fcd0aa5f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def prehodi(ovire):\n",
    "    vrstice = defaultdict(list)\n",
    "    for y, x0, x1 in ovire:\n",
    "        vrstice[y].append((x0, x1))\n",
    "    prehodi = set()\n",
    "    for y, xs in vrstice.items():\n",
    "        xs.sort()\n",
    "        for (_, xa1), (xb0, _) in zip(xs, xs[1:]):\n",
    "            if xb0 == xa1 + 2:\n",
    "                prehodi.add((y, xa1 + 1))\n",
    "    return prehodi"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6d7323d7",
   "metadata": {},
   "source": [
    "Zanimiva je zanka, `for (_, x0), (x1, _) in zip(xs, xs[1:])`. `xs` je seznam začetkov in koncev ovir - se pravi parov. Če naredimo `zip(xs, xs[1:])` bomo dobili pare parov. Zato jih razpakiramo v `(xa0, xa1), (xb0, xb1)`. Ker `xa0` in `xb1` ne potrebujemo, pa ju, tako kot zgoraj, zamenjamo s podčrtaji.\n",
    "\n",
    "Še lažje pa je, če se izognemo razmetavanju po vrsticah in uredimo kar celoten seznam. Python terke ureja najprej po prvem elementu - v našem primeru so to številke vrstic -, če je prvi enak, pa po drugem, torej stolpcu. Natančno to kar potrebujemo: potem bomo šli preprosto po zaporednih ovirah v tako urejenem seznamu. Med dvema ovirama je prehod, če sta v isti vrstici in je med njima prosto polje."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "7e7612fd",
   "metadata": {},
   "outputs": [],
   "source": [
    "def prehodi(ovire):\n",
    "    ovire = sorted(ovire)\n",
    "    preh = set()\n",
    "    for (ya, _, xa1), (yb, xb0, _) in zip(ovire, ovire[1:]):\n",
    "        if ya == yb and xb0 == xa1 + 2:\n",
    "            preh.add((ya, xa1 + 1))\n",
    "    return preh"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2f7f33b0",
   "metadata": {},
   "source": [
    "Tule je pomembno, da napišemo `ovire = sorted(ovire)` in ne `ovire.sort()`. Funkcija `sort` sestavi nov, urejen seznam (ki mu potem dodelimo isto ime, `ovire`, vendar s tem ne spremenimo podanega seznama). Medota `sort` pa bi uredila, torej spremenilaseznam, ki smo ga podali funkciji kot argument. Tega pa ne smemo početi.\n",
    "\n",
    "Od različice 3.10 ima Python v modulu `collections` funkcijo `pairwise`. Klic `pairwise(s)` naredi (praktično) isto kot `zip(s, s[1:])`. To nam skrajša funkcijo v"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "c1a35efd",
   "metadata": {},
   "outputs": [],
   "source": [
    "def prehodi(ovire):\n",
    "    preh = set()\n",
    "    for (ya, _, xa1), (yb, xb0, _) in pairwise(sorted(ovire)):\n",
    "        if ya == yb and xb0 == xa1 + 2:\n",
    "            preh.add((ya, xa1 + 1))\n",
    "    return preh"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "105214a0",
   "metadata": {},
   "source": [
    "In kdor se še malo znajde, napiše kar"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "6f1548cd",
   "metadata": {},
   "outputs": [],
   "source": [
    "def prehodi(ovire):\n",
    "    return {(ya, xa1 + 1)\n",
    "            for (ya, _, xa1), (yb, xb0, _) in pairwise(sorted(ovire))\n",
    "            if ya == yb and xb0 == xa1 + 2}"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "6cf69290",
   "metadata": {},
   "source": [
    "## 2. Nadloga\n",
    "\n",
    "Nek kolesar obvlada veščino voženj po ovirah. Napiši funkcijo `nadlezna_ovira(ovire, y, x, pot)`, ki prejme ovire, začetne koordinate kolesarja in pot v obliki niza znakov `<`, `>`, `^` in `v`. Vrne naj oviro, na kateri je kolesar preživel največ \"potez\".\n",
    "\n",
    "Klic `nadlezna_ovira(ovire, 10, 4, \"^^^^^^>vvv<<vvv<^<^^\")`, ki opisuje (levo) pot na sliki, vrne `(7, 4, 5)`, saj je bil kolesar na njej trikrat (najprej na poti gor, potem pa še dvakrat zapored, ko je šel levo prek ovire).\n",
    "\n",
    "Pot se nikoli ne začne na oviri, lahko pa se na njej konča.\n",
    "\n",
    "Če kolesar ne naleti na nobeno oviro, naj funkcija vrne `None`. Če je enako nadležnih več ovir, lahko vrne poljubno izmed njih.\n",
    "\n",
    "### Rešitev\n",
    "\n",
    "Kolesarja bo potrebno voziti okrog. To lahko počnemo tako\n",
    "\n",
    "```python\n",
    "    for smer in pot:\n",
    "        if smer == \"<\":\n",
    "            x -= 1\n",
    "        elif smer == \">\":\n",
    "            x += 1\n",
    "        elif smer == \"^\":\n",
    "            y -= 1\n",
    "        elif smer == \"v\":\n",
    "            y += 1\n",
    "```\n",
    "\n",
    "ali pa kar tako:\n",
    "\n",
    "```python\n",
    "    for smer in pot:\n",
    "        x, y = {\"<\": (x - 1, y), \"^\": (x, y - 1), \"v\": (x, y + 1), \">\": (x + 1, y)}[smer]\n",
    "```\n",
    "\n",
    "V slovarju `podrte` bomo šteli, kolikokrat je podrl katero oviro. Ključi bodo trojke z ovirami, vrednosti števci. Da se ne hecamo po nepotrebnem z if-i, bomo uporabili `defaultdict(int)`.\n",
    "\n",
    "```python\n",
    "    podrte = defaultdict(int)\n",
    "    for smer in pot:\n",
    "        x, y = {\"<\": (x - 1, y), \"^\": (x, y - 1), \"v\": (x, y + 1), \">\": (x + 1, y)}[smer]\n",
    "        for yo, x0, x1 in ovire:\n",
    "            if yo == y and x0 <= x <= x1:\n",
    "                podrte[(y, x0, x1)] += 1\n",
    "```\n",
    "\n",
    "Na koncu je potrebno poiskati ključ, ki mu pripada največja vrednost. Če je slovar prazen, pa vrniti `None`.\n",
    "\n",
    "Dolga različica funkcije je"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "aac0c568",
   "metadata": {},
   "outputs": [],
   "source": [
    "def nadlezna_ovira(ovire, y, x, pot):\n",
    "    podrte = defaultdict(int)\n",
    "    for smer in pot:\n",
    "        if smer == \"<\":\n",
    "            x -= 1\n",
    "        elif smer == \">\":\n",
    "            x += 1\n",
    "        elif smer == \"^\":\n",
    "            y -= 1\n",
    "        elif smer == \"v\":\n",
    "            y += 1\n",
    "        for yo, x0, x1 in ovire:\n",
    "            if yo == y and x0 <= x <= x1:\n",
    "                podrte[(y, x0, x1)] += 1\n",
    "\n",
    "    if not podrte:\n",
    "        return None\n",
    "\n",
    "    naj = None\n",
    "    for ovira in podrte:\n",
    "        if naj is None or podrte[ovira] > podrte[naj]:\n",
    "            naj = ovira\n",
    "    return naj"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9d464414",
   "metadata": {},
   "source": [
    "Krajše pa gre tako:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "31ad8a41",
   "metadata": {},
   "outputs": [],
   "source": [
    "def nadlezna_ovira(ovire, y, x, pot):\n",
    "    podrte = defaultdict(int)\n",
    "    for smer in pot:\n",
    "        x, y = {\"<\": (x - 1, y), \"^\": (x, y - 1), \"v\": (x, y + 1), \">\": (x + 1, y)}[smer]\n",
    "        for yo, x0, x1 in ovire:\n",
    "            if yo == y and x0 <= x <= x1:\n",
    "                podrte[(y, x0, x1)] += 1\n",
    "\n",
    "    return max(podrte, key=podrte.get, default=None)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "135fc0c7",
   "metadata": {},
   "source": [
    "## 3. Odstranjevanje\n",
    "\n",
    "Po (pre)dolgih letih so zdaj končno zamenjali vodjo MOL-ovega Oddelka za gospodarske dejavnosti in motorni promet. (To ni šala, kar preverite!)\n",
    "\n",
    "Napiši funkcijo `odstrani(ovire, stolpci)`, ki prejme seznam ovir in številk stolpcev. Iz seznama naj odstrani vse ovire, ki zapirajo kateregakoli od podanih stolpcev. Funkcija ne sme vrniti ničesar: spreminjati mora podani seznam.\n",
    "\n",
    "### Rešitev\n",
    "\n",
    "Najpreprosteje je tako:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "43b49bef",
   "metadata": {},
   "outputs": [],
   "source": [
    "def odstrani(ovire, stolpci):\n",
    "    i = 0\n",
    "    while i < len(ovire):\n",
    "        for stolpec in stolpci:\n",
    "            if ovire[i][1] <= stolpec <= ovire[i][2]:\n",
    "                del ovire[i]\n",
    "                break\n",
    "        else:\n",
    "            i += 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3a0e994d",
   "metadata": {},
   "source": [
    "Čez ovire gremo z zanko `while`: `i` bo vseboval indeks ovire. Za vsako oviro gremo čez vse stolpce. Če vidimo, da ovira pokriva ta stolpec, pobrišemo oviro in prekinemo zanko. Če pa se zanka `for` izteče brez `break`, povečamo `i`, da bomo nadaljevali z naslednjo oviro.\n",
    "\n",
    "Ta detajl je pomemben: `i` povečujemo le, če ne pobrišemo ovire. Če jo pobrišemo, se na i-to mesto namreč postavi naslednja ovira (kot smo vsaj enkrat, nemara pa tudi večkrat videli na predavanjih), torej po brisanju `i`-te ovire spet preverimo (novo) oviro na `i`-tem mestu. Iz istega razloga rešitev v slogu\n",
    "\n",
    "```python\n",
    "def odstrani(ovire, stolpci):\n",
    "    for ovira in ovire:\n",
    "        for stolpec in stolpci:\n",
    "            if ovire[i][1] <= stolpec <= ovire[i][2]:\n",
    "                ovire.remove(ovira)\n",
    "                break\n",
    "```\n",
    "\n",
    "ne bi delovala, saj bi zanka po brisanju neke ovire preskočila oviro, ki ji sledi."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "91776eec",
   "metadata": {},
   "source": [
    "Zanki lahko tudi obrnemo: gremo čez stolpec in pobrišemo ovire v tem stolpcu."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "e2778755",
   "metadata": {},
   "outputs": [],
   "source": [
    "def odstrani(ovire, stolpci):\n",
    "    for stolpec in stolpci:\n",
    "        i = 0\n",
    "        while i < len(ovire):\n",
    "            if ovire[i][1] <= stolpec <= ovire[i][2]:\n",
    "                del ovire[i]\n",
    "            else:\n",
    "                i += 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "594afc61",
   "metadata": {},
   "source": [
    "Lahko pa si napišemo pomožno funkcijo `zapira(ovira, stolpci)`, ki preveri, ali ovira zapira katerega od podanih stolpcev."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "5fec759f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def zapira(ovira, stolpci):\n",
    "    y, x0, x1 = ovira\n",
    "    for stolpec in stolpci:\n",
    "        if x0 <= stolpec <= x1:\n",
    "            return True\n",
    "    return False"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "26165b82",
   "metadata": {},
   "source": [
    "Z njo si poenostavimo logiko zanko v `odstrani`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "ee162490",
   "metadata": {},
   "outputs": [],
   "source": [
    "def odstrani(ovire, stolpci):\n",
    "    i = 0\n",
    "    while i < len(ovire):\n",
    "        if zapira(ovire[i], stolpci):\n",
    "            del ovire[i]\n",
    "        else:\n",
    "            i += 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b3ef2143",
   "metadata": {},
   "source": [
    "Funkcijo `zapira` je možno napisati tudi krajše."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "6f34dcd5",
   "metadata": {},
   "outputs": [],
   "source": [
    "def zapira(ovira, stolpci):\n",
    "    return any(ovira[1] <= stolpec <= ovira[2] for stolpec in stolpci)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "54bb3586",
   "metadata": {},
   "source": [
    "Če je tako, pa funkcije niti ne potrebujemo, temveč lahko `zapira` stlačimo kar v `odstrani`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "afc13d3c",
   "metadata": {},
   "outputs": [],
   "source": [
    "def odstrani(ovire, stolpci):\n",
    "    i = 0\n",
    "    while i < len(ovire):\n",
    "        _, x0, x1 = ovire[i]\n",
    "        if any(x0 <= stolpec <= x1 for stolpec in stolpci):\n",
    "            del ovire[i]\n",
    "        else:\n",
    "            i += 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ef7586ca",
   "metadata": {},
   "source": [
    "Drugačen pristop je, da ne brišemo elementov obstoječega seznama, temveč sestavimo nov seznam, ki vsebuje le preostale ovire. Na koncu funkcije pa preprosto zamenjamo vse elemente seznama `ovire` s temi."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "0c0e7711",
   "metadata": {},
   "outputs": [],
   "source": [
    "def odstrani(ovire, stolpci):\n",
    "    ostale = []\n",
    "    for ovira in ovire:\n",
    "        if not zapira(ovira, stolpci):\n",
    "            ostale.append(ovira)\n",
    "    ovire[:] = ostale"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e44f23dd",
   "metadata": {},
   "source": [
    "Ali pa kar"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "770ee824",
   "metadata": {},
   "outputs": [],
   "source": [
    "def odstrani(ovire, stolpci):\n",
    "    ovire[:] = [ovira for ovira in ovire if not zapira(ovira, stolpci)]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e2dd485c",
   "metadata": {},
   "source": [
    "Če se nam ne da pisati funkcije `zapira`, pa je celotna rešitev kar"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "13593830",
   "metadata": {},
   "outputs": [],
   "source": [
    "def odstrani(ovire, stolpci):\n",
    "    ovire[:] = [ovira for ovira in ovire\n",
    "                if not any(ovira[1] <= stolpec <= ovira[2] for stolpec in stolpci)]"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "d7c26abc",
   "metadata": {},
   "source": [
    "## 4. Žaba\n",
    "\n",
    "Tako kot veverice si tudi žabe ne upajo stopiti na kolesarsko pot, temveč se premikajo zgolj po ovirah. Žaba lahko hodi levo in desno po oviri, skače pa vedno samo naravnost navgor. (Zaradi močnega vetra v to smer.)\n",
    "\n",
    "Žaba želi priti na vrh poti in pri tem delati čim krajše skoke. Za pot z ovire `(14, 8, 10)` bo morala narediti vsaj en skok dolžine 3; primer možne takšne poti je na sliki.\n",
    "\n",
    "Napiši funkcijo `najdaljsi_skok(ovire, ovira)`, ki prejme seznam ovir in začetno oviro (kot terko (y, x0, x1)), ter vrne najdaljši skok, ki ga bo morala opraviti žaba, če izbere pot, pri kateri je najdaljši skok čim krajši.\n",
    "\n",
    "V pomoč: v datoteki s testi je funkcija `naprej(ovire, ovira)`, ki vrne vse ovire, na katere je možno skočiti z ovira.\n",
    "Pazi (1): Med deveto in peto vrstico so tri prazne vrste, zato se šteje, da je skok med njima dolg 3 (ne 4!).\n",
    "\n",
    "Pazi (2): žaba naj ne skače kar brezglavo na najbližjo oviro! Če iz `(14, 8, 10)` skoči na `(12, 10, 12)` in potem na `(10, 12, 12)`, se zafrkne, saj mora potem z `(10, 12, 12)` narediti skok dolžine 7!\n",
    "\n",
    "### Rešitev"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "e158e4ba",
   "metadata": {},
   "outputs": [],
   "source": [
    "def naprej(ovire, ovira):\n",
    "    yo, xo0, xo1 = ovira\n",
    "    return [(y, x0, x1) for y, x0, x1 in ovire\n",
    "            if y < yo and (x0 <= xo0 <= x1 or xo0 <= x0 <= xo1)]\n",
    "\n",
    "\n",
    "def najdaljsi_skok(ovire, ovira):\n",
    "    naj = ovira[0] - 1\n",
    "    for nasl in naprej(ovire, ovira):\n",
    "        najt = max(ovira[0] - nasl[0] - 1, najdaljsi_skok(ovire, nasl))\n",
    "        if najt < naj:\n",
    "            naj = najt\n",
    "    return naj"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "172f707f",
   "metadata": {},
   "source": [
    "Najkrajši skok je, za začetek, skok s te ovire do konca, `ovira[0] - 1`.\n",
    "\n",
    "Nato gremo čez vse ovire, na katere lahko skočimo (`nasl`). Skok do ovire `nasl` je dolg `ovira[0] - nasl[0] - 1`. Najdaljši skok s te ovire, `nasl`, do konca, bo `najdaljsi_skok(ovire, nasl)`. Najdaljši skok, če nadaljujemo po prek ovire `nasl`, bo tisto, kar od tega dvojega je večje - sam skok do `nasl` ali pa eden od skokov naprej. Torej `najt = max(ovira[0] - nasl[0] - 1, najdaljsi_skok(ovire, nasl))`. Če je to manjše od najmanjšega skoka doslej, si zapomnimo to dolžino. In jo na koncu vrnemo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "a159142d",
   "metadata": {},
   "outputs": [],
   "source": [
    "def najdaljsi_skok(ovire, ovira):\n",
    "    naj = ovira[0] - 1\n",
    "    for nasl in naprej(ovire, ovira):\n",
    "        najt = max(ovira[0] - nasl[0] - 1, najdaljsi_skok(ovire, nasl))\n",
    "        if najt < naj:\n",
    "            naj = najt\n",
    "    return naj"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e3bd1695",
   "metadata": {},
   "source": [
    "Če se komu ne da tipkati, pa napiše"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "13982489",
   "metadata": {},
   "outputs": [],
   "source": [
    "def najdaljsi_skok(ovire, ovira):\n",
    "    return min((max(ovira[0] - nasl[0] - 1, najdaljsi_skok(ovire, nasl))\n",
    "                for nasl in naprej(ovire, ovira)),\n",
    "               default=ovira[0] - 1)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "id": "36652783",
   "metadata": {},
   "source": [
    "## 5. Anarhist\n",
    "\n",
    "Napiši razred `Kolesar`.\n",
    "\n",
    "- Konstruktor prejme argumente `(ovire, y, x)`, to je seznam ovir in začetno točko. Začetna točka gotovo ni na oviri. Razred sme v kasnejših metodah spreminjati podani seznam.\n",
    "- Metoda `premik(smer)` ga premakne s trenutne točke za eno polje v podani smeri (<, >, ^ ali v). Če je na tistem polju slučajno ovira, jo kolesar zdrobi v sončni prah. Potem te ovire ni več.\n",
    "- Metoda `lokacija()` vrne trenutno lokacijo kolesarja v obliki terke `(y, x)`.\n",
    "- Metoda `uspesnost()` vrne število ovir, ki jih je kolesar uničil doslej.\n",
    "\n",
    "Kolesar, ki bi opravil (levo) pot na sliki, bi pri tem uničil štiri ovire.\n",
    "\n",
    "### Rešitev\n",
    "\n",
    "Ker naloga pravi, da smemo spreminjati podani seznam, ga pač spreminjajmo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "c24437fe",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Kolesar:\n",
    "    def __init__(self, ovire, y, x):\n",
    "        self.x = x\n",
    "        self.y = y\n",
    "        self.ovire = ovire\n",
    "        self.unicenih = 0\n",
    "\n",
    "    def premik(self, smer):\n",
    "        dx, dy = {\"<\": (-1, 0), \"^\": (0, -1), \"v\": (0, 1), \">\": (1, 0)}[smer]\n",
    "        self.x += dx\n",
    "        self.y += dy\n",
    "        for y, x0, x1 in self.ovire:\n",
    "            if self.y == y and x0 <= self.x <= x1:\n",
    "                self.ovire.remove((y, x0, x1))\n",
    "                self.unicenih += 1\n",
    "                break\n",
    "\n",
    "    def lokacija(self):\n",
    "        return (self.y, self.x)\n",
    "\n",
    "    def uspesnost(self):\n",
    "        return self.unicenih\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6a240f49",
   "metadata": {},
   "source": [
    "Še bolj prav bi bilo, če bi namesto `remove` uporabili `del` - ker je hitrejše in ker nas ne bi nič stalo poznati indeks elementa (z izjemo klica funkcije `enumerate` in dodatne spremenljivke `i`). Vendar ovir ni tako veliko, da bi se splačalo komplicirati s tem.\n",
    "\n",
    "Lahko pa se lotimo z druge strani: namesto, da brišemo ovire, hranimo množico razbitih ovir. Nekaj v tem slogu:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "56143c5a",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Kolesar:\n",
    "    def __init__(self, ovire, y, x):\n",
    "        self.x = x\n",
    "        self.y = y\n",
    "        self.ovire = ovire\n",
    "        self.unicene = set()\n",
    "\n",
    "    def premik(self, smer):\n",
    "        dx, dy = {\"<\": (-1, 0), \"^\": (0, -1), \"v\": (0, 1), \">\": (1, 0)}[smer]\n",
    "        self.x += dx\n",
    "        self.y += dy\n",
    "        for y, x0, x1 in ovire:\n",
    "            if y == self.y and x0 <= self.x <= x1:\n",
    "                self.unicene.add((y, x0, x1))\n",
    "                break\n",
    "\n",
    "    def lokacija(self):\n",
    "        return (self.y, self.x)\n",
    "\n",
    "    def uspesnost(self):\n",
    "        return len(self.unicene)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "39e6e4b9",
   "metadata": {},
   "source": [
    "## Vse skupaj\n",
    "\n",
    "Zanimivo, kako jedrnato je bilo možno rešiti tale izpit."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "56b8df04",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 1\n",
    "\n",
    "def prehodi(ovire):\n",
    "    return {(ya, xa1 + 1)\n",
    "            for (ya, _, xa1), (yb, xb0, _) in pairwise(sorted(ovire))\n",
    "            if ya == yb and xb0 == xa1 + 2}\n",
    "\n",
    "\n",
    "# 2\n",
    "\n",
    "def nadlezna_ovira(ovire, y, x, pot):\n",
    "    podrte = defaultdict(int)\n",
    "    for smer in pot:\n",
    "        x, y = {\"<\": (x - 1, y), \"^\": (x, y - 1), \"v\": (x, y + 1), \">\": (x + 1, y)}[smer]\n",
    "        for yo, x0, x1 in ovire:\n",
    "            if yo == y and x0 <= x <= x1:\n",
    "                podrte[(y, x0, x1)] += 1\n",
    "\n",
    "    return max(podrte, key=podrte.get, default=None)\n",
    "\n",
    "\n",
    "# 3 \n",
    "\n",
    "def odstrani(ovire, stolpci):\n",
    "    ovire[:] = [ovira for ovira in ovire\n",
    "                if not any(ovira[1] <= stolpec <= ovira[2] for stolpec in stolpci)]\n",
    "\n",
    "    \n",
    "# 4\n",
    "\n",
    "# Funkcija `naprej` je podana\n",
    "def naprej(ovire, ovira):\n",
    "    yo, xo0, xo1 = ovira\n",
    "    return [(y, x0, x1) for y, x0, x1 in ovire\n",
    "            if y < yo and (x0 <= xo0 <= x1 or xo0 <= x0 <= xo1)]\n",
    "\n",
    "def najdaljsi_skok(ovire, ovira):\n",
    "    return min((max(ovira[0] - nasl[0] - 1, najdaljsi_skok(ovire, nasl))\n",
    "                for nasl in naprej(ovire, ovira)),\n",
    "               default=ovira[0] - 1)\n",
    "\n",
    "\n",
    "# 5\n",
    "\n",
    "class Kolesar:\n",
    "    def __init__(self, ovire, y, x):\n",
    "        self.x = x\n",
    "        self.y = y\n",
    "        self.ovire = ovire\n",
    "        self.unicene = set()\n",
    "\n",
    "    def premik(self, smer):\n",
    "        dx, dy = {\"<\": (-1, 0), \"^\": (0, -1), \"v\": (0, 1), \">\": (1, 0)}[smer]\n",
    "        self.x += dx\n",
    "        self.y += dy\n",
    "        for y, x0, x1 in ovire:\n",
    "            if y == self.y and x0 <= self.x <= x1:\n",
    "                self.unicene.add((y, x0, x1))\n",
    "                break\n",
    "\n",
    "    def lokacija(self):\n",
    "        return (self.y, self.x)\n",
    "\n",
    "    def uspesnost(self):\n",
    "        return len(self.unicene)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}