Matematikai Algoritmusok és Felfedezések I.

12. Előadás: Algoritmikus gondolkodás

2021 május 3.

Beadandó tapasztalatok

• Fájl olvasás with
• Hatékony megszámolás egy ciklussal
• Függvények felhasználása
• Sok if elkerülése
• List comprehension

lassú megoldás a 3. feladatra

drb_szotar={}
for i in hun_alph:
    darab = 0
    for j in range(len(szoveg)):
        if szoveg[j] == i:                    
            darab = darab + 1
    drb_szotar[i] = darab

gyors megoldás

char_freq = {}
for char in szoveg:
    if char in char_freq:
        char_freq[char] += 1
    else:
        char_freq[char] = 1

Programkészítés menete

• Feladat értelmezése
• Tervezés
• Implementálás
• Tesztelés
• Valamit elrontottunk, vissza egy korábbi ponthoz!

Tervezés

• Adatszerkezet kitalálása. Milyen adatokat fogok tárolni? Hogyan érdemes őket tárolni?
• Milyen műveletekre lesz szükségem? Azokat hogyan lehet algoritmussal megvalósítani?
• Mennyire számít a sebesség? Ha számít, akkor hogyan érhetem el, hogy gyors legyen?
• Mennyire pontos eredményt szeretnék?
• Objektum orientáltan csináljam vagy procedurálisan, esetleg funkcionálisan?
• Hogyan lehet ezeket objektum orientáltan megoldani? Milyen osztályokat érdemes elkészíteni?

Implementálás és tesztelés

• Apró lépésekben érdemes dolgozni. Kb mindig legyen működő a program.
• Ne feledjük el, hogy rengeteg mindent már megírtak, érdemes ezt kihasználni.
• Érdemes kommentekkel ellátni a kódot, és beszédes változóneveket használni, hogy pár nap múlva is érthető legyen.
• Minden lényegesebb lépés után teszteljünk.
• Általában az implementálás, a tesztelés és a hibajavítás gyorsan váltogatja egymást.

"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/)

Példa 1. Sodoku megoldó

import numpy as np
import itertools as it

board=np.array( [
    [7,8,0,4,0,0,1,2,0],
    [6,0,0,0,7,5,0,0,9],
    [0,0,0,6,0,1,0,7,8],
    [0,0,7,0,4,0,2,6,0],
    [0,0,1,0,5,0,9,3,0],
    [9,0,4,0,6,0,0,0,5],
    [0,7,0,3,0,0,0,1,2],
    [1,2,0,0,0,0,4,0,0],
    [0,4,9,2,0,6,0,0,0]
])

def print_board(bo):
    for i in range(len(bo)):
        if i % 3 == 0 and i != 0:
            print("- - - - - - - - - - - - ")

        for j in range(len(bo[0])):
            if j % 3 == 0 and j != 0:
                print(" | ", end="")

            if j == 8:
                print(bo[i][j])
            else:
                print(str(bo[i][j]) + " ", end="")

print_board(board)

7 8 0  | 4 0 0  | 1 2 0
6 0 0  | 0 7 5  | 0 0 9
0 0 0  | 6 0 1  | 0 7 8
- - - - - - - - - - - - 
0 0 7  | 0 4 0  | 2 6 0
0 0 1  | 0 5 0  | 9 3 0
9 0 4  | 0 6 0  | 0 0 5
- - - - - - - - - - - - 
0 7 0  | 3 0 0  | 0 1 2
1 2 0  | 0 0 0  | 4 0 0
0 4 9  | 2 0 6  | 0 0 0

# üres mező keresése
def find_empty(bo):
    for i,j in it.product(range(len(bo)),range(len(bo[0]))):
        if bo[i][j] == 0:
            return (i, j)   

    return None

print_board(board)
print(find_empty(board))

