Tole je četrta naloga z letošnjega Advent of Code, le da sem jo razdelil v funkcije, tako da bo malo težje uporabiti rešitve s spleta. Ne bo si nemogoče pomagati z njimi, vendar predlagam, da tega ne počnete, saj se tako ne boste naučili ničesar.

Za začetek si lahko preberete originalno nalogo.

Testi

Testi: testi-zaspani-strazarji.zip

Obvezna naloga

Napisati bo potrebno pet funkcij, a ne bo hudega. Prva in tretja sta zelo podobni nalogam z vaj. Pri drugi si lahko zelo pomagate s primerom s predavanj, ki je objavljen ob domači nalogi. Četrta je naloga za začetek Programiranja 1, peta pa nezahtevna vaja iz slovarjev.

  • razberi(vrstica) prebere vrstico iz datoteke in vrne terko, ki vsebuje (leto, mesec, dan, ura, minuta, kaj, kdo). Prvih pet stvari so števila; kaj pomenijo, je očitno. kaj je niz, ki vsebuje besedo, ki sledi časovni oznaki v oklepajih, to je "Guard", "falls" ali "wakes". kdo je številka stražarja, če gre za vrstico, ki opisuje stražarja (torej, če je kaj enak "Guard"), sicer pa je enak None.

    • razberi("[1518-11-09 23:58] Guard #853 begins shift") vrne (1518, 11, 9, 23, 58, "Guard", 853),
    • razberi("[1518-04-02 00:30] falls asleep") vrne (1518, 4, 2, 0, 30, "falls", None),
    • razberi("[1518-08-11 00:47] wakes up") vrne (1518, 8, 11, 0, 47, "wakes", None).

    Nasvet: razbij po presledkih, naprej pa si pomagaj tako, da veš, od katerega do katerega znaka niza so zapisani leto, mesec, dan, ura in minuta.

  • preberi_datoteko(ime_datoteke) prejme ime datoteke in iz nje prebere podatke o tem, kako so stražarji zaspali in se budili. Zloži jih v seznam trojk, ki vsebuje številko stražarja, minuto, v kateri je zaspal, in minuto, v kateri se je zbudil. Če datoteka vsebuje

    [1518-11-01 00:00] Guard #10 begins shift
[1518-11-01 00:05] falls asleep
[1518-11-01 00:25] wakes up
[1518-11-01 00:30] falls asleep
[1518-11-01 00:55] wakes up
[1518-11-01 23:58] Guard #99 begins shift
[1518-11-02 00:40] falls asleep
[1518-11-02 00:50] wakes up
[1518-11-03 00:05] Guard #10 begins shift
[1518-11-03 00:24] falls asleep
[1518-11-03 00:29] wakes up

    funkcija vrne

    [(10, 5, 25),
 (10, 30, 55),
 (99, 40, 50),
 (10, 24, 29)]

    Problem: vrstice datoteke niso urejene. Do urejenih vrstic pridete tako, da namesto open(blabla) napišete sorted(open(blabla)).

    Lahko si pomagaš s prejšnjo funkcijo in zavržeš vse tisto, česar ne potrebuješ.

  • izpis_dogodka(strazar, spi, zbudi) prejme podatke (tri številke) o tem, kdaj je nek stražar zaspal in kdaj se je zbudil, kot rezultat pa vrne niz z izpisom tega dogodka. Klic izpis_dogodka(1945, 5, 42) vrne "1945: 05-42" in izpis_dogodka(19, 13, 42) vrne " 19: 13-42". Številka stražarja vedno zavzame štiri mesta; ure in minute so poravnane tako, da imajo spredaj 0.

    Poravnavo z ničlami dosežemo tako, da pred število mest dodamo 0:

    >>> x = 42
