Kaladont
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)
vrneTrue
, če sta besedipotem
inprej
različni ter sepotem
začne s črko, s katero se je končala besedaprej
. Če ni tako, naj vrneFalse
.izberi_besedo(beseda, slovar)
prejme nizbeseda
in seznamslovar
, 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 vrneTrue
, če se nobena beseda ne ponovi, terFalse
, če se.preveri_zaporedje(besede)
prejme zaporedje besed, izrečenih v igri in vrneTrue
, č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 funkcijamozne_naslednje
) in seznam, ki pove, koliko besed se začna s posamezno črko (torej točno seznam, kakršnega vrača funkcijapogostosti_zacetnic
). Med podanimimoznostmi
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 elemente
, pokličes.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.