Krožišča

Testi

Testi: testi-krozisca.zip

Naloga

Otroci so na nekem tekmovanju reševali tole nalogo.

V mestu krožišč avtomobilska navigacija ne daje navodil, kot

• na naslednjem krožišču zavijte na četrti izvoz,
• na naslednjem krožišču zavijte na prvi izvoz,
• na naslednjem krožišču zavijte na drugi izvoz.

Namesto tega pove kar zaporedje izvozov. Če smo v A in so navodila 4 1 2, bomo peljali, kot kaže slika.

Pri katerem izvozu bomo končali, če začnemo pri A in namesto gornjemu zaporedju sledimo zaporedju izvozov 3 1 3 2 3?

Otroci so to reševali ročno, mi pa bomo programirali. Da bo lažje, si bomo vsa krožišča in krajišča oštevilčili, takole.

Za oceno 6

1. Napiši funkcijo preberi(ime_datoteke), ki prejme ime datoteke in vrne zemljevid. Datoteka je sestavljena tako, da prva vrstica ustreza prvemu krožišču (ali uvozu/izvodu), druga drugemu, tretje tretjemu in tako naprej. Vsaka vrstica vsebuje številke krožišč, s katerimi je posamično krožišče povezano. Krožišča so našteta po vrsti, začenši s poljubnim.

   Gornjemu zemljevidu ustreza datoteka

   3
   4
   1 8 7 6 4
   5 2 3 6
   10 4 11
   11 4 3
   3 8 11
   3 16 9 7
   11 8 16 14
   5 11 13
   10 5 6 7 9 14
   13
   12 10 14
   13 11 9 16
   16
   14 9 8 15
   

   Četrta vrstica, recimo, vsebuje 5 2 3 6, ker je četrto križišče povezano s križišči 5, 2, 3 in 6.

   Funkcija naj vrne slovar, katerega ključi so številke križišč, pripadajoče vrednosti pa seznami številk (int!) sosednjih križišč. Funkcija naj "preobrne" seznam ta, da se bodo začeli z najmanjšo številko, križišča pa morajo biti še vedno po vrsti. Tako bo ključu 4 pripadal element [2, 3, 6, 5] (in ne [5, 2, 3, 6], ko bi direktno prebrali iz datoteke, in tudi ne [2, 3, 5, 6], kot bi dobili, če bi seznam le uredili).

Rešitev

Prva funkcija, preberi, je imela nenačrtovan kamen spotike. Brez njega bi bila rešitev takšna.

def preberi(ime_datoteke):
    povezave = {}
    for i, vrstica in enumerate(open(ime_datoteke)):
        povezave[i + 1] = [int(x) for x in vrstica.split()]
    return povezave

Pač beremo iz datoteke in zlagamo v slovar. S par triki, ki olajšajo delo.

Najprej, datoteke ne beremo takole

    vrstice = open(ime_datoteke).read().split("\n")
    for vrstica in vrstice:

Iz dveh razlogov. Prvi je ta, da z

    for vrstica in open(ime_datoteke):

z veliko manj besedami dosežemo isto (z veliko manjšo porabo pomnilnika, kar pa se pri tako drobcenih datotekah kot je naša, seveda ne pozna). Pomembnejši razlog pa je, da split("\n") ne bo vedno dosegel tega kar želimo: če se zadnja vrstica konča z \n (kar se po nekih pravilih marsikdaj mora), jih bo, če uporabimo split("\n") sledila še ena prazna vrstica. Če beremo z for vrstica in open(ime_datoteke) pa te težave ni.

Če že moramo komplicirati, potem namesto split("\n") pokličemo splitlines().

Naslednji trik: potrebujemo številke vrstic. Lahko bi pisali

    stevilka = 0
    for vrstica in open(ime_datoteke):
        stevilka += 1
        povezave[stevilka] = [... ...]

Vendar tega ne počnemo, ker nam točno to (le z enim indeksom zamika) priskrbi enumerate.

Ker uporabljamo enumerate, ki seveda začne šteti od 0, je ključ v slovarju je za 1 večji od številke vrstice (zato povezave[i + 1]).

