Če bi gladina svetovnih morij in oceanov Rešitev: narasla, bi se lahko kakšen otok popolnoma potopil in bi se tako število otokov na svetu zmanjšalo za ena. Po drugi strani pa bi lahko pri kakšnem otoku voda zalila le nižje ležeče dele, hribi pa bi še vedno štrleli ven in bi tako iz enega nastalo več samostojnih otokov; tako bi se število otokov na svetu povečalo. Podobno je, če se gladina oceanov zniža— kakšen otok lahko na novo pogleda iz vode, lahko pa se več otokov združi v enega samega, ker se plitvine med njimi izsušijo. Tako se torej, če spreminjamo gladino oceanov, število otokov zdaj povečuje, zdaj zmanjšuje. Nas pa zanima, kakšno je največje število otokov, ki bi ga lahko na svetu imeli, če bi mogli primerno izbrati gladino oceanov. (Za potrebe te naloge štejemo tudi celine kot velike otoke.)

Da bo naloga lažja, predpostavimo, da je Zemlja ploščata, ne pa okrogla, in da je njeno površje kot karirasta mreža, v kateri je višina površja znotraj vsake celice konstantna. Naj bo v(x, y) višina celice na preseku vrstice y in stolpca x. Če je gladina oceanov g, si mislimo, da so vse celice (x, y), za katere je v(x, y) < g, potopljene pod vodo, vse ostale pa so kopne. Pri tej nalogi torej ne bomo komplicirali z jezeri, depresijami, rečnimi in jezerskimi otoki ipd. Otok definirajmo kot vsako tako skupino kopnih celic, ki je povezana (torej se da priti od poljubne celice otoka do poljubne druge celice otoka, pri tem pa ves čas hoditi po samih kopnih celicah in iti vedno s trenutne celice na eno od njenih štirih sosed, ki imajo z njo skupnega enega od robov) in ki ji ne moremo dodati nobene druge trenutno kopne celice, ne da bi ta pogoj prenehal veljati. (Glej primer spodaj.) Napiši program, ki pri danih podatkih o višinah ugotovi, katero je največje možno število otokov, ki jih je mogoče dobiti s primernim izborom gladine oceanov g.

Vhodna datoteka: v prvi vrstici sta najprej števili h in w, ki povesta višino oz. širino kariraste mreže. To sta celi števili, velja 1 <= h <=100, 1 <=w <=100. Sledi h vrstic, v vsaki je po w števil, ki povedo višine celic: v(1, y), v(2, y), . . . , v(w, y). Višine so cela števila, zanje velja 0 <=v(x, y)<= 1 000 000 000.
Izhodna datoteka: vanjo naj tvoj program izpiše največje možno število otokov, ki ga je mogoče pri dani vhodni datoteki dobiti, če primerno izberemo gladino oceanov g.

Primer vhodne datoteke:
5 10
6 6 8 6 3 4 2 3 6 7
3 7 9 7 3 3 3 2 6 6
3 6 7 7 2 2 6 5 5 6
5 5 5 2 2 5 5 8 5 5
5 6 5 1 0 3 4 4 4 3
Pripadajoča izhodna datoteka:
5

Potrebovali bomo:

• Funkcijo, ki prebere datoteko,
• funkcijo, ki za dan relief in gladino poišče število otokov,
• funkcijo, ki za dan seznam poišče maksimalno število otokov,
• funkcijo, ki maksimalno število otokov zapiše v datoteko.

Problem – Kako poiskati maksimalno število otokov?

Število otokov pri različnih gladinah ni odvisno med seboj, zato nam rešitev pri neki gladini ne more pomagati pri računanju neke druge gladine. Tako moramo število otokov izračunati za vsako gladino posebaj.

Sedaj moramo samo še razmisliti, kako dobiti število otokov pri neki gladini. Sprehodimo se čez seznam sez. Ko pridemo do novega koščka kopnega, smo našli nov otok. Poiščemo vse točke oz. elemente seznama, ki pripadajo temu koščku in jih označimo. Sprehod nadaljujemo na naslednjem polju začetnega kopnega.

Potrebovali bomo šest funkcij:

• preberiDatoteko(datoteka)
• PoisciMaxVisina(sez)
• PoisciMinVisina(sez)
• ZapolniSez(sez,vr,st,g)
• PoisciStOtokov(sez1,g)
• PoisciMaxOtokov(imeDatoteke, imeNoveDatoteke)
• ZapisiVDatoteko(sez1, g)

S pomočjo te funkcije bomo dobili seznam, ki bo vseboval relief.
Najprej preverimo, če datoteka sploh obstaja. V nasprotnem primeru sprožimo napako.

• Uvozimo knjižnico os.
• Os.path.file(imeDatoteke) vrne True, če datoteka obstaja oz. False, če ne.

Sedaj lahko odpremo datoteko za branje.

• dat=open(imeDatoteke, 'r')

Posamezne vrstice bomo brali z metodo dat.readline().
Ko začnemo brati, pazimo, da prva vrstica vsebuje podatke o dimenzijah. Zato prva vrstica ne pride v poštev za v seznam. Shranimo jo v nov seznam, ki ga poimenujemo dim. Seveda moramo prej razbiti niz, ki smo ga prebrali (dat.readline()).

Pomagamo si s funkcijami oz. metodami:

• niz.strip () ... vrne kopijo niza niz in na koncu odreže bele znake
• sez2=niz.split() ... vrne seznam besed v nizu niz (besede so ločene z enim ali več presledki)
• sez2=int(sez2[0]) ... ničti element seznama sez2 pretvori v celo število.

Kot smo že omenili, beremo vsako vrstico posebej (dat.readline()). Ko preberemo vrstico, dobimo niz, torej moramo niz spremeniti v seznam znakov. A prej odstranimo bele znake (niz.strip()). Nato z metodo list naredimo seznam znakov prebrane vrstice. Ta seznam dodamo seznamu sez, ki smo ga prej definirali.

Ko imamo seznam, najprej preverimo, če je datoteka smiselna (da bo program čim bolj stabilen.) Torej, če se ujemajo podane dimenzije z dimenzijo seznama. Če seznam ne ustreza pravilom, sprožimo napako.

Če ne pride do napake in se celotna funkcija izvrši, vrnemo seznam sez.

Funkciji sprejmeta seznam in vrneta minimalni oz. maksimalni element.
Sprehodimo se čez vrstice in si zapomnimo minimalni oz. maksimalni element vrstice. Shranimo ga v poseben seznam minV oz. maxV.

• Pomagamo si s funkcijami min oz. max, ki vrneta minimalen oz. maksimalen element.

Na koncu vrnemo min(minV) oz. max(maxV).

Funkcija ZapolniSez(sez, vr, st,g) sprejme seznam reliefa, drugi in tretji parameter predstavljata lokacijo kopnega. Okrog lokacije poiščemo še ostalo kopno, ki se je drži. Četrti parameter je višina gladine.

Kot smo že zgoraj omenili bo funkcija zapolnila s posebni znakom ('+') kopno okoli podane lokacije (če je podana lokacija res kopno).

Ustavitveni pogoji:

Vprašamo se, kaj vse mora nujno »ustaviti funkcijo«. Funkcija se ustavi če:

• je podana lokacija izven tabele
• je lokacija že zapolnjena z znakom '+' ali če je lokacija pod gladino.

Če kateri od ustavitvenih pogojev velja, kličemo samo return (končamo funkcijo, seznam se ne spremeni).

Rekurzivno klicanje – funkcija kliče samo sebe

Če se funkcija ne ustavi pri nobenem od ustavitvenih pogojev, štirikrat rekurzivno pokličemo polja okoli nas:

• Za pozicijo nad nami povečamo vrstico (parameter vr) za ena, stolpec (parameter st) ostane enak.
• Za pozicijo pod nami zmanjšamo vrstico za ena, stolpec je enak.
• Za pozicijo levo od trenutne zmanjšamo stolpec za ena, vrstica ostane enaka.
• Za pozicijo desno od trenutne povečamo stolpec za 1, vrstica ostane enaka.

Funkcija ne vrača ničesar, samo spreminja podan seznam.

Funkcija sprejme seznam sez1 in višino gladine g.
Nujno je potrebno, da naredimo globoko kopijo podanega seznama, saj bomo seznam spreminjali.

• Uvozimo knjižnico copy
• sez=copy.deepcopy(sez1)
• Globoko zato, ker so tudi elementi seznama seznami/objekti.

Definiramo števec st=0, ki bo štel število otokov za dano gladino.
S for zanko se sprehodimo čez seznam sez. Ko pridemo do elementa seznama, ki je nov košček kopnega, smo našli nov otok. Poiščemo vse točke oz. elemente seznama. To naredimo s pomočjo funkcije ZapolniSez. Števec st povečamo za ena. Sprehod nadaljujemo na naslednjem polju začetnega kopnega.
Vrnemo števec st.

Funkcija sprejme ime datoteke (ime) in celo število (st), ki ga želimo zapisati.
Najprej bomo preverili, če datoteka, ki jo želimo ustvariti, že obstaja. Če obstaja, uporabnika toliko časa sprašujemo za novo ime, dokler to ime za datoteko še ne obstaja v trenutnem direktorju. Če tega ne bi preverjali, bi se prejšnja istoimenska datoteka prepisala.
Ko vemo, da bomo varno ustvarili datoteko, le-to ustvarimo.

• dat=open(imeDatoteke, »w«)

  • S parametrom »w« povemo, da bomo datoteko odprli za pisanje.

S pomočjo klica funkcije dat.write(str(st)) zapišemo število v datoteko. str(st) dodamo zato, ker moramo metodi write() podati parameter tipa niz.
Na koncu samo še zapremo datoteko (dat.close()).

Funkcija sprejme ime vhodne (imeDatoteke) in ime izhodne datoteke(imeNoveDatoteke). Za dano vhodno datoteko zapiše novo datoteko z imenom imeNoveDatoteke v katero zapiše maksimalno število otokov.
Sedaj imamo pripravljene oz. definirane funkcije, ki jih bomo potrebovali.
Najprej s pomočjo funkcije preberiIzDatoteke dobimo seznam reliefa.
Nato poiščemo maksimalno in minimalno gladino:

• maxV=PoisciMaxVisina(sez)
• minV=PoisciMinVisina(sez)

Definiramo še prazen seznam stevci, kamor bomo vpisovali št. otokov za dano gladino.
Sedaj za vsako gladino od minimalne do maksimalne izračunamo število otokov.

• To naredimo tako, da se sprehodimo s for zanko od minV do maxV+1 indeksa. Znotraj for zanke tako za vsako gladino kličemo PoisciStOtokov(sez, g).
  Dobljeno število otokov in gladino dodamo kot dvojico v seznam stevci.
  Sedaj s pomočjo seznama stevci definiramo nov seznam st, ki bo vseboval samo število otokov.

  • st=[i[1] for i in stevci]
    V M si zapomnimo maksimalen element seznama st. Pomagamo si s funkcijo max.
    Stevilo M zapišemo v datoteko ImeNoveDatoteke:
• ZapisiVDatoteko(ImeNoveDatoteke, M)

Python datoteka

S testiranjem bomo preverili, če se funkcija »obnaša« pravilno oz. tako kot bi pričakovali.
Kot bomo videli kasneje si bomo pomagali z varovalnimi mrežami try, except (stavek except: polovi vse napake znotraj try-a.)
V primeru, da funkcijo kličemo pravilno in ne pričakujemo napak, uporabimo naslednjo kodo:
try:
    klic funkcije
except Exception as e:
    print ('Prišlo je do napake!')
    print(e)

Če se bo funkcija pravilno izvršila, se nam na ekran ne bo izpisalo nič. Če pa bo ob klicu prišlo do napake, bo napako ulovil stavek Except. Izpisalo se bo sporočilo »Prišlo je do napake« in izpisala se bo tudi napaka, ki jo vrne Python (e).
V primeru, da pričakujemo oz. vemo, da mora funkcija sprožiti napako uporabimo kodo:
try:
    klic funkcije
    print('V ta print ne bi smelo priti!')
except:
    pass

Ker pričakujemo, da bo ob neustreznih parametrih prišlo do napake ob klicu funkcije, za klicem spišemo nek stavek print. Če bo vse prav in bo do napake res prišlo, se ta print ne bo izvedel. Če se bo print izvedel, to pomeni, da funkcija ni sprožila napake in da je posledično spisana narobe. Če se bo zgodilo pričakovano, torej če se bo sprožila napaka, vemo, da stavek except »ulovil« napako. Zato stavek pass,ki ne naredi ničesar, saj je prav, da se je sprožila napaka.

Glede na to kakšen primer testiramo, v testno datoteko spišemo kodo kot v zgornjih dveh primerih. Ko imamo spisane vse try, except stavke in smo z njimi res preverili vse možne primere, smo končali s pisanjem testne datoteke. Izvršimo testno datoteko (pritisnemo F5). Če se v Python Shell-u ne izpiše nič, to pomeni, da se funkcija obnaša pravilno.

• Odpremo novo Python datoteko.

• Uvozimo metode/funkcije iz Python datoteke, kjer se nahaja naša testirana funkcija:

  • Import Otoki

• Stestiramo osnovne primere

  • Primer, ki je podan znotraj naloge (Otoki.txt)

  • Zelo osnoven primer reliefa (Otoki1.txt)

    • Če bi si izmislili večjo datoteko, bi zelo težko preverili rezultat na peš.
• Stestiramo primere, kjer pričakujemo, da funkcija vrne napako.
• Podani napačni parametri (oba parametra, ki jih funkcija sprejme, sta imeni datotek, zato morata biti niz.
• Vsebina datoteke je nepravilna:
• primer z neujemanjem dimenzij (Otoki2.txt)
• primer prevelikega reliefa (dovoljujemo le 100x100) (Otoki3.txt)
• primer, kjer v reliefu niso same cifre (Otoki4.txt)

• Za vhodno datoteko podamo datoteko, ki ustreza pravilom (prva vrstica predstavlja dimenzije, naslednje vrstice pa tabelo)
• Za izhodno datoteko pravilno podamo ime datoteke (niz)

• Naredimo oba primera z datotekama Otoki.txt in Otoki1.txt

  • Preverimo, če se ugotovitve ujemajo

Primer dveh pravilnih datotek in klicev funkcij:

Otoki.txt:

datoteka Otoki.txt

Klic funkcije: Otoki.PoisciMaxOtokov('Otoki.txt', 'Izh.txt')
Pričakujemo, da se bo v Izh.txt zapisala petica (5).

Otoki1.txt:

datoteka Otoki1.txt

Klic funkcije: Otoki.PoisciMaxOtokov('Otoki1.txt', 'Izh1.txt')
Pričakujemo, da se bo v datoteki Izh1.txt prav tako zapisala petica(5).

Komentar in koda:

Ker v obeh primerih pričakujemo, da ne bo prišlo do napake, bomo uporabili prvi način uporabe varovalne mreže try, except.
try:
    Otoki.PoisciMaxOtokov('Otoki.txt', 'Izh.txt«)
except Exception as e:
    print ('Prišlo je do napake!')
    print(e)

try:
    Otoki.PoisciMaxOtokov('Otoki1.txt', 'Izh1.txt«)
except Exception as e:
    print ('Prišlo je do napake!')
    print(e)

Stestiramo primere, kjer pričakujemo, da funkcija vrne napako.

• Vprašamo se, kdaj mora funkcija sprožiti napako.

  • Ločimo dva primera:

    • napačni prametri (oba parametra morata biti tipa niz)
    • vhodna datoteka ne ustreza pravilom (napačna dimenzija, prevelika tabela, nedovoljeni znaki)

Uporabljali bomo drugi način uporabe varovalne mreže.

Funkcijo na primer pokličemo Zapolni(8,9).

• Funkcija mora sprožiti napako – 3. in 4. element morata biti niza
  try:
      Otoki.PoisciMaxOtokov(8, 9)
      print('V ta print ne bi smelo priti!')
  except:
      pass
  

Neujemanje dimenzij

Preverimo, če funkcija sproži napako, kadar se podana dimenzija v prvi vrstici datoteke razlikuje od dejanske dimenzije tabele. Primer take datoteke je Otoki2.txt, kjer je dejanska dimenzija tabele 5x10.

Otoki2.txt:

datoteka Otoki.txt

Varovalna mreža in klic funkcije:
try:
    Otoki.PoisciMaxOtokov('Otoki2.txt', 'Izh2.txt')
    print(‘V ta print ne bi smelo priti!’)
except:
    pass

Prevelika tabela

Funkcija zahteva, da je maksimalna tabela velikosti 100x100.
Primer datoteke, ki vsebuje tabelo večjo od 100x100 , je Otoki3.txt:

datoteka Otoki3.txt

Varovalna mreža in klic funkcije:
try:
    Otoki.PoisciMaxOtokov('Otoki3.txt', 'Izh3.txt')
    print(‘V ta print ne bi smelo priti!’)
except:
    pass

Nedovoljeni znaki znotraj tabele

Funkcija dovoljuje znotraj tabele cela števila.
Preverimo, če vrne napako, kadar zgornja trditev ne drži.
Taka datoteka je Otoki4.txt:

datoteka Otoki4.txt

Varovalna mreža in klic funkcije:
try:
    Otoki.PoisciMaxOtokov('Otoki5.txt', 'Izh5.txt')
    print('V ta print ne bi smelo priti!')
except:
    pass

S testnimi primeri bomo preverili, če se funkcija obnaša pravilno v različnih primerih.
Preverimo, če se funkcija res v vseh primerih obnaša pravilno.

Zaženemo testno datoteko. Opazimo, da se v Python Shell-u ne izpiše nič. To pomeni, da funkcija gotovo v vseh primeri deluje pravilno. Preveriti moramo samo še, če so vse datoteke, ki pa so vseeno nastale, pravilne (res vsebujejo pravilno število poti).
Opazimo, da funkcija deluje pravilno.