7 8 0  | 4 0 0  | 1 2 0
6 0 0  | 0 7 5  | 0 0 9
0 0 0  | 6 0 1  | 0 7 8
- - - - - - - - - - - - 
0 0 7  | 0 4 0  | 2 6 0
0 0 1  | 0 5 0  | 9 3 0
9 0 4  | 0 6 0  | 0 0 5
- - - - - - - - - - - - 
0 7 0  | 3 0 0  | 0 1 2
1 2 0  | 0 0 0  | 4 0 0
0 4 9  | 2 0 6  | 0 0 0
(0, 2)

def valid(bo, num, pos):
    #1-től 9-ig
    if num not in range(1,10):
        return False
    
    if bo[pos[0],pos[1]]!=0:
        return False
    
    # sor
    for i in range(len(bo[0])):
        if bo[pos[0]][i] == num and pos[1] != i:
            return False

    # oszlop
    for i in range(len(bo)):
        if bo[i][pos[1]] == num and pos[0] != i:
            return False

    # négyzet
    box_x = pos[1] // 3
    box_y = pos[0] // 3

    for i in range(box_y*3, box_y*3 + 3):
        for j in range(box_x * 3, box_x*3 + 3):
            if bo[i][j] == num and (i,j) != pos:
                return False
 
    return True

for i in range(1,10):
    print(i,valid(board,i,(1,3)))

1 False
2 False
3 False
4 False
5 False
6 False
7 False
8 True
9 False

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?

• Az összes eseten végig akarunk menni, de azokból túl sok van, hogy mind tároljuk.
• Ezért egy sorrendet állítunk föl, és a szerint próbáljuk végig.
• 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.

# 1. megoldás  
def solve(bo):
    find = find_empty(bo)
    if not find:
        return bo
    
    # lépések listája, éppen mit és hova próbálunk beírni. 
    listofsteps=[[bo.copy(),1,find]]
        
    while True:
        # éppen hol tartunk
        lastboard=listofsteps[-1][0]
        lastnum=listofsteps[-1][1]
        lastpos=listofsteps[-1][2]
        
        # ha helyes a próbálkozás, továbblépünk a következő üres mezőre
        if valid(lastboard, lastnum,lastpos):
            newboard=lastboard.copy()
            newboard[ lastpos[0], lastpos[1]]= lastnum
            newfind = find_empty(newboard)
            if not newfind:
                bo[:] =newboard
                return True
            else:
                listofsteps.append([newboard,1,newfind])
        elif lastnum<10:
            listofsteps[-1][1]=listofsteps[-1][1]+1
        else: 
            # ha beszoroltunk visszalépünk az egyel korábbi pozícióhoz és ott tekinjük a következő számot 
            del listofsteps[-1]
            if len(listofsteps)==0:
                return False
            else:
                listofsteps[-1][1]=listofsteps[-1][1]+1
                    

print_board(board)
solve(board)
print("________________________")
print_board(board)

7 8 0  | 4 0 0  | 1 2 0
6 0 0  | 0 7 5  | 0 0 9
0 0 0  | 6 0 1  | 0 7 8
- - - - - - - - - - - - 
0 0 7  | 0 4 0  | 2 6 0
0 0 1  | 0 5 0  | 9 3 0
9 0 4  | 0 6 0  | 0 0 5
- - - - - - - - - - - - 
0 7 0  | 3 0 0  | 0 1 2
1 2 0  | 0 0 0  | 4 0 0
0 4 9  | 2 0 6  | 0 0 0
________________________
7 8 5  | 4 3 9  | 1 2 6
6 1 2  | 8 7 5  | 3 4 9
4 9 3  | 6 2 1  | 5 7 8
- - - - - - - - - - - - 
8 5 7  | 9 4 3  | 2 6 1
2 6 1  | 7 5 8  | 9 3 4
9 3 4  | 1 6 2  | 7 8 5
- - - - - - - - - - - - 
5 7 8  | 3 9 4  | 6 1 2
1 2 6  | 5 8 7  | 4 9 3
3 4 9  | 2 1 6  | 8 5 7

Második megoldás, rekurzióval.