Končno, vrstico razbijemo s split() (ne split(" ")! ta bo delal težave, če bo v vrstici slučajno več zaporednih presledkov) in vsako številko posebej pretvorimo v int. Torej [int(x) for x in vrstica.split()].

Do sem - relativno preprosto. Naprej še preprosteje, le da mnogi niso videli te preprostosti.

Krožišče 14 ima izvoze v križišča 13, 11, 9 in 16. Pomembno je, da so našteti po vrsti, vseeno pa je, s katero številko začnem. Pisali bi lahko tudi 11, 9, 16, 13 ali 9, 16, 13, 11 ali 16, 13, 11, 9. Vse je pravilno (narobe pa je, recimo 11, 16, 9, 13, saj si krožišča ne sledijo v takšnem vrstnem redu).

Ker je zoprno pisati teste, kadar lahko funkcija vrne različne pravilne odgovore (pravzaprav meni ni zoprno napisati testov, temveč je vam zoprno razumeti tako sestalvjene teste), sem razmišljal, da bo najpreprosteje, da predpišem, s katero številko se mora začeti seznam izvozov iz vsakega krožišča. Logični opciji sta dve: enak vrstni red kot v datoteki ali pa tako, da se začne z najmanjšo. Brez posebnega razmišljanja sem se odločil za drugo možnost - morda tudi zato, da vam naložim še drobno dodatno nalogo.

Ta se ni izkazala za tako drobno. Večina mailov se je sukala okrog nje.

Najpogostejša rešitev, ki sem jo videl, je bila tale. Preberemo 13 11 9 16. Preverimo, ali je najmanjša številka na začetku. Če ni, jo prestavimo na konec. Ponavljamo.

Torej nekaj takega

    while min(sosedi) != sosedi[0]:
        sosedi = sosedi[1:] + [sosedi[0]]

V študentskih programih sem videl tudi različice s pop, ki iz različnih skrivnostnih razlogov delujejo, včasih pa tudi ne.

A vse to je le zapletanje. Razmislimo, kaj počne gornji program ali, še boljše, kaj je potrebno storiti. Recimo, da imamo nek daljši seznam krožišč, [5, 9, 7, 3, 2, 4, 8]. Obrniti ga je potrebno v [2, 4, 8, 5, 9, 6, 3]. Kako to naredimo? Samo vse, kar je pred najmanjšim elementom, moramo prestaviti na konec. Novi seznam bo torej sestavljen iz najmanjšega elementa in vsega za njim, sledilo pa mu bo, vse, kar je bilo prej pred najmanjšim elementom.

Tako dobimo

def preberi(ime_datoteke):
    povezave = {}
    for i, vrstica in enumerate(open(ime_datoteke)):
        sosedi = [int(x) for x in vrstica.split()]
        najm = sosedi.index(min(sosedi))
        povezave[i + 1] = sosedi[najm:] + sosedi[:najm]
    return povezave

Tule smo uporabiti (prepovedano?) metodo index. Zakaj jaz lahko, vam pa ne pustim? Zato: index vrne prvo pojavitev podanega elementa v seznamu. To bo res v redu le takrat, kadar se element dejansko pojavi le enkrat. Če se večkrat ... Če bi jaz sestavil metodo index, bi jo napisal tako, da bi v primeru, da se element pojavi večkrat, javila napako, namesto, da vrne prvo pojavitev.

Ampak tu ni problema: ker med vsakim parom krožišč obstaja le ena povezava, je vsak element unikaten.

Še drug problem z index je, da običajno tako ali tako poznamo - ali pa bi vsaj lahko poznali indeks elementa, recimo tako, da bi v zanki uporabili enumerate. Indeksa najmanjšega elementa pa ne poznamo in ga moramo v resnici poiskati.

(nadaljevanje naloge)

