Motivační ukázka: flašky

Jak rozdělit čtrnáctilitrový demižon vína napůl pomocí kanystru na benzín a sudu od piva? Úloh tohohle ražení se dá najít spousta. Zkusme napsat program, který je zvládne všechny... ačkoliv mu to bude trvat dost dlouho.

Pravidla hry dovolují přelívat víno z jedné nádoby do druhé tak, aby se buďto první vyprázdnila nebo druhá naplnila. Každá nádoba má známý objem a na začátku obsahuje daný obsah vína. Náš program má najít postup, jak se dostat do nějakého cílového stavu (pro každou flašku máme dané množství vína, jaké má na konci obsahovat) a to na co nejmenší počet přelití.

Hloupé ale dostačující řešení je nechat počítač přelívat pro každou (systematicky zvolenou) dvojici flašek a kontrolovat, jestli už nejsme v cílovém stavu. Dlužno podotknout, že pro n flašek je n · (n-1) dvojic a když řešení potřebuje k kroků, bude počítač muset udělat něco jako (n · (n-1))k pokusů. To je dost strašné, ale pro tři flašky a krátká řešení to na obyčejném počítači doběhne.

K řešení s výhodou použijeme rekurzi.

Řešení.
def prelij(objemy, stav, odkud, kam):
	mnozstvi = min(stav[odkud], objemy[kam] - stav[kam])
	vysledek = list(stav)
	vysledek[odkud] -= mnozstvi
	vysledek[kam] += mnozstvi
	return tuple(vysledek)

def reseni(objemy, stav, cil, kroky, nejde_rychleji):
	if stav == cil:
		return [stav]
	elif kroky == 0:
		return False
	for odkud in range(len(stav)):
		for kam in range(len(stav)):
			vysledek = prelij(objemy, stav, odkud, kam)
			if vysledek not in nejde_rychleji or nejde_rychleji[vysledek] <= kroky - 1:
				pokus = reseni(objemy, vysledek, cil, kroky - 1, nejde_rychleji)
				if pokus:
					pokus.append(stav)
					return pokus
				else:
					nejde_rychleji[vysledek] = kroky
	return False

>> reseni((14, 9, 5), (14, 0, 0), (7, 7, 0), 13, dict())[::-1]

Počítání překlepů

Příklad. Napište funkci jde_proskrtat(zdroj, cil), která rozhodne, jestli jde pouhým odebíráním písmen získat z jednoho textu druhý. Základní myšlenkou se inspirujte u programu na přelévání vína.

Nápověda.
def jde_proskrtat(zdroj, cil):
    if zdroj == cil:
        return True
    if not zdroj:
        return False
    for i in range(len(zdroj)):
        # ...tady musite neco doplnit
    return # a tady taky

Příklad. Přepište předchozí funkci tak, aby běžela přijatelně rychle.

Nápověda.
def jde_proskrtat(zdroj, cil):
    if not cil: # pokud je cil prazdny retezec
        return True
    zacatek = zdroj.find(cil[0])
    if zacatek == -1:
        return False
    return # ...tady musite neco doplnit

Příklad. Přepište předchozí funkci bez rekurze.

Nápověda.
def jde_proskrtat(zdroj, cil):
    zacatek = 0
    for znak in cil:
        pozice = zdroj.find(znak, zacatek)
        if # tady musite doplnit podminku i jeji kod
        
        zacatek = pozice
    return # a co tady?

Příklad. Napište funkci jde_doplnit(zdroj, cil), která rozhodne, jestli jde pouhým přidáváním písmen získat z jednoho textu druhý.

Nápověda.
Pracovali jste doteď pečlivě?

Intermezzo: metody str.split, str.join, str.find

Funkce str.split(oddělovač, počet) se nám bude hodit až později ke čtení souborů s bludištěm, tematicky ale zapadá sem. Když ji zavoláme na nějaký řetězec bez parametrů, navrátí seznam jednotlivých slov v původním řetězci, rozdělených podle mezer, řádků a tabulátorů. Jako parametr jí můžeme dát řetězec, který bude sloužit jako oddělovač. Druhý parametr může být číslo, které omezí počet nalezených oddělovačů a zbytek řetězce nechá vcelku.

>>> "nazdar světe jak se vede".split()
['nazdar', 'světe', 'jak', 'se', 'vede']
>>> "nazdar světe jak se vede".split("a")
['n', 'zd', 'r světe j', 'k se vede']
>>> "nazdar světe jak se vede".split("a", 2)
['n', 'zd', 'r světe jak se vede'] # všimněte si, že délka výsledného seznamu je nanejvýš pocet + 1

Příklad. Všimněte si (zkuste), že oddělovač nesmí být prázdný řetězec. Jak z řetězce vyrobíte seznam všech jeho znaků?

Funkce str.join(sekvence) dělá v určitém smyslu pravý opak, spojí řetězce ze sekvence do jednoho. Důležité (a odlišné od většiny programovacích jazyků) je, že se volá na oddělovač; chceme-li řetězce spojit bez oddělovače, zavoláme ji na prázdný řetězec "". Sekvence může být například seznam, a musí obsahovat jen řetězce (ne například čísla).

