PALMA junior
Úloha o automatizovanej farme

Autorské riešenie
[stiahni riasy1.py, riasy2.py, riasy3.py]

• Počet riešiteľov: 26 / 33 = 79 %

• Úspešnosť riešenia: 5,67 / 7 = 81 %

Kým sa pustíme do programovania, pozrime sa poriadne na to, čo o riešenom probléme vieme.

Pestujeme riasy, ktoré sú v boxoch. Boxy sú usporiadané do obdĺžnikovej oblasti.

Nejakú časť boxov ráno zalejeme:

• zaliať môžeme konkrétny riadok, stĺpec, vybranú obdĺžnikovú oblasť alebo nič,

• do boxu pri jeho zalievaní pritečie 1 liter vody,

• kapacita boxu je 5 litrov, nadbytočná voda odtečie.

Voda z boxov sa odparuje:

• v priebehu dňa sa z boxu odparí 1 liter vody,

• ak sa z boxu odparí všetka voda, riasa definitívne zahynie a systém zablokuje ďalší prítok vody.

Na začiatku poznáme stav vody v boxoch a plán zalievania. Úlohou je zistiť, aký bude stav po poslednom zaliatí a následnom odparení vody.

Poznáme štruktúru dát, ktoré popisujú stav vody v boxoch aj štruktúru dát, ktoré popisujú plán zalievania. Celú simuláciu zmien stavu by sme mohli rozdeliť na nasledovné kroky:

postupne vyberaj inštrukcie na zalievanie

1. podľa typu inštrukcie (riadok, stĺpec, oblasť, nič) zalej zodpovedajúcu časť boxov

   • do zalievaného boxu pritečie najviac 1 liter vody.

   • množstvo vody nesmie prekročiť 5 litrov

   • ak v nejakom boxe je 0 litrov, zalievanie nič nezmení, riasa uhynula,

   •  0 teda môžeme chápať aj ako informáciu, že riasa uhynula.

2. simuluj vyparovanie každého z boxov

   • ak v boxe bolo 0 litrov, nemá sa čo odpariť

Pre realizáciu jednotlivých častí si môžeme vytvoriť samostatné funkcie. Výsledný program môže vyzerať nasledovne: 

#riasy1.py
def zalej_riadok(riadok, stav):
    pocet_stlpcov = len(stav[0])
    for stlpec in range(pocet_stlpcov):
        if stav[riadok][stlpec] > 0:
            stav[riadok][stlpec] = min(stav[riadok][stlpec] + 1, 5)


def zalej_stlpec(stlpec, stav):
    pocet_riadkov = len(stav)
    for riadok in range(pocet_riadkov):
        if stav[riadok][stlpec] > 0:
            stav[riadok][stlpec] = min(stav[riadok][stlpec] + 1, 5)


def zalej_oblast(start_riadok, start_stlpec, pocet_riadkov, pocet_stlpcov, stav):
    for riadok in range(start_riadok, start_riadok + pocet_riadkov):
        for stlpec in range(start_stlpec, start_stlpec + pocet_stlpcov):
            if stav[riadok][stlpec] > 0:
                stav[riadok][stlpec] = min(stav[riadok][stlpec] + 1, 5)


def odpar_vodu(stav):
    pocet_riadkov = len(stav)
    pocet_stlpcov = len(stav[0])
    for riadok in range(pocet_riadkov):
        for stlpec in range(pocet_stlpcov):
            stav[riadok][stlpec] = max(stav[riadok][stlpec] - 1, 0)


def simuluj_pestovanie(stav, plan):
    for zaznam in plan:
        if zaznam:
            if zaznam[0] == 'riadok':
                zalej_riadok(zaznam[1], stav)
            elif zaznam[0] == 'stlpec':
                zalej_stlpec(zaznam[1], stav)
            else:
                zalej_oblast(zaznam[0], zaznam[1], zaznam[2], zaznam[3], stav)
        odpar_vodu(stav)

Všimnime si niektoré časti riešenia:

• Pre zalievanie sme si vytvorili funkcie: zalej_riadok, zalej_stlpec a zalej_oblast. Každá z nich dostane údaje pre identifikáciu menenej časti a samotný stav boxov. Zoznam je meniteľná štruktúra, funkcie zmenený stav nemusia vracať. Inak povedané, každá z nich pracuje s tým istým zoznamom. Pri aktualizácii testujeme, či už riasa nevyschla a ak áno, už ju nezalievame (0 je zároveň informácia, že riasa vyschla). Ak by sme zaliatím boxu prekročili úroveň 5 litrov, výsledná hodnota bude 5 litrov.

• Pre simuláciu odparovania sme si vytvorili funkciu odpar_vodu. Ak by malo množstvo vody klesnúť pod 0, necháme ho na hodnote 0.

• Vo funkcii simuluj_pestovanie prázdne inštrukcie prechádzame "bez povšimnutia". Aj keď sa v daný deň nezaleje žiadna oblasť, voda sa z boxov odparovať môže.

Máme síce funkčné riešenie, ale možno stojí za to zamyslieť sa, či ho vieme nejako vylepšiť. Ak sa pozrieme na funkcie pre zalievanie, tak zistíme, že robia to isté, i keď každá na inej časti farmy.