2. Napiši funkcijo mozna_pot(pot, zemljevid), ki prejme seznam številk krožišč/krajišč in zemljevid. Vrne naj True, če je takšno pot možno prevoziti, in False, če ne.

   Pot je možno prevoziti, če se začne in konča s končno povezavo (prepoznate jo po tem, da je povezana le z enim krožiščem), če vmes ni končnih povezav, če se nobeno krožišče ne ponovi (iz krožišča 6 ne moremo zapeljati v krožišče 6) in če so vsa krožišča na poti dejansko povezana.

Rešitev

Preveriti je potrebno, da se

• začne s povezavo, ki ima le eno krožišče, len(zemljevid[pot[0]]) == 1,
• konča s povezavo, ki ima le eno krožišče, len(zemljevid[pot[-1]]) == 1,
• da imajo vsa vmes, torej na pot[1:-1] več kot eno povezavo, all(len(zemljevid[x]) > 1 for x in pot[1:-1]) in
• da so vsi pari zaporednih krožišč med seboj povezani, all(y in zemljevid[x] and x != y for x, y in zip(pot, pot[1:])).

Zloženo skupaj:

def mozna_pot(pot, zemljevid):
    return len(zemljevid[pot[0]]) == 1 \
        and len(zemljevid[pot[-1]]) == 1 \
        and all(len(zemljevid[x]) > 1 for x in pot[1:-1]) \
        and all(y in zemljevid[x] and x != y for x, y in zip(pot, pot[1:]))

(nadaljevanje naloge)

3. Napiši funkcijo hamiltonova(pot, zemljevid), ki pove (True ali False), če je pot Hamiltonova. Pot je Hamiltonova, če je možna (prejšnja funkcija), gre prek vseh krožišč in to prek vsakega natančno enkrat.

Rešitev

Pot mora

• biti možna, mozna_pot(pot, zemljevid),
• vsako vozlišče se mora pojaviti le enkrat, torej mora biti velikost množice vozlišče enaka dolžini seznama, len(set(pot)) == len(pot),
• množica vozlišč mora biti enaka množici vseh vozlišč, ki imajo več kot eno povezavo, set(pot[1:-1]) == {x for x, y in zemljevid.items() if len(y) > 1}.

Torej:

def hamiltonova(pot, zemljevid):
    return mozna_pot(pot, zemljevid) \
        and len(set(pot)) == len(pot) \
        and set(pot[1:-1]) == {x for x, y in zemljevid.items() if len(y) > 1}

Za oceno 7

Napiši funkcijo navodila(pot, zemljevid), ki prejme zaporedje krožišč in vrne navodila (seznam števil), ki povedo, kako prevoziti to pot. Pot bo vedno možna.

Klic navodila([1, 3, 6, 4, 2], zemljevid) mora vrniti [3, 2, 2]: če začnemo v 1, prispemo v 3, kjer moramo zaviti na 3. izvoz, znajdemo se na 6, kjer gremo na 2. izvoz, pridemo v 4, kjer gremo spet na 2. izvoz pa smo na 2.

Namig: naloga je precej lažja, kot je morda videti. Najlažje jo je rešiti tako, da opazuješ trojke. Recimo, da greš iz 6 v 11 v 10. Lahko poveš, na kateri izvoz bo šel v 11? Veš, kje boš prišel noter in kje ven, ne? To, s katero številko se začne naštevanje v seznamu sosedov, je pravzaprav nepomembno, pomembna je le razlika. In kadar so stvari krožne, utegne priti prav ostanek po deljenju, ki se lepo vede tudi pri negativnih številih: -2 % 5 je enako 3 (če bi moral iti dva izvoza v napačni smeri, je pri petkrakem križišču to isto kot trije v pravi).

Naloga je celo tako lahka, da jo lahko, ne da bi se pretegnili, rešimo v eni sami vrstici.

Rešitev

Najprej poglejmo le en korak. Križišče 11 je povezano s križišči [5, 6, 7, 9, 14, 10]. (Ali pa z [7, 9, 14, 10, 5, 6], saj je vseeno.) Recimo, da moramo odtod oditi v križišče 14. Na kateri izvoz moramo?

