Testi

testi-potapljanje-ladjic.py

Naloga

Naloga bo povezana s potapljanjem ladjic - na enodimenzionalni plošči, ker bo tako (za zdaj) lažje.

Stanje na plošči bomo shranili v seznamu nizov: vsak niz bo predstavljal eno polje. Prazni nizi predstavljajo prazna polja. Polja, na katerih so ladje, so predstavljena z "oznako" ladje; oznaka je vedno dolga eno črko. Tako seznam ['a', '', 'x', 'x', 'x', '', 'y', 'y', '', ''] predstavlja ploščo, ki ima na prvem polju ladjo a, drugo polje je prazno, na naslednjih treh poljih je ladja z oznako x, nato sledi prazno polje, na naslednjih dveh poljih je ladja z oznako y, sledita pa še dve prazni polji.

Ogrevalna naloga

Napiši funkcijo prazna(n), ki kot argument prejme velikost plošče in kot rezultat vrne prazno ploščo. Tako mora prazna(4) vrniti seznam ['', '', '', ''].

Napiši funkcijo je_prazna(plosca), ki kot argument prejme ploščo in kot rezultat vrne True, če je plošča prazna, in False, če ni.

Napiši funkcijo v_niz(plosca), ki vrne niz, ki predstavlja ploščo. Gre za niz sestavljen iz znakov v seznamu, le prazni nizi so zamenjani s presledki. Tako mora klic v_niz([' ', 'a', '', '', '', 'x', 'x', 'x', '', 'y', 'y', '', '']) vrniti niz ' a xxx yy '.

Rešitev

Prazna plošča je seznam z n praznimi nizi. Tu precej pomaga, če vemo, kaj množenje naredi s seznami.

def prazna(n):
    return [""] * n

Preverjanje, ali je plošča prazna, je praktično enako nalogam vrste "ali seznam vsebuje sodo število", ki smo jih pred dvema tednoma reševali na predavanjih in vajah.

def je_prazna(plosca):
    for e in plosca:
        if e != '':
            return False
    return True

Nekoč bomo izvedeli, da gre tudi veliko krajše:

def je_prazna(plosca):
    return not any(plosca)

Lenuhi lahko naredijo tudi tole

def je_prazna(plosca):
    return plosca == prazna(len(plosca))

V zadnji funkciji sestavimo prazen niz in mu korak za korakom dodajamo elemente. Naloga je praktično enaka nalogi "napiši funkcijo, ki izračuna vsoto", le da moramo tu poskrbeti, da se prazna polja spremenijo v presledke.

def v_niz(plosca):
    s = ""
    for c in plosca:
        if c != "":
            s += c
        else:
            s += " "
    return s

Če se spomnimo, da se or zanimivo vede, lahko napišemo tudi

def v_niz(plosca):
    s = ""
    for c in plosca:
        s += c or " "
    return s

Nekoč pa se bomo naučili, da se da tudi krajše. Na primer tako:

def v_niz(plosca):
    return "".join(c or " " for c in plosca)

Obvezna naloga

Napiši funkcijo je_prostor(plosca, kje, dolzina), ki pove, ali je na podano ploščo možno postaviti ladjo, ki se začne pri indeksu kje in je dolga dolzina. Ladje se smejo dotikati robov plošče, ne smejo pa se dotikati drugih ladij.

Napiši funkcijo postavi(plosca, kje, dolzina, oznaka), ki najprej preveri, ali je možno na podano mesto postaviti ladjo podane dolžine. Če to ne gre, vrne False (in ne stori ničesar drugega). Če gre, postavi ladjo na to mesto (torej ustrezno spremeni seznam plosca) in vrne True.

Napiši funkcijo obstaja(plosca, oznaka), ki pove, ali na plošči obstaja ladja s podano oznako. Funkcija vrne True ali False.

Napiši funkcijo vse_oznake(plosca), ki vrne seznam vseh oznak ladij, ki se nahajajo na podani plošči. Klic vse_oznake(['a', '', 'x', 'x', 'x', '', 'y', 'y', '', '']) mora vrniti seznam ['a', 'x', 'y']. Vrstni red elementov v seznamu je lahko poljuben; dovoljen rezultat je tudi, recimo ['y', 'a', 'x'].

Napiši funkcijo strel(plosca, kje), ki simulira strel na podano ploščo. Funkcija mora vrniti

• 0, če na podanem polju ni bilo ladje,
• 1, če je na podanem polju ladja, ki pa s tem strelom še ni potopljena,
• 2, če je na podanem polju ladja, ki je s tem strelom tudi dokončno potopljena, vendar so na plošči še druge ladje.
• 3, če je bila s tem strelom dokončno potopljena zadnja ladja.

Poleg tega mora funkcija strel seveda tudi spremeniti stanje na plošči, to je, pobrisati morebitno ladjo (oz. del ladje) na zadetem polju.

Rešitev

Da bi bil na polju kje prostor za ladjo dolžine dolzina, mora veljati naslednje

• ladja ne sme gledati prek roba plošče (kje + koliko <= len(plosca)),
• polja, kamor jo hočemo postaviti, morajo biti prosta (je_prazna(plosca[kje: kje + koliko])),
• polje levo od plošče mora biti prazno, razen če je ladja na levem robu. Z drugimi besedami, ladja mora biti na levem robu ali pa mora biti polje levo od nje prazno (kje == 0 or plosca[kje - 1] == ""),
• enako na desni strani kje + koliko >= len(plosca) or plosca[kje + koliko] == "".

