Naloga prihaja s tekmovanja Bober 2014/15. (Hvala, Kanada.)

Kolona strumnih bobrov koraka prek terena, na katerem so zajci neprijazno skopali nekaj lukenj. Tule, recimo, so prišli do luknje globine 3.

Bobri storijo tole: prvi bober skoči vanjo, drugi nanj in tako naprej, dokler ni luknja polna.

Ostali bobri prečkajo luknjo.

Ko so na oni strani, se primerjo za repe in tako izvlečejo bobre, ki so v luknji, iz luknje.

Lukenj je lahko seveda več. Razdalje med luknjami so dovolj velike, da bobri nikoli ne prečkajo dveh lukenj hkrati.

Bobre bomo opisovali z nizi. V gornjem primeru bi bil to niz \"54321\"; številke (ali črke) so napisane od leve proti desni, tako da gre v luknjo najprej tisti bober, ki je na najbolj desnem mestu v nizu.

Ogrevalna naloga

Napiši funkcijo ena_luknja(bobri, globina), ki prejme niz, ki predstavlja zaporedje bobrov in globino luknje, čez katero bodo šli bobri. Funkcija mora vrniti niz, ki predstavlja zaporedje bobrov po prečkanju luknje.

Če je bobrov premalo in bodo ostali v luknji, naj funkcija vrne None.

Klic ena_luknja("54321", 3) mora vrniti niz "12354".

Klikni za rešitev Prve naloge ste se mnogi lotili s "simulacijo" in pridelali nekaj takega (no, nekaj bolj zapletenega - tole moje je jasnejša različica simulacije): 
python
def ena_luknja(bobri, globina):
    bobri = list(bobri)

    luknja = []
    while len(luknja) < globina and bobri:
        luknja.append(bobri.pop())

    if not bobri:
        return None
    while luknja:
        bobri.insert(0, luknja.pop())

    return "".join(bobri)
Niz z bobri najprej spremenimo v seznam (`bobri = list(bobri)`), da ga bomo lahko spreminjali. Nato pripravimo prazno luknjo in zmečemo vse bobre vanjo. Polnimo jo, dokler ni polna (`len(luknja) < globina`) in dokler je še kaj bobrov (`bobri`). Prazen seznam je neresničen; pogoj `bobri` bo torej neresničen, če bobrov zmanjka. V luknjo vedno pade najbolj desni bober, torej zadnji bober v seznamu. Za to je priročna metoda `pop`, ki vrne zadnji element seznama in ga mimogrede še pobriše. Nato izvlečemo bobre iz luknje. Če ni zunaj več nikogar, vrnemo `None`. Sicer pa dokler luknja ni prazna (`while luknja`) na začetek seznama bobrov z `insert` vrinemo zadnjega (predzadnjega, predpredzadnjega ... spet uporabimo `pop`) bobra iz luknje. Na koncu z `"".join(bobri)` zlepimo nize v seznamu bobri v niz in ga vrnemo. Tole je lepo in prav in poučno, vendar naj bi bila tole naloga iz rezanja seznamov. :) Da dobimo krajšo rešitev, moramo razmisliti, kaj se pravzaprav dogaja, ko gredo bobri čez luknjo. Desnih `globina` bobrov se obrne okrog in premakne na levo stran, tisti, levo od njih, pa gredo v nespremenjeneme vrstnem redu na desno. Desnih `globina` dobimo z `bobri[-globina:]`. Ker je to potrebno še obrniti, dodamo `[::-1]`. Rešitev je torej: 
python
def ena_luknja(bobri, globina):
    if globina < len(bobri):
        return bobri[-globina:][::-1] + bobri[:-globina]
Če je bobrov premalo, funkcija ne vrne ničesar, torej vrne `None`.

Obvezna naloga

Napiši funkcijo prek_lukenj(bobri, globine), ki prejme zaporedje bobrov in globine lukenj, prek katerih bodo bobri potovali. Vrniti mora zaporedje bobrov, ko prečkajo vse luknje.

Prečkanje na gornji sliki bi simulirali s klicem prek_lukenj("7654321", [4, 2, 3]). Kakšen niz mora vrniti, odkrijte sami. ;)

Klikni za rešitev Za drugo nalogo se moramo spomniti, da smo že napisali funkcijo `ena_luknja` in jo poklicati. Obstajajo študenti, ki se tega niso spomnili, in takšni so bili obsojeni (= takšni so se obsodili) na to, da so morali znotraj funkcije `prek_lukenj` znova napisati še celotno funkcijo `ena_luknja`, kar je bilo še posebej prijetno, če so le-to napisali v obliki kakšne zapletene simulacije. Poleg tega moramo popaziti, da lahko ta funkcija kdaj vrne `None`. V tem primeru bodisi vrnemo `None` (`return None` ali kar `return`), ali pa prekinemo zanko, pa bo `return bobri` vrnila `None`. 
python
def prek_lukenj(bobri, luknje):
    for globina in luknje:
        bobri = ena_luknja(bobri, globina)
        if bobri == None:
            break
    return bobri

Dodatna naloga

Napišite funkcijo anti_luknja(globine, bobrov). Njena argumenta so globine lukenj in število bober, ki bodo lezli prek njih. Funkcija naj vrne seznam globin lukenj, ki bi jih bilo potrebno skopati desno od teh lukenj, da bi se vrstni red bobrov spremenil nazaj v prvotnega.

Dodatna naloga je zanimiva tudi, če se vam je ne da sprogramirati: če želite, preprosto napišite rešitev v slovenščini, ne Pythonu.

Klikni za rešitev Tretja naloga pa je bolj za razmišljanje kot za programiranje. Najpreprostejša rešitev je, da bobre pošljemo nazaj. Najprej jim nastavimo luknjo globine `n - 1`, da obrnemo njihov vrstni red. Nato jih pošljemo nazaj prek vseh lukenj, na koncu pa ponovno obrnemo. 
python
def anti_luknje(luknje, n):
    return [n - 1] + luknje[::-1] + [n - 1]
Last modified: Tuesday, 26 February 2019, 6:56 PM