>>> f"{x:06}"
'000042'

  • naj_drugi(pari) prejme seznam parov. Poišče največji drugi element in vrne pripadajoči prvi element. Klic naj_drugi([(5, 3), (8, 9), (13, 5), (10, 7)]) vrne 8: največji drugi element je 9 in pripadajoči prvi element je 8.

  • naj_zaspanec(dogodki) prejme seznam trojk s številko stražarja in minuto, ko je zaspal in ko se je zbudil. Vrne številko stražarja, ki je skupno (ne le enkrat, temveč če seštejemo vse njegovo spanje) prespal največ minut.

    Če stražar zaspi ob minuti 5 in se zbudi ob minuti 8, to pomeni, da je spal ob minutah 5, 6 in 7, torej je spal tri minute.

    Noben stražar ne zaspi pred polnočjo in noben ne spi po 1:00, zato dolžino spanja vedno dobiš tako, da odšteješ drugo številko od tretje.

Razberi

Vrstico morda najprej razbijmo glede na presledke (vrstica.split()). Vzamemo le prvi štiri stvari, ostala šara nas ne zanima (vrstica.split()[:4]). Te štiri stvari so datum (na primer "[1518-11-01"), ura (na primer "00:30]), niz, ki pove, o čem govori vrstica ("Guard", "falls" ali "awakes") in še en, ki bo vseboval številko stražarja ("#), če gre za vrstico "Guard". Pospravimo jih v

datum, ura, kaj, kdo = vrstica.split()[:4]

Iz datum in ura moramo izločiti leto, mesec, dan, uro in minute. Tu si pomagamo kar s tem, da točno vemo, kje jih najti. Mimogrede jih še pretvorimo v int.

leto, mesec, dan = int(datum[1:5]), int(datum[6:8]), int(datum[9:])
ura, min = int(ura[:2]), int(ura[3:5])

Na koncu le še preverimo, ali gre za vrstico s stražarjem (Guard). Če je tako, v kdo zapišemo številko stražarja, sicer ga nastavimo na None.

Vse skupaj je videti tako.

def razberi(vrstica):
    datum, ura, kaj, kdo = vrstica.split()[:4]
    leto, mesec, dan = int(datum[1:5]), int(datum[6:8]), int(datum[9:])
    ura, min = int(ura[:2]), int(ura[3:5])
    if kdo[0] == "#":
        kdo = int(kdo[1:])
    else:
        kdo = None
    return leto, mesec, dan, ura, min, kaj, kdo

Preberi datoteko

Pomoč za to funkcijo sem objavil na forumu.

Ko preberete vrstico,

  • če je to vrstica s stražarjem, si le zapomnite številko stražarja (seznam dogodkov pustite pri miru!);
  • sicer če je to vrstica, da je stražar zaspal, si le zapomnite, kdaj je zaspal (seznam dogodkov pustite pri miru);
  • sicer (torej je to vrstica, da se je stražar zbudil), dodajte v seznam ustrezno trojko, kjer bo številka stražarja, kdaj je zaspal in kdaj se je zbudil.

Vsaka od gornjih treh alinej je samo en if oziroma elif oziroma else, ki mu sledi eno samo prirejanje oz. dodajanje v seznam.

Če boste lepo sledili tem navodilom, bo funkcija popolnoma preprosta, dolga pa bo ~10 vrstic.

Konkretno, takšna bo:

def preberi_datoteko(ime):
    dogodki = []
    for vrstica in sorted(open(ime)):
        leto, mesec, dan, ura, min, kaj, kdo = razberi(vrstica)
        if kdo:
            strazar = kdo
        elif kaj == "falls":
            spi = min
        else:
            dogodki.append((strazar, spi, min))
    return dogodki

Izpis dogodka

Nekateri so tu skoraj doktorirali iz mučenja z raznimi str-ji in zfill-i. Kdor predpostavi, da je domača naloga povezana s snovjo predavanj in se spomni, kar smo povedali tam (ali pa pogleda v zapiske), pa to reši na edini pravi način:

def izpis_dogodka(strazar, spi, zbudi):
    return f"{strazar:>4}: {spi:02}-{zbudi:02}"

Naj drugi

Kako to narediti na počasen način, vemo. Naredimo na hitrejšega.

def naj_drugi(pari):
    return max((v, k) for k, v in pari)[1]

Vzamemo vse pare in jih obrnemo, tako da bo drugi element pred prvim. Poiščemo največji element. Kot smo že večkrat slišali, se terke primerjajo tako, da najprej primerja prvi element -- ki je v tem primeru drugi. max((v, k) for k, v in pari) bo torej vrnil terko z največjim prvim (to je: originalno drugim) elementom. Funkcija vrne drugi (to je: originalno prvi) element te terke.

Naj zaspanec

Uporabljali bomo slovar spanje; njegovi ključi bodo številke stražarjev, vrednosti pa, koliko časa so spali. Da bo preprosteje, bomo vzeli kar defaultdict.

def naj_zaspanec(dogodki):
    spanje = defaultdict(int)
    for strazar, spi, budi in dogodki:
        spanje[strazar] += budi - spi
    return naj_drugi(spanje.items())

Ko je slovar sestavljen, kako izvemo, pri kateri vrednosti je ključ največji? spanje.items() vrne seznam parov - ki je ravno pravi za tisto, kar potrebuje funkcija naj_drugi.

Dodatna naloga

Napiši še tidve funkciji.

  • kdaj_spi(strazar, dogodki) prejme številko stražarja in sezname trojk, kot v prejšnjih funkcijah. Vrne tisto minuto, v kateri je podani stražar največkrat spal.

  • naj_cas(strazar, dogodki) preveri vse stražarje in minute, v katerih spijo. Gre čez vse kombinacije stražarjev in minut, ko so le-ti spali. Vrne par (strazar, minuta), ki je najbolj pogosta.

    Če stražar 99 spi od minute 5 do 8, to pomeni kombinacije (99, 5), (99, 6) in (99, 7).

    Če imamo

    Date   ID   Minute
        000000000011111111112222222222333333333344444444445555555555
        012345678901234567890123456789012345678901234567890123456789
11-01  #10  .....####################.....#########################.....
11-02  #99  ........................................##########..........
11-03  #10  ........................#####...............................
11-04  #99  ....................................##########..............
11-05  #99  .............................................##########.....

    vrne (99, 45), saj je to najbolj pogosta kombinacija. Stražar 99 je namreč trikrat spal v minuti 45; vse druge kombinacije so manj pogoste.

S tema dvema funkcijama si končal rešitev naloge za Advent of Code in jo lahko oddaš tudi tja. :)