>>> ["nazdar", "světe", "jak", "se", "vede"].join("... ")
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'list' object has no attribute 'join'
>>> "... ".join(["nazdar", "světe", "jak", "se", "vede"])
'nazdar... světe... jak... se... vede'

Funkce str.find(řetězec) navrací první pozici (index), na které najdeme zadaný řetězec. Když hledáme něco delšího než jedno písmeno, vrací pozici začátku. Když nenajde nic, vrací -1.

>>> "nazdar".find("z")
2
>>> "nazdar"[2]
'z'
>>> "nazdar".find("zdar")
2
>>> "nazdar".find("q")
-1

Důležitá pro nás bude možnost zavolat funkci str.find(řetězec, start) se dvěma parametry. Chová se stejně, ale hledat začíná až od pozice start včetně. Volání s jedním parametrem tedy je totéž, jako bychom dopsali na druhé místo nulu.

Odbočka v intermezzu: příkaz break

Příkazem break vyskočíte z nejbližšího cyklu, který se právě provádí. Funguje na for i na while cykly. Svým způsobem se podobá příkazu return ve funkci, ale nemůže nic navracet.

Podobný příkaz je continue, který se chová podobně, ale cyklus nezastaví; jen přeskočí na další otočku, na další prvek sekvence.

Ukázka.
>>> for znak in "toto je ex-papoušek":
...     if znak == " ":
...             continue
...     if znak == "-":
...             break
...     print(znak)
... 
t
o
t
o
j
e
e
x

Příklad. Některé programovací jazyky nabízejí cyklus s podmínkou na konci (známý jako do...while), který podobně jako while cyklus běží, dokud je podmínka splněná, ale ta podmínka se vyhodnocuje až na konci. Cyklus proto vždy proběhne aspoň jednou. Rozmyslete si, jako něco podobného napsat v Pythonu pomocí while cyklu a příkazu break, a jaké jsou jiné možnosti.

Konec odbočky v intermezzu.

Příklad. Napište funkci split(text, oddělovač), která navrátí totéž jako text.split(oddělovač) (ale samozřejmě aniž byste tuhle zabudovanou funkci použili).

Asi budete muset napsat while cyklus, kterým projdete všechny postupně všechny výskyty oddělovače v textu. Ten se vám bude hodit i v následujícím příkladu.

Nápověda.
def split(text, znak):
    vysledek = list()
    pozice = 0
    while 1:
        dalsi = text.find(znak, pozice)
        if # něco
            break
        vysledek.append # něco
        pozice = # něco
    vysledek.append # něco
    return vysledek

Počítání překlepů znova a doopravdy

Příklad. Napište funkci pocet_preklepu(zdroj, cil), která spočítá, jaký nejmenší počet písmen je potřeba ubrat a přidat, abychom získali z řetězce zdroj řetězec cil. Podrobněji nás ty úpravy nezajímají, stačí počet.

Všimněte si, že tentokrát nějaké řešení vždycky existuje: můžeme všechno smazat a pak to napsat načisto. Pokud oba řetězce nemají žádná společná písmena, bude to i nejlepší řešení, ale takové případy nás při počítání překlepů moc nezajímají.

Abyste získali přijatelně rychlé řešení, vyjděte z následující úvahy: poslední písmeno řetězce zdroj buďto musíme smazat, nebo ho najdeme někde v řetězci cil a pak musíme smazat všechno za ním. V obou případech nám z řetězce zdroj zbude nějaká kratší část a na tu můžeme zavolat rekurzi. Když je zdroj prázdný, nezbývá než dopsat všechna písmena řetězce cil. Ze všech možností vybírejte tu s nejméně chybami a nepřehlédněte, že "najdeme někde" v tomto odstavci znamená vyzkoušet cyklem všechny výskyty.

Nápověda.
def pocet_preklepu(zdroj, cil):
    if not zdroj:
        return len(cil)
    min_pocet = pocet_preklepu(zdroj[?], cil) + 1
    pozice = -1
    while 1:
        pozice = cil.find(zdroj[?], pozice + 1)
        if pozice == -1:
            break
        pocet = pocet_preklepu(zdroj[?], cil[?]) + len(cil) - (?)
        if pocet < min_pocet:
            min_pocet = pocet
    return min_pocet

Příklad. Přepište předchozí funkci bez použití rekurze.

Budete si potřebovat uchovávat předpočítané výsledky volání té funkce pro nějaké části obou řetězců. Nejrozumnější mi přijde pamatovat si výsledky pro nějaký prefix řetězce zdroj a všechny prefix řetězce cil, pak můžete spočítat hodnoty pro prefix řetězce zdroj o písmeno delší. Prefix znamená začátek řetězce, v Pythonu psáno řetězec[:něco]. V kódu z předchozího příkladu vlastně stačí nahradit volání funkce čtením ze seznamu a výsledky si opatrně ukládat do jiného seznamu. A napsat dva vnořené cykly.

Zpět k poníkům

Zbylé dva příklady s poníky jsou na původní stránce z minula. Jako první probereme editor mapy, pak se dáme do zabíjení.