Naivno bi rekli, da na četrtega, saj je [5, 6, 7, 9, 14, 10].index(14) enako 4. (Spet smemo mirno uporabiti indeks, saj, kot prvo, vsak element nastopa le enkrat in, kot drugo, v resnici ne vemo, kje je element in ga moramo poiskati.) Vendar to očitno ne bo čisto dobro, saj bi lahko isto krožišče opisali tudi z [7, 9, 14, 10, 5, 6] in v tem primeru bi morali zapeljati na izvoz 2.

"Garmin" nam pove nekaj v slogu "na drugem izvozu zavijte desno". Očitno je pomembno tudi, kje smo vstopili v krožišče. Če smo prišli s krožišča 5, potem gremo v resnici na četrti izvoz. Če s križišča 7, gremo na drugega. Če s križišča 9, na prvega.

Pa recimo, da vemo, s katerega križišča smo prišli, na katerem smo in v katerega gremo. Imenujmo jih prejsnje, trenutno in naslednje. Trenutno vozlišče potrebujemo samo zato, da dobimo seznam povezav; tako bo sosedi = zemljevid[trenutno] enak, recimo [5, 6, 7, 9, 14, 10]. V tem seznamu poiščemo zaporedno številko prejšnjega in naslednjega ter ju odštejemo, pa vemo, na kateri izvoz moramo; zanima nas torej sosedi.index(naslednje) - sosedi.index(prejsnje). Če smo prišli s križišča 7 (povezava z indeksom 2) in gremo na 14 (povezava z indeksom 4), moramo iti na 4 - 2 = 2, se pravi drugi izhod.

Kaj pa obratno? Če smo prišli s 14 in gremo na 6? Po gornji formuli moramo iti na -2 izhod. Ker na krožišču ne smemo voziti v napačno smer, bomo šli v pravo. Celo križišče ima 6 izhodov. Prevoziti jih moramo 6 - 2 = 4, pa bomo na želenem izhodu.

Če je torej rezultat manjši od 0, mu moramo prišteti število vseh povezav. Gre pa tudi hitreje: izračunamo ostanek po deljenju s številom povezav. 2 % 6 bo še vedno 2, -2 % 6 pa bo 4.

Zdaj pa to izvedimo za vsa krožišča na poti, razen prvega in zadnjega.

def navodila(pot, zemljevid):
    preskoki = []
    for i in range(1, len(pot) - 1):
        prejsnje, trenutno, naslednje = pot[i - 1], pot[i], pot[i + 1]
        povezave = zemljevid[trenutno]
        preskoki.append((povezave.index(naslednje) - povezave.index(prejsnje)) % len(povezave))
    return preskoki

Tokrat nimamo range(len(pot)), temveč odbijemo prvo in zadnje, saj tam ne dajemo navodil. Potem pa za vsako trojko zaporednih vozlišč na poti storimo natančno, kar smo opisali zgoraj.

Že dolgo vemo, da pare zaporednih vozlišč dobimo z zip(pot, pot[1:]). (To je tako pogosta zadeva, da ima jezik Kotlin, "izboljšana Java", kar funkcijo zipWithNext.) Vendar tu ne potrebujemo zaporednih parov vozlišč temveč zaporedne trojke vozlišč. Torej zip(pot, pot[1:], pot[2:]).

Tako dobimo lepšo rešitev.

def navodila(pot, zemljevid):
    preskoki = []
    for prejsnje, trenutno, naslednje in zip(pot, pot[1:], pot[2:]):
        povezave = zemljevid[trenutno]
        preskoki.append((povezave.index(naslednje) - povezave.index(prejsnje)) % len(povezave))
    return preskoki

To pa je klasičen vzorec, ki ga opišemo z izpeljanim seznamom.

def navodila(pot, zemljevid):
    return [(zemljevid[y].index(z) - zemljevid[y].index(x)) % len(zemljevid[y])
            for x, y, z in zip(pot, pot[1:], pot[2:])]

Z drugimi besedami, funkcija vrne seznam razlik med vhodno in izhodno povezavo za vsako krožišče. Natančno, kar smo napisali tule.

Za oceno 8

