Rekurze, práce se soubory, bitmapová grafika - IB111 Základy … · 2019-12-05 ·...

REKURZE, PRÁCE SE SOUBORY, BITMAPOVÁ GRAFIKAIB111 ZÁKLADY PROGRAMOVÁNÍ

Nikola Beneš28. listopadu 2019

PROGRAM, KTERÝ VYPÍŠE SÁM SEBE

• bez podvádění• program nesmí být prázdný• žádné čtení souborů

template = """template = {0}{1}{0}

print(template.format('{0}', template))"""

print(template.format('"""', template))

• jiné varianty (bez format) v souborech quine2, quine3

1

sym = "\\\","ind = " "lines = [ "sym = ", "ind = ", "lines = [", "]", "print(lines[0] + sym[1] + sym[0] * 2 + sym + sym[1])", "print(lines[1] + sym[1] + ind + sym[1])", "print(lines[2])", "for line in lines:", " print(ind + sym[1] + line + sym[1] + sym[2])", "for line in lines[3:]:", " print(line)",]print(lines[0] + sym[1] + sym[0] * 2 + sym + sym[1])print(lines[1] + sym[1] + ind + sym[1])print(lines[2])for line in lines: print(ind + sym[1] + line + sym[1] + sym[2])for line in lines[3:]: print(line)

def quoted(text: str) -> str: return '"' + text + '"'

texts = [ "def quoted(text: str) -> str:", " return '", "' + text + '", "'", "texts = [", "]", "", "print(texts[0])", "print(texts[1] + quoted(texts[2]) + texts[3])", "print()", "print()", "print(texts[4])", "for line in texts:", " print(' ' + quoted(line) + ',')", "for line in texts[5:]:", " print(line)",]

print(texts[0])print(texts[1] + quoted(texts[2]) + texts[3])print()print()print(texts[4])for line in texts: print(' ' + quoted(line) + ',')for line in texts[5:]: print(line)

template = """template = {0}{1}{0}

print(template.format('{0}', template))"""

print(template.format('"""', template))

V ČEM JE PROBLÉM?

def maybe_get_pair() -> Optional[Tuple[int, int]]:return 0, 0

if maybe_get_pair() is not None:row, col = maybe_get_pair()

• zkuste spustit mypy; co se stane?• mypy neví, že dvě různá volání funkce vrátí stejný výsledek• a ani to obecně nemůže vědět

2

from typing import Optional, Tuple

def maybe_get_pair() -> Optional[Tuple[int, int]]: return 0, 0

if maybe_get_pair() is not None: row, col = maybe_get_pair()

JSOU TYTO FUNKCE EKVIVALENTNÍ?

def fun1():if answer() == 42:

print(answer())

def fun2():result = answer()if result == 42:

print(result)

• obecně NE!• funkce answer může mít vedlejší efekty a při různých voláníchmůže vracet různé hodnoty

• random• input• globální proměnné• aktuální čas (datetime)• čtení ze souboru, komunikace po síti, …

3

def answer(): # try adding some side effects here return 42

def fun1(): if answer() == 42: print(answer())

def fun2(): result = answer() if result == 42: print(result)

JEŠTĚ K REKURZI

Problém dam

• Jak umístit N dam na šachovnici o rozměrech N × N tak, aby sevzájemně neohrožovaly?

80Z0Z0L0Z7ZQZ0Z0Z060Z0Z0ZQZ5L0Z0Z0Z040Z0L0Z0Z3Z0Z0Z0ZQ20Z0ZQZ0Z1Z0L0Z0Z0

a b c d e f g h 4

PROBLÉM DAM

• problém splnění omezení (constraint satisfaction problem)

Naivní řešení

• vyzkoušíme všechna možná rozmístění N dam na šachovnici• pokud najdeme takové, kde se dámy vzájemně neohrožují,skončíme

Lepší řešení

• budujeme si situaci na šachovnici postupně• novou dámu na šachovnici přidáme, pokud se vzájemněneohrožuje s žádnými už umístěnými dámami

• pokud už nemáme žádnou možnost, jak pokračovat, vrátíme seo něco zpět a zkusíme jinou cestu (backtracking)

Hrr na ně, a když to nepude, tož cófnem.5

PROBLÉM DAM

Důležitá pozorování:

• v každém sloupci a každém řádku musí stát právě jedna dáma• můžeme tedy situaci budovat např. po řádcích• jak reprezentovat šachovnici?

• 2D matice• seznam pozic všech dam• pro každý řádek si pamatovat sloupec, na kterém je dáma

