Izziv je bil torej tak: imamo seznam besed. Sestaviti želimo najdaljšo verigo besed, v kateri se vsaka beseda začne z zadnjo črko prejšnje. Besede se ne smejo ponavljati. Veriga se lahko začne s poljubno besedo.
Pri reševanju lahko uporabljamo nekoliko krajši slovar besed in enega
z več kot 1500 besedami, ki jih lahko uvozimo iz modula
besede
, ki je priložen nalogi.
= ["ABRAHAM", "MELODIJA", "ASTEROID", "DREVO", "MEČ", "OBLAK", "KLEPTOMAN", "KAČA"]
slovar from besede import nouns
Očitno je prva možnost, da pregledamo vsa možna zaporedja. Enako očitno je tudi, da je teh zaporedij veliko.
Nekateri študenti so se lotili tega izziva. To je pohvalno.
def vse_verige(slovar):
= []
verige = set(slovar)
slovar for prva in slovar:
+= nadaljevanja(prva, slovar - {prva})
verige return verige
def nadaljevanja(beseda, slovar):
= [[beseda]]
rezultat for naslednja in slovar:
if naslednja[0] == beseda[-1]:
for podverige in nadaljevanja(naslednja, slovar - {naslednja}):
+ podverige)
rezultat.append([beseda] return rezultat
vse_verige(slovar)
[['KAČA'],
['KAČA', 'ASTEROID'],
['KAČA', 'ASTEROID', 'DREVO'],
['KAČA', 'ASTEROID', 'DREVO', 'OBLAK'],
['KAČA', 'ASTEROID', 'DREVO', 'OBLAK', 'KLEPTOMAN'],
['KAČA', 'ABRAHAM'],
['KAČA', 'ABRAHAM', 'MEČ'],
['KAČA', 'ABRAHAM', 'MELODIJA'],
['KAČA', 'ABRAHAM', 'MELODIJA', 'ASTEROID'],
['KAČA', 'ABRAHAM', 'MELODIJA', 'ASTEROID', 'DREVO'],
['KAČA', 'ABRAHAM', 'MELODIJA', 'ASTEROID', 'DREVO', 'OBLAK'],
['KAČA', 'ABRAHAM', 'MELODIJA', 'ASTEROID', 'DREVO', 'OBLAK', 'KLEPTOMAN'],
['DREVO'],
['DREVO', 'OBLAK'],
['DREVO', 'OBLAK', 'KAČA'],
['DREVO', 'OBLAK', 'KAČA', 'ASTEROID'],
['DREVO', 'OBLAK', 'KAČA', 'ABRAHAM'],
['DREVO', 'OBLAK', 'KAČA', 'ABRAHAM', 'MEČ'],
['DREVO', 'OBLAK', 'KAČA', 'ABRAHAM', 'MELODIJA'],
['DREVO', 'OBLAK', 'KAČA', 'ABRAHAM', 'MELODIJA', 'ASTEROID'],
['DREVO', 'OBLAK', 'KLEPTOMAN'],
['ASTEROID'],
['ASTEROID', 'DREVO'],
['ASTEROID', 'DREVO', 'OBLAK'],
['ASTEROID', 'DREVO', 'OBLAK', 'KAČA'],
['ASTEROID', 'DREVO', 'OBLAK', 'KAČA', 'ABRAHAM'],
['ASTEROID', 'DREVO', 'OBLAK', 'KAČA', 'ABRAHAM', 'MEČ'],
['ASTEROID', 'DREVO', 'OBLAK', 'KAČA', 'ABRAHAM', 'MELODIJA'],
['ASTEROID', 'DREVO', 'OBLAK', 'KLEPTOMAN'],
['MEČ'],
['MELODIJA'],
['MELODIJA', 'ASTEROID'],
['MELODIJA', 'ASTEROID', 'DREVO'],
['MELODIJA', 'ASTEROID', 'DREVO', 'OBLAK'],
['MELODIJA', 'ASTEROID', 'DREVO', 'OBLAK', 'KAČA'],
['MELODIJA', 'ASTEROID', 'DREVO', 'OBLAK', 'KAČA', 'ABRAHAM'],
['MELODIJA', 'ASTEROID', 'DREVO', 'OBLAK', 'KAČA', 'ABRAHAM', 'MEČ'],
['MELODIJA', 'ASTEROID', 'DREVO', 'OBLAK', 'KLEPTOMAN'],
['MELODIJA', 'ABRAHAM'],
['MELODIJA', 'ABRAHAM', 'MEČ'],
['OBLAK'],
['OBLAK', 'KAČA'],
['OBLAK', 'KAČA', 'ASTEROID'],
['OBLAK', 'KAČA', 'ASTEROID', 'DREVO'],
['OBLAK', 'KAČA', 'ABRAHAM'],
['OBLAK', 'KAČA', 'ABRAHAM', 'MEČ'],
['OBLAK', 'KAČA', 'ABRAHAM', 'MELODIJA'],
['OBLAK', 'KAČA', 'ABRAHAM', 'MELODIJA', 'ASTEROID'],
['OBLAK', 'KAČA', 'ABRAHAM', 'MELODIJA', 'ASTEROID', 'DREVO'],
['OBLAK', 'KLEPTOMAN'],
['KLEPTOMAN'],
['ABRAHAM'],
['ABRAHAM', 'MEČ'],
['ABRAHAM', 'MELODIJA'],
['ABRAHAM', 'MELODIJA', 'ASTEROID'],
['ABRAHAM', 'MELODIJA', 'ASTEROID', 'DREVO'],
['ABRAHAM', 'MELODIJA', 'ASTEROID', 'DREVO', 'OBLAK'],
['ABRAHAM', 'MELODIJA', 'ASTEROID', 'DREVO', 'OBLAK', 'KAČA'],
['ABRAHAM', 'MELODIJA', 'ASTEROID', 'DREVO', 'OBLAK', 'KLEPTOMAN']]
Prva funkcija ni bila nič posebnega.
Mali trik: slovar
pretvori v množico. Na ta način lahko
preprosteje odstranjujemo uporabljene besede. O kakšni posebni hitrosti
pa pri teh funkcijah itak ne moremo govoriti.
Funkcija vse_verige
gre čez vse možne prve besede in v
seznam verig (verige
) doda vse verige, ki jih vrne funkcija
nadaljevanja
, ki, kot pove njeno ime, poišče vsa možna
nadaljevanja pri podani besedi in množici še neuporabljenih besed.
def vse_verige(slovar):
= []
verige = set(slovar)
slovar for prva in slovar:
+= nadaljevanja(prva, slovar - {prva})
verige return verige
Druga funkcija je zanimivejša. V seznam rezultat
nabira
vse možne verige, ki se začnejo s podano besedo. Za začetek je to
veriga, ki vsebuje samo to besedo, torej veriga [beseda]
.
Ker gre za seznam verig, je to v začetku seznam, ki vsebuje,
[beseda]
, se pravi [[beseda]]
.
Nato gre funkcija čez vse besede, ki so še v slovarju. Če se beseeda
začne z ustrezno črko, gre z zanko for
čez vsa možna
nadaljevanja, ki se začnejo s to, naslednjo besedo, se pravi
for podverige in nadaljevanja(naslednja, slovar - {naslednja})
.
Vsako tako "podverigo" dodajo v seznam, na začetek pa pripnejo prvo
besedo (beseda
).
def nadaljevanja(beseda, slovar):
= [[beseda]]
rezultat for naslednja in slovar:
if naslednja[0] == beseda[-1]:
for podverige in nadaljevanja(naslednja, slovar - {naslednja}):
+ podverige)
rezultat.append([beseda] return rezultat
To je to.
Seznam je dolg že pri osmih besedah. Besed v seznamu, podanem ob domači nalogi, je bilo približno 1500, zato ta rešitev tam ne bo delovala - ne glede na to, kako jo sfriziramo. Po mojem.
Preden napišemo rešitev, ki deluje tudi za daljše sezname, povejmo le, da se da obe funkciji združiti v eno, vendar s tem ne pridobimo ničesar bistvenega. Tako, kot je, je lepše. Poleg tega povejmo še, da se ju da zapisati kompaktneje.
def najdaljsa_veriga(slovar):
return max(sum((nadaljevanja(prva, set(slovar)) for prva in slovar), []), key=len)
def nadaljevanja(beseda, slovar):
return [[beseda] + pod
for naprej in slovar if naprej[0] == beseda[-1]
for pod in nadaljevanja(naprej, slovar - {beseda})] or [[beseda]]
najdaljsa_veriga(slovar)
['MELODIJA', 'ASTEROID', 'DREVO', 'OBLAK', 'KAČA', 'ABRAHAM', 'MEČ']
Ali je to boljše, je stvar okusa. Najbrž slabega okusa.
(Mimogrede lahko ugotovimo tudi, da je to res najdaljše, kar je možno
sestaviti iz
["ABRAHAM", "MELODIJA", "ASTEROID", "DREVO", "MEČ", "OBLAK", "KLEPTOMAN", "KAČA"]
.
Imamo dve besedi, ki se začneta s K in le eno, ki so konča s K. Poleg
tega je ena od besed na K, KLEPTOMAN, lahko le zadnja, saj ni besed na
N. Pred KLEPTOMAN je lahko le OBLAK, pred OBLAK le DREVO, pred DREVO
ASTEROID, pred ASTEROID pa KAČA ali MELODIJA. Takšno zaporedje,
MELODIJA, ASTEROID, DREVO, OBLAK, KLEPTOMAN ima pet besed. Besede
KLEPTOMAN torej en bo v rešitvi. Najdena rešitev pa vsebuje vse besede
razen KLEPTOMAN, torej je najdaljša možna.)
Kadar ne moremo najti najboljše možne rešitve, bomo morali biti zadovoljni s kar dobro. Tudi šahist ne more razmisliti vseh možnih nadaljevanj igre, temveč razmišlja za nekaj potez naprej. Nekaj podobnega bomo naredili tu: med možnimi nadaljevanji bomo izbrali tistega, ki se konča s črko, na katero se začne čimveč besed. Na ta način se izognemo besedam, ki porabljajo redke, dragocene črke.
Najprej pomislimo, da se splača razdeliti besede glede na črko, s katero se začenjajo.
from collections import defaultdict
def razdeli_besede(slovar):
= defaultdict(list)
po_zacetnicah for beseda in slovar:
0]].append(beseda)
po_zacetnicah[beseda[return po_zacetnicah
= razdeli_besede(nouns) po_zacetnicah
Zaradi praktičnosti smo uporabili defaultdict
. Ne o tem
- pa tudi o slovarjih - se še nismo učili, zato se tudi zdaj ne bomo
poglabljali v to. Vedimo le: z, recimo, po_zacetnicah["K"]
dobimo vse besede, ki se začnejo s črko K.
print(po_zacetnicah["K"])
['KNOWLEDGE', 'KING', 'KEY', 'KIND', 'KITCHEN', 'KID', 'KNIFE', 'KNEE', 'KEEP', 'KICK', 'KILL', 'KISS']
Program bomo sestavili iz dveh funkcij. Prva bo iz seznama možnih nadaljevanj izbrala eno (poskusili bomo: čim boljše) nadaljevanje. Druga bo klicala prvo.
def najboljsa_naslednja(moznosti, po_zacetnicah):
if not moznosti:
return None
return moznosti[0]
def sestavi_zaporedje(slovar):
= razdeli_besede(slovar)
po_zacetnicah = najboljsa_naslednja(slovar, po_zacetnicah)
naslednja = []
zaporedje while naslednja:
zaporedje.append(naslednja)0]].remove(naslednja)
po_zacetnicah[naslednja[= najboljsa_naslednja(po_zacetnicah[naslednja[-1]], po_zacetnicah)
naslednja return zaporedje
Naš prvi približek najboljsa_naslednja
je neumen: vrne
preprosto prvo možnost. Če je seznam možnosti prazen, vrne
None
. Funkcija sicer dobi tudi slovar
po_zacetnicah
, vendar ga - v tej, neumni obliki - ne
uporablja.
Funkcija sestavi_zaporedje
prejme slovar vseh besed.
Razbije ga na seznam po začetnicah. Izbere prvo besedo (ki ji iz
praktičnih razlogov, reče naslednja
in pripravi prazno
zaporedje.
Nato ponavlja, dokler ima kako naslednjo besedo: besedo doda v zaporedje, jo pobriše iz seznama vseh besed, ki se začnejo s to črko in nato izbere naslednjo besedo, tako da pokliče prvo funkcijo.
Ugotovimo, kako dobro to deluje.
= sestavi_zaporedje(nouns)
zaporedje print(zaporedje)
print(len(zaporedje))
['PEOPLE', 'ECONOMICS', 'SYSTEM', 'MAP', 'PERSON', 'NATURE', 'EXAM', 'MEAT', 'TWO', 'OVEN', 'NEWS', 'SOFTWARE', 'EQUIPMENT', 'THANKS', 'SCIENCE', 'ENVIRONMENT', 'THEORY', 'YEAR', 'READING', 'GOVERNMENT', 'TELEVISION', 'NIGHT', 'TEMPERATURE', 'ENERGY', 'YOUTH', 'HISTORY', 'YARD', 'DATA', 'ART', 'THING', 'GOAL', 'LAW', 'WAY', 'YOU', 'UNDERSTANDING', 'GROWTH', 'HEALTH', 'HOUSING', 'GRANDMOTHER', 'ROAD', 'DEFINITION', 'NATION', 'NEWSPAPER', 'ROLE', 'EDUCATION', 'NEGOTIATION', 'NUMBER', 'RELATIONSHIP', 'PROBLEM', 'MUSIC', 'COMPUTER', 'REALITY', 'YOUNG', 'GUIDANCE', 'EVENT', 'THOUGHT', 'TECHNOLOGY', 'YELLOW', 'WORLD', 'DEVELOPMENT', 'TRUTH', 'HEART', 'TEACHER', 'RESPONSIBILITY', 'YESTERDAY']
65
To ni tako slabo, vendar bo boljše, če naredimo kakšno manj neumno izbiro naslednje besede. Gotovo se nam splača varčevati z redkimi besedami: za naslednjo besedo nočemo izbrati besede, ki se konča s črko, s katero se začenja malo besed. Oziroma obratno: izmed različnih možnosti bomo za naslednjo besedo izbrali takšno, s katero se začenja čim več besed.
def najboljsa_naslednja(moznosti, po_crkah):
= None
naj_naprej = -1
naj_pogostost for naprej in moznosti:
= len(po_crkah[naprej[-1]])
pogostost if pogostost > naj_pogostost:
= pogostost
naj_pogostost = naprej
naj_naprej return naj_naprej
def sestavi_zaporedje(slovar):
= razdeli_besede(slovar)
po_zacetnicah = najboljsa_naslednja(slovar, po_zacetnicah)
naslednja = []
zaporedje while naslednja:
zaporedje.append(naslednja)0]].remove(naslednja)
po_zacetnicah[naslednja[= najboljsa_naslednja(po_zacetnicah[naslednja[-1]], po_zacetnicah)
naslednja return zaporedje
= sestavi_zaporedje(nouns)
zaporedje print(len(zaporedje))
523