Beadandó tapasztalatok¶
- Fájl olvasás
with - Hatékony megszámolás egy ciklussal
- Függvények felhasználása
- Sok
ifelkerülése - List comprehension
Gyors megoldás a 4. feladatra¶
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ó¶
In [35]:
import numpy as np
import itertools as it
In [36]:
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]
])
In [37]:
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="")
In [38]:
print_board(board)
In [42]:
# ü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
In [43]:
print_board(board)
print(find_empty(board))
In [46]:
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
In [45]:
for i in range(1,10):
print(i,valid(board,i,(1,3)))
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.
In [48]:
# 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
In [49]:
print_board(board)
solve(board)
print("________________________")
print_board(board)
Második megoldás, rekurzióval.
In [50]:
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]
])
In [51]:
# 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
In [52]:
print_board(board)
solve2(board)
print("________________________")
print_board(board)
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.
In [24]:
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
In [53]:
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]])
In [54]:
print(I)
In [55]:
I.edmonds_karp(4,5)
Out[55]:
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.
In [28]:
import itertools as it
import numpy as np
In [56]:
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)
In [58]:
G=game(np.zeros((4, 4)))
print(G)
G.flip(1,1)
print(G)
In [31]:
G=game(np.zeros((4, 4)))
print(G)
G.bigflip(1,1)
print(G)
In [59]:
G=game(np.random.randint(2, size=(4, 4)))
print(G)
In [60]:
G.solve()
In [61]:
G=game(np.random.randint(2, size=(4, 4)))
G.solve2()