Riadok môžeme chápať ako obdĺžnikovú oblasť, ktorá má len jeden riadok. Podobne aj na stĺpec sa môžeme pozrieť ako na obdĺžnikovú oblasť len s jedným stĺpcom. Mala by nám teda stačiť len jedna funkcia: zalej_oblast. Pozrime sa na riešenie, v ktorom riadky aj stĺpce chápeme ako oblasti: 

#riasy2.py
def zalej_oblast(start_riadok, start_stlpec, pocet_riadkov, pocet_stlpcov, stav):
    for riadok in range(start_riadok, start_riadok + pocet_riadkov):
        for stlpec in range(start_stlpec, start_stlpec + pocet_stlpcov):
            if stav[riadok][stlpec] > 0:
                stav[riadok][stlpec] = min(stav[riadok][stlpec] + 1, 5)


def odpar_vodu(stav):
    pocet_riadkov = len(stav)
    pocet_stlpcov = len(stav[0])
    for riadok in range(pocet_riadkov):
        for stlpec in range(pocet_stlpcov):
            stav[riadok][stlpec] = max(stav[riadok][stlpec] - 1, 0)


def simuluj_pestovanie(stav, plan):
    pocet_riadkov = len(stav)
    pocet_stlpcov = len(stav[0])
    for zaznam in plan:
        if zaznam:
            if zaznam[0] == 'riadok':
                zalej_oblast(zaznam[1], 0, 1, pocet_stlpcov, stav)
            elif zaznam[0] == 'stlpec':
                zalej_oblast(0, zaznam[1], pocet_riadkov, 1, stav)
            else:
                zalej_oblast(zaznam[0], zaznam[1], zaznam[2], zaznam[3], stav)
        odpar_vodu(stav)

Funkcie zalej_riadok a zalej_stlpec už nepotrebujeme. Nahradili sme ich funkciou zalej_oblast, ktorá je univerzálnejšia. Vo funkcii simuluj_pestovanie však riadky a stĺpce musíme vyjadriť ako oblasti. Riadok vyjadríme ako oblasť s jedným riadkom a všetkými stĺpcami a stĺpec ako oblasť s jedným stĺpcom a všetkými riadkami.

Pokračujme v našej snahe o vylepšenie programu ďalej.

Ak sa pozrieme na funkcie zalej_oblast a odpar_vodu tak vidíme, že robia podobné veci. Jedna vo vybranej oblasti pridáva vodu (+1) a druhá odoberá vodu (-1). Vytvorme jednu univerzálnu funkciu, ktorá podľa hodnoty parametra vodu pridá alebo uberie.

#riasy3.py
def zmen_oblast(start_riadok, start_stlpec, pocet_riadkov, pocet_stlpcov, zmena, stav):
    for riadok in range(start_riadok, start_riadok + pocet_riadkov):
        for stlpec in range(start_stlpec, start_stlpec + pocet_stlpcov):
            if stav[riadok][stlpec] > 0:
                if zmena == 1:
                    stav[riadok][stlpec] = min(stav[riadok][stlpec] + 1, 5)
                else:
                    stav[riadok][stlpec] = max(stav[riadok][stlpec] - 1, 0)


def simuluj_pestovanie(stav, plan):
    pocet_riadkov = len(stav)
    pocet_stlpcov = len(stav[0])
    for zaznam in plan:
        if zaznam:
            if zaznam[0] == 'riadok':
                zmen_oblast(zaznam[1], 0, 1, pocet_stlpcov, 1, stav)
            elif zaznam[0] == 'stlpec':
                zmen_oblast(0, zaznam[1], pocet_riadkov, 1, 1, stav)
            else:
                zmen_oblast(zaznam[0], zaznam[1], zaznam[2], zaznam[3], 1, stav)
        zmen_oblast(0, 0, pocet_riadkov, pocet_stlpcov, -1, stav)

Ukázali sme si tri riešenia toho istého problému. Dekompozíciu, ktorú sme spravili na začiatku, sme však do zodpovedajúcich funkcií v jednotlivých riešeniach premietli rôzne. Rôzne, i keď v niečom podobné činnosti, sme najskôr implementovali ako samostatné funkcie. Neskôr sme ich zlúčili do univerzálnejších funkcií, ktorých správanie sme ovplyvnili hodnotami parametrov.

Vaše zaujímavé riešenia a najčastejšie chyby

S touto úlohou ste si poradili celkom dobre. Aj keď ide o komplexný problém, ktorý sa dá pomerne dobre rozdeliť na niekoľko menších problémov a ich riešenie implementovať do samostatných funkcií, väčšina z vás tak neurobila. Celé riešenie bolo často ímplementované v jednej rozsiahlej funkcii. Takýto prístup zneprehľadňuje samotné riešenie a nepomáha v prípada hľadania chyby alebo testovania kódu.

Niekoľko týmov si neuvedomilo dôsledky nulového stavu vody v boxoch. Ak takýto stav nastane, box sa už nezalieva a ani vod sa z neho neodparuje.