1. Točni vlaki Slovenskih železnic (hipotetični, miselni eksperiment)

Napiši funkcijo tocni(redi, dejanski), ki prejma dva seznama seznamov. Vsak element se nanaša na en vlak; istoležni elementi se nanašajo na iste vlake. Prvi seznam vsebuje predvidene čase prihoda na postaje, drugi pa dejanske prihode. Časi so podani v minutah od polnoči. Funkcija naj vrne število vlakov, ki niso na nobeni postaji zamujali več kot dvajset minut (kar uporabniki Slovenskih železnic štejemo za praktično točen prihod). Klic

tocni([[570, 590, 616, 620], [1200, 1500], [800, 900, 1000], [700, 800]],
      [[570, 611, 622, 630], [1200, 1510], [810, 910, 1000], [800, 900]]))

vrne 2: "točna" sta bila drugi in tretji vlak. Prvi in četrti sta vsaj enkrat zamudila več kot 20 minut.

Namig: če želiš, si lahko napišeš tudi pomožno funkcijo tocen(red, dejansko), ki prejme seznam za en sam vlak in vrne True, če je bil točen in False, če je kje zamudil za več kot 20 minut. (Če je ne napišeš, ignoriraj teste zanjo.)

Rešitev

Ubogajmo, napišimo funkcijo tocen. Gremo čez vse pare predvidenih in dejanskih časov; če naletimo na zamudo, vrnemo False, sicer, na koncu, po zanki, vrnemo True.

def tocen(red, dejansko):
    for cas_red, cas_dejansko in zip(red, dejansko):
        if cas_dejansko - cas_red > 20:
            return False
    return True

Naprej je preprosto: gremo čez vse vlake in za vsakega, ki je bil točen, prištejemo 1.

def tocni(red, dejansko):
    tocnih = 0
    for r, d in zip(red, dejansko):
        if tocen(r, d):
            tocnih += 1
    return tocnih

Če znamo uporabljati izpeljane sezname (in če vemo, da je False isto kot 0 in True isto kot 1), sta funkciji lahko tudi takšni:

def tocen(red, dejansko):
    return all(d - r <= 20 for r, d in zip(red, dejansko))

def tocni(redi, dejanski):
    return sum(tocen(red, dejansko) for red, dejansko in zip(redi, dejanski))

Brez dodatne funkcije je malo bolj zoprno. Ena od za silo elegantnih rešitev je else po for:

def tocni(red, dejansko):
    tocnih = 0
    for red1, dejansko1 in zip(red, dejansko):
        for predviden, prisel in zip(red1, dejansko1):
            if prisel > predviden + 20:
                break
        else:
            tocnih += 1
    return tocnih

Obstajajo pa seveda tudi druge.

Kdor je prelen za pisanje dodatne funkcije, zna pa uporabljati izpeljane sezname, pa zbaše vse skupaj v

def tocni(red, dejansko):
    return sum(
        all(prisel <= predviden + 20 for prisel, predviden in zip(pri, pre))
        for pri, pre in zip(red, dejansko)
    )

2. Enake linije

Dve liniji sta "enaki", če vsebujeta iste postaje ali pa imata isto začetno in končno postajo ter ena od njiju vsebuje vse postaje, ki jih vsebuje druga; v tem primeru je druga hitrejša različica prve. Noben vlak ne ustavi večkrat na isti postaji.

Napiši funkcijo enaki(linija1, linija2), ki prejme seznama imen postaj in vrne True, če sta liniji enaki in False, če ne. Funkcija naj ignorira vrstni red (razen prve in zadnje postaje, ki morata biti enaki): liniji Ljubljana - Sevnica - Trebnje - Novo mesto in Ljubljana - Trebnje - Sevnica - Novo mesto sta enaki.

Rešitev

Študent naj bi razmislil, kaj pomeni, da ima ena linija vse postaje, ki jih ima druga: gre za podmnožice. Seznama torej pretvorimo v množice in preverimo ali je ena podmnožica druge oziroma obratno. Poleg tega pa preverimo še prvo in zadnjo postajo, torej:

def enaki(linija1, linija2):
    return linija1[0] == linija2[0] \
        and linija1[-1] == linija2[-1] \
        and (set(linija1) <= set(linija2)
             or set(linija2) <= set(linija1))

Ne spreglejte oklepajev. Imamo tri stvari: prvi postaji sta enaki IN zadnji sta enaki IN (prva je podmnožica druge ali pa je druga podmnožica prve). Brez teh oklepajev rešitev ni pravilna, ker ima and prednost pred or.

3. Kopičenje zamud

Napiši funkcijo zamujenih(vlak, cakajoci), ki prejme niz s kodo vlaka, ki zamuja in slovar, katerega ključi so kode vlakov, vrednosti pa množice vseh vlakov, ki morajo čakati, kadar ta vlak zamuja. Funkcija naj vrne število vseh zamujenih vlakov. Pri tem upoštevaj, da bodo zamujali tudi vlaki, ki čakajo zamujene vlake, ki čakajo zamujene vlake ...

V primeru iz testov je tako: če zamuja LP3682, bosta zaradi tega zamujala tudi LP8524 in IC021. Ker zamuja LP8524 bodo morali čakati tudi EN123, IC521 in LP6316, zaradi IC021 pa LP222 in IC204. Zaradi EN123 ne čaka nihče, zaradi IC521 pa ... in tako naprej. Skupno zaradi LP3682 zamudi 14 vlakov.

Vlaki se nikoli ne čakajo v krogu: če A čaka B in B čaka C, potem ne B ne C ne čakata na A.

Rešitev

Vrniti morate velikost "rodbine vlakov" - kar je prva naloga iz rekurzije, ki smo jo delali na predavanjih...

def zamujenih(vlak, cakajoci):
    zamud = 1
    for vlak1 in cakajoci[vlak]:
         zamud += zamujenih(vlak1, cakajoci)
    return zamud

Malo hitreje pa je tako:

def zamujenih(vlak, cakajoci):
    return 1 + sum(zamujenih(vlak1, cakajoci) for vlak1 in cakajoci[vlak])

Kdor ve kaj več, je opazil, da ni tako preprosto: lahko bi se zgodil, da bi na A čakala B in C, potem pa bi na oba, torej na B in na C, čakal nek vlak D. Tale program bi D štel dvakrat. To bi lahko rešili tako, da bi namesto preštevanja našteli vsa imena v rodbini in pogledali, koliko jih je.

4. Raztegnjen vozni red

V želji odpraviti zamude bodo Slovenske železnice preprosto raztegnile vozni red: vsi časi bodo povečani za 10 %. (Vlake, ki bi zaradi tega odpeljali naslednji dan, pa bodo preprosto ukinili.)

SŽ shranjujejo čase v obliki parov (terk) (ure, minute), na primer (11, 48).

Napiši funkcije:

Rešitev

Tole je le naloga, ki preverja, ali znate napisati par funkcij in v njih malo računati.

def v_minute(cas):
    return cas[0] * 60 + cas[1]

def v_cas(minute):
    return minute // 60, minute % 60

def raztegni(cas):
    return v_cas(round(1.1 * v_minute(cas)))

Vse skupaj

Rešitev celotnega izpita (brez ekstra trikov) je torej takšna:

# 1

def tocen(red, dejansko):
    for cas_red, cas_dejansko in zip(red, dejansko):
        if cas_dejansko - cas_red > 20:
            return False
    return True

def tocni(red, dejansko):
    tocnih = 0
    for r, d in zip(red, dejansko):
        if tocen(r, d):
            tocnih += 1
    return tocnih

# 2

def enaki(linija1, linija2):
    return linija1[0] == linija2[0] \
        and linija1[-1] == linija2[-1] \
        and (set(linija1) <= set(linija2)
             or set(linija2) <= set(linija1))

# 3

def zamujenih(vlak, cakajoci):
    zamud = 1
    for vlak1 in cakajoci[vlak]:
         zamud += zamujenih(vlak1, cakajoci)
    return zamud

# 4

def v_minute(cas):
    return cas[0] * 60 + cas[1]

def v_cas(minute):
    return minute // 60, minute % 60

def raztegni(cas):
    return v_cas(round(1.1 * v_minute(cas)))