Dirke na Čopovi

Ko sem na forum pisal neko sporočilo o kolesarjenju pa Manhattnu, me je zgrabilo domoljubje in se sem odločil, da bi enkrat za spremembo pripravil tudi nalogo o kolesarjenju po Ljubljani.

V videu o vedenju kolesarjev nas je MOL poučil, da je osnovno opravilo ljubljanskih kolesark divjanje med pešci. (V tej nalogi bom govoril o kolesarkah, čeprav MOL v svojem videu kritizira samo kolesarje, kolesarke pa ignorira, kot da nismo v 21. stoletju.) To je popolnoma res! Tako se po zadnjih statistikah vede 98 % ljubljanskih kolesark in le 2 % takšno vedenje obsojata. (Obstaja možnost, da se je Angelca zmotila pri izpolnjevanju Excela in zamenjala celici, vendar to za našo nalogo niti ni pomembno.)

Kolesarke se torej dobivajo vsako sredo ob 16.00 na dirki, na katerih se spusté od Pošte do ciljne črte na Prešernovem trgu. Vsakič zabeležijo, kdo je zmagal in kdo so bile poraženke. Vrstni red poraženk ni zabeležen, prav tako nihče ne meri časov.

Iz obeh dirk skupaj lahko sklepamo tudi, da je Jana hitrejša od Rezke, čeprav nista nikoli sodelovali na isti tekmi. Vemo namreč, da je Jana hitrejša od Lize, Liza pa od Rezke.

Obvezna naloga

Nekatere od teh funkcij bodo skoraj gotovo rekurzivne (če si hočete dobro), nekatere pa skoraj gotovo ne bodo (če si hočete dobro).

hitrejsa(prva, druga, razmerja)

Rešitev

Na predavanjih smo se igrali z rodbino in se spraševali, ali je v rodbini osebe prva kakšna oseba z imenom druga. Tole je podobno, samo da nihče ni hitrejši od sebe (česar testi sicer ne preverjajo).

Pravilna rešitev je torej, da je prva hitrejša kot druga, če jo je kdaj premagala ali pa je med tistimi, ki jih je premagala prva tudi kakšna tretja oseba, ki je hitrejša kot druga.

def hitrejsa(prva, druga, razmerja):
    if druga in razmerja[prva]:
        return True
    for tretja in razmerja[prva]:
        if hitrejsa(tretja, druga, razmerja):
            return True
    return False

Če poznamo any in generatorje pa

def hitrejsa(prva, druga, razmerja):
    return druga in razmerja[prva] \
        or any(hitrejsa(tretja, druga, razmerja)
               for tretja in razmerja[prva])

Sovražnik rekurzije pa se rekurziji izogne s postopkom, ki mu boste v drugem letniku rekli iskanje v širino:

def hitrejsa(prva, druga, razmerja):
    pocasnejsi = list(razmerja[prva])
    for kolesar in pocasnejsi:
        if kolesar == druga:
            return True
        pocasnejsi += razmerja[kolesar]
    return False

skalpi(kolesarka, razmerja)

Rešitev

Vsaka kolesarka pobere svoj skalp, poleg tega pa skalpe vseh, ki so jih pobrali tisti, ki jih je kdaj premagala.

def skalpi(kolesarka, razmerja):
    skalp = {kolesarka}
    for kolesar in razmerja[kolesarka]:
        skalp |= skalpi(kolesar, razmerja)
    return skalp

Tole je popolnoma enako zbiranju vseh imen članov rodbine. Ta, ki se mu je pri tem zatikalo, naj si prebere zapiske.

Enovrstična rešitev zahteva malo več razumevanja Pythona. Spodnje naj razume, kdor hoče.

def skalpi(kolesarka, razmerja):
    return {kolesarka}.union(*(skalpi(kolesar, razmerja) for kolesar in razmerja[kolesarka]))

izlocanje(kandidatke, razmerja)

Rešitev

Tole pa ni naloga iz rekurzije.

Lepa rešitev je

def izlocanje(kandidatke, razmerja):
    return {kolesarka
            for kolesarka in kandidatke
            if not any(hitrejsa(druga, kolesarka, razmerja) for druga in kandidatke)}

Malo manj lepa:

def izlocanje(kandidatke, razmerja):
    ostanejo = set()
    for kolesarka in kandidatke:
        if not any(hitrejsa(druga, kolesarka, razmerja) for druga in kandidatke):
            ostanejo.add(kolesarka)
    return ostanejo

Kdor res ne mara generatorjev, zna pa vsaj Python, napiše

def izlocanje(kandidatke, razmerja):
    ostanejo = set()
    for kolesarka in kandidatke:
        for druga in kandidatke:
            if hitrejsa(druga, kolesarka, razmerja):
                break
        else:
            ostanejo.add(kolesarka)
    return ostanejo

Kdor noče programirati v Pythonu, pa si pomaga z zastavico:

def izlocanje(kandidatke, razmerja):
    ostanejo = set()
    for kolesarka in kandidatke:
        nepremagana = True
        for druga in kandidatke:
            if hitrejsa(druga, kolesarka, razmerja):
                nepremagana = False
                break
        if nepremagana:
            ostanejo.add(kolesarka)
    return ostanejo

Dodatna naloga

Napiši funkcijo dokazov(prva, druga, razmerja), ki vrne število dokazov, da je prva hitrejša kot druga. Če prva ni hitrejša kot druga (ker razmerje ni znano ali pa je celo počasnejšia), funkcija vrne 0.

Rešitev

Naloga je v bistvu preprosta, le prav jo moramo razmisliti.

def dokazov(prva, druga, razmerja):
    return (druga in razmerja[prva]) \
           + sum(dokazov(tretja, druga, razmerja) for tretja in razmerja[prva])

Še bolj dodatna naloga

Rešitev

(Ni jih bilo, testov. Preveč dela, preprosto pozabil na pol-obljubo.)

Naloga zahteva, da kolesarke topološko uredimo (glej: topological sorting). Postopkov je več, tule pa smo si, priročno, pripravili funkcijo izlocanje, s katero je rešitev čisto kratka: v vsakem koraku poiščemo kolesarke, ki so hitrejše od vseh ostalih. Te dodamo v urejen seznam in jih odstranimo iz množice "vseh ostalih".

def uredi(razmerja):
    kolesarke = set(razmerja)
    urejene = []
    while kolesarke:
        hitre = izlocanje(kolesarke, razmerja)
        urejene += hitre
        kolesarke -= hitre
    return urejene