board=np.array( [
    [0,0,0,0,0,0,1,9,0],
    [2,3,0,0,0,0,6,0,0],
    [0,0,0,2,4,0,0,0,0],
    [0,0,0,0,0,0,9,6,0],
    [0,0,0,1,6,0,0,7,0],
    [0,4,8,0,7,0,0,0,0],
    [0,0,1,0,0,3,4,0,5],
    [0,0,9,0,0,8,0,0,0],
    [0,0,6,0,0,5,8,0,0]
])

# 2. megoldás, rekurzió
def solve2(bo):
    find = find_empty(bo)
    if not find:
        return True
    else:
        row, col = find

    for i in range(1,10):
        if valid(bo, i, (row, col)):
            bo[row][col] = i

            if solve2(bo):
                return True

            bo[row][col] = 0

    return False

print_board(board)
solve2(board)
print("________________________")
print_board(board)

0 0 0  | 0 0 0  | 1 9 0
2 3 0  | 0 0 0  | 6 0 0
0 0 0  | 2 4 0  | 0 0 0
- - - - - - - - - - - - 
0 0 0  | 0 0 0  | 9 6 0
0 0 0  | 1 6 0  | 0 7 0
0 4 8  | 0 7 0  | 0 0 0
- - - - - - - - - - - - 
0 0 1  | 0 0 3  | 4 0 5
0 0 9  | 0 0 8  | 0 0 0
0 0 6  | 0 0 5  | 8 0 0
________________________
8 6 4  | 5 3 7  | 1 9 2
2 3 5  | 9 8 1  | 6 4 7
9 1 7  | 2 4 6  | 5 8 3
- - - - - - - - - - - - 
1 7 3  | 8 5 2  | 9 6 4
5 9 2  | 1 6 4  | 3 7 8
6 4 8  | 3 7 9  | 2 5 1
- - - - - - - - - - - - 
7 8 1  | 6 9 3  | 4 2 5
3 5 9  | 4 2 8  | 7 1 6
4 2 6  | 7 1 5  | 8 3 9

Példa 2. Edmonds Karp

Adott egy folyamfeladat. Keressünk maximális folyamot benne.

Ford Fulkerson algoritmusnak az Edmonds Karp verzióját valósítjuk meg.

• mindig keresünk egy javító utat, ami mentén tudunk növelni a folyamon
• ehhez fenntartunk egy segédgráfot, amit mindig frissítünk
• ha van a segédgráfban javító út, akkor a mentén javítunk. Mindig a legrövidebb javító utat válasszuk.

class Iranyitott():
    def __init__(self,graph):
        self.graph=graph
        self.num=len(graph)
        
    def __str__(self):
        return "\n".join([str(x) for x in self.graph])
    
    def bfs(self, s, t, parent):
        visited = [False] * (self.num)
        #queue = collections.deque()
        queue = []
         
        # a kezdő csúcsot visitedre állítjuk és a sorba rakjuk 
        #queue.append(s)
        queue.append(s)
        visited[s] = True
         
        # szoksásos BFS bejárás
        while queue:
            #u = queue.popleft()
            u=queue.pop(0)
            # nézzük u szomszédait, ha valamelyiken még nem jártunk, mehet a sorba, és visited-re állítjuk
            for ind, val in enumerate(self.graph[u]):
                if (visited[ind] == False) and (val > 0):
                    queue.append(ind)
                    visited[ind] = True
                    parent[ind] = u
 
        # hal elértünk t-ig akkor igazzal térünk vissza, különben hamis
        return visited[t]
        
    def edmonds_karp(self, source, sink):
 
        # ebben fogjuk tárolni a bfs eredményét
        parent = [-1] * (self.num)

        max_flow = 0 

        # Amíg van javító út 
        while self.bfs (source, sink, parent):

            # megnézzük mennyivel tudunk javítani
            path_flow = float("Inf")
            s = sink
            while s != source:
                path_flow = min(path_flow, self.graph[parent[s]][s])
                s = parent[s]

            # növeljük a folyam értékét
            max_flow += path_flow

            # a javító út mentén javítunk
            v = sink
            while v !=  source:
                u = parent[v]
                self.graph[u][v] -= path_flow
                self.graph[v][u] += path_flow
                v = parent[v]

        return max_flow