• jak poznat, že nově přidáváná dáma někoho ohrožuje?• číslo sloupce už je použito (kontrola sloupců)• jak poznat diagonály?

6

PROBLÉM DAM – DIAGONÁLY

80Z0Z0Z0Z7Z0Z0Z0Z060Z0Z0Z0Z5Z0Z0Z0Z040Z0Z0Z0Z3Z0Z0Z0Z020Z0Z0Z0Z1Z0Z0Z0Z0

a b c d e f g h

Kdy jsou dámy se souřadnicemi (𝑥1, 𝑦1) a (𝑥2, 𝑦2) na stejnédiagonále? Právě tehdy, když |𝑥1 − 𝑥2| = |𝑦1 − 𝑦2|.

7

PROBLÉM DAM – DIAGONÁLY

def queen_check(state: List[int], new_col: int) -> bool:new_row = len(state)for row, col in enumerate(state):

if col == new_col or \abs(row - new_row) == abs(col - new_col):return False

return True

• state je seznam už umístěných dam• new_col je sloupec, kam chceme nově umístit dámu

8

from typing import Optional, List

def queens(size: int) -> Optional[List[int]]: return queens_recursive([], size)

def queens_recursive(state: List[int], size: int) \ -> Optional[List[int]]: if len(state) == size: # solution! return state

for column in range(size): if queen_check(state, column): state.append(column) result = queens_recursive(state, size) if result is not None: return result state.pop()

return None

def queen_check(state: List[int], new_col: int) -> bool: new_row = len(state) for row, col in enumerate(state): if col == new_col or \ abs(row - new_row) == abs(col - new_col): return False return True

def draw_chessboard(state: List[int], size: int) -> None: start, empty, queen = "|", " |", " Q |" for row in range(size): draw_line(size) if row < len(state): col = state[row] print(start + empty * col + queen + empty * (size - col - 1)) else: print(start + empty * size)

draw_line(size)

def draw_line(size: int) -> None: print("+" + "---+" * size)

PROBLÉM DAM – REKURZE

def queens_recursive(state: List[int], size: int) \-> Optional[List[int]]:

if len(state) == size:# solution!return state

for column in range(size):if queen_check(state, column):

state.append(column)result = queens_recursive(state, size)if result is not None:

return resultstate.pop()

return None9





return None



draw_line(size)


PROBLÉM DAM – HLAVNÍ FUNKCE

def queens(size: int) -> Optional[List[int]]:return queens_recursive([], size)

Námět k dalšímu rozšíření:

• spočítat/vrátit všechna řešení

Problémy, které se dají řešit podobným způsobem:

• sudoku• různé jiné logické hádanky• optimální strategie ve hrách dvou hráčů• optimalizační problémy (plánování, rozvrhování)• …

(některé se dají řešit „chytřeji“ než backtrackingem)

10





return None



draw_line(size)


PRÁCE SE SOUBORY

MOTIVACE

Chceme zpracovávat data

• jakou mají podobu?• text, čísla, strukturovaná data, obrázky, …

• jak jsou reprezentována?• tabulka (xls, ods, csv, …)• dokument (doc, odt, md, html, …)• čistý text• …

11

PRÁCE SE SOUBORY V PYTHONU

Obecné schéma

• otevření souboru• práce se souborem (čtení / zápis)• zavření souboru

my_file = open("/tmp/my_file", "w")my_file.write("’Twas brillig, and the slithy toves\n")my_file.write("Did gyre and gimble in the wabe;\n")my_file.write("All mimsy were the borogoves,\n")my_file.write("And the mome raths outgrabe.\n")my_file.close()

12


my_file = open("/tmp/my_file", "r")for line in my_file: print(line)my_file.close()

with open("/tmp/my_file", "r") as my_file: lines = my_file.readlines()

print(lines)

OTEVŘENÍ SOUBORU

• open(name, mode)• jméno souboru: řetězec (pozor na Windows a '\\')• způsob otevření:

• čtení ("r") – implicitní, pokud neuvedeme nic• zápis ("w") – přepíše soubor, pokud není, vytvoří jej• přidání na konec ("a")• čtení i zápis ("r+", "w+" nebo "a+")• binární režim (přidat "b" k některému způsobu)

• tyto módy otevření souboru se používají i v jiných jazycích

13

PRÁCE SE SOUBORY

Čtení ze souboru

• f.read(pocet) – přečte daný počet znaků• f.read() – přečte celý soubor, vrací řetězec• f.readline() – přečte celý jeden řádek• f.readlines() – přečte všechny řádky, vrací seznam řádků

