{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Python gyakorlat 7" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": [ "import numpy as np\n", "import random as rn\n", "import networkx as nx" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# 1. Robot a labirintusban" ] }, { "cell_type": "code", "execution_count": 40, "metadata": {}, "outputs": [], "source": [ "# labirintus rajzoló. Egy -1/0/1/../9 numpy tömböt vár. -1-fal, 0,1,2,...,9 nem fal\n", "def printmaze(a):\n", " def selector(c):\n", " if c==-1:\n", " return chr(0x2588)\n", " if c in range (10):\n", " return str(c)[0]\n", " else:\n", " return ' '\n", " for row in a:\n", " print(\"\".join([selector(c) for c in row]))\n", " # print(\"\".join([\" \" if c==0 else chr(0x2B1B) for c in row]))\n", "\n", "#Labirintus\n", "def makemaze(w=16,h=8,entry=0,inner=0):\n", " maze=-np.ones((2*w+1,2*h+1))\n", " vis=np.zeros((2*w+1,2*h+1))\n", " \n", " def walk(x, y):\n", " vis[x][y] = 1\n", " maze[x,y]=int(rn.randrange(10))\n", " \n", " d = [(x - 2, y), (x, y + 2), (x + 2, y), (x, y - 2)]\n", " rn.shuffle(d)\n", " \n", " for (xx, yy) in d:\n", " if (not xx in range(2*w+1)) or (not yy in range(2*h+1)) or vis[xx][yy]: \n", " continue\n", " if xx == x: \n", " maze[x][max(y, yy)-1] = int(rn.randrange(10))\n", " if yy == y: \n", " maze[max(x, xx)-1][y] = int(rn.randrange(10))\n", " walk(xx, yy)\n", " \n", " walk(2*rn.randrange(w)+1, 2*rn.randrange(h)+1)\n", " \n", " ### bejáratok\n", " for i in range(entry):\n", " if rn.randrange(2)==0:\n", " pos=rn.randrange(w)\n", " if rn.randrange(2)==0:\n", " maze[2*pos+1,0]=int(rn.randrange(10))\n", " else:\n", " maze[2*pos+1,-1]=int(rn.randrange(10))\n", " else: \n", " pos=rn.randrange(h)\n", " if rn.randrange(2)==0:\n", " maze[0,2*pos+1]=int(rn.randrange(10))\n", " else:\n", " maze[-1,2*pos+1]=int(rn.randrange(10))\n", " \n", " ### belső körökhöz fal törlés\n", " for i in range(inner):\n", " if rn.randrange(2)==0:\n", " maze[2*rn.randrange(w-1)+2,2*rn.randrange(h)+1]=int(rn.randrange(10))\n", " else:\n", " maze[2*rn.randrange(w)+1,2*rn.randrange(h-1)+2]=int(rn.randrange(10))\n", " \n", " return maze" ] }, { "cell_type": "code", "execution_count": 78, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "█████6███████████████\n", "█696█9498747█5621225█\n", "███9█4█████2█1███████\n", "█533█8█208█4█7119020█\n", "█1███0█2███4█9█████0█\n", "07█096█4█70736█875█4█\n", "█2█████9█8█████4█1█8█\n", "█8█00493█5█782█6█6213\n", "█2█6███3█7█9█9█3███2█\n", "147857█85086█479█9514\n", "█████████████████████\n" ] } ], "source": [ "printmaze(makemaze(5,10,5,5))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 1.1 Robi a robot szeretne kijutni a labirintusból (a középső mezőről indul). Segíts neki! Találd meg a legrövidebb kiutat (számokkal egyelőre még ne foglalkozz, ha nem -1 van írva a mezőre, oda be lehet lépni)." ] }, { "cell_type": "code", "execution_count": 80, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "███████████████████████████████████████\n", "█2793667█85911187918█063█0448407912971█\n", "█1█5█████6█████████0█0█1█2█2█████0█████\n", "█7█0█947█4█230793287█0█243█31041█7█073█\n", "█4█0█3█5█4█0███6█████7█████████1███4█7█\n", "█8█705█101█8█213█19417█982█344█2█830█3█\n", "█5█████████0█████0█████3███3█9█5█3███5█\n", "█9█849█753█91772█349█385402473█974█415█\n", "█8█8███9█0█████0███9█████████4█████0███\n", "█226█980█5403941█044█525946864█358█104█\n", "███4█5█████████7█4███1███████2█5█1███6█\n", "█802█1768928█1█5█084█97627█965█3█0█3█6█\n", "█0█████0███7█5█3███8█2███2█3███8█3█6█1█\n", "█5█513█5█094█29392█9█082█3█39891█221█2█\n", "███6█6███3█████████9█████6█████████3█7█\n", "█207█309█066302848█2█61268█3081371█8█1█\n", "█9█████7█████1███8█3█1█4███4█████3█4█9█\n", "█485█1█76809█260█87515█1█3974892█1█6█4█\n", "███4█3█████6█2███████████7█████5█2███8█\n", "█9█794█320█2█0█237█7176459█055█4█321█5█\n", "█4███0█3███5█1█9█9█1█5███████5█0███4█7█\n", "█55248█5█307█6█7█018█1█00339█7█411█1█7█\n", "█0█████6█1█████1█████1█8███1█2███1█4█8█\n", "█0█900█9█6074710█8176415█102█084█5█3█3█\n", "█7█5█6█2█████████████0█7█6█████9███9█3█\n", "█129█092█0614177523249█1█72298█08441█8█\n", "███████8███5███0███████8█████3███████0█\n", "█74105█1001145█0█17213█67118█162█06387█\n", "███0█9███████2█0█4███2█████9█0█8█8███3█\n", "█905█8█8061810█60908█404█347█1█3█7█196█\n", "█4█████9█████████████7█3█7███1█4███4█8█\n", "█096█954█848█318501676█5█300█5█60019█1█\n", "███3█1███4█6█1███████9█8███8█1███████4█\n", "█898█46373█200█4█65108█24998█8█4211384█\n", "█1█████████████9█0███████1███2█6███████\n", "█128339724█9█58364█27902█658█2█740█472█\n", "█6█████5█3█0█5███████7█8███4█8███7█0█4█\n", "█3█2█627█169█5306156█3█5█097█4█965█6█7█\n", "█6█7█4█████████████5█6█2█2███8█1█████5█\n", "█7█4█5442121683668█9█7█4█8█207█8█34805█\n", "█0█4███████████9███1█5█3███9███3█5███7█\n", "█2248111049788█2005400█66106█60513█376█\n", "█████████████6█████████████7███████████\n" ] } ], "source": [ "width=21\n", "height=19\n", "entrances=int(rn.randrange(int((width+height)/4)))\n", "inner_cricles=int(rn.randrange(int((width+height)/2)))\n", "maze=makemaze(width,height,entrances,inner_cricles)\n", "printmaze(maze)\n", "\n", "start_x=2*int(width/2)+1\n", "start_y=2*int(height/2)+1" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 1.2 Robi vagy lép egyet előre, vagy kanyrodik 90 fokot: mindkető műveletnek egységnyi költsége van. Ezt is figyelembe véve találd meg a legrövidebb kiutat (számokkal egyelőre még ne foglalkozz, ha nem -1 van írva a mezőre, oda be lehet lépni)." ] }, { "cell_type": "code", "execution_count": 73, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "8\n", "0\n", "2\n", "6\n", "4\n", "9\n", "7\n", "3\n", "4\n", "6\n", "3\n", "6\n", "0\n", "5\n", "1\n", "9\n", "3\n", "5\n", "4\n", "9\n", "----------\n", "0\n", "0\n", "1\n", "2\n", "3\n", "3\n", "3\n", "4\n", "4\n", "4\n", "5\n", "5\n", "6\n", "6\n", "6\n", "7\n", "8\n", "9\n", "9\n", "9\n" ] }, { "ename": "AssertionError", "evalue": "", "output_type": "error", "traceback": [ "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[0;31mAssertionError\u001b[0m Traceback (most recent call last)", "\u001b[0;32m\u001b[0m in \u001b[0;36m\u001b[0;34m\u001b[0m\n\u001b[1;32m 54\u001b[0m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mkupac\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mdelMin\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 55\u001b[0m \u001b[0;31m#itt már üres, el kell szálljon\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 56\u001b[0;31m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mkupac\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mdelMin\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m", "\u001b[0;32m\u001b[0m in \u001b[0;36mdelMin\u001b[0;34m(self)\u001b[0m\n\u001b[1;32m 36\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 37\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0mdelMin\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 38\u001b[0;31m \u001b[0;32massert\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mcurrentSize\u001b[0m\u001b[0;34m!=\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 39\u001b[0m \u001b[0mretval\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mheapList\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 40\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mheapList\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mheapList\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mcurrentSize\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;31mAssertionError\u001b[0m: " ] } ], "source": [ "#bináris kupac a Dijkstrához\n", "class BinaryHeap:\n", " def __init__(self):\n", " self.heapList = [0]\n", " self.currentSize = 0\n", " def percUp(self,i):\n", " while i // 2 > 0:\n", " if self.heapList[i] < self.heapList[i // 2]:\n", " tmp = self.heapList[i // 2]\n", " self.heapList[i // 2] = self.heapList[i]\n", " self.heapList[i] = tmp\n", " i = i // 2\n", " \n", " def insert(self,k):\n", " self.heapList.append(k)\n", " self.currentSize = self.currentSize + 1\n", " self.percUp(self.currentSize)\n", " \n", " def percDown(self,i):\n", " while (i * 2) <= self.currentSize:\n", " mc = self.minChild(i)\n", " if self.heapList[i] > self.heapList[mc]:\n", " tmp = self.heapList[i]\n", " self.heapList[i] = self.heapList[mc]\n", " self.heapList[mc] = tmp\n", " i = mc\n", "\n", " def minChild(self,i):\n", " if i * 2 + 1 > self.currentSize:\n", " return i * 2\n", " else:\n", " if self.heapList[i*2] < self.heapList[i*2+1]:\n", " return i * 2\n", " else:\n", " return i * 2 + 1\n", " \n", " def delMin(self):\n", " assert(self.currentSize!=0)\n", " retval = self.heapList[1]\n", " self.heapList[1] = self.heapList[self.currentSize]\n", " self.currentSize = self.currentSize - 1\n", " self.heapList.pop()\n", " self.percDown(1)\n", " return retval\n", " \n", "# tesztelés\n", "kupac=BinaryHeap()\n", "for i in range(20):\n", " num=rn.randrange(10)\n", " print(num)\n", " kupac.insert(num)\n", "print(\"----------\")\n", "for i in range(20):\n", " print(kupac.delMin())\n", "#itt már üres, el kell szálljon\n", "print(kupac.delMin())" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 1.3 A szabad mezőkre írt számok a tengerszint feletti magasságot szimbolizálják. Egy mezőre belépés költsége a kettő mezőre beírt szám különbsége + 1 ha a különbség pozitív, 0 különben. Ezt figyelembe véve (most Robi ingyen kanyarodik) találd meg a legkevesebb energiát felhasználó kiutat." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 1.4 * A szabad mezőkre írt számok a tengerszint feletti magasságot szimbolizálják. Egy mezőre belépés költsége a kettő mezőre beírt szám különbsége + 1, ha a különbség pozitív, különben a különbség 0.8-szorosa (Robi lefele gurulva 80% hatékonysággal tölti az akkumulátorát). Ezt figyelembe véve (most Robi ingyen kanyarodik) találd meg a legkevesebb energiát felhasználó kiutat." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# 2\n", "\n", "A következő cellában levő kóddal egy páciens agyának leképezését reprezentáló `brain.graphml` gráfot olvassuk be. \n", "
\n", "Minden csúcs a szürkeállomány egy részét reprezentálja, míg az élek a területek közötti kötegeket. Az ilyen gráfokat nevezzük Connectome-nak. \n", "
\n", "Azzal a feltevéssel élünk, hogy a különböző agyterületek jeleket küldenek egymásnak, amik a kötegeken keresztül közlekednek. \n", "
\n", "\n", "A gráf a csúcsok és élek leírására a következő adatokat tartalmazza: \n", "
\n", "\n", "| Csúcstulajdonság | Leírása |\n", "| :- | :- |\n", "| dn_position_x | Az agyterület középpontjának x koordinátája |\n", "| dn_position_y | Az agyterület középpontjának y koordinátája |\n", "| dn_position_z | Az agyterület középpontjának z koordinátája |\n", "| dn_correspondence_id | Az id mégegyszer |\n", "| dn_region | Tartalmazó régió megnevezése |\n", "| dn_fsname | Terület rövid megnevezése |\n", "| dn_name | Terület teljes neve |\n", "| dn_hemisphere | Agyféltek |\n", "\n", "\n", "| Éltulajdonság | Leírása |\n", "| :- | :- |\n", "| fiber_length_mean | Az összekötő köteg becsült átlagos hossza |\n", "| FA_mean | Az összekötő köteg detektálásának biztonsága |\n", "| number_of_fibers | Az összekötő kötegben található idegrostok becsült száma (nem egész szám)|" ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "{'dn_position_x': 29.8898305085, 'dn_position_y': 80.5084745763, 'dn_position_z': 19.5, 'dn_correspondence_id': '35', 'dn_region': 'cortical', 'dn_fsname': 'parstriangularis_8', 'dn_name': 'rh.parstriangularis_8', 'dn_hemisphere': 'right'}\n", "{'fiber_length_mean': 22.6231660843, 'FA_mean': 0.119496156461, 'number_of_fibers': 13.125}\n" ] } ], "source": [ "G = nx.read_graphml(\"brain.graphml\")\n", "\n", "print(G.nodes['35'])\n", "\n", "print(G.edges['35', '184'])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Válaszolj a következő kérédsekre/ oldd meg a feladatokat!\n", "\n", "
    \n", "
  • Összefüggő-e a gráf?
    • \n", "
  • Melyik a legtöbb kapcsolattal rendelkező terület?
    • \n", "
  • Melyik két közvetlen kapcsoaltban lévő terület között kell a jelnek a leghosszabb utat megtennie?
    • \n", "
  • Melyik két közvetlen kapcsolatban lévő terület van fizikailag a legmesszebb egymástól? (Két terület távolságát definiáljuk a középpontjaik távolságaként.)
    • \n", "
  • Mekkora a legrövidebb utak közül a leghosszabb? (Mekkora a gráf átmérője?) Milyen arányban van ez az agy fizikai átmérőjével?
    • \n", "
  • Mennyi a két agyféltekében lévő csúcsok egymástól vett átlagos távolsága? (Nem fizikai..)
    • \n", "
  • Melyik régió tartalmazza a legtöbb csúcsot?
    • \n", "
  • Nézz utána, hogyan tudsz készíteni graphml file-t `networkx` csomag segítségével, és mentsd el a különböző régiók részgráfjait!
    • \n", "
" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# 3\n", "A Csíkszerda kórus minden koncertjét hosszú előkészületek előzik meg. Segíts nekik az ütemterv megszervezésében!\n", "
\n", "A következő lépéseket kell teljesíteni:\n", "\n", "| Feladat kódja | Feladat leírása | Időtartam |\n", "| :- | :- | :- |\n", "| A | Darab betanulása |7 hét |\n", "| B | Jelmezek elkészítése | 3 hét |\n", "| C | Díszletek elékszítése | 3 hét |\n", "| D | Poszterek tervezése | 3 nap |\n", "| E | Poszerek nyomtatása | 1 nap |\n", "| F | Jegyek nyomtatása | 1 nap |\n", "| G | Előadási jog megszerzése | 1 hét |\n", "| H | Terembérlés | 2 hét |\n", "| I | Világítás megszervezése | 1 hét |\n", "| J | Kották nyomtatása | 2 nap |\n", "| K | Helyszíni főpróba | 2 nap |\n", "\n", "A feladatok között a következő összefüggések vannak:\n", "\n", "| Feladat kódja | Megelőző feladatok |\n", "| :- | :- |\n", "| A | J, G |\n", "| B | G |\n", "| C | G, H |\n", "| D | G |\n", "| E | D, G |\n", "| F | G |\n", "| G | - |\n", "| H | G |\n", "| I | G, H |\n", "| J | G |\n", "| K | A, B, C, D, E, F, G, H, I, J|\n", "\n", "Mondd meg a karvezetőnek, hogy az előkészületekre minimum mennyi időt kell szánni, és adj a feladatok elvégzésének egy logikus sorrendjét!" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# 4\n", "Egy (rosszul megtervezett) számzár négy karakterből álló kódot vár a `0,1,2,3, ... , 9` karakterkészletből és folytonosan fogad el kódokat. \n", "
\n", "(Tehát például ha egy betörő beüti az `120056` karaktersorozatot, akkor egyszerre kipróbálta az \n", "`1200`, `2005`, `0056` kódokat, pedig csak 6 karaktert ütött be.)\n", "
\n", "\n", "Segíts a betörőnek, hogy minél gyorsabban kipróbálhasson minden lehetséges kódot! " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "000000010002\n", "40.000\n", "00001\n", "0001235\n", "10.003\n", "csúcsok: 000, 123, \n", "élei: (000,001), (000,002) euler-séta" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# 5\n", "Az egyik legismertebb [Snake](https://snake.googlemaps.com/) AI stratégia, hogy a tábla lehetséges mezőit egy gráf csúcsainak tekintjük, a szomszédságot élekkel reprezentáljuk, majd a kapott gráfon generálunk egy Hamilton-kört. A növekvő kígyót ezen a körön járatjuk végig, így biztosítva, hogy sohasem ütközik magába és bejár minden lehetséges mezőt, így biztosan eljut az almához. \n", "
\n", "\n", "Írj függvényt, ami tetszőleges méretű táblához generál egy Hamilton-kört! A függvény bemenete legyen két természetes szám, `n` és `k`, ahol `n` a tábla magassága `k` pedig a szélessége, kimenete pedig csak a Hamilton-kör éleit tartalmazó `networx.Graph`, ahol a csúcsokat 2-elemű tuple-ok reprezentálnak a táblán megfelelő mező indexei szerint." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def generate_snake_path(n,k):\n", " # ToDo\n", " return None\n", "\n", "\n", "snake_path = generate_snake_path(3,4)\n", "assert isinstance(snake_path, nx.Graph)\n", "assert len(nx.cycle_basis(snake_path)) == 1\n", "assert len(nx.cycle_basis(snake_path)[0]) == 3*4" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.7.6" } }, "nbformat": 4, "nbformat_minor": 4 }