I=Iranyitott( [[0, 16, 13, 0, 0, 0],
          [0, 0, 10, 12, 0, 0],
          [0, 4, 0, 0, 14, 0],
          [0, 0, 9, 0, 0, 20],
          [0, 0, 0, 7, 0, 4],
          [0, 0, 0, 0, 0, 0]])

print(I)

[0, 16, 13, 0, 0, 0]
[0, 0, 10, 12, 0, 0]
[0, 4, 0, 0, 14, 0]
[0, 0, 9, 0, 0, 20]
[0, 0, 0, 7, 0, 4]
[0, 0, 0, 0, 0, 0]

I.edmonds_karp(4,5)

11

Példa 3. Egy feladvány

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.

import itertools as it
import numpy as np

class game:
    def __init__(self,b):
        self.board=b
        self.size=len(b[0])
    
    def __str__(self):
        return "\n".join([str(x) for x in self.board])+"\n"
    
    def flip(self,pos_x,pos_y):
        for x,y in it.product(range(self.size),range(self.size)):
            if x==pos_x or y==pos_y:
                self.board[x,y]=1-self.board[x,y]
    
    def bigflip(self,pos_x,pos_y):
        for x,y in it.product(range(self.size),range(self.size)):
            if x==pos_x or y==pos_y:
                self.flip(x,y)
                print(self)
    
    def solve(self):                                ## páros szor páros táblára
        for x,y in it.product(range(self.size),range(self.size)):
            if self.board[x,y]==0:
                self.bigflip(x,y)
    
    
    def solve2(self):                               ## páros szor páros táblára
        to_press=[]
        column=self.board.sum(axis=0)
        row=self.board.sum(axis=1)
        print("Oszlops és sor összeg:", column,row)
        for x,y in it.product(range(self.size),range(self.size)):
            if (column[y]+row[x]+self.board[x,y])%2==0:
                to_press.append((x,y))
        print("Szükséges lépések:", to_press)
        print(self)
        for x,y in to_press:
            self.flip(x,y)
            print(self)
        

G=game(np.zeros((4, 4)))
print(G)
G.flip(1,1)
print(G)

[0. 0. 0. 0.]
[0. 0. 0. 0.]
[0. 0. 0. 0.]
[0. 0. 0. 0.]

[0. 1. 0. 0.]
[1. 1. 1. 1.]
[0. 1. 0. 0.]
[0. 1. 0. 0.]

G=game(np.zeros((4, 4)))
print(G)
G.bigflip(1,1)
print(G)

[0. 0. 0. 0.]
[0. 0. 0. 0.]
[0. 0. 0. 0.]
[0. 0. 0. 0.]

[1. 1. 1. 1.]
[0. 1. 0. 0.]
[0. 1. 0. 0.]
[0. 1. 0. 0.]

[0. 1. 1. 1.]
[1. 0. 1. 1.]
[1. 1. 0. 0.]
[1. 1. 0. 0.]

[0. 0. 1. 1.]
[0. 1. 0. 0.]
[1. 0. 0. 0.]
[1. 0. 0. 0.]

[0. 0. 0. 1.]
[1. 0. 1. 1.]
[1. 0. 1. 0.]
[1. 0. 1. 0.]

[0. 0. 0. 0.]
[0. 1. 0. 0.]
[1. 0. 1. 1.]
[1. 0. 1. 1.]

[0. 1. 0. 0.]
[0. 0. 0. 0.]
[0. 1. 0. 0.]
[1. 1. 1. 1.]

[0. 0. 0. 0.]
[0. 1. 0. 0.]
[0. 0. 0. 0.]
[0. 0. 0. 0.]

[0. 0. 0. 0.]
[0. 1. 0. 0.]
[0. 0. 0. 0.]
[0. 0. 0. 0.]

G=game(np.random.randint(2, size=(4, 4)))
print(G)

[0 0 1 0]
[0 0 1 1]
[0 1 1 0]
[1 0 0 0]

G.solve()

[1 1 0 0]
[1 1 0 0]
[1 0 1 0]
[1 1 1 0]

