Programiranje

Kaladont je ime zobne paste. In tudi igre. V različici, opisani na Wikipediji, mora vsak igralec povedati besedo, ki se začne s črkama, s katero se je končala zadnja beseda (ROŽE - ŽENIN - INTERNIST - STOPNICA ...). Tu jo bomo poenostavili tako, da bomo zahtevali le, da se prva črka ujema z zadnjo (in ne prvi dve z zadnjima dvema).

Obvezna naloga

Napiši naslednje funkcije.

• lahko_sledi(prej, potem) vrne True, če sta besedi potem in prej različni ter se potem začne s črko, s katero se je končala beseda prej. Če ni tako, naj vrne False.

• izberi_besedo(beseda, slovar) prejme niz beseda in seznam slovar, ki vsebuje vse možne besede. Funkcija vrne besedo iz slovarja, ki sme slediti podani besedi. Ker bo običajno na voljo več kandidatov, naj vrne najdaljšo besedo. Če je enako dolgih besed več, naj vrne tisto, ki je prej po abecedi.

• ni_ponavljanj(besede) prejme seznam besed in vrne True, če se nobena beseda ne ponovi, ter False, če se.

• preveri_zaporedje(besede) prejme zaporedje besed, izrečenih v igri in vrne True, če je zaporedje legalno. Zaporedje je legalno, če se vsaka beseda začne z zadnjo črko prejšnje in če se nobena beseda ne ponovi.

Rešitev

lahko_sledi

lahko_sledi je lahko samo takšna.

def lahko_sledi(prej, potem):
    return prej != potem and prej[-1] == potem[0]

Lahko obrnemo vrstni red pogojev. Kar je več, ni dobro.

Ni dobro, recimo, tole.

def lahko_sledi(prej, potem):
    if prej != potem and prej[-1] == potem[0]:
        return True
    else:
        return False

ker namiguje, da študent ne ve, da je rezultat izraza prej != potem and prej[-1] == potem[0] že True ali False - torej točno to, kar moramo vrniti.

Še bolj nedobro je

def lahko_sledi(prej, potem):
    if prej != potem:
        if prej[-1] == potem[0]:
            return True
        else:
            return False
    else:
        return False

ker sicer kaže, da študent odlično obvlada if in else, ni pa še slišal za and.

izberi_besedo

V funkciji izberi_besedo vadimo klasičen vzorec: iščemo element seznama (ali kakega drugega zaporedja), ki je optimalen po določenem kriteriju. V tem primeru po tem, da

• sme slediti podani besedi in,
• je najdaljši ali,
• ali pa enako dolg kot najdaljši, vendar prej po abecedi.

Kriteriji so nabrani v treh vrsticah, v katere smo razbili if. Pazite na oklepaje: držati mora prvo poleg tega pa tudi bodisi drugo bodisi tretje. Zato za and oklepaj, ki nam, priročno, tudi dopušča, da tu prelomimo vrstico in naredimo funkcijo preglednejšo.

def izberi_besedo(beseda, slovar):
    naj_beseda = ""
    for potem in slovar:
        if lahko_sledi(beseda, potem) and (
                len(potem) > len(naj_beseda) or
                len(potem) == len(naj_beseda) and potem < naj_beseda):
            naj_beseda = potem
    return naj_beseda

Drugi motiv za to nalogo je bil, torej, poleg tega, da ste vadili "klasičen vzorec" tudi ta, da ste bili pozorni pri sestavljanju pogojev. Če ste najprej sprogramirali narobe, potem pa naključno vrteli and, or in oklepaje toliko časa, da je začelo delati, potem je to slaba strategije učenja. Ko ne deluje, se moramo potruditi razumeti, zakaj ne.

ni_ponavljanj

To nalogo sem vam dal zato, ker sem vedel, da se boste mučili s tem, kako odkriti, ali seznam vsebuje določeno besedo, ne da bi gledali besedo, zaradi katere gledate, ali vsebuje to besedo. To sem povedal precej zapleteno, ampak tisti, ki so se zaplezali, vedo, o čem govorim. O tem.

def ni_ponavljanj(besede):  # Ta funkcija ne deluje!
    for besedа1 in besede:
        for beseda2 in besede:
            if beseda1 == beseda2:
                return False
    return True

Ideja je v tem, da gremo čez vse besede (zunanja zanka) in gledamo, ali se pojavijo še kje v seznamu (notranja zanka). A seveda se pojavijo: naleteli bomo na prav to ponovitev.

