Zadanie

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Žabovi na zaba@ksp.sk

Zadanie možno vyzerá odstrašujúco dlhé. Je však jednoduchšie ako by sa mohlo zdať. Odporúčame ho riešiť úlohu po úlohe a veľa si kresliť. Už za nakreslenie niekoľkých obrázkov viete získať pomerne veľa bodov. Vaše kresby nám môžete odfotiť a vložiť do riešenia.

Poznáte lemingov zo známej počítačovej hry? Sú to malé postavičky, ktoré postupne vychádzajú zo svojho domčeka, idú neustále dopredu a snažia sa doraziť do cieľa. Niektorí z nich počas tejto cesty možno umrú, ale to až tak nevadí, lebo ich je skutočne veľa. Byť lemingom však vôbec nie je také ľahké, hlavne keď máte pred domom obrovskú dieru, ktorej sa vydáte v ústrety. Ak do nej spadnete, umriete.

V Lemingove je medzi štartovacím a cieľovým domčekom v rade niekoľko obrovitánskych (pre naše účely nekonečne hlbokých) dier, každá označená niektorým písmenom anglickej abecedy. Každú sekundu sa zo štartu vynorí nový leming, ktorý sa celý čas hýbe doprava a snaží sa dostať k cieľu.

Keď ste prišli na návštevu Lemingova s desom ste sa pozerali, ako sa každú sekundu vrhne ďalší leming do prvej diery. Nijakým spôsobom sa totiž cez ňu nevie dostať. V tomto okamihu hrôzy ste však v sebe objavili skryté magické schopnosti. Vysvitlo, že keď dostatočne nahlas poviete každú sekundu jediné písmeno, nad dierami označenými týmito písmenami sa na sekundu objaví most. Prechod cez most trvá lemingovi presne sekundu. To znamená, že leming stojaci na ľavom okraji jamy, nad ktorou sa objavil most, má akurát dosť času, aby sa dostal na jej druhú stranu.

Pozrite sa na obrázok nižšie. Na začiatku sekundy sa pri štarte objavil nový leming a vy ste zakričali písmeno B. Nad jamami s písmenom B sa objavil most. Cez prvú dieru vedie most, leming po ňom môže prejsť a dostať sa na druhú stranu. Následne všetky mosty zmiznú a zo štartu sa vynorí ďalší leming. V tomto momente ste však v nezávideniahodnej situácii, nech totiž poviete akékoľvek písmeno, nezachránite oboch lemingov. Môžete povedať písmeno B a zachrániť druhého leminga, alebo písmeno A a pomôcť prvému. Alebo budete zlí a poviete napríklad Z a oboch ich pošlete do jamy.

