{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "animal-abuse",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "\n",
    "# Matematikai Algoritmusok és Felfedezések I.\n",
    "\n",
    "## 12. Előadás: Algoritmikus gondolkodás\n",
    "\n",
    "### 2021 május 3.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "restricted-contamination",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## Beadandó tapasztalatok\n",
    "\n",
    "- Fájl olvasás  `with`\n",
    "- Hatékony megszámolás egy ciklussal\n",
    "- Függvények felhasználása\n",
    "- Sok `if` elkerülése\n",
    "- List comprehension\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "mighty-burke",
   "metadata": {},
   "source": [
    "#### lassú megoldás a 3. feladatra\n",
    "```\n",
    "drb_szotar={}\n",
    "for i in hun_alph:\n",
    "    darab = 0\n",
    "    for j in range(len(szoveg)):\n",
    "        if szoveg[j] == i:                    \n",
    "            darab = darab + 1\n",
    "    drb_szotar[i] = darab                       \n",
    "```\n",
    "\n",
    "#### gyors megoldás\n",
    "```\n",
    "char_freq = {}\n",
    "for char in szoveg:\n",
    "    if char in char_freq:\n",
    "        char_freq[char] += 1\n",
    "    else:\n",
    "        char_freq[char] = 1\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "gothic-prefix",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "\n",
    "<img src=\"https://imgs.xkcd.com/comics/automation_2x.png \" alt=\"drawing\" width=\"800\"/>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "spanish-tours",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Programkészítés menete\n",
    "\n",
    "- Feladat értelmezése\n",
    "- Tervezés\n",
    "- Implementálás\n",
    "- Tesztelés\n",
    "- Valamit elrontottunk, vissza egy korábbi ponthoz!"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "concrete-zimbabwe",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Tervezés\n",
    "- Adatszerkezet kitalálása. Milyen adatokat fogok tárolni? Hogyan érdemes őket tárolni? \n",
    "- Milyen műveletekre lesz szükségem? Azokat hogyan lehet algoritmussal megvalósítani?\n",
    "- Mennyire számít a sebesség? Ha számít, akkor hogyan érhetem el, hogy gyors legyen?\n",
    "- Mennyire pontos eredményt szeretnék? \n",
    "- Objektum orientáltan csináljam vagy procedurálisan, esetleg funkcionálisan? \n",
    "- Hogyan lehet ezeket objektum orientáltan megoldani? Milyen osztályokat érdemes elkészíteni?\n",
    " "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "western-passion",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Implementálás és tesztelés\n",
    " - Apró lépésekben érdemes dolgozni. Kb mindig legyen működő a program.\n",
    " - Ne feledjük el, hogy rengeteg mindent már megírtak, érdemes ezt kihasználni.\n",
    " - Érdemes kommentekkel ellátni a kódot, és beszédes változóneveket használni, hogy pár nap múlva is érthető legyen. \n",
    " - Minden lényegesebb lépés után teszteljünk. \n",
    " - Általában az implementálás, a tesztelés és a hibajavítás gyorsan váltogatja egymást. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "expensive-middle",
   "metadata": {},
   "source": [
    "\"For some people, programming and debugging are the same thing. That is, programming is the process of gradually debugging a program until it does what you want. The idea is that you should start with a program that does something and make small modifications, debugging them as you go, so that you always have a working program.\" (https://runestone.academy/)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "together-specification",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## Példa 1. Sodoku megoldó\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "legendary-imperial",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import itertools as it"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "rising-boundary",
   "metadata": {},
   "outputs": [],
   "source": [
    "board=np.array( [\n",
    "    [7,8,0,4,0,0,1,2,0],\n",
    "    [6,0,0,0,7,5,0,0,9],\n",
    "    [0,0,0,6,0,1,0,7,8],\n",
    "    [0,0,7,0,4,0,2,6,0],\n",
    "    [0,0,1,0,5,0,9,3,0],\n",
    "    [9,0,4,0,6,0,0,0,5],\n",
    "    [0,7,0,3,0,0,0,1,2],\n",
    "    [1,2,0,0,0,0,4,0,0],\n",
    "    [0,4,9,2,0,6,0,0,0]\n",
    "])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "cathedral-muslim",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def print_board(bo):\n",
    "    for i in range(len(bo)):\n",
    "        if i % 3 == 0 and i != 0:\n",
    "            print(\"- - - - - - - - - - - - \")\n",
    "\n",
    "        for j in range(len(bo[0])):\n",
    "            if j % 3 == 0 and j != 0:\n",
    "                print(\" | \", end=\"\")\n",
    "\n",
    "            if j == 8:\n",
    "                print(bo[i][j])\n",
    "            else:\n",
    "                print(str(bo[i][j]) + \" \", end=\"\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "organic-ordering",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7 8 0  | 4 0 0  | 1 2 0\n",
      "6 0 0  | 0 7 5  | 0 0 9\n",
      "0 0 0  | 6 0 1  | 0 7 8\n",
      "- - - - - - - - - - - - \n",
      "0 0 7  | 0 4 0  | 2 6 0\n",
      "0 0 1  | 0 5 0  | 9 3 0\n",
      "9 0 4  | 0 6 0  | 0 0 5\n",
      "- - - - - - - - - - - - \n",
      "0 7 0  | 3 0 0  | 0 1 2\n",
      "1 2 0  | 0 0 0  | 4 0 0\n",
      "0 4 9  | 2 0 6  | 0 0 0\n"
     ]
    }
   ],
   "source": [
    "print_board(board)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "subtle-hammer",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "# üres mező keresése\n",
    "def find_empty(bo):\n",
    "    for i,j in it.product(range(len(bo)),range(len(bo[0]))):\n",
    "        if bo[i][j] == 0:\n",
    "            return (i, j)   \n",
    "\n",
    "    return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "million-thermal",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7 8 0  | 4 0 0  | 1 2 0\n",
      "6 0 0  | 0 7 5  | 0 0 9\n",
      "0 0 0  | 6 0 1  | 0 7 8\n",
      "- - - - - - - - - - - - \n",
      "0 0 7  | 0 4 0  | 2 6 0\n",
      "0 0 1  | 0 5 0  | 9 3 0\n",
      "9 0 4  | 0 6 0  | 0 0 5\n",
      "- - - - - - - - - - - - \n",
      "0 7 0  | 3 0 0  | 0 1 2\n",
      "1 2 0  | 0 0 0  | 4 0 0\n",
      "0 4 9  | 2 0 6  | 0 0 0\n",
      "(0, 2)\n"
     ]
    }
   ],
   "source": [
    "print_board(board)\n",
    "print(find_empty(board))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "political-shuttle",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def valid(bo, num, pos):\n",
    "    #1-től 9-ig\n",
    "    if num not in range(1,10):\n",
    "        return False\n",
    "    \n",
    "    if bo[pos[0],pos[1]]!=0:\n",
    "        return False\n",
    "    \n",
    "    # sor\n",
    "    for i in range(len(bo[0])):\n",
    "        if bo[pos[0]][i] == num and pos[1] != i:\n",
    "            return False\n",
    "\n",
    "    # oszlop\n",
    "    for i in range(len(bo)):\n",
    "        if bo[i][pos[1]] == num and pos[0] != i:\n",
    "            return False\n",
    "\n",
    "    # négyzet\n",
    "    box_x = pos[1] // 3\n",
    "    box_y = pos[0] // 3\n",
    "\n",
    "    for i in range(box_y*3, box_y*3 + 3):\n",
    "        for j in range(box_x * 3, box_x*3 + 3):\n",
    "            if bo[i][j] == num and (i,j) != pos:\n",
    "                return False\n",
    " \n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "closed-nature",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 False\n",
      "2 False\n",
      "3 False\n",
      "4 False\n",
      "5 False\n",
      "6 False\n",
      "7 False\n",
      "8 True\n",
      "9 False\n"
     ]
    }
   ],
   "source": [
    "for i in range(1,10):\n",
    "    print(i,valid(board,i,(1,3)))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "accomplished-watch",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Az ötlet, hogy próbáljunk végig mindent. A brute force megoldások sokszor lassúak, viszont néha nincs jobb lehetőség. Mire kell figyelni?\n",
    "- Az összes eseten végig akarunk menni, de azokból túl sok van, hogy mind tároljuk.\n",
    "- Ezért egy sorrendet állítunk föl, és a szerint próbáljuk végig. \n",
    "- Tehát azt kell ügyesen megvalósítani, hogy ha egy adott próbálkozásnál tartunk, abból hogyan lehet a következő próbálkozásra áttérni. \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "inner-withdrawal",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 1. megoldás  \n",
    "def solve(bo):\n",
    "    find = find_empty(bo)\n",
    "    if not find:\n",
    "        return bo\n",
    "    \n",
    "    # lépések listája, éppen mit és hova próbálunk beírni. \n",
    "    listofsteps=[[bo.copy(),1,find]]\n",
    "        \n",
    "    while True:\n",
    "        # éppen hol tartunk\n",
    "        lastboard=listofsteps[-1][0]\n",
    "        lastnum=listofsteps[-1][1]\n",
    "        lastpos=listofsteps[-1][2]\n",
    "        \n",
    "        # ha helyes a próbálkozás, továbblépünk a következő üres mezőre\n",
    "        if valid(lastboard, lastnum,lastpos):\n",
    "            newboard=lastboard.copy()\n",
    "            newboard[ lastpos[0], lastpos[1]]= lastnum\n",
    "            newfind = find_empty(newboard)\n",
    "            if not newfind:\n",
    "                bo[:] =newboard\n",
    "                return True\n",
    "            else:\n",
    "                listofsteps.append([newboard,1,newfind])\n",
    "        elif lastnum<10:\n",
    "            listofsteps[-1][1]=listofsteps[-1][1]+1\n",
    "        else: \n",
    "            # ha beszoroltunk visszalépünk az egyel korábbi pozícióhoz és ott tekinjük a következő számot \n",
    "            del listofsteps[-1]\n",
    "            if len(listofsteps)==0:\n",
    "                return False\n",
    "            else:\n",
    "                listofsteps[-1][1]=listofsteps[-1][1]+1\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "duplicate-prefix",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7 8 0  | 4 0 0  | 1 2 0\n",
      "6 0 0  | 0 7 5  | 0 0 9\n",
      "0 0 0  | 6 0 1  | 0 7 8\n",
      "- - - - - - - - - - - - \n",
      "0 0 7  | 0 4 0  | 2 6 0\n",
      "0 0 1  | 0 5 0  | 9 3 0\n",
      "9 0 4  | 0 6 0  | 0 0 5\n",
      "- - - - - - - - - - - - \n",
      "0 7 0  | 3 0 0  | 0 1 2\n",
      "1 2 0  | 0 0 0  | 4 0 0\n",
      "0 4 9  | 2 0 6  | 0 0 0\n",
      "________________________\n",
      "7 8 5  | 4 3 9  | 1 2 6\n",
      "6 1 2  | 8 7 5  | 3 4 9\n",
      "4 9 3  | 6 2 1  | 5 7 8\n",
      "- - - - - - - - - - - - \n",
      "8 5 7  | 9 4 3  | 2 6 1\n",
      "2 6 1  | 7 5 8  | 9 3 4\n",
      "9 3 4  | 1 6 2  | 7 8 5\n",
      "- - - - - - - - - - - - \n",
      "5 7 8  | 3 9 4  | 6 1 2\n",
      "1 2 6  | 5 8 7  | 4 9 3\n",
      "3 4 9  | 2 1 6  | 8 5 7\n"
     ]
    }
   ],
   "source": [
    "print_board(board)\n",
    "solve(board)\n",
    "print(\"________________________\")\n",
    "print_board(board)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "democratic-anxiety",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Második megoldás, rekurzióval."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "intelligent-guide",
   "metadata": {},
   "outputs": [],
   "source": [
    "board=np.array( [\n",
    "    [0,0,0,0,0,0,1,9,0],\n",
    "    [2,3,0,0,0,0,6,0,0],\n",
    "    [0,0,0,2,4,0,0,0,0],\n",
    "    [0,0,0,0,0,0,9,6,0],\n",
    "    [0,0,0,1,6,0,0,7,0],\n",
    "    [0,4,8,0,7,0,0,0,0],\n",
    "    [0,0,1,0,0,3,4,0,5],\n",
    "    [0,0,9,0,0,8,0,0,0],\n",
    "    [0,0,6,0,0,5,8,0,0]\n",
    "])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "sapphire-tutorial",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 2. megoldás, rekurzió\n",
    "def solve2(bo):\n",
    "    find = find_empty(bo)\n",
    "    if not find:\n",
    "        return True\n",
    "    else:\n",
    "        row, col = find\n",
    "\n",
    "    for i in range(1,10):\n",
    "        if valid(bo, i, (row, col)):\n",
    "            bo[row][col] = i\n",
    "\n",
    "            if solve2(bo):\n",
    "                return True\n",
    "\n",
    "            bo[row][col] = 0\n",
    "\n",
    "    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "talented-indication",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 0 0  | 0 0 0  | 1 9 0\n",
      "2 3 0  | 0 0 0  | 6 0 0\n",
      "0 0 0  | 2 4 0  | 0 0 0\n",
      "- - - - - - - - - - - - \n",
      "0 0 0  | 0 0 0  | 9 6 0\n",
      "0 0 0  | 1 6 0  | 0 7 0\n",
      "0 4 8  | 0 7 0  | 0 0 0\n",
      "- - - - - - - - - - - - \n",
      "0 0 1  | 0 0 3  | 4 0 5\n",
      "0 0 9  | 0 0 8  | 0 0 0\n",
      "0 0 6  | 0 0 5  | 8 0 0\n",
      "________________________\n",
      "8 6 4  | 5 3 7  | 1 9 2\n",
      "2 3 5  | 9 8 1  | 6 4 7\n",
      "9 1 7  | 2 4 6  | 5 8 3\n",
      "- - - - - - - - - - - - \n",
      "1 7 3  | 8 5 2  | 9 6 4\n",
      "5 9 2  | 1 6 4  | 3 7 8\n",
      "6 4 8  | 3 7 9  | 2 5 1\n",
      "- - - - - - - - - - - - \n",
      "7 8 1  | 6 9 3  | 4 2 5\n",
      "3 5 9  | 4 2 8  | 7 1 6\n",
      "4 2 6  | 7 1 5  | 8 3 9\n"
     ]
    }
   ],
   "source": [
    "print_board(board)\n",
    "solve2(board)\n",
    "print(\"________________________\")\n",
    "print_board(board)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "appropriate-authentication",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "\n",
    "<img src=\"https://i.imgur.com/xNNPN0d.jpg\" alt=\"drawing\" width=\"800\"/>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "affecting-birthday",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## Példa 2. Edmonds Karp\n",
    "\n",
    "Adott egy folyamfeladat. Keressünk maximális folyamot benne.  \n",
    "\n",
    "\n",
    "    \n",
    "<img src=\"https://media.geeksforgeeks.org/wp-content/cdn-uploads/ford_fulkerson11.png\" alt=\"drawing\" width=\"800\"/>\n",
    "\n",
    "\n",
    "Ford Fulkerson algoritmusnak az Edmonds Karp verzióját valósítjuk meg. \n",
    "- mindig keresünk egy javító utat, ami mentén tudunk növelni a folyamon\n",
    "- ehhez fenntartunk egy segédgráfot, amit mindig frissítünk\n",
    "- ha van a segédgráfban javító út, akkor a mentén javítunk. Mindig a legrövidebb javító utat válasszuk. \n",
    " \n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "limiting-india",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Iranyitott():\n",
    "    def __init__(self,graph):\n",
    "        self.graph=graph\n",
    "        self.num=len(graph)\n",
    "        \n",
    "    def __str__(self):\n",
    "        return \"\\n\".join([str(x) for x in self.graph])\n",
    "    \n",
    "    def bfs(self, s, t, parent):\n",
    "        visited = [False] * (self.num)\n",
    "        #queue = collections.deque()\n",
    "        queue = []\n",
    "         \n",
    "        # a kezdő csúcsot visitedre állítjuk és a sorba rakjuk \n",
    "        #queue.append(s)\n",
    "        queue.append(s)\n",
    "        visited[s] = True\n",
    "         \n",
    "        # szoksásos BFS bejárás\n",
    "        while queue:\n",
    "            #u = queue.popleft()\n",
    "            u=queue.pop(0)\n",
    "            # nézzük u szomszédait, ha valamelyiken még nem jártunk, mehet a sorba, és visited-re állítjuk\n",
    "            for ind, val in enumerate(self.graph[u]):\n",
    "                if (visited[ind] == False) and (val > 0):\n",
    "                    queue.append(ind)\n",
    "                    visited[ind] = True\n",
    "                    parent[ind] = u\n",
    " \n",
    "        # hal elértünk t-ig akkor igazzal térünk vissza, különben hamis\n",
    "        return visited[t]\n",
    "        \n",
    "    def edmonds_karp(self, source, sink):\n",
    " \n",
    "        # ebben fogjuk tárolni a bfs eredményét\n",
    "        parent = [-1] * (self.num)\n",
    "\n",
    "        max_flow = 0 \n",
    "\n",
    "        # Amíg van javító út \n",
    "        while self.bfs (source, sink, parent):\n",
    "\n",
    "            # megnézzük mennyivel tudunk javítani\n",
    "            path_flow = float(\"Inf\")\n",
    "            s = sink\n",
    "            while s != source:\n",
    "                path_flow = min(path_flow, self.graph[parent[s]][s])\n",
    "                s = parent[s]\n",
    "\n",
    "            # növeljük a folyam értékét\n",
    "            max_flow += path_flow\n",
    "\n",
    "            # a javító út mentén javítunk\n",
    "            v = sink\n",
    "            while v !=  source:\n",
    "                u = parent[v]\n",
    "                self.graph[u][v] -= path_flow\n",
    "                self.graph[v][u] += path_flow\n",
    "                v = parent[v]\n",
    "\n",
    "        return max_flow"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "chubby-stevens",
   "metadata": {},
   "outputs": [],
   "source": [
    "I=Iranyitott( [[0, 16, 13, 0, 0, 0],\n",
    "          [0, 0, 10, 12, 0, 0],\n",
    "          [0, 4, 0, 0, 14, 0],\n",
    "          [0, 0, 9, 0, 0, 20],\n",
    "          [0, 0, 0, 7, 0, 4],\n",
    "          [0, 0, 0, 0, 0, 0]])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "negative-marshall",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 16, 13, 0, 0, 0]\n",
      "[0, 0, 10, 12, 0, 0]\n",
      "[0, 4, 0, 0, 14, 0]\n",
      "[0, 0, 9, 0, 0, 20]\n",
      "[0, 0, 0, 7, 0, 4]\n",
      "[0, 0, 0, 0, 0, 0]\n"
     ]
    }
   ],
   "source": [
    "print(I)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "speaking-walker",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "11"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "I.edmonds_karp(4,5)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "quantitative-lending",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "## Példa 3. Egy feladvány"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "aggressive-defeat",
   "metadata": {},
   "source": [
    "Van egy sakktáblánk, melynek a mezői véletlenszerűen feketére vagy fehérre vannak színezve. Szeretnénk elérni, hogy az összes mező fekete legyen. Egyetlen eszközünk van erre, ha megnyomunk egy mezőt, akkor a sorában és az oszlopában minden mező megváltoztatja a színét. Készítsük egy algoritmust, mely megadja, hogy melyik mezőket kell megnyomni, hogy végül teljesen legyen a tábla. \n",
    "\n",
    "<img src=\"puzzle2.jpg\" alt=\"drawing\" width=\"500\"/>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "accepting-night",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "import itertools as it\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "accurate-bishop",
   "metadata": {},
   "outputs": [],
   "source": [
    "class game:\n",
    "    def __init__(self,b):\n",
    "        self.board=b\n",
    "        self.size=len(b[0])\n",
    "    \n",
    "    def __str__(self):\n",
    "        return \"\\n\".join([str(x) for x in self.board])+\"\\n\"\n",
    "    \n",
    "    def flip(self,pos_x,pos_y):\n",
    "        for x,y in it.product(range(self.size),range(self.size)):\n",
    "            if x==pos_x or y==pos_y:\n",
    "                self.board[x,y]=1-self.board[x,y]\n",
    "    \n",
    "    def bigflip(self,pos_x,pos_y):\n",
    "        for x,y in it.product(range(self.size),range(self.size)):\n",
    "            if x==pos_x or y==pos_y:\n",
    "                self.flip(x,y)\n",
    "                print(self)\n",
    "    \n",
    "    def solve(self):                                ## páros szor páros táblára\n",
    "        for x,y in it.product(range(self.size),range(self.size)):\n",
    "            if self.board[x,y]==0:\n",
    "                self.bigflip(x,y)\n",
    "    \n",
    "    \n",
    "    def solve2(self):                               ## páros szor páros táblára\n",
    "        to_press=[]\n",
    "        column=self.board.sum(axis=0)\n",
    "        row=self.board.sum(axis=1)\n",
    "        print(\"Oszlops és sor összeg:\", column,row)\n",
    "        for x,y in it.product(range(self.size),range(self.size)):\n",
    "            if (column[y]+row[x]+self.board[x,y])%2==0:\n",
    "                to_press.append((x,y))\n",
    "        print(\"Szükséges lépések:\", to_press)\n",
    "        print(self)\n",
    "        for x,y in to_press:\n",
    "            self.flip(x,y)\n",
    "            print(self)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "muslim-boring",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0. 0. 0. 0.]\n",
      "[0. 0. 0. 0.]\n",
      "[0. 0. 0. 0.]\n",
      "[0. 0. 0. 0.]\n",
      "\n",
      "[0. 1. 0. 0.]\n",
      "[1. 1. 1. 1.]\n",
      "[0. 1. 0. 0.]\n",
      "[0. 1. 0. 0.]\n",
      "\n"
     ]
    }
   ],
   "source": [
    "G=game(np.zeros((4, 4)))\n",
    "print(G)\n",
    "G.flip(1,1)\n",
    "print(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "id": "cleared-southwest",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0. 0. 0. 0.]\n",
      "[0. 0. 0. 0.]\n",
      "[0. 0. 0. 0.]\n",
      "[0. 0. 0. 0.]\n",
      "\n",
      "[1. 1. 1. 1.]\n",
      "[0. 1. 0. 0.]\n",
      "[0. 1. 0. 0.]\n",
      "[0. 1. 0. 0.]\n",
      "\n",
      "[0. 1. 1. 1.]\n",
      "[1. 0. 1. 1.]\n",
      "[1. 1. 0. 0.]\n",
      "[1. 1. 0. 0.]\n",
      "\n",
      "[0. 0. 1. 1.]\n",
      "[0. 1. 0. 0.]\n",
      "[1. 0. 0. 0.]\n",
      "[1. 0. 0. 0.]\n",
      "\n",
      "[0. 0. 0. 1.]\n",
      "[1. 0. 1. 1.]\n",
      "[1. 0. 1. 0.]\n",
      "[1. 0. 1. 0.]\n",
      "\n",
      "[0. 0. 0. 0.]\n",
      "[0. 1. 0. 0.]\n",
      "[1. 0. 1. 1.]\n",
      "[1. 0. 1. 1.]\n",
      "\n",
      "[0. 1. 0. 0.]\n",
      "[0. 0. 0. 0.]\n",
      "[0. 1. 0. 0.]\n",
      "[1. 1. 1. 1.]\n",
      "\n",
      "[0. 0. 0. 0.]\n",
      "[0. 1. 0. 0.]\n",
      "[0. 0. 0. 0.]\n",
      "[0. 0. 0. 0.]\n",
      "\n",
      "[0. 0. 0. 0.]\n",
      "[0. 1. 0. 0.]\n",
      "[0. 0. 0. 0.]\n",
      "[0. 0. 0. 0.]\n",
      "\n"
     ]
    }
   ],
   "source": [
    "G=game(np.zeros((4, 4)))\n",
    "print(G)\n",
    "G.bigflip(1,1)\n",
    "print(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "removed-works",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0 0 1 0]\n",
      "[0 0 1 1]\n",
      "[0 1 1 0]\n",
      "[1 0 0 0]\n",
      "\n"
     ]
    }
   ],
   "source": [
    "G=game(np.random.randint(2, size=(4, 4)))\n",
    "print(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "unnecessary-cinema",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1 1 0 0]\n",
      "[1 1 0 0]\n",
      "[1 0 1 0]\n",
      "[1 1 1 0]\n",
      "\n",
      "[0 0 1 1]\n",
      "[1 0 0 0]\n",
      "[1 1 1 0]\n",
      "[1 0 1 0]\n",
      "\n",
      "[1 1 0 0]\n",
      "[1 0 1 0]\n",
      "[1 1 0 0]\n",
      "[1 0 0 0]\n",
      "\n",
      "[0 0 1 1]\n",
      "[1 0 1 1]\n",
      "[1 1 0 1]\n",
      "[1 0 0 1]\n",
      "\n",
      "[1 0 1 1]\n",
      "[0 1 0 0]\n",
      "[0 1 0 1]\n",
      "[0 0 0 1]\n",
      "\n",
      "[0 0 1 1]\n",
      "[1 1 0 0]\n",
      "[1 0 1 0]\n",
      "[1 0 0 1]\n",
      "\n",
      "[1 0 1 1]\n",
      "[0 1 0 0]\n",
      "[0 0 1 0]\n",
      "[0 1 1 0]\n",
      "\n",
      "[0 1 0 0]\n",
      "[1 1 0 0]\n",
      "[1 0 1 0]\n",
      "[1 1 1 0]\n",
      "\n",
      "[1 0 1 1]\n",
      "[1 0 0 0]\n",
      "[1 1 1 0]\n",
      "[1 0 1 0]\n",
      "\n",
      "[0 1 0 0]\n",
      "[1 0 1 0]\n",
      "[1 1 0 0]\n",
      "[1 0 0 0]\n",
      "\n",
      "[1 0 1 1]\n",
      "[1 0 1 1]\n",
      "[1 1 0 1]\n",
      "[1 0 0 1]\n",
      "\n",
      "[1 1 1 1]\n",
      "[0 1 0 0]\n",
      "[1 0 0 1]\n",
      "[1 1 0 1]\n",
      "\n",
      "[1 0 1 1]\n",
      "[0 0 0 0]\n",
      "[0 1 1 0]\n",
      "[1 0 0 1]\n",
      "\n",
      "[1 1 1 1]\n",
      "[0 1 0 0]\n",
      "[0 0 1 0]\n",
      "[0 1 1 0]\n",
      "\n",
      "[0 0 0 0]\n",
      "[1 1 0 0]\n",
      "[1 0 1 0]\n",
      "[1 1 1 0]\n",
      "\n",
      "[1 0 0 0]\n",
      "[0 0 1 1]\n",
      "[0 0 1 0]\n",
      "[0 1 1 0]\n",
      "\n",
      "[1 1 0 0]\n",
      "[1 1 0 0]\n",
      "[0 1 1 0]\n",
      "[0 0 1 0]\n",
      "\n",
      "[1 1 1 0]\n",
      "[0 0 1 1]\n",
      "[0 1 0 0]\n",
      "[0 0 0 0]\n",
      "\n",
      "[1 1 1 1]\n",
      "[1 1 0 0]\n",
      "[0 1 0 1]\n",
      "[0 0 0 1]\n",
      "\n",
      "[0 1 1 1]\n",
      "[0 1 0 0]\n",
      "[1 0 1 0]\n",
      "[1 0 0 1]\n",
      "\n",
      "[1 1 1 1]\n",
      "[1 1 0 0]\n",
      "[0 0 1 0]\n",
      "[0 1 1 0]\n",
      "\n",
      "[0 0 0 0]\n",
      "[1 1 1 0]\n",
      "[0 0 0 0]\n",
      "[0 1 0 0]\n",
      "\n",
      "[1 0 0 0]\n",
      "[0 0 0 1]\n",
      "[1 0 0 0]\n",
      "[1 1 0 0]\n",
      "\n",
      "[1 1 0 0]\n",
      "[1 1 1 0]\n",
      "[1 1 0 0]\n",
      "[1 0 0 0]\n",
      "\n",
      "[1 1 1 0]\n",
      "[0 0 0 1]\n",
      "[1 1 1 0]\n",
      "[1 0 1 0]\n",
      "\n",
      "[1 1 1 1]\n",
      "[1 1 1 0]\n",
      "[1 1 1 1]\n",
      "[1 0 1 1]\n",
      "\n",
      "[1 1 0 1]\n",
      "[1 1 0 0]\n",
      "[0 0 0 0]\n",
      "[1 0 0 1]\n",
      "\n",
      "[1 1 1 1]\n",
      "[1 1 1 0]\n",
      "[0 0 1 0]\n",
      "[0 1 1 0]\n",
      "\n",
      "[0 0 0 0]\n",
      "[1 1 1 1]\n",
      "[0 0 1 1]\n",
      "[0 1 1 1]\n",
      "\n",
      "[1 0 0 0]\n",
      "[0 0 0 0]\n",
      "[1 0 1 1]\n",
      "[1 1 1 1]\n",
      "\n",
      "[1 1 0 0]\n",
      "[1 1 1 1]\n",
      "[1 1 1 1]\n",
      "[1 0 1 1]\n",
      "\n",
      "[1 1 1 0]\n",
      "[0 0 0 0]\n",
      "[1 1 0 1]\n",
      "[1 0 0 1]\n",
      "\n",
      "[1 1 1 1]\n",
      "[1 1 1 1]\n",
      "[1 1 0 0]\n",
      "[1 0 0 0]\n",
      "\n",
      "[1 1 1 0]\n",
      "[1 1 1 0]\n",
      "[0 0 1 1]\n",
      "[1 0 0 1]\n",
      "\n",
      "[1 1 1 1]\n",
      "[1 1 1 1]\n",
      "[0 0 1 0]\n",
      "[0 1 1 0]\n",
      "\n",
      "[0 0 0 0]\n",
      "[0 1 1 1]\n",
      "[1 0 1 0]\n",
      "[1 1 1 0]\n",
      "\n",
      "[1 0 0 0]\n",
      "[1 0 0 0]\n",
      "[0 0 1 0]\n",
      "[0 1 1 0]\n",
      "\n",
      "[0 0 0 0]\n",
      "[0 0 0 0]\n",
      "[1 1 0 1]\n",
      "[1 1 1 0]\n",
      "\n",
      "[0 1 0 0]\n",
      "[0 1 0 0]\n",
      "[0 0 1 0]\n",
      "[1 0 1 0]\n",
      "\n",
      "[0 1 1 0]\n",
      "[0 1 1 0]\n",
      "[1 1 0 1]\n",
      "[1 0 0 0]\n",
      "\n",
      "[0 1 1 1]\n",
      "[0 1 1 1]\n",
      "[0 0 1 0]\n",
      "[1 0 0 1]\n",
      "\n",
      "[1 1 1 1]\n",
      "[1 1 1 1]\n",
      "[1 0 1 0]\n",
      "[0 1 1 0]\n",
      "\n",
      "[0 0 0 0]\n",
      "[1 0 1 1]\n",
      "[1 1 1 0]\n",
      "[0 0 1 0]\n",
      "\n",
      "[0 1 0 0]\n",
      "[0 1 0 0]\n",
      "[1 0 1 0]\n",
      "[0 1 1 0]\n",
      "\n",
      "[1 1 0 0]\n",
      "[1 1 0 0]\n",
      "[0 1 0 1]\n",
      "[1 1 1 0]\n",
      "\n",
      "[1 0 0 0]\n",
      "[1 0 0 0]\n",
      "[1 0 1 0]\n",
      "[1 0 1 0]\n",
      "\n",
      "[1 0 1 0]\n",
      "[1 0 1 0]\n",
      "[0 1 0 1]\n",
      "[1 0 0 0]\n",
      "\n",
      "[1 0 1 1]\n",
      "[1 0 1 1]\n",
      "[1 0 1 0]\n",
      "[1 0 0 1]\n",
      "\n",
      "[1 1 1 1]\n",
      "[1 1 1 1]\n",
      "[1 1 1 0]\n",
      "[0 1 1 0]\n",
      "\n",
      "[0 0 0 0]\n",
      "[1 1 1 0]\n",
      "[1 1 1 1]\n",
      "[0 1 1 1]\n",
      "\n",
      "[0 0 0 1]\n",
      "[0 0 0 1]\n",
      "[1 1 1 0]\n",
      "[0 1 1 0]\n",
      "\n",
      "[1 0 0 1]\n",
      "[1 0 0 1]\n",
      "[0 0 0 1]\n",
      "[1 1 1 0]\n",
      "\n",
      "[1 1 0 1]\n",
      "[1 1 0 1]\n",
      "[1 1 1 0]\n",
      "[1 0 1 0]\n",
      "\n",
      "[1 1 1 1]\n",
      "[1 1 1 1]\n",
      "[0 0 0 1]\n",
      "[1 0 0 0]\n",
      "\n",
      "[1 1 1 0]\n",
      "[1 1 1 0]\n",
      "[1 1 1 0]\n",
      "[1 0 0 1]\n",
      "\n",
      "[1 1 1 1]\n",
      "[1 1 1 1]\n",
      "[1 1 1 1]\n",
      "[0 1 1 0]\n",
      "\n",
      "[0 0 0 0]\n",
      "[0 1 1 1]\n",
      "[0 1 1 1]\n",
      "[1 1 1 0]\n",
      "\n",
      "[1 0 0 0]\n",
      "[1 0 0 0]\n",
      "[1 1 1 1]\n",
      "[0 1 1 0]\n",
      "\n",
      "[0 0 0 0]\n",
      "[0 0 0 0]\n",
      "[0 0 0 0]\n",
      "[1 1 1 0]\n",
      "\n",
      "[1 0 0 0]\n",
      "[1 0 0 0]\n",
      "[1 0 0 0]\n",
      "[0 0 0 1]\n",
      "\n",
      "[1 1 0 0]\n",
      "[1 1 0 0]\n",
      "[1 1 0 0]\n",
      "[1 1 1 0]\n",
      "\n",
      "[1 1 1 0]\n",
      "[1 1 1 0]\n",
      "[1 1 1 0]\n",
      "[0 0 0 1]\n",
      "\n",
      "[1 1 1 1]\n",
      "[1 1 1 1]\n",
      "[1 1 1 1]\n",
      "[1 1 1 0]\n",
      "\n",
      "[0 0 0 0]\n",
      "[1 1 1 0]\n",
      "[1 1 1 0]\n",
      "[1 1 1 1]\n",
      "\n",
      "[0 0 0 1]\n",
      "[0 0 0 1]\n",
      "[1 1 1 1]\n",
      "[1 1 1 0]\n",
      "\n",
      "[0 0 0 0]\n",
      "[0 0 0 0]\n",
      "[0 0 0 0]\n",
      "[1 1 1 1]\n",
      "\n",
      "[1 0 0 0]\n",
      "[1 0 0 0]\n",
      "[1 0 0 0]\n",
      "[0 0 0 0]\n",
      "\n",
      "[1 1 0 0]\n",
      "[1 1 0 0]\n",
      "[1 1 0 0]\n",
      "[1 1 1 1]\n",
      "\n",
      "[1 1 1 0]\n",
      "[1 1 1 0]\n",
      "[1 1 1 0]\n",
      "[0 0 0 0]\n",
      "\n",
      "[1 1 1 1]\n",
      "[1 1 1 1]\n",
      "[1 1 1 1]\n",
      "[1 1 1 1]\n",
      "\n"
     ]
    }
   ],
   "source": [
    "G.solve()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "id": "invisible-traveler",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Oszlops és sor összeg: [2 4 2 1] [1 4 3 1]\n",
      "Szükséges lépések: [(0, 1), (0, 3), (1, 3), (2, 0), (2, 1), (2, 2), (2, 3), (3, 1), (3, 3)]\n",
      "[0 1 0 0]\n",
      "[1 1 1 1]\n",
      "[1 1 1 0]\n",
      "[0 1 0 0]\n",
      "\n",
      "[1 0 1 1]\n",
      "[1 0 1 1]\n",
      "[1 0 1 0]\n",
      "[0 0 0 0]\n",
      "\n",
      "[0 1 0 0]\n",
      "[1 0 1 0]\n",
      "[1 0 1 1]\n",
      "[0 0 0 1]\n",
      "\n",
      "[0 1 0 1]\n",
      "[0 1 0 1]\n",
      "[1 0 1 0]\n",
      "[0 0 0 0]\n",
      "\n",
      "[1 1 0 1]\n",
      "[1 1 0 1]\n",
      "[0 1 0 1]\n",
      "[1 0 0 0]\n",
      "\n",
      "[1 0 0 1]\n",
      "[1 0 0 1]\n",
      "[1 0 1 0]\n",
      "[1 1 0 0]\n",
      "\n",
      "[1 0 1 1]\n",
      "[1 0 1 1]\n",
      "[0 1 0 1]\n",
      "[1 1 1 0]\n",
      "\n",
      "[1 0 1 0]\n",
      "[1 0 1 0]\n",
      "[1 0 1 0]\n",
      "[1 1 1 1]\n",
      "\n",
      "[1 1 1 0]\n",
      "[1 1 1 0]\n",
      "[1 1 1 0]\n",
      "[0 0 0 0]\n",
      "\n",
      "[1 1 1 1]\n",
      "[1 1 1 1]\n",
      "[1 1 1 1]\n",
      "[1 1 1 1]\n",
      "\n"
     ]
    }
   ],
   "source": [
    "G=game(np.random.randint(2, size=(4, 4)))\n",
    "G.solve2()\n"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "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.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}