Očiten popravek te funkcije je, da štejemo pojavitve te besede.

def ni_ponavljanj(besede):
    for beseda1 in besede:
        pojavitev = 0
        for beseda2 in besede:
            if beseda1 == beseda2:
                pojavitev += 1
        if pojavitev > 1:
            return False
    return True

Tisti, ki vam dela programiranje težave, si le pozorno oglejte to funkcijo, saj se v njej skriva marsikaj.

Zunanja zanka še vedno izbira besedo, ki jo bomo preverjali. V notranji zanki preštejemo, kolikokrat se ta beseda pojavi.

        pojavitev = 0
        for beseda2 in besede:
            if beseda1 == beseda2:
                pojavitev += 1

Nato preverimo, ali se je pojavila več kot enkrat. Če je tako vrnemo True. Takoj. Ta pogoj (if pojavitev > 1) je znotraj zunanje zanke, saj ga moramo preveriti za vsako besedo beseda1.

Če se beseda pojavi le enkrat, ne storimo ničesar. Tu ni nobenega else. Pač pa čisto na koncu funkcije, po zunanji zanki, čaka return True. Do njega bomo prišli le, če nismo pri nobeni besedi vrnili return False, se pravi, če se nobena beseda ni pojavila več kot enkrat.

Če je to komu (še) težko brati, lahko razdeli funkcijo na dve, pa bo preglednejše.

def stevilo_ponovitev(beseda, besede):
    pojavitev = 0
    for beseda2 in besede:
        if beseda1 == beseda2:
            pojavitev += 1
    return pojavitev


def ni_ponavljanj(besede):
    for beseda1 in besede:
        if stevilo_ponovitev(beseda1, besede) > 1:
            return False
    return True

To je morda preprosteje prebrati, saj je vsaka funkcija zase preprosta.

Kdor ve, kaj več, ve, da imajo seznami metodo count, ki jo lahko uporabimo namesto prve funkcije. Zadošča torej

def ni_ponavljanj(besede):
    for beseda1 in besede:
        if besede.count(beseda1) > 1:
            return False
    return True

Kdor tega še ni vedel, bo to izvedel po predavanju, ki sledi tej domači nalogi.

Zdaj pa poskusimo še drugače: za vsako besedo raje preverimo, ali se pojavi med besedami, ki ji sledijo. Za to ni dovolj, da vemo le za trenutno besedo, ki jo preverjamo, temveč moramo poznati tudi njeno mesto v seznamu, indeks. Kadar potrebujemo takšne pare, uporabimo, vemo, enumerate.

Zunanja zanka bo torej for i, beseda1 in enumerate(besede):. Imamo torej besedo in njeno mesto v seznamu. Zdaj preverimo samo besede od te besede naprej, besede[i + 1:]. Če med njimi zalotimo besedo beseda1, vrnemo False.

def ni_ponavljanj(besede):
    for i, beseda1 in enumerate(besede):
        for beseda2 in besede[i + 1:]:
            if beseda1 == beseda2:
                return False
    return True

Namesto tega lahko preverjamo tudi vnazaj -- preverjamo, ali smo določeno besedo že videli med besedami pred njo, besede[:i].

def ni_ponavljanj(besede):
    for i, beseda1 in enumerate(besede):
        for beseda2 in besede[:i]:
            if beseda1 == beseda2:
                return False
    return True

Podobno kot smo se prej spomnili na count, se lahko zdaj na in:

def ni_ponavljanj(besede):
    for i, beseda1 in enumerate(besede):
        if beseda2 in besede[:i]:
            return False
    return True

Čeprav je rešitev na koncu kar kratka, zahteva, da se spomnimo (vsaj) na enumerate. Tisti, ki so prišli do te rešitve, ali do katerekoli od gornjih, so se nekaj naučili. Nekateri pa so raje malo pogooglali in izvedeli, da lahko z izrazom len(set(s)) == len(s) izvemo, ali seznam s vsebuje duplikate. Pa so napisali takšno rešitev.

def ni_ponavljanj(besede):
    return len(set(besede)) == len(besede)

Ti se niso naučili ničesar. Razen, če so že prej vedeli, kaj je set in znali delati s tem, niso pa še pomislili na tale trik.