Úloha

  1. (2 body) Nech v jamách sú postupne napísané písmená BABKA (ako na obrázku vyššie). Zo začiatočnej pozície, v ktorej je živý iba leming, ktorý práve vyšiel zo štartu, ste postupne povedali nasledovné písmená: BBABKAABABABKA – každú sekundu jedno v tomto poradí. Nakreslite, kde sa nachádzali lemingovia po tom, čo ste prečítali prvé štyri písmená, teda BBAB a po tom, čo ste prečítali prvých trinásť písmen, teda BBABKAABABABK.

    Popri tom, ako ste vraveli text BBABKAABABABKA ste si pozorne všímali, kde sa nachádzajú lemingovia. Zaujímalo vás totiž koľkokrát sa v tomto texte vyskytlo slovo BABKA, ktoré je tvorené písmenami z jám. Ako vám vie poloha lemingov prezradiť, že v hovorenom texte sa nachádza slovo z jám? Prečo je tomu tak?

  2. (2 bod) Hľadanie slov v texte sa vám zapáčilo a povedali ste si, že by to mohlo byť aj pomerne užitočné. Pozor však, že hľadané písmená sa v texte musia nachádzať za sebou. V texte BAZBKA sa teda slovo BABKA nenachádza ani raz.

    Vymyslite text dlhý 15 písmen, v ktorom sa slovo KATKA nachádza čo najviackrát.

  3. (4 body) Keď ste sa vrátili z Lemingova, po rozume vám stále behal ich zvláštny spôsob života. Začali ste si teda kresliť na papier, akoby sa lemingovia pohybovali pri rôznych písmenách v jamách a textoch, ktoré by ste čítali. Prekresľovať zakaždým všetkých lemingov je ale strašne otravné. Radšej by ste sa sústredili iba na jedného – toho čo je najviac vpravo a teda najbližšie k cieľu. Posúvať jedného leminga je totiž oveľa jednoduchšie. Keď však tento leming prišiel do cieľa a zmizol v domčeku, zrazu ste nevedli, kde sú ostatní lemingovia. Možno to viete spätne vypočítať.

    Predstavte si, že poznáte písmená v jamách a pozíciu najpravejšieho leminga, ktorý ešte nevošiel do cieľového domčeka. Vedeli by ste zistiť, kde sa nachádzajú ostatní lemingovia? Viete o každom mieste naľavo od neho povedať, či sa tam leming nachádza alebo nie? Je toto umiestnenie jednoznačné? Odôvodnite svoje tvrdenia v popise. Takisto do popisu napíšte postup, ktorým by ste zisťovali pozície zvyšných lemingov.

    Aby ste lepšie pochopili, čo v tejto úlohe treba robiť, skúste si ju vyriešiť na konkrétnom príklade z obrázku nižšie. Za správne určenie pozícií lemingov v tomto obrázku môžete získať až 2 body.

  1. (4 body) Povedať niečo o lemingoch keď poznáte písmenká v jame je ľahké, čo však, keď neviete ani to? Predstavte si, že medzi štartom a cieľom je 17 jám a nepoznáte písmená, ktoré im prislúchajú. Medzi jamami sa nachádzajú nejaký lemingovia. Vy ste si všimli jedného, ktorý práve dorazil na koniec slova a chystá sa vstúpiť do domčeka s cieľom. K nemu najbližšie stojí leming za 12-tou jamou, medzi nimi žiaden ďalší leming nie je. Rozhodnite a svoje tvrdenie odôvodnite, či za siedmou a jedenástou jamou stojí leming.
  1. (3 body) Počas toho ako ste sa hrali s rôznymi slovami sa vám najviac zapáčili také, v ktorých sa pravidelne opakovala nejaká postupnosť písmen, mali takzvanú periódu. Slovo je periodické práve vtedy, ak vzniklo opakovaním tej istej postupnosti písmen. Napríklad periodické slovo MAMA vzniklo opakovaním postupnosti MA. Slovo ABABABABABAB mohlo vzniknúť aj opakovaním štyroch písmen ABAB aj opakovaním dvoch písmen AB. V takomto prípade nás však zaujíma najkratšia možná perióda.

    Presnejšie, slovo má periódu \(p\), ak platí, že ľubovoľné dve písmená, ktoré sú od seba vo vzdialenosti \(p\), sú rovnaké. Slovo ABABABAB má preto periódu 2, slovo PAAPPAAPPAAP má periódu 4 a slovo LLLLLLL má periódu 1. Dokonca, mierne prekvapivo, napríklad slovo KATKA má periódu 3 – naozaj platí, že písmená vo vzdialenosti tri sú v ňom rovnaké. Ako ďalšie príklady si môžeme ukázať slovo KATKAKAK s periódou 7 a slovo MACKA s periódou 5.

    Zaujíma vás, či vám vedia lemingovia pomôcť s určovaním periódy. Do jám ste teda napísali písmená slova, ktorého periodickosť chcete zistiť. Následne ste postupne čítali písmená tohto slova a sledovali, ako sa hýbu lemingovia. Keď ste skončili, pri cieľovom domčeku určite stál leming a ďalší boli možno niekde po ceste. Viete na základe tohto zistiť, akú periódu má zadané slovo? Svoje tvrdenia odôvodnite. Snažte, aby bolo vaše riešenie všeobecné a fungovalo na ľubovoľnom slove.

Podúloha a.

V prvej podúlohe si stačilo poriadne prečítať, ako sa lemingovia hýbu, a následne tento pohyb odsimulovať na zadanom slove BBABKAABABABKA. simuláciu. Odporúčame sa na to pozrieť.)* Celú simuláciu si môžete pozrieť na tomto obrázku:

Po prečítaní BBAB sú lemingovia usporiadaní takto:

a po prečítaní BBABKAABABABK nasledovne:

Otázka v tejto podúlohe okrem toho bola, koľkokrát sa v texte BBABKAABABABKA nachádza slovo BABKA a ako to súvisí s pohybom lemingov. Ľahko zistíme, že v tomto slove sa slovo BABKA nachádza na dvoch miestach. Keď si navyše odsimulujeme pohyb lemingov, všimneme si, že vždy keď toto slovo končí, jeden leming príde do cieľového domčeka. Ak sme totiž prečítali slovo BABKA postupne sa nad každou jamou objavil most. Leming, ktorý sa zo štartovacieho domčeka vynoril keď sme začali čítať túto časť textu, tak má vždy most, na ktorý vie stúpiť a postupne príde do konca. Táto vlastnosť platí aj naopak. Ak leming príde do cieľového domčeka, znamená to, že počas jeho cesty sa pred ním museli objavovať mosty a teda sme prečítali slovo BABKA. Vidíme, že počet slov tvorených písmenami z jám v zadanom texte je rovnaký ako počet lemingov, ktorým sa podarilo prísť do cieľa.

Podúloha b.

Našou úlohou je vymyslieť 15 písmenný text, ktorý obsahuje slovo KATKA čo najviac krát. Je jasné, že ak budeme toto slovo opakovať jedno za druhým, zopakujeme ho 3 krát a vytvoríme text KATKAKATKAKATKA.

Ide to však aj lepšie a k tomu nám pomôžu práve lemingovia. Je napríklad jasné, že hľadaný text bude začínať slovom KATKA..., toto je totiž najrýchlejší spôsob ako dosiahnuť prvú zhodu a z každého textu, ktorý by takto nezačínal by sme mohli prvé písmeno odstrániť bez toho aby sme zmenšili počet výskytov. Takisto už vieme, že počet výskytov slova KATKA v texte je totožný počtu lemingov, ktorí prešli ponad jamy s písmenami slova KATKA. Vytvorme si teda takéto jamy a prečítajme začiatok textu, teda KATKA.... Dostaneme nasledovnú situáciu.

Ako vieme dosiahnuť ďalší výskyt slova KATKA? Tak, že niektorého leminga dostaneme do cieľa. A najrýchlejšie to zvládne leming, ktorý stojí za druhou jamou. Aké písmená musíme prečítať aby prišiel do cieľa? Predsa tie, ktoré sú v jamách pred ním, teda T, K a A. Pridaním troch písmen dostaneme ďalší výskyt a náš text vyzerá: KATKATKA.... V tomto momente je však situácia úplne rovnaká ako na obrázku a najbližšie k cieľu je opäť leming stojaci za druhou jamou. Dostávame preto text KATKATKATKATKAT, v ktorom sa slovo KATKA nachádza štyrikrát.

Samozrejme, k tomuto riešeniu sa dalo prísť čisto pozorovaním a skúšaním, je však pekné sa pozrieť na to, ako toto riešenie vlastne súvisí s pohybom lemingov a čo nám vedia o riešení prezradiť.

Podúloha c.

V podúlohe c. nastala situácia, v ktorej sme sledovali ako sa jeden leming postupne dostal až k cieľovému domčeku. Bohužiaľ sme si však nevšímali žiadnych iných lemingov a zaujíma nás, či ich polohu vieme napriek tomu určiť.

Koľko informácie teda vieme odvodiť z toho, že jeden leming stojí pred cieľom? V skutočnosti pomerne veľa. Ako sme si ukázali už v podúlohe a., to že sa tento leming dostal až na koniec znamená, že sa pred ním vždy musel objaviť most, aby po ňom prešiel a dostal sa ďalej. Tým pádom poznáme niekoľko posledných písmen, ktoré boli vyslovené. Úplne presne, vieme, že tieto písmená boli postupne všetky písmená z jám.

A to nám už stačí na vyriešenie celej úlohy. Uvedomme si totiž, že ak sa nejaký leming nachádza niekde uprostred cesty, tak sa zo štartu vynoril neskôr ako leming stojaci pri cieli. Tým pádom všetky písmená, ktoré tento leming za svojho života počul, počul aj leming pri cieli. A síce nevieme, či tam skutočne je, vieme si odvodiť, čo by počul keby tam bol a skontrolovať či to sedí s jamami, ponad ktoré musel prejsť.

Ukážme si to trochu konkrétnejšie. Nech sa v jamách postupne nachádzajú písmená \(j_1, j_2 \dots j_n\). To sú zároveň aj posledné písmená, ktoré boli vyslovené. Teraz by sme chceli zistiť, či sa za prvou jamou nachádza leming. Ak by tam bol, tak počul posledné písmeno, ktoré bolo vyslovené, teda \(j_n\). Ale ponad prvú jamu mohol prejsť iba ak sa nad ňou objavil most, teda ak platilo, že \(j_1 = j_n\).