[0 0 1 1]
[1 0 0 0]
[1 1 1 0]
[1 0 1 0]

[1 1 0 0]
[1 0 1 0]
[1 1 0 0]
[1 0 0 0]

[0 0 1 1]
[1 0 1 1]
[1 1 0 1]
[1 0 0 1]

[1 0 1 1]
[0 1 0 0]
[0 1 0 1]
[0 0 0 1]

[0 0 1 1]
[1 1 0 0]
[1 0 1 0]
[1 0 0 1]

[1 0 1 1]
[0 1 0 0]
[0 0 1 0]
[0 1 1 0]

[0 1 0 0]
[1 1 0 0]
[1 0 1 0]
[1 1 1 0]

[1 0 1 1]
[1 0 0 0]
[1 1 1 0]
[1 0 1 0]

[0 1 0 0]
[1 0 1 0]
[1 1 0 0]
[1 0 0 0]

[1 0 1 1]
[1 0 1 1]
[1 1 0 1]
[1 0 0 1]

[1 1 1 1]
[0 1 0 0]
[1 0 0 1]
[1 1 0 1]

[1 0 1 1]
[0 0 0 0]
[0 1 1 0]
[1 0 0 1]

[1 1 1 1]
[0 1 0 0]
[0 0 1 0]
[0 1 1 0]

[0 0 0 0]
[1 1 0 0]
[1 0 1 0]
[1 1 1 0]

[1 0 0 0]
[0 0 1 1]
[0 0 1 0]
[0 1 1 0]

[1 1 0 0]
[1 1 0 0]
[0 1 1 0]
[0 0 1 0]

[1 1 1 0]
[0 0 1 1]
[0 1 0 0]
[0 0 0 0]

[1 1 1 1]
[1 1 0 0]
[0 1 0 1]
[0 0 0 1]

[0 1 1 1]
[0 1 0 0]
[1 0 1 0]
[1 0 0 1]

[1 1 1 1]
[1 1 0 0]
[0 0 1 0]
[0 1 1 0]

[0 0 0 0]
[1 1 1 0]
[0 0 0 0]
[0 1 0 0]

[1 0 0 0]
[0 0 0 1]
[1 0 0 0]
[1 1 0 0]

[1 1 0 0]
[1 1 1 0]
[1 1 0 0]
[1 0 0 0]

[1 1 1 0]
[0 0 0 1]
[1 1 1 0]
[1 0 1 0]

[1 1 1 1]
[1 1 1 0]
[1 1 1 1]
[1 0 1 1]

[1 1 0 1]
[1 1 0 0]
[0 0 0 0]
[1 0 0 1]

[1 1 1 1]
[1 1 1 0]
[0 0 1 0]
[0 1 1 0]

[0 0 0 0]
[1 1 1 1]
[0 0 1 1]
[0 1 1 1]

[1 0 0 0]
[0 0 0 0]
[1 0 1 1]
[1 1 1 1]

[1 1 0 0]
[1 1 1 1]
[1 1 1 1]
[1 0 1 1]

[1 1 1 0]
[0 0 0 0]
[1 1 0 1]
[1 0 0 1]

[1 1 1 1]
[1 1 1 1]
[1 1 0 0]
[1 0 0 0]

[1 1 1 0]
[1 1 1 0]
[0 0 1 1]
[1 0 0 1]

[1 1 1 1]
[1 1 1 1]
[0 0 1 0]
[0 1 1 0]

[0 0 0 0]
[0 1 1 1]
[1 0 1 0]
[1 1 1 0]

[1 0 0 0]
[1 0 0 0]
[0 0 1 0]
[0 1 1 0]

[0 0 0 0]
[0 0 0 0]
[1 1 0 1]
[1 1 1 0]

[0 1 0 0]
[0 1 0 0]
[0 0 1 0]
[1 0 1 0]

[0 1 1 0]
[0 1 1 0]
[1 1 0 1]
[1 0 0 0]

[0 1 1 1]
[0 1 1 1]
[0 0 1 0]
[1 0 0 1]