Zápis do souboru

• f.write(text) – zapíše řetězec do souboru• neukončuje řádky, je třeba explicitně použít '\n'

Jiné

• f.tell() – aktuální pozice v souboru• f.seek(pozice) – přesun pozice v souboru

14

PRÁCE SE SOUBORY V PYTHONU

Iterace po řádcích

for line in my_file:print(line)

Speciální blok with

• při jeho použití není třeba soubor zavírat• zavře se sám při ukončení bloku

with open("/tmp/my_file", "r") as my_file:lines = my_file.readlines()

print(lines)

• with má obecnější použití (správa zdrojů a jejich úklid pomocítzv. manažerů kontextu – mimo záběr předmětu)

15


my_file = open("/tmp/my_file", "r")for line in my_file: print(line)my_file.close()

with open("/tmp/my_file", "r") as my_file: lines = my_file.readlines()

print(lines)

ZÁKLADNÍ PRÁCE S ŘETĚZCI (PŘIPOMENUTÍ)

text.strip() # odstraní bílé znaky z krajůtext.lstrip() # totéž, jen ze začátkutext.rstrip() # totéž, jen z koncetext.strip("ABC") # odstraní zadané znaky

text.split() # vytvoří seznam jednotlivých slovtext.split(", ") # dělí podle zadaného řetězcetext.split(":", maxsplit=n) # jen daný počet rozdělení

text.replace(x, y) # nahradí všechny výskyty x -> y

text.find(s) # index výskytu s nebo -1s in text # True/False, jestli text obsahuje s

16

SPECIÁLNÍ ZNAKY

• uvádějí se znakem zpětného lomítka \

"\n" # konec řádku"\"" # jedna uvozovka'\'' # jeden apostrof"\t" # tabulátor"\\" # jedno zpětné lomítko

https://docs.python.org/3/reference/lexical_analysis.html#strings

• co když chceme tuto vlastnost zpětného lomítka „vypnout“?• raw string: přidání r nebo R před řetězec

r"dvě zpětná lomítka: \\"r'žádné speciální znaky \n \t'

17

https://docs.python.org/3/reference/lexical_analysis.html#strings

PŘÍKLAD: ČETNOST JMEN

• zajímají nás nejčastější jména narozených ve vybraném roce• zdroj dat: http://www.mvcr.cz (2016)

• původní formát XLS, převedeno do CSV (uložit jako…)• první řádek je hlavička tabulky• na dalších řádcích je vždy jméno a četnosti podle let

• jak řešit?• zjistíme si, který sloupec nás zajímá• vyčteme z něj četnost• seřadíme jména podle četnosti• vypíšeme deset nejčastějších

18

http://www.mvcr.cz

PŘÍKLAD: ČETNOST JMEN

with open("cetnost-jmena.csv") as f:data = f.readline().split(",")col = data.index(year)for line in f:

data = line.split(",")name = data[0].capitalize()count = int(data[col])if count > 0 and name != "Součet":

freq[name] = count

19

# frequency of given names

year = input("Zadej rok: ")freq = {}

with open("cetnost-jmena.csv") as f: data = f.readline().split(",") col = data.index(year) for line in f: data = line.split(",") name = data[0].capitalize() count = int(data[col]) if count > 0 and name != "Součet": freq[name] = count

freq_sorted = sorted(freq.items(), key=lambda x: (x[1], x[0]), reverse=True)

print("Deset nejčastějších jmen narozených v roce {}:".format(year))for name, count in freq_sorted[:10]: print("{:7d} {}".format(count, name))

PRÁCE S BITMAPOVÝMI OBRÁZKY

KNIHOVNA PILLOW

Pillow: https://pillow.readthedocs.io/

• práce s bitmapovými obrázky (různých formátů)• bohatá funkcionalita

from PIL import Image

• objekt Image reprezentuje obrázek• vytvoření obrázku:

• Image.new – nový prázdný obrázek• Image.open – ze zadaného souboru

• základní operace• getpixel – zjištění barvy pixelu• putpixel – nastavení barvy pixelu• size, width, height – velikost obrázku• show, save – zobrazení, uložení• convert – změna formátu

20

https://pillow.readthedocs.io/

VYTVÁŘENÍ BITMAPOVÝCH OBRÁZKŮ

Příklad: Geometrické útvary

• čtverec• kruh• spirála• elipsa

def square(image, left, top, size):for x in range(left, left + size):

for y in range(top, top + size):image.putpixel((x, y), (255, 0, 0))