A čo s pozíciou za druhou jamou? Je tam leming? Postupujme úplne rovnako. Ak by tam bol, tak postupne počul písmená \(j_{n-1}\) a \(j_n\). Tieto písmená sa ale musia zhodovať s prvými dvoma jamami, teda znakmi \(j_1\) a \(j_2\).

Vyriešme teraz túto úlohu všeobecne. Označme si \(j[zac:kon]\) slovo, ktoré dostaneme zo slova \(j\) ak vyberieme iba písmená na pozíciách \(zac\)\(kon\). Napríklad ak j = UURUURUU, tak j[2:5] = URUU a j[4:8] = UURUU. Potom platí, že za \(i\)-tou jamou je leming práve vtedy, ak j[n-i+1:n] (písmená, ktoré leming počul) a j[1:i] (jamy, nad ktorými musel prejsť) sú rovnaké.

V príklade na obrázku, kde je j = UURUURUU sa teda lemingovia nachádzajú za prvou jamou (j[1:1] = U = j[8:8]), druhou jamou (j[1:2] = UU = j[7:8]) a piatou jamou (j[1:5] = UURUU = j[4:8]). A samozrejme aj pred prvou, lebo tam je leming v podstate vždy.

Mimochodom, druhý možný prístup je, že ak poznáme všetky posledné písmená, ktoré boli vyslovené, môžeme jednoducho pochod lemingov odsimulovať a dostať sa tak k rovnakému riešeniu.

Hľadanie vzorky v texte

Pre zaujímavosť, všetko v tomto vzoráku úzko súvisí s hľadaním vzorky v texte. Úlohe, v ktorej máme v dlhom texte nájsť nejakú všetky výskyty kratšej vzorky, slova. V podstate klasická možnosť Find rôznych editorov. Dokonca, hrátky s lemingami vedú k optimálnemu riešeniu.

Základná myšlienka je rovnaká. Ak by sme simulovali pochod lemingov nad jamami s písmenami vzorky, ľahko nájdeme jej výskyty. Simulovať pohyb všetkých lemingov je však pomalé, oveľa jednoduchšie je sledovať len jedného, ktorý je najbližšie k cieľu. Tento leming sa totiž posunie dopredu ak sa ďalšie písmeno textu zhoduje s jamou, ktorá je pred ním, alebo padne a umrie. Jediný problém nastane, ak leming umrie. V tomto momente totiž musíme nájsť najbližšieho živého leminga, aby sme ho začali sledovať.

A pri tom vieme využiť podúlohu c. Vidíme totiž, že zo znalosti pozície niektorého leminga vieme zistiť, kde sa nachádzajú tí za ním. A dokonca to nesúvisí s textom, ktorý čítame, pretože ten je určený pozíciou nami sledovaného leminga. Túto informáciu si teda vieme vypočítať ešte pred tým, ako začneme čítať text. V podstate nás bude pre každú pozíciu zaujímať: Ak je na tejto pozícii živý leming, kde naľavo od neho je najbližší živý leming?

S touto informáciou je potom posúvanie leminga počas čítania textu jednoduché. Ak ide dopredu, tak ho proste posunieme a ak umrie, tak sa pozrieme do našej predpočítanej tabuľky aby sme zistili, ktorý leming ho nahradí.

Samozrejme, samotný algoritmus je ešte o niečo komplikovanejší, existuje napríklad spôsob ako si túto tabuľku predpočítať naozaj efektívne bez toho, aby sme simulovali celý proces, toto sú však hlavné myšlienky, ktoré sa v riešení používajú. V prípade, že by ste si chceli o tom prečítať viac, tento algoritmus sa volá KMP (podľa tvorcov Knuth, Morris a Pratt) a článok o ňom nájdete aj v KSP kuchárke.

Podúloha d.

Situácia, ktorú potrebujeme vyriešiť, vyzerá nasledovne:

Nepoznáme písmená v jamách a jediné čo vieme sú pozície dvoch najpravejších lemingov. Ako zistíme, či sú lemingovia aj za siedmou a jedenástou jamou? Postup z podúlohy c. nám nepomôže, pretože nepoznáme písmená a teda nevieme odsimulovať ako sa lemingovia hýbali.

