Jak řešit praktickou open-data úlohu

V tomto textu se Ti pokusíme vysvětlit, jak řešit open-datovou úlohu. Odsuď budeme předpokládat, že máš základní znalost Pythonu.

Celý postup si ukážeme na úloze 34-Z1-1 Letopočty. V ní máme spočítat počet dní, které uběhnou mezi dvěma letopočty. Nicméně jsme na jiné planetě, kde rok má 42 dní, každý 3. rok je přestupný (má 43 dní), jenže každý 48. rok přestupný není.

Odevzdávátko

Praktické úlohy se odevzdávají v odevzdávátku.

Nejprve si vygeneruješ vstup, který si z odevzdávátka stáhneš. Potom si na svém počítači vyrobíš (jakýmkoliv způsobem) odpovídající výstup. Ten potom do odevzdávátka nahraješ zpátky a my ho obodujeme. Vstupy jsou v drtivé většině případů textové soubory, které můžeš otevřít ve svém editoru.

Všimni si, že nemusíš k vyřešení úlohy psát program. První vstup lze obvykle vyřešit ručně. Zato další už jsou velké, aby se tohle dělat nedalo. Takže na ně je zapotřebí napsat nějaký program.

Danger! Pokud preferuješ odevzdávat programy v příkazové řádce, koukni se na KSP klienta. Ten je však spíš určen pro zkušenější řešitele, prozatím jej můžeš přeskočit, stejně jako další sekce označené symbolem nebezpečné sumy.

Vymýšlení řešení

Dříve, než se pustíš do programování úlohy, hodí se mít zhruba rozmyšlené, jak vůbec by měl program fungovat. Na řešení ukázkové úlohy můžeme zvolit následující postup:

Budeme procházet roky mezi zadanými letopočty. Pro každý rok spočteme, jestli je přestupný nebo ne, a podle toho přičteme počet dní do součtu:


soucet = 0
for rok in range(start, konec+1):
    if rok % 3 == 0 and rok % 48 != 0:
        soucet += 43  # Je přestupný rok
    else:
        soucet += 42  # Není přestupný rok
print(soucet)

Vstup a výstup

Teď máme program, který úlohu řeší, a vstup, který máme vyřešit. Pojďme naučit náš program vstup načíst.

Obecně jsou dva způsoby, jak načítat vstup: čtení ze standardního vstupu a čtení ze souboru.

Čtení ze standardního vstupu

O něco jednodušší a častější způsob je čtení ze standardního vstupu. V Pythonu se používá funkce input() a print() na načítání a vypisování textu:


print("Jak se jmenuješ?")
jmeno = input()  # Načti řádek vstupu
print("Ahoj " + jmeno + "!")

Když umístíš vstup do adresáře vedle programu, tak můžeš program spouštět takto:

python Program.py < 01.in > 01.out
Get-Content 01.in | python Program.py > 01.out

Výstup tvého programu skončí v souboru 01.out a ten můžeš odevzdat.

Čtení ze souboru

Čtení ze souboru naopak nevyžaduje moc práce s terminálem, zato je trochu složitější v programu:


with open("01.in") as vstup:
    with open("01.out") as vystup:
        data = vstup.readline()
        vystup.write("Na prvním řádku se nachází: " + data)

Zpět k problému

A jak bude vypadat program pro každý způsob čtení?

Čtení ze standardního vstupu:


pocet = int(input())
for i in range(pocet):
    cisla = input().split()
    start = int(cisla[0])
    konec = int(cisla[1])

    soucet = 0
    for rok in range(start, konec+1):
        if rok % 3 == 0 and rok % 48 != 0:
            soucet += 43  # Je přestupný rok
        else:
            soucet += 42  # Není přestupný rok
    print(soucet)

A ze souboru:


with open("01.in") as vstup:
    with open("01.out") as vystup:
        pocet = int(vstup.readline())
        for i in range(pocet):
            cisla = vstup.readline().split()
            start = int(cisla[0])
            konec = int(cisla[1])

            soucet = 0
            for rok in range(start, konec+1):
                if rok % 3 == 0 and rok % 48 != 0:
                    soucet += 43  # Je přestupný rok
                else:
                    soucet += 42  # Není přestupný rok
            vystup.write(str(soucet) + '\n')

Nyní stačí program spustit na vstupy a odevzdat výstupy. Za každý správně vyřešený vstup dostaneš body.

Debuggování

Občas se ale v programech může vyskytnout nějaká chyba. U některých chyb je oprava zřejmá, ale jindy je to mnohem složitější. Co v takovém případě dělat?

Prvním krokem je najít vstup, na kterém program selže (ať už spadne na kdovíjakou výjimku, vydá špatný výsledek, nebo nedoběhne vůbec). Když program selže již na ukázkovém vstupu, máme docela štěstí, známe správný výsledek a můžeme přistoupit k hledání chyby. Ukázkový vstup navíc bývá dostatečně malý na to, aby jej šlo odladit ručně.

Jinak se hodí napsat si své vlastní vstupy a zkusit je všechny. A jindy je zapotřebí se zamyslet nad tím, kdy by program mohl selhat.

Danger! Když ani zamyšlení nepomáhá, existuje jiný, byť pracný způsob, jak najít hledaný vstup. Nejdřív napíšeme generátor, který nám vygeneruje spoustu malých vstupů. Potom si pořídíme řešení, které je zaručeně správné, třeba za cenu toho, že jej najdeme pomalejším programem. Nyní opakovaně pouštíme obě řešení na vstupy a hledáme, kde se liší výstupy.

Metody debuggování

Výpisy

Nejjednodušší a spolehlivou metodou je průběžně si vypisovat mezivýsledky programu. Podle nich se dá najít, kdy a kde nastala chyba.

Krokování (Interaktivní debuggování)

Obdobně se dá debuggovat krokováním, kdy spouštíme program po částech, měníme mu proměnné za běhu, atd. Mnohá vývojářská prostředí tuto možnost nabízí.

Gumová kachnička

Spolehlivým (byť pro někoho nečekaným) způsobem je odříkat gumové kachničce, co se v programu děje (postačí ale i jakýkoliv plyšák). Často si při vysvětlování člověk uvědomí, že vlastně dělá úplně něco jiného.

Přestávka

A pokud už nic nepomáhá, někdy je nejvyšší čas na pauzu. Pustit se do něčeho jiného a vrátit se s čistou hlavou a nově načerpanou energií.

Napiš nám

Pokud si i tak nevíš rady, napiš nám na zdrojaky@ksp.mff.cuni.cz. Pošli nám:

Před termínem série Ti můžeme pomoct jen trochu, po termínu Ti pomůžeme i s velkými chybami a vymýšlením algoritmu.

Rychlost programů

Odevzdávátko má časový limit na každý vstup, do kterého ho musíš vyřešit. Většinou to bývá 5 minut.

Občas jsou programy ale moc pomalé. Někdy je to způsobené chybou v programu, jindy program má moc velkou složitost.

Cvičení: Vymyslete rychlejší řešení úlohy s Letopočty.

Návod pro vás připravil

Daniel Skýpala