5. Řetězce a seznamy

5.1. Seznamy

Seznam je datová struktura pro uložení více prvků, např. posloupnosti čísel nebo slov ve větě.

Pro práci se seznamy je připraveno několik užitečných funkcí. Dokážete odhadnout, co která dělá?

Pomocí for cyklu můžeme projít všechny prvky seznamu:

Odkazy a kopie

Pokud máme seznam values a provedeme a = values, nevytváří se nová kopie pole, v paměti bude stále jediné, akorát se na něj budou nyní odkazovat 2 proměnné.

(codelens_lists_demo)

Pokud potřebujete kopii pole, použijte příkaz a = list(values).

(codelens_lists_demo2)

Pokud budete někdy vytvářet kopii složitější datové struktury (např. seznamu seznamů), použijte funkci deepcopy z knihovny copy.

Slicing

Slicing je jednoduchý způsob, jak získat nějakou podčást (výřez) seznamu.

5.1.1. Součet, maximum a hledání

Napište funkce nad seznamem čísel, které zjistí:

  • součet všech čísel v seznamu,

  • nejvyšší číslo v seznamu,

  • zda se určitá hodnota vyskytuje v seznamu,

tedy ekvivalenty operací max, sum a in (ale s použitím pouze základních operací nad seznamy).

def my_sum(numbers):
    pass

def my_max(numbers):
    pass

def my_in(x, array):
    pass

def test_sum_max_in():
    assert my_sum([6, 5, 11, 8]) == 30
    assert my_max([6, 5, 11, 8]) == 11
    assert my_max([-10, -3, -5]) == -3
    assert my_in(5, [6, 5, 11, 8]) == True
    assert my_in(4, [6, 5, 11, 8]) == False

5.1.2. Součin nenulových čísel

Napište funkci, která vypočítá součin čísel v seznamu, ale ignoruje přitom případné nuly.

def nonzero_product(numbers):
    pass

def test_nonzero_product():
    assert nonzero_product([0, 2, 3, 0, 0, 3]) == 18
    assert nonzero_product([0, 0, 0, 0]) == 1

5.1.3. Modifikace vs. vytváření nového seznamu

Napište funkci double_all, která dostane na vstupu seznam čísel a každý jeho prvek vynásobí dvěma. Dále napište funkci create_doubled, která dostane na vstupu seznam čísel a vrátí nový seznam získaný ze vstupního tak, že každý prvek vynásobí dvěma. Na rozdíl od předchozí funkce však nemění předaný seznam.

def double_all(numbers):
    pass

def test_double_all():
    a = [1, 4, 2, 5]
    double_all(a)
    assert a == [2, 8, 4, 10]

def create_doubled(numbers):
    pass

def test_create_doubled():
    a = [1, 4, 2, 5]
    b = create_doubled(a)
    assert a == [1, 4, 2, 5]
    assert b == [2, 8, 4, 10]

5.1.4. Zploštění

Napište funkci, jejímž vstupem je seznam seznamů a výstupem je seznam, který obsahuje prvky všech jednotlivých seznamů.

def flatten(lists):
    pass

def test_flatten():
    assert flatten([[0, 2, 3], [1, 2, 3], [9, 10]]) == [0, 2, 3, 1, 2, 3, 9, 10]

5.2. Řetězce

Samotný počítač pracuje s binárními čísly, ale protože my lidé raději pracujeme s desítkovými čísly a ještě raději s písmenky a z něho složeným textem. Postupně tak přibyla do většiny programovacích jazyků možnost jak s písmenky a texty z nich složených pracovat velmi jednoduchým a efektivním způsobem. Python v tomto ohledu není výjimkou a v této sekci se právě tomu, jak se s písmenky pracuje Pythonu budeme věnovat.

Co je to řetězec

Řetězec (= string) je nemodifikovatelná posloupnost po sobě jdoucích znaků (charů), která je datového typu str, například jednou z takových posloupností znaků h, j, o a a může být ahoj.