Kdaj spi

Spanje bo seznam s 60 elementi, ki bodo povedali, koliko je stražar spal v kateri minuti.

Gremo čez vsa spanja. Če se nanašajo na tega stražarja, gremo čez vse minute tega spanja in ustrezno povečamo števce.

def kdaj_spi(strazar, dogodki):
    spanje = [0] * 60
    for kdo, spi, budi in dogodki:
        if kdo == strazar:
            for min in range(spi, budi):
                spanje[min] += 1
    return naj_drugi(enumerate(spanje))

Na koncu spet uporabimo funkcijo naj_drugi. Iz seznama spanje sestavimo seznam parov indeksov in vrednosti. Zanima nas indeks pri največji vrednosti.

Naj čas

Zdaj bo spanje slovar, ki bo štel, kolikokrat smo videli posamezno kombinacijo stražarja in minute. Spet gremo čez vse dogodke in znotraj tega čez vse minute, ter štejemo kombinacije.

def naj_cas(dogodki):
    spanje = defaultdict(int)
    for strazar, spi, budi in dogodki:
        for min in range(spi, budi):
            spanje[(strazar, min)] += 1
    return naj_drugi(spanje.items())

Na koncu z naj_drugi vrnemo najpogostejšo kombinacijo.

Obe funkciji je mogoče napisati krajše, če poznamo razred Counter iz modula collections.

def kdaj_spi(strazar, dogodki):
    return Counter(min for kdo, spi, budi in dogodki if kdo == strazar for min in range(spi, budi)).most_common(1)[0][0]

def naj_cas(dogodki):
    return Counter((strazar, min) for strazar, spi, budi in dogodki for min in range(spi, budi)).most_common(1)[0][0]
Last modified: Thursday, 25 March 2021, 6:26 PM