Naloga za oceno 8 je obratna nalogi za oceno 7. Napiši funkcijo prevozi(zacetek, navodila, zemljevid), ki dobi začetno točko (pri gornjem zemljevidu bo to vedno 1, 2, 12 ali 15) in navodila, kakršna vrača prejšnja funkcija. Vrniti mora zaporedje prevoženih vozlišč.

Klic prevozi(1, [3, 2, 2], zemljevid) vrne [1, 3, 6, 4, 2]

Rešitev

Tole bi se dalo narediti s kako spremenljivko manj, a naredimo raje jasneje. V vsakem koraku moramo vedeti, v katerem krožišču smo (trenutno) in skozi kateri vhod smo vstopili vanj. Začeli bomo z

    trenutno = zemljevid[zacetek][0]
    vhod = zemljevid[trenutno].index(zacetek)
    pot = [zacetek, trenutno]

Tu je trenutno že krožišče, v katerm smo po prvi prevoženi povezavi (ki je v navodilu ni); vhod je indeks povezave v tem smo, in pot, ki jo bomo na koncu vrnili, že vsebuje začetno in trenutno vozlišče.

Potem pa gremo po navodilih.

    for preskoci in navodila:
        izhod = (vhod + preskoci) % len(zemljevid[trenutno])
        prej = trenutno
        trenutno = zemljevid[trenutno][izhod]
        vhod = zemljevid[trenutno].index(prej)
        pot.append(trenutno)

Tisti % len(zemljevid[trenutno]) je potreben zato, da "pridemo okoli": če smo na predzadnjem izhodu in gremo za štiri naprej, moramo pristati na tretjem. Tako naračunamo številko izhoda. Nato si shranimo trenutno vozlišče v prej. Naračunamo novo trenutno vozlišče (trenutno = zemljevid[trenutno][izhod]), potem pa še, skozi kateri vhod smo prišli vanj (vhod = zemljevid[trenutno].index(prej)). Pazimo: zemljevid[trenutno] se tu nanaša na novo trenutno vozlišče in ne na trenutno vozlišče iz prejšnje vrstice.

V pot dodamo novo trenutno vozlišče in gremo naprej. Celotna funkcija je tako:

def prevozi(zacetek, navodila, zemljevid):
    trenutno = zemljevid[zacetek][0]
    vhod = zemljevid[trenutno].index(zacetek)
    pot = [zacetek, trenutno]
    for preskoci in navodila:
        izhod = (vhod + preskoci) % len(zemljevid[trenutno])
        prej = trenutno
        trenutno = zemljevid[trenutno][izhod]
        vhod = zemljevid[trenutno].index(prej)
        pot.append(trenutno)
    return pot

Za oceno 9

1. Napiši funkcijo sosedi(doslej, zemljevid), ki prejme neko množico številk krožišč in uvozov (doslej), ter vrne množico številk vseh vozlišč, s katerimi so ta vozlišča povezana (razen teh vozlišč). Tako, recimo, klic({1, 3, 7}, zemljevid) vrne {4, 6, 11, 8}.

2. Napiši funkcijo razdalja(x, y, zemljevid), ki prejme številki dveh uvozov (lahko pa tudi dveh krožišč!) in vrne razdaljo med njima. Razdalja je definirana kot število povezav, ki jih je potrebno prevoziti med njima; razdalja med 3 in 11 je enaka 2.

Namig: če začneš z množico {x} in dodaš njene sosede, in potem v to množico sosede te množice, in potem še njihove sosede ... boš prej ko slej dodal(a) y. S tole nalogo se boš verjetno namučil(a) manj kot z nalogo za oceno 8!

Rešitev

Funkcijo sosedi precej poenostavi, če se spomnimo, da lahko sezname povezav spremenimo v množice in preprosto računamo njihove unije. Na koncu pa le odštejemo množico krožišč, ki so že v doslej.

def sosedi(doslej, zemljevid):
    naprej = set()
    for x in doslej:
        naprej |= set(zemljevid[x])
    return naprej - doslej

Funkcijo sosedi ste morali napisati le zato, da bi znali napisati funkcijo razdalja. Ta je zdaj preprosta: štejemo, kolikokrat moramo dodati sosede.