Jak vytvářet řetězce

Když chceme vytvořit řetězec musíme náš text obalit do mezi " (uvozovek), ‘ (apostrofů) případně """ (trojitých uvozovek), ale poslednímu způsobu se budeme věnovat, protože je oproti těm prvním dvěma speciální.

Vyzkoušejte si

Číslo vs řetězec

Jako lidé je nám celkem jedno jestli je 42 číslo nebo text. Python je ale v tomhle ohledu poněkud striknější, protože potřebuje vědět jak s ním má zacházet.

Intuitivně byste řekli, že 6 je přece 6! Jenže proto, aby mohly být dvě hodnoty sobě rovné, musí nejdřív souhlasit jejich datový typ a to v tomto případě nesouhlasí (str není int). Na toto místo patří ještě poznámka, že ne všechny programovací jazyky se k tomuto staví stejně. Existují programovací jazyky, které vám hodnoty automaticky převedou do nějakého typu, ve kterém se porovnání dá provést… Diskuze o tom, zdali je to moudré jsou vždy vděčným způsobem jak mezi programátory rozpoutat pořádnou flame-war.

A když tedy potřebujete pracovat s číslem jako řetězcem, použijte třeba funkci str(42).

Speciální znaky

S některými znaky v řetězcích musíme zacházet jinak než s ostatními. Například když chceme udělat nový řádek, nemůžeme použít odřádkování pomocí klávesy Enter, ale musíme místo ní napsat sekvenci \n (zpětné lomítko následované znakem n). Znak je \ má uvnitř řetězců speciální význam, říká, že se spolu se znakem po něm má nahradit něčím jiným. Což znamená také znamená, že abychom do řetězce dostali znak \ musíme zadat \\.

Taktéž s uvozovkami a apostrofy můžeme narazit, pokusíme-li se je použít v řetězci, který jako obalovací znaky používá stejný znak. Python by v takovém případě považoval nalezený znak za konec řetězce a vše co následuje za ním za další kód.

Víceřádkové řetězce

Protože je někdy můžeme chtít používat delší řetězce se řadou nových řádků, může být přehlednější obalit náš text pomocí """ (trojích uvozovek), v rámci něhož stačí udělat normální odřádkování pomocí klávesy Enter.

Tenhle postup se též může hodit jako svérázný (a rychlý) způsob zakomentování většího množství řádků, trik spočívá v tom, že řetězec se nikam neuloží, takže se prostě zahodí:

"""
def foo():
    some problematic code
