Skúška 9.2.2023 - Indiáni v labyrinte¶

Keď sa indián dostane do labyrintu, tak samostatne postupuje, kým má kam. Každé prejdené políčko pritom označí značkou, že tu už bol a teda takto označené políčko je už neskôr nepriechodné. Lenže indián postupuje samostatne len pokým je jeho cesta jednoznačná, t.j. ak stojí na políčku, z ktorého je viac možností, kam sa vybrať, tak tu skončí (na tomto políčku zostane stáť). Vtedy môžeme na nejaké iné voľné políčko umiestniť ďalšieho indiána a ten opäť postupuje samostatne, kým je jeho cesta jednoznačná. Takto môže niekoľko indiánov označiť hoci aj všetky políčka labyrintu. Zrejme, ak indiána umiestnime na políčko, ktoré má viac ako jednu možnosť, kam sa dá pokračovať, indián toto jedno políčko označí značkou a na ňom aj zastane.

Tvojou úlohou je prečítať textový súbor s popisom labyrintu a potom postupne podľa ďalších pokynov umiestňovať niekoľko indiánov a pritom sledovať, ako sa označujú políčka. Program na požiadanie oznámi počet voľných políčok, počet políčok označených značkami, prípadne momentálne pozície všetkých indiánov.

Riešenie zapíš do triedy Indiani s týmito metódami:

class Indiani:
    def __init__(self, meno_suboru):
        ...

    def __repr__(self):
        ...

    def indian(self, riadok, stlpec):
        ...

    def pocet_znaciek(self):
        ...

    def pocet_volnych(self):
        ...

    def vsetci_indiani(self):
        ...

Kde metódy:

__init__(meno_suboru): prečíta súbor a vytvorí z neho dvojrozmernú hraciu plochu
__repr__(): vráti znakový reťazec, ktorý reprezentuje momentálny stav hracej plochy, pričom nepriechodné steny sa zobrazia ako '#', voľné políčka ako '.', označené políčka bez indiána ako '+' a políčka s indiánmi ako 'i', medzi riadkami je znak '\n'
indian(riadok, stlpec): umiestni na dané políčko indiána a realizuje jeho samostatný prechod labyrintom aj s označovaním políčok; ak je toto políčko už označené, alebo je to prekážka, indián sa neumiestni a tento príkaz sa ignoruje
pocet_znaciek(): vráti momentálny počet označených políčok
pocet_volnych(): vráti momentálny počet voľných políčok
vsetci_indiani(): vráti množinu (typ set) pozícií všetkých indiánov v labyrinte, pričom pozície sú dvojice (riadok, stĺpec)

Textový súbor obsahuje popis labyrintu (štvorcová sieť) v tvare:

prvý riadok obsahuje 2 čísla: počet riadkov a počet stĺpcov labyrintu
všetky ďalšie riadky súboru obsahujú štvorice čísel, ktoré popisujú jeden blok prekážok, t.j. obdĺžnik obsadených políčok v tvare:
```
riadok stĺpec počet_riadkov počet_stĺpcov
```
kde riadok, stĺpec (číslujeme od 0) je pozícia ľavého horného políčka a ďalšie dve čísla sú veľkosť takéhoto bloku, napríklad 2 1 3 5 označuje blok 15 nepriechodných políčok, pričom začína v 2. riadku a 1. stĺpci

Napríklad, pre súbor

5
1 3 3
0 3 2

má labyrint takýto tvar:

.....
.###.
####.
####.
##...

Ak umiestnime prvého indiána na políčko (1, 0), tak označí všetky voľné políčka a zastane na políčku (4, 2). Metóda pocet_znaciek() vráti číslo 12, metóda vsetci_indiani() vráti jednoprvkovú množinu s pozíciou indiána, teda {(4, 2)}.

Ak by sme ale indiána umiestnili na políčko, napríklad (0, 3), ten by toto jedno políčko označil a, keďže sa nevie rozhodnúť, kadiaľ má pokračovať, tak tu zastane. Ak by sme teraz zisťovali pocet_znaciek(), dostali by sme číslo 1. Ďalších dvoch indiánov by sme mohli položiť, napríklad na pozície (0, 2) a (4, 2). Každý z nich by označkoval svoju časť labyrintu. Metóda pocet_znaciek() by teraz vrátila číslo 12 a metóda vsetci_indiani() vráti ich pozície, napríklad {(0, 3), (1, 0), (0, 4)}. Na poradí pozícií indiánov zrejme nezáleží.

Program môžeš testovať, napríklad takto:

if __name__ == '__main__':
    i = Indiani('subor1.txt')
    print(i)
    print('pocet volnych =', i.pocet_volnych())
    i.indian(0, 3)
    print(i)
    print('pocet znaciek =', i.pocet_znaciek())
    print('pozicie indianov =', i.vsetci_indiani())
    i.indian(0, 2)
    i.indian(4, 2)
    print(i)
    print('pocet znaciek =', i.pocet_znaciek())
    print('pozicie indianov =', i.vsetci_indiani())

mal by vypísať:

.....
.###.
####.
####.
##...
pocet volnych = 12
...i.
.###.
####.
####.
##...
pocet znaciek = 1
pozicie indianov = {(0, 3)}
+++ii
i###+
####+
####+
##+++
pocet znaciek = 12
pozicie indianov = {(1, 0), (0, 3), (0, 4)}

Z úlohového servera L.I.S.T. si stiahni kostru programu skuska.py. Pozri si testovacie dáta v súboroch 'subor1.txt', …, ktoré bude používať testovač.

Aby si mohol spúšťať skúškové testy, program ulož do súboru skuska.py. Riešenie (bez dátových súborov) odovzdaj na úlohový server https://list.fmph.uniba.sk/. Tvoj odovzdaný program musí začínať tromi riadkami komentárov:

# 6. skuska: indiani
# autor: Janko Hraško
# datum: 9.2.2023