21


def square(image, left, top, size): for x in range(left, left + size): for y in range(top, top + size): image.putpixel((x, y), (255, 0, 0))

def circle(image, cx, cy, r, pixel): for x in range(cx - r, cx + r + 1): for y in range(cy - r, cy + r + 1): if (cx - x) ** 2 + (cy - y) ** 2 < r ** 2: image.putpixel((x, y), pixel)

def invert_circle(image, cx, cy, r): for x in range(cx - r, cx + r + 1): for y in range(cy - r, cy + r + 1): if (cx - x) ** 2 + (cy - y) ** 2 < r ** 2: pr, pg, pb = image.getpixel((x, y)) image.putpixel((x, y), (255 - pr, 255 - pg, 255 - pb))

if __name__ == '__main__': image = Image.new("RGB", (800, 600), (255, 255, 255)) # square(image, 100, 100, 200) # square(image, 150, 150, 200) # circle(image, 100, 100, 70, (255, 0, 0)) # circle(image, 120, 120, 50, (0, 255, 0)) # invert_circle(image, 150, 150, 100) # image.show() # image.save("image.png")

TRANSFORMACE BITMAPOVÝCH OBRÁZKŮ

Příklad: Transformace barev

• invertování barev• odstranění barev• změna odstínu (nápověda: HSV)

def invert_colours(image):for y in range(image.height):

for x in range(image.width):r, g, b = image.getpixel((x, y))image.putpixel((x, y),

(255 - r, 255 - g, 255 - b))

22


def remove_red(image): for y in range(image.height): for x in range(image.width): r, g, b = image.getpixel((x, y)) image.putpixel((x, y), (0, g, b))

def invert_colours(image): for y in range(image.height): for x in range(image.width): r, g, b = image.getpixel((x, y)) image.putpixel((x, y), (255 - r, 255 - g, 255 - b))

def modified_hue(image, shift): new_image = image.convert("HSV") for y in range(new_image.height): for x in range(new_image.width): h, s, v = new_image.getpixel((x, y)) new_image.putpixel((x, y), ((h + shift) % 256, s, v))

return new_image

if __name__ == '__main__': # supply your own image file here # the convert("RGB") method call is not needed if the picture is in RGB image = Image.open("image.jpg").convert("RGB") # remove_red(image) # invert_colours(image) # image.show() # new_image = modified_hue(image, 20) # new_image.show()

TRANSFORMACE BITMAPOVÝCH OBRÁZKŮ

Příklad: Transformace struktury

• převrácení• zrcadlení• rozostření

def flip(image):new_image = Image.new("RGB", image.size)width, height = image.sizefor y in range(height):

for x in range(width):new_image.putpixel(

(width - 1 - x, y),image.getpixel((x, y)))

return new_image

23


def flip(image): new_image = Image.new("RGB", image.size) width, height = image.size

for y in range(height): for x in range(width): new_image.putpixel( (width - 1 - x, y), image.getpixel((x, y)))

return new_image