def razdalja(x, y, zemljevid):
    doslej = {x}
    korakov = 0
    while y not in doslej:
        doslej |= sosedi(doslej, zemljevid)
        korakov += 1
    return korakov

V modulu itertools je funkcija count(n), ki šteje od n do neskončno. Sam bi funkcijo razdalja napisal z njo, takole.

from itertools import count

def razdalja(x, y, zemljevid):
    doslej = {x}
    for korakov in count(1):
        doslej |= sosedi(doslej, zemljevid)
        if y in doslej:
            return korakov

Kakega posebnega prihranka pri dolžini niti ni. Pač pa je možno s funkcijo reduce temeljito oklestiti funkcijo sosedi:

from functools import reduce

def sosedi(doslej, zemljevid):
    return reduce(lambda sosedi, krozisce: sosedi | set(zemljevid[krozisce]),
                  doslej,
                  set()) - doslej

Toliko, da boste vedeli, da se pri Programiranju 1 še ne naučimo čisto vsega. :)

Za oceno 10

Napiši funkcijo najkrajsa_navodila(x, y, zemljevid), ki vrne najkrajša navodila, ki nas pripeljejo od x do y. Pri tem bosta x in y vedno številki uvozov (in ne krožišč).

Namig: mogoče se ti splača napisati funkcijo, podobno funkciji sosedi, ki pa ne prejme in vrača množice, temveč prejme slovar, katerega ključi so takšni, kot so bili prej elementi množice, pripadajoča vrednost pa je številka krožišča, iz katerega se pride v krožišče, ki ga predstavlja ključ. Ta funkcija gre torej prek ključev in v slovar dodaja nove ključe -- sosede teh ključev, kot vrednost pa jim priredi ključ, zaradi katerega je bil ta ključ dodan. (Če je bilo to povedano nekoliko kriptično, je to nekoliko namerno. Za oceno 10 morate tudi kaj potuhtati!) Ko boste imeli to funkcijo, jo uporabite podobno kot sosedi v prejšnji nalogi. Potem pa sledite temu slovarju od končne točke do začetne. Tako boste dobili pot v obratni smeri. Obrnite jo. Funkcijo, ki iz poti (seznama številk) naredi navodila, pa že imate.

Klic najkrajsa_navodila(15, 1) vrne [3, 3, 4], saj moramo na 16 na tretji izhod, na 8 na tretjega in na 3 na četrtega.

Rešitev

Nalogo za oceno 9 ste morali pisati predvsem za to, da vam pomaga rešiti nalogo za oceno 10.

Najprej napišimo funkcijo sosedi_do, ki je podobna funkciji sosedi, tako kot predlaga nasvet v nalogi.

def sosedi_do(doslej, zemljevid):
    for x in list(doslej):
        for sosed in zemljevid[x]:
            if sosed not in doslej:
                doslej[sosed] = x

Najkrajša navodila zdaj dobimo tako, da najprej naredimo nekaj podobnega kot pri merjenju razdalje, le da rezultat ni množica temveč slovar, ki pove, iz katerega vozlišča (vrednosti) se pride v posamezno vozlišče (ključ). Za začetno vozlišče pa rečemo, da vanj ni treba priti, zato začnemo z doslej = {x: None}.

V drugem delu ritensko rekonstruiramo pot. Na koncu pokličemo funkcijo navodila, da dobimo navodila za takšno pot.

def najkrajsa_navodila(x, y, zemljevid):
    doslej = {x: None}
    while y not in doslej:
        sosedi_do(doslej, zemljevid)

    pot = []
    while y is not None:
        pot.insert(0, y)
        y = doslej[y]

    return navodila(pot, zemljevid)

Vstavljanje na začetek seznama je počasnejše od dodajanje na konec. Pri tako kratkih seznamih se to ne pozna, prej zelo dolgih pa. Zato vsak spodoben programer dodaja na konec, pot.append(y) in pot obrne šele na koncu, tako da pokliče navodila(pot[::-1], zemljevid).