Kdor na Googlu najde nasvet, ki ga ne razume, vendar ga vseeno uporabi, se ni naučil ničesar. To je v bistvu učenje na pamet -- zdaj bo lahko vsakič, ko bo dobil enako nalogo, že vedel, kako jo rešiti. Ko bo dobil malenkost drugačno, pa ne. Pri programiranju učenje na pamet ne deluje.

preveri_zaporedje

To nalogo ste dobili, da bi se spomnili, kako dobimo zaporedne elemente zaporedja. Tako, kot kakršnekoli pare, se pravi z zip, le da pri zaporednih parih pač potrebujemo za 1 zamaknjena seznama.

Najprej bomo torej šli prek parov, for prej, potem in zip(besede, besede[1:]) in preverili, ali besedi prej lahko sledi beseda potem. Če preživimo ta test, pa preverimo, ali ni ponavljanj. Če jih ni, vrnemo True, če so False. Torej

def preveri_zaporedje(besede):
    for prej, potem in zip(besede, besede[1:]):
        if not lahko_sledi(prej, potem):
            return False
    return ni_ponavljanj(besede)

Če ne vemo za zip, se moramo hecati z indeksi.

def preveri_zaporedje(besede):
    for i in range(1, len(besede)):
        if not lahko_sledi(besede[i - 1], besede[i]):
            return False
    return ni_ponavljanj(besede)

Tudi to je v redu, ni pa prav Pythonovsko. Naslednji teden se bomo namreč učili, kako se to napiše krajše.

def preveri_zaporedje(besede):
    return ni_ponavljanj(besede) and \
           all(lahko_sledi(prej, potem) for prej, potem in zip(besede, besede[1:]))

Ne le, da ni prav Pythonovsko. Podobno se dela tudi v drugih sodobnih jezikih. Tako so te tri funkcije videti v Kotlinu.

fun lahko_sledi(prej: String, potem: String) = prej.last() == potem.first()

fun ni_ponavljanj(besede: List<String>) = besede.toSet().size == besede.size

fun preveri_zaporedje(zaporedje: List<String>) =
    ni_ponavljanj(zaporedje) &&
    zaporedje.zipWithNext().all { lahko_sledi(it.first, it.second)}

Dodatna naloga

Napiši še naslednje funkcije.

• pogostosti_zacetnic(slovar) prejme seznam besed, zapisanih z velikimi črkami, in vrne seznam s 25 elementi. Prvi element pove, koliko besed v slovarju se začne s črko A, drugi, koliko besed se začne s črko B in tako naprej do Ž.

  Pomagaj si s funkcijo

  def indeks(crka):
      crka = {"Q": "Č", "W" :"Š", "Y": "Ž"}.get(crka, crka)
      return "ABCČDEFGHIJKLMNOPRSŠTUVZŽ".index(crka)
  

  ki vrne 0, če jih podaš A, 1 če ji podaš B ... in 25, če jih podaš Ž. Funkcija nekako deluje tudi za angleške črke, le da postavi Q na mesto Č-ja, W na Š in Y na Ž, X-a pa nikamor, saj večina angleških besed nima navade začenjati se na X.

• mozne_naslednje(beseda, slovar) prejme besedo in slovar možnih besed. Vrne seznam vseh besed, ki se začnejo z zadnjo črko podane besede.

• najboljsa_naslednja(moznosti, pogostosti) prejme seznam možnih naslednjih besed (torej točno seznam, kakršnega vrača funkcija mozne_naslednje) in seznam, ki pove, koliko besed se začna s posamezno črko (torej točno seznam, kakršnega vrača funkcija pogostosti_zacetnic). Med podanimi moznostmi poišče in vrne tisto besedo, ki se konča s črko, s katero se začne največ besed (pri čemer ne sme upoštevati te besede, če se slučajno začne in konča z isto črko). Če je enako pogostih več, vrne tisto, ki je prej po abecedi. Dolžina ni pomembna.