"""

Základní operace s řetězci

Jak jsme si nastínili v úvodu je řetězec posloupnost znaků, očíslovaná od začátku řetězce od 0 (což znamená být že poslední znak je na pozici délky řetězce mínus 1!) a můžeme k nim přistupovat pomocí hranatých závorek. Dalšími základními operacemi je zjištění její délky pomocí funkce len(retezec), jejich zřetězení (konkatenace) pomocí operátoru + a opakování pomocí operátoru *.

Řetězec je ale neměnný, nemůžeme na danou pozici přiřadit žádný nový znak:

Další operace

Může nás též zajímat, zda-li nějaký znak je v řetězci přítomen, k tomu slouží operátor in. Také můžeme nad řetězce iterovat po jednom znaku.

Každé písmeno má přiřazenou svou číselnou reprezentaci, tu můžeme získat pomocí funkce ord(znak), pro opačný směr slouží funkce chr(znak). Další užitečné funkce jsou retezec.upper() a retezec.lower(), které převedou celý řetězec na velká/malá písmena.

Krájení (slicování)

Někdy se může velmi hodit získat pouze nějakou podčást řetězce. K tomu se používá tzv. slicování (krájení). Která funguje, že definujeme od, do a každý kolikátý znak chceme. Pohrajte si:

5.2.1. Prokládání textu textem

Napište funkci, která mezi každá dvě písmena daného textu vloží dodaný text.

def dummy(text, rubbish):
    pass

def test_dummy():
    assert dummy('pampeliska', '') == 'pampeliska'
    assert dummy('pampeliska', 'X') == 'pXaXmXpXeXlXiXsXkXa'
    assert dummy('pampeliska', 'XX') == 'pXXaXXmXXpXXeXXlXXiXXsXXkXXa'

5.2.2. Zdvojení písmen

Napište funkci, která vrátí nový řetězec, ve kterém bylo každé písmenko zdvojeno.

def duplication(text):
    pass

def test_duplication():
    assert duplication("PYTHON") == "PPYYTTHHOONN"

5.2.3. Pozpátku

Napište funkci, která vám vrátí řetězec s písmeny uspořádanými pozpátku.

def reverse(text):
    pass

def test_reverse():
    assert reverse('ONMEJATEJOLSEH') == "HESLOJETAJEMNO"

5.2.4. Cenzura

Napište funkci, která zcenzuruje dodaný řetězec tak, že každý druhý znak nahradí za X.

def censorship(text):
    pass

def test_censorship():
    assert censorship("Vinnetou: Jsem krestan.") == "VXnXeXoX:XJXeX XrXsXaX."

5.2.5. Počet A

Napište funkci, která spočítá počet výskytů písmene (znaku) A/a.

def count_a(text):
    pass

def test_count_a():
    assert count_a('Liska Adelka') == 3

5.2.6. Znaky na stejných pozicích

Napište funkci, která dostane dva řetězce a vypíše ty znaky, které jsou na shodných pozicích stejné.

def string_intersection(left, right):
    pass

string_intersection('ZIRAFA', 'KARAFA')
# R A F A
string_intersection('PES', 'KOCKA')
# (prazdny retezec)

5.2.7. Rozdíl v počtu a

Napište funkci příjimající dva řetězce, která vypíše informaci o tom, který z řetězců obsahuje méně znaků ‘a’/’A’ a jaký je absolutní rozdíl mezi počty ‘a’/’A’ mezi oběma řetězci. Případně vypíše, že je počet áček v obou řetězcích stejný.

def diff_a(left, right):
    pass

diff_a("AstalaVistas", "Jehovista")
# Second string contains less 'a'/'A': 3
diff_a("", "")
# Both strings contain same number of 'a'/'A'

5.2.8. Palindrom

Napište funkci, která vrátí, zda je řetězec palindromem. Palindromem je takové slovo či věta, která má při čtení v libovolném směru stejný význam, například nepotopen či jelenovi pivo nelej (mezery můžete ignorovat).

def palindrom(text):
    pass

def test_palindrom():
    assert palindrom("JELENOVIPIVONELEJ") == True

5.2.9. Hodnota slova

Každý znak A-Z má hodnotu 1-26 (diakritiku a velikost písmen pro tento příklad ignorujte). Napište funkci, která spočítá a vrátí hodnotu vloženého řetězce (slova).

def word_value(text):
    pass

def test_word_value():
    assert word_value("AHOJ") == 34

5.2.10. Divný filtr

Napište funkci, která profiltruje vstupní text následujícím způsobem: sečte hodnoty dvou předchozích písmen (A–Z jsou 1–26, diakritiku a velikost písmen můžete pro tento příklad ignorovat) a pokud bude rovna hodnotě aktuálního písmene, odstraní ho.

Poznámka: pokud písmeno odstraníte už jej nikdy nepoužijete ;-)

def strange_filter(text):
    pass

def test_strange_filter():
    assert strange_filter("ABCDEIGHO") == "ABDEGH"

5.2.11. Kapitalizace slov

Napište funkci pro kapitalizaci všech slov v dodaném vstupním řetězci.

def capitalize(text):
    pass

def test_capitalize():
    assert capitalize("jenom tak klidne levituji ve vzduchu.") == "Jenom Tak Klidne Levituji Ve Vzduchu."

5.2.12. Náhodný řetězec

Napište funkci pro generování náhodných řetězců, která bude brát dva parametry: length udávající délku výstupu a chars obsahující řetězec všech povolených znaků.

from random import randint

def random_string(length, chars):
    pass

print(random_string(10, "ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890"))

5.2.13. Naivní hledání

Napište funkci se dvěma parametry needle (jehla) a haystack (kupka sena) pro hledání začáteční pozice subřetězce. Pokud nebude podřetězec nalezen vrátí funkce -1.

Poznámka: použijte naivní algoritmus… ona existuje spousta chytrých algoritmů na hledání podřetězců, jejichž pochopení a implementace je nad rámec tohoto předmětu.

def search(needle, haystack):
    pass

def test_search():
    assert search("tri", "bratri") == 3

5.3. Šifry a jiné kratochvíle

Od pradávna existovali lidé, kteří potřebovali ukrývat význam zpráv před nechtěnými zraky nepovolaných či přímo nepřátelských lidí. Například historie Caesarovy šifry se táhne až k Juliu Caesarovi a od té doby je v neustálém hledáčku států a bezpečnosti… S nástupem sofistikovaných strojů se objevily různé „neprolomitelné“ šifrovací zařízení. Jedním z klasických je německá Enigma z druhé světové války, jejíž prolomení vedlo k založení informatiky jako vědecké disciplíny a vedlo k dnešním počítačům.

Co je to šifrování

Šifrování je proces, při kterém z nějakého nezašifrovaného textu (plaintextu) pomocí jistého principu (například posunu) a znalosti (hesla, klíče,…) vytvoříme zašifrovaný text. Z tohoto zašifrovaného textu je pak v ideálním případě původní text zjistitelný pouze velmi obtížně či příliš zdlouhavě. Šifrování je velmi komplexní téma a zabývá se jím kryptografie, více se můžete dozvědět například v předmětu PV080.

Proč se budeme zabývat šifrováním

V rámci této podkapitoly se budeme věnovat jednodušším a známým šifrám, protože umí velmi dobře posloužit na procvičení práce s řetězci, seznamy a znaky.

Chcete-li potrápit své mozkové závity u šifer neznámých a třeba využít své nově nabyté programátorské schopnosti poohlédněte se po šifrovačkách, například InterLoS či TMOU.

5.3.1. Caesarova šifra

Napište funkci, která zašifruje text tak, že posune všechna jeho písmena v abecedě o n dopředu (cyklicky), můžete se inspirovat popisem Caesarovy šifry.

def caesar(text, klic):
    pass

def test_caesar():
    assert caesar('zirafa', 3) == "CLUDID"

5.3.2. Vigenèrova šifra

Napište funkci, která zašifruje text podle předem daného klíče. Pro posun písmen zdrojového textu se postupně používají písmena z klíče: ‘a’ posouvá o 0, ‘b’ o 1, … ‘z’ o 25. Pokud je klíč kratší než zdrojový text, jsou použita písmena z klíče opět od začátku. Můžete se inspirovat popisem Vigenèrovy šifry.

def vigenere(text, klic):
    pass

def test_vigenere():
    assert vigenere('pampeliska', 'klic') == "ZLUROWQUUL"

5.3.3. Protřepat, nemíchat

Vytvořte funkci, která bude na vstupu brát text a číslo. Funkce vrátí text kde jednotlivé n-tice budou vždy pozpátku.

def tuple_reverse(text, n):
   pass

def test_tuple_reverse():
    assert tuple_reverse('HESLOJETAJEMNO', 3) == "SEHJOLATEMEJON"
    assert tuple_reverse('SEHJOLATEMEJON', 3) == "HESLOJETAJEMNO"
Next Section - 6. Binární vyhledávání, testování, typy