[1 1 1 1]
[1 1 1 1]
[1 0 1 0]
[0 1 1 0]

[0 0 0 0]
[1 0 1 1]
[1 1 1 0]
[0 0 1 0]

[0 1 0 0]
[0 1 0 0]
[1 0 1 0]
[0 1 1 0]

[1 1 0 0]
[1 1 0 0]
[0 1 0 1]
[1 1 1 0]

[1 0 0 0]
[1 0 0 0]
[1 0 1 0]
[1 0 1 0]

[1 0 1 0]
[1 0 1 0]
[0 1 0 1]
[1 0 0 0]

[1 0 1 1]
[1 0 1 1]
[1 0 1 0]
[1 0 0 1]

[1 1 1 1]
[1 1 1 1]
[1 1 1 0]
[0 1 1 0]

[0 0 0 0]
[1 1 1 0]
[1 1 1 1]
[0 1 1 1]

[0 0 0 1]
[0 0 0 1]
[1 1 1 0]
[0 1 1 0]

[1 0 0 1]
[1 0 0 1]
[0 0 0 1]
[1 1 1 0]

[1 1 0 1]
[1 1 0 1]
[1 1 1 0]
[1 0 1 0]

[1 1 1 1]
[1 1 1 1]
[0 0 0 1]
[1 0 0 0]

[1 1 1 0]
[1 1 1 0]
[1 1 1 0]
[1 0 0 1]

[1 1 1 1]
[1 1 1 1]
[1 1 1 1]
[0 1 1 0]

[0 0 0 0]
[0 1 1 1]
[0 1 1 1]
[1 1 1 0]

[1 0 0 0]
[1 0 0 0]
[1 1 1 1]
[0 1 1 0]

[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[1 1 1 0]

[1 0 0 0]
[1 0 0 0]
[1 0 0 0]
[0 0 0 1]

[1 1 0 0]
[1 1 0 0]
[1 1 0 0]
[1 1 1 0]

[1 1 1 0]
[1 1 1 0]
[1 1 1 0]
[0 0 0 1]

[1 1 1 1]
[1 1 1 1]
[1 1 1 1]
[1 1 1 0]

[0 0 0 0]
[1 1 1 0]
[1 1 1 0]
[1 1 1 1]

[0 0 0 1]
[0 0 0 1]
[1 1 1 1]
[1 1 1 0]

[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[1 1 1 1]

[1 0 0 0]
[1 0 0 0]
[1 0 0 0]
[0 0 0 0]

[1 1 0 0]
[1 1 0 0]
[1 1 0 0]
[1 1 1 1]

[1 1 1 0]
[1 1 1 0]
[1 1 1 0]
[0 0 0 0]

[1 1 1 1]
[1 1 1 1]
[1 1 1 1]
[1 1 1 1]

G=game(np.random.randint(2, size=(4, 4)))
G.solve2()

Oszlops és sor összeg: [2 4 2 1] [1 4 3 1]
Szükséges lépések: [(0, 1), (0, 3), (1, 3), (2, 0), (2, 1), (2, 2), (2, 3), (3, 1), (3, 3)]
[0 1 0 0]
[1 1 1 1]
[1 1 1 0]
[0 1 0 0]

[1 0 1 1]
[1 0 1 1]
[1 0 1 0]
[0 0 0 0]

[0 1 0 0]
[1 0 1 0]
[1 0 1 1]
[0 0 0 1]

[0 1 0 1]
[0 1 0 1]
[1 0 1 0]
[0 0 0 0]

[1 1 0 1]
[1 1 0 1]
[0 1 0 1]
[1 0 0 0]

[1 0 0 1]
[1 0 0 1]
[1 0 1 0]
[1 1 0 0]

[1 0 1 1]
[1 0 1 1]
[0 1 0 1]
[1 1 1 0]

[1 0 1 0]
[1 0 1 0]
[1 0 1 0]
[1 1 1 1]

[1 1 1 0]
[1 1 1 0]
[1 1 1 0]
[0 0 0 0]

[1 1 1 1]
[1 1 1 1]
[1 1 1 1]
[1 1 1 1]