• sestavi_zaporedje(slovar) prejme slovar besed in vrne seznam z zaporedjem besed, ki ga sestavi po naslednjem receptu:

  • prva beseda je beseda, ki se konča s črko, s katero se začne največ besed (ta beseda sama -- če se slučajno začne in konča z isto črko -- pri tem ne šteje)
  • vsako naslednjo besedo izbere na podoben način: med vsemi možnimi nadaljevanji izbere besedo, ki se konča s črko, s katero se začne največ besed; v primeru, da je enako pogostih več, vzame tisto, ki je prej po abecedi - uporabi prejšnjo funkcijo. Pri tem ignorira to besedo kot tudi vse druge besede, ki so se se že pojavile.

  Ta funkcija bo neverjetno zapletena, če ne boš v njej spretno uporabljal(a) funkcij, ki si jih napisal(a) zgoraj.

  Ne pozabite vsakič, ko uporabite določeno besedo, zmanjšati števila besed, ki se začnejo s to začetnico.

  Če želiš iz seznama s odstraniti element e, pokliče s.remove(e). Opozarjam pa, da se takšnih stvari navadno ne dela s seznamom. Tu ga uporabljamo samo zato, ker boljšega še ne poznamo.

Rešitev

pogostosti_zacetnic(slovar)

Pripravili si bomo tabelico s 25 ničlami. Najpreprostejši način za to je, da vzamemo seznam, v katerem je samo ena ničla in ga pomnožimo s 25: [0] * 25. Seznam si predstavljamo kot 25 škatlic. Gremo čez besede in pri vsaki povečamo škatlico, ki ustreza prvi črki besede.

def indeks(crka):
    crka = {"Q": "Č", "W": "Š", "Y": "Ž"}.get(crka, crka)
    return "ABCČDEFGHIJKLMNOPRSŠTUVZŽ".index(crka)


def pogostosti_zacetnic(slovar):
    pogostosti = [0] * 25
    for beseda in slovar:
        pogostosti[indeks(beseda[0])] += 1
    return pogostosti

mozne_naslednje

Funkcija, ki vrne seznam, se navadno začne tako, da ustvari seznam. V tem primeru prazen. Potem gremo čez vse besede iz slovarja in vsako, ki bi lahko sledila podani besedi, dodamo v seznam možnih besed.

def mozne_naslednje(beseda, slovar):
    mozne = []
    for potem in slovar:
        if lahko_sledi(beseda, potem):
            mozne.append(potem)
    return mozne

najboljsa_naslednja

Podobno kot pri funkciji izberi_besedo gre za iskanje elementa seznama, ki je optimalen glede na nek kriterij.

Paziti moramo le, da število preostalih besed, ki se začnejo s črko, s katero se končuje posamezna beseda, zmanjšamo za 1, kadar sta prva in zadnja črka besede enaki. Če imamo 80 besed, ki se začnejo s črko R, bo besedi ROPAR sledila ena od 79 besed, saj smo ROPARja porabili.

def najboljsa_naslednja(moznosti, pogostosti):
    naj_beseda = ""
    naj_pogostost = -1
    for beseda in moznosti:
        pogostost = pogostosti[indeks(beseda[-1])]
        if beseda[0] == beseda[-1]:
            pogostost -= 1
        if pogostost > naj_pogostost \
                or (pogostost == naj_pogostost and beseda < naj_beseda):
            naj_pogostost = pogostost
            naj_beseda = beseda
    return naj_beseda

Funkcija je res nekoliko dolga, a pretežno rutinska.

sestavi_zaporedje

Zdaj, ko je vse tako lepo pripravljeno, funkcija sestavi_zaporedje ni nič pretirano zpaletenega. Naredimo lahko, recimo, tako.

def sestavi_zaporedje(slovar):
    slovar = slovar[:]
    zaporedje = []
    beseda = najboljsa_naslednja(slovar, pogostosti_zacetnic(slovar))
    while beseda:
        zaporedje.append(beseda)
        slovar.remove(beseda)
        beseda = najboljsa_naslednja(mozne_naslednje(beseda, slovar), pogostosti_zacetnic(slovar))
    return zaporedje

Čemu slovar = slovar[:]? Ker bomo znotraj funkcije spreminjali slovar, je lepo, da si naredimo svojo kopijo, ne pa, da tistemu, ki je poklical funkcijo, pokvarimo seznam, ki nam ga je dal. Za to nas ni nihče pooblastil.

Prvo besedo izberemo izmed vseh v slovarju. Dodamo jo v zaporedje in odstranimo iz slovarja. Potem poiščemo naslednjo besedo. Zanka teče, dokler imamo naslednjo besedo.

V tej rešitve me nekoliko moti, da stalno kličemo pogostosti_zacetnic. Lahko bi jih poklicali le enkrat, si jih zapomnili in jih potem zmanjšali ob vsaki uporabljeni besedi. V resnici sem prvič nalogo rešil na ta način, vendar ne zapletajmo brez potrebe.