Uvedomme si, že situácie sa v lemingove opakujú a sú závislé iba na tom, aké písmená sme čítali. To znamená, že vždy keď prečítame celé slovo z jám a leming sa ocitne pred cieľom, teda za sedemnástou jamou, bude najbližšie k nemu leming za dvanástou jamou. Pozícia leminga pred cieľom totiž presne určuje čo počul leming za jamou 12 a tieto písmená sú stále rovnaké. Dokonca, z podúlohy c. vieme povedať, že ak si slovo z jám označíme S, tak platí S[1:12] = S[6:17].

Predstavme si, že situáciu z obrázku chceme zopakovať, pokúsime sa teda leminga za 12 jamou dostať na koniec. Najbližších päť písmen budeme teda hovoriť presne to, čo potrebuje, aby sa mu vytvoril most. Nevadí, že tie písmená teraz nepoznáme, nám stačí len to, že by sme to vedeli spraviť, keby sme ich poznali, teda že taká možnosť existuje.

V okamihu ako sa tento leming ocitne pred cieľom, tak za 12 jamou sa musí objaviť nový leming. Lebo ak je na konci, tak situácia sa musí opakovať s tým, čo vidíme na pôvodnom obrázku. Z otáznikov sa teda po piatich písmenách vynoril leming a postavil sa za 12 jamu. Kde však tento leming začínal? Vráťme sa o 5 krokov späť a tento leming stojí za 7 jamou. Ukázali sme si teda, že za siedmou jamou sa musel nachádzať leming. Dokonca, rovnakým postupom by sme vedeli odôvodniť, že aj za druhou jamou je leming – to bude totiž ten, ktorý sa po piatich písmenách postaví za siedmu jamu.

Môže byť leming za jamou 11? Pozrime sa, čo by to znamenalo, keby tam bol. Posledné prečítané písmeno muselo vytvoriť most nad jamami 12 aj 11, obaja totiž prežili a prešli po nej. Teda S[11] = S[12]. Vráťme sa teda o krok dozadu. Opäť musí platiť, že posledné písmeno vytvorilo most aj nad 11 aj nad 10 jamou, teda S[10] = S[11]. Tento postup však môžeme opakovať až do úplného začiatku. Z toho vyplýva, že všetky písmená v jamách 1 až 12 musia byť rovnaké. Na začiatku sme si však uvedomili, že S[1:12] = S[6:17], tým pádom S[12] = S[17], S[11] = S[16]S[1] = S[6]. Teda nie len prvých 12 písmen v jamách je rovnakých, všetky písmená sú rovnaké.

To však nie je možné, ak by totiž všetky písmená boli rovnaké, tak ak sa nejaký leming dostane až k cieľu, za každou jednou jamou sa musí nachádzať leming. Nestalo by sa teda, že za jamami 13 až 16 by žiadni neboli. Tým pádom, chyba musí byť v našom predpoklade. Za jamou 11 sa leming nemôže nachádzať.

Podúloha e.

Ostáva nám nájsť najkratšiu periódu zadaného reťazca. Perióda dĺžky \(p\) je definovaná tak, že každá dvojica písmen vzdialených od seba o \(p\) písmen je rovnaká. Teda musí platiť, že S[i] = S[i+p] pre všetky možné \(i\), čo sú všetky čísla od 1 po \(n-p\). To sa však dá napísať aj tak, že S[1:n-p] = S[p+1:n]. Takýto zápis sme však už niekde videli nie? Toto bol presne zápis, ktorým sme zisťovali, či sa za jamou \(n-p\) nachádza leming, ak je ďalší leming pri cieli.

Vidíme teda, že z pozícií dvoch posledných lemingov vieme určiť periódu celého textu. Stačí si odsimulovať pochod lemingov v prípade, že postupne čítame písmaná, ktoré sa nachádzajú nad jamami. Keď sa najpravejší leming nachádza pred domčekom, pozrieme sa, kde je k nemu najbližší živý leming. Počet jám medzi nimi udáva periódu celého reťazca. Táto perióda je navyše najkratšia možná.

Napriek tomu ako jednoducho správanie lemingov vyzeralo, pomohlo nám odvodiť si pomerne široké závery o reťazcoch všeobecne. Nielenže sme dokázali hľadať vzorku v texte, dokázali sme dokonca zistiť aj periódu zadaného reťazca.

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.