def mirror(image): for y in range(image.height): for x in range(image.width // 2): image.putpixel( (image.width - 1 - x, y), image.getpixel((x, y)))

if __name__ == '__main__': # supply your own image file here # the convert("RGB") method call is not needed if the picture is in RGB image = Image.open("image.jpg").convert("RGB") # new_image = flip(image) # mirror(new_image) # new_image.show()

BONUS: REGULÁRNÍ VÝRAZY

REGULÁRNÍ VÝRAZY – MOTIVACE

• hledání nebo zpracování nějak strukturovaných dat• e-mailové adresy• telefonní čísla• webové odkazy• náhrada „Jméno Příjmení“ za „Příjmení, Jméno“• změna formátu data (20. 11. 2017 → 2017-11-20)• odstranění znaků určitého druhu• data v netradičním formátu, která vyžadují předzpracování

• dá se řešit s dosavadními nástroji• funkce s řetězci• procházení řetězců po znacích

• ale může to být obtížně napsatelné

24

REGULÁRNÍ VÝRAZY – MOTIVACE

Arnold Schwarzenegger se narodil 30. 7. 1947.Madonna se narodila 16. srpna 1958.Ludwig van Beethoven se narodil 16. 12. 1770.

• chceme z těchto dat vyčíst, kdy má kdo narozeniny• víme, že data mají následující strukturu:

• „jméno se narodil(a) den měsíc rok.“• jméno je libovolná (neprázdná) posloupnost znaků• den je číslo ukončené tečkou• měsíc je buď číslo ukončené tečkou nebo jedno slovo• rok je číslo

.+ se narodila? [0-9]+\. ([0-9]+\.|\w+) [0-9]+\.

• toto je tzv. regulární výraz

25

REGULÁRNÍ VÝRAZY

Kde se s nimi setkáme?

• programovací jazyky• zejména tzv. skriptovací jazyky• ale dnes už ve všech moderních jazycích

• (chytřejší) textové editory• (chytřejší souborové manažery)• nástroje příkazové řádky (sed, grep, …)

• teorie: formální jazyky, konečné automaty

26

REGULÁRNÍ VÝRAZY

• způsob, jak popisovat vzory v textu• obecně používaný nástroj• základní syntax stejná nebo velmi podobná ve většinějazyků/prostředí

• kde si je vzykoušet?• https://regex101.com/• https://pythex.org/• a mnohé další, hledejte „python regex online“

• pro soutěživé: https://alf.nu/RegexGolf

27

https://regex101.com/https://pythex.org/https://alf.nu/RegexGolf

REGULÁRNÍ VÝRAZY – STRUČNĚ

• základní znaky popisují samy sebe• hranaté závorky – rozsah možných znaků [abc], [a-z]

• ^ je negace [^abc]• . – libovolný jeden znak• ^ – začátek řetězce• $ – konec řetězce• (, ) – závorkování, vytvoření skupiny• | – alternativa (nebo)• opakování

• * – nula nebo více opakování předešlé části výrazu• + – jedno nebo více opakování předešlé části výrazu• ? – nula nebo jeden výskyt předešlé části výrazu• {m,n} – m až n opakování předešlé části výrazu (lze i {n})

• speicální znaky ztratí svou funkci, když před ně dáme \

28

REGULÁRNÍ VÝRAZY V PYTHONU

• knihovna re (import re)• re.match hledá výskyt na začátku řetězce• re.search hledá výskyt kdekoli v řetězci• re.findall hledá všechny výskyty v řetězci• re.sub nahradí výskyty regulárního výrazu zadaným řetězcem• (re.compile – předkompiluje regulární výraz pro většíefektivitu)

• využijeme „raw string“ – r'regulární výraz', abynedocházelo k interpretaci speciálních znaků (zejména \)

29


• match/search vrací speciální objekt (nebo None)• přístup k jednotlivým skupinám pomocí metody group• informace o tom, kde začínají a končí jednotlivé skupiny pomocímetod start a end, příp. span

m = re.match(r'(\w+) (\w+)', "Isaac Newton, fyzik")if m is not None:

print(m.group(0))print(m.group(1))print(m.group(2))print(m.start(1), m.end(1))print(m.span(2))

30

import re

m = re.match(r'(\w+) (\w+)', "Isaac Newton, fyzik")if m is not None: print(m.group(0)) print(m.group(1)) print(m.group(2)) print(m.start(1), m.end(1)) print(m.span(2))

print(re.sub(r'(\w+) (\w+)', r'\2, \1', "Isaac Newton"))

print(re.search(r'(\w+) \1', "Same word word twice"))


• zpětné reference \1 apod.• odkazují se na předchozí uzávorkované skupiny

• použití při substitucích:


• použití při vyhledavání:• (z teoretického hlediska tohle není regulární)


31

import re

m = re.match(r'(\w+) (\w+)', "Isaac Newton, fyzik")if m is not None: print(m.group(0)) print(m.group(1)) print(m.group(2)) print(m.start(1), m.end(1)) print(m.span(2))



PŘÍKLAD: HROMADNÉ PŘEJMENOVÁNÍ SOUBORŮ

• máme soubory se jmény něco1.txt až něco117.txt• chceme je přejmenovat tak, aby se pěkně řadily podle čísla

• použijeme tvar něco0001.txt• jak přejmenovat všechny?

• pomůže nám knihovna os:• os.listdir() nám vrátí seznam souborů v adresáři• os.rename() přejmenuje soubor

32

import osimport re

for filename in os.listdir(): m = re.match(r'něco(\d+)\.txt$', filename) if m is not None: start, end = m.span(1) new_name = "{}{:04d}{}".format(filename[:start], int(m.group(1)), filename[end:]) os.rename(filename, new_name)

Práce se souboryPráce s bitmapovými obrázkyBonus: Regulární výrazy

Date post:	27-Feb-2020
Category:	Documents
Upload:	others
View:	1 times
Download:	0 times

Rekurze, práce se soubory, bitmapová grafika - IB111 Základy … · 2019-12-05 ·...

Documents