Držati mora vse od zgoraj naštetega, torej

def je_prostor(plosca, kje, koliko):
    return kje + koliko <= len(plosca) and \
         je_prazna(plosca[kje: kje + koliko]) and \
         (kje == 0 or plosca[kje - 1] == "") and \
         (kje + koliko >= len(plosca) or plosca[kje + koliko] == "")

Z \ na koncu vrste povem, da se vrstica nadaljuje v naslednji vrsti.

Ne prezrite oklepajev v vrsticah z or. Operator and ima namreč prednost pred or.

Postavljanje ladje nam ne bo dalo vetra: če ni prostora, vrnemo False, sicer v enem zamahu, s prirejanjem rezin, spremenimo elemente seznama od kje do kje + koliko.

def postavi(plosca, kje, koliko, oznaka):
    if not je_prostor(plosca, kje, koliko):
        return False
    plosca[kje:kje + koliko] = [oznaka] * koliko
    return True

Preverjanje, ali na plošči obstaja ladja z določeno oznako, je trivialno (če nismo pozabili na operator in).

def obstaja(plosca, oznaka):
    return oznaka in plosca

Vse oznake naberemo tako, da pripravimo prazen seznam. Gremo čez ploščo in vsak element dodamo, če ga še ni.

def vse_oznake(plosca):
    vse = []
    for e in plosca:
        if e and e not in vse:
            vse.append(e)
    return vse

Naslednji teden se bomo naučili, da gre tudi krajše:

def vse_oznake(plosca):
    return list(set(plosca))

Končno še strel. Najprej si zapomnimo oznako ladje, ki jo bomo (morda) uničili. Če tam ni ničesar, vrnemo 0. Sicer uničimo, kar je na tistem mestu. Če na plošči še obstaja ladja s to oznako, vrnemo 1. Če je plošča prazna, vrnemo 3 (konec igre). Sicer vrnemo 2.

def strel(plosca, kje):
    oznaka = plosca[kje]
    if oznaka == '':
        return 0
    plosca[kje] = ''
    if obstaja(plosca, oznaka):
        return 1
    elif je_prazna(plosca):
        return 3
    else:
        return 2

Dodatna naloga

Napiši funkcijo razpostavi(n, ladje), ki dobi želeno velikost plošče in seznam parov (oznaka, dolzina) in kot rezultat vrne igralno ploščo, na kateri se nahajajo podane ladje. Tako lahko klic razpostavi(12, [('a', 2), ('b', 3), ('c', 1)]) vrne, na primer, ['', 'b', 'b', 'b', '', '', 'a', 'a', '', '', 'c', ''].

Namig: nikjer ne piše, da mora biti plošča, ki jo vrneš, vsakič drugačna. Nalogo si lahko poenostaviš tako, da pri podanih velikostih ladij vedno vrneš enako ploščo.

Rešitev

Če nikjer ne piše ... pa postavimo ladje kar po vrsti, ne? Naredimo prazno ploščo, gremo čez seznam ladij in na ploščo postavimo ladjo ([oznaka] * dolzina) in potem za njo še prazno polje. Na koncu pobrišemo prazno polje za zadnjo ladjo (za vsak slučaj, če so ladje ravno napolnile ploščo in smo zdaj že predolgi). Nato dodamo toliko praznih polj, kot jih še manjka.

def razpostavi(n, ladje): plosca = [] for oznaka, dolzina in ladje: plosca += [oznaka] * dolzina plosca.append('') del plosca[-1] plosca += [''] * (n - len(plosca)) return plosca

Dodatni izziv je bilo naključno postavljanje ladij. Najprikladnejši trik, ki mi je prišel na misel, je tale. Naredimo seznam nizov, ki predstavljajo ladje, za vsako ladjo pa je presledek. Mimogrede še preštejemo njihovo skupno dolžino, skupaj s tem presledkom.

    deli = []
    sk_dolzina = 0
    for oznaka, dolzina in ladje:
        deli.append(oznaka * dolzina + ' ')
        sk_dolzina += dolzina + 1

Nato v ta seznam dodamo še toliko nizov , kolikor jih manjka, da bo plošča polna.

    deli += [' '] * (n - sk_dolzina)

To naključno premešamo.

    shuffle(deli)

Kar smo dobili, bomo spremenili v ploščo, le na nekaj še pomislimo: tako kot je narejeno zdaj, je zadnji znak na plošči gotovo presledek. Če je zadnji del ladja+presledek (nekaj, česar dolžina je večja od 1), pobrišemo ta presledek in dodamo presledek na neko naključno mesto v seznamu.

    if len(deli[-1]) != 1:
        deli[-1] = deli[-1][:-1]
        n = randint(0, len(deli))
        deli[n:n] = [' ']

Zdaj pa sestavimo ploščo iz teh delov - prepisati moramo le vse znake iz nizov in zamenjati presledke s praznimi nizi. Vse skupaj je videti tako:

from random import *

def razpostavi(n, ladje):
    deli = []
    sk_dolzina = 0
    for oznaka, dolzina in ladje:
        deli.append(oznaka * dolzina + ' ')
        sk_dolzina += dolzina + 1
    deli += [' '] * (n - sk_dolzina)
    shuffle(deli)
    if len(deli[-1]) != 1:
        deli[-1] = deli[-1][:-1]
        n = randint(0, len(deli))
        deli[n:n] = [' ']
    plosca = []
    for en_del in deli:
        for c in en_del:
            if c == ' ':
                c = ''
            plosca.append(c)
    return plosca