Naloga med študenti ni požela prevelikega navdušenja, zdela se jim je eno samo pisanje, eno samo dolgočasno preobračanje podatkov.
Zanje imam slabo novico: dobrodošli v resničnem življenju.
Naloga bo vseeno zanimiva: učili se bomo lepo po kosih vrteti te podatke. In še nevemkaterič videli, zakaj so izpeljani seznami in množice tako praktični.
Imamo datoteko takšne oblike:
class: 1-3 or 5-7
row: 6-11 or 33-44
seat: 13-40 or 45-50
your ticket:
7,1,14
nearby tickets:
7,3,47
40,4,50
55,2,20
38,6,12
Prvi blok opisuje podatke in možne interval vrednosti. (Vedno sta dva, vendar to v navodilih ni posebej omenjeno in se na to ne bomo zanašali, saj je splošna rešitev preprostejša.)
Tretji del vsebuje vrstice. Vsaka vrstica ima vse te podatke, vendar ne vemo, v kakšen vrstnem redu. Vemo pa, da isti stolpec vedno ustreza istemu podatku.
Vmesni del vsebuje naše podatke.
Prvi del naloge je preprost: nekatera izmed števil v tretjem bloku se ne pojavijo v prav nobenem intervalu. V gornjem primeru so to 4, 55 in 12. Zanima nas njihova vsota.
Drugi del je zabavnejši. Za vsak stolpec je potrebno ugotoviti, kateri del predstavlja. Za to najprej izločimo vse vrstice, ki vsebujejo kakšno številko, ki se ne pojavi v nobenem intervalu. Nato pa opazujemo, kateri stolpec bi, glede na podane številke, lahko predstavljal kateri podatek. Nekateri lahko ustrezajo več podatkom, a izkazalo se bo, da je rešitev, v kateri vsakemu stolpcu ustreza natančno eno pravilo, enolična.
Preberemo datoteko in jo s split("\n\n")
razkosamo v tri
bloke.
= open("input.txt").read().split("\n\n") rules_part, my_ticket, tickets
Prvi del, pravila bomo razstavili v slovar. Ne, ker bi v resnici potrebovali slovar, temveč ker bomo včasih potrebovali samo intervale, včasih pa tudi ime polja. Ključ bo polje, vrednosti pa bodo kar množica, ki vsebuje vsa dovoljena števila za to polje.
S splitlines()
razstavimo blok na vrstice. Vsako vrstico
s split(":")
razbijemo na ime polja in niz s seznam
intervalov, intervals
. (Kaj se zgodi na koncu, pa povem
spodaj.)
(Še tolažba: te vrstice so najbolj zapleteni del programa. :)
= {}
rules for rule in rules_part.splitlines():
= rule.split(":")
field, intervals = set.union(*(set(range(int(f), int(t) + 1))
rules[field] for f, t in (p.split("-") for p in intervals.split(" or "))))
Zdaj recimo, da imamo
= "1-3 or 5-7" intervals
Razbijemo jih glede na " or "
.
" or ") intervals.split(
['1-3', '5-7']
Vsakega razbijemo glede na "-"
.
"-") for p in intervals.split(" or ")] [p.split(
[['1', '3'], ['5', '7']]
Zdaj gremo z zanko čez to in sestavimo intervale.
range(int(f), int(t) + 1)
[for f, t in (p.split("-") for p in intervals.split(" or "))]
[range(1, 4), range(5, 8)]
Pravzaprav nas ne zanimajo range
-i, temveč množice.
set(range(int(f), int(t) + 1))
[for f, t in (p.split("-") for p in intervals.split(" or "))]
[{1, 2, 3}, {5, 6, 7}]
Vse množice zložimo skupaj.
set.union(*(set(range(int(f), int(t) + 1))
for f, t in (p.split("-") for p in intervals.split(" or "))))
{1, 2, 3, 5, 6, 7}
No, to smo spravili v slovar.
To je trivialno.
= [int(x) for x in my_ticket.splitlines()[1].split(",")]
my_ticket
= [[int(x) for x in v.split(",")]
tickets for v in tickets.splitlines()[1:]]
Tudi to je trivialno. Sestavimo množico vseh dovoljenih števil. Gremo čez vse vozovnice; za vsako izračunamo vsoto neveljavnih števil v njej in potem poračunamo vsoto te vsote.
= set.union(*rules.values())
all_valid print(sum(sum(x
for x in ticket
if x not in all_valid)
for ticket in tickets))
19060
Ta je pa bolj zanimiv. Najprej sestavimo seznam, ki vsebuje le veljavne vozovnice, torej vozovnice, v kateri se ne pojavi nobena številka, ki je ni v nobenem intervalu. Ali so vse številke veljavne, preverimo tako, da ugotovimo, ali je množica teh številk podmnožica množice vseh veljavnih številk.
= [ticket for ticket in tickets if set(ticket) <= all_valid] valid_tickets
Od tod naprej pa bomo preverjali, kateri stolpec bi lahko, glede na števila, ki jih vsebuje, ustrezal kateremu pravilu. Torej bomo delali s stolpci. Sestavimo seznam množic števil v vsakem stolpcu. Stolpcev je pa toliko kot pravil.
= ({ticket[i] for ticket in valid_tickets}
columns for i in range(len(rules)))
Stolpce bomo potrebovali samo enkrat, torej je vseeno, če jih ne
tlačimo v seznam, temveč naredimo kar generator. Kot zanimivost povejmo
še, da bi jih lahko naredili tudi z
columns = map(set, zip(*valid_tickets))
in v tem primeru bi
lahko bili tudi valid_tickets
kar generator.
= (ticket for ticket in tickets if set(ticket) <= all_valid)
valid_tickets = map(set, zip(*valid_tickets)) columns
Zdaj pa sestavimo seznam, ki bo vseboval indeks stolpca in imena vseh
pravil, ki bi jim stolpec lahko ustrezal. Stolpce torej oštevilčimo
(enumerate(columns)
) in za vsak par i, column
,
poiščemo vsa polja, za katera velja, da so števila v tem stolpcu
podmnožica veljavnih števil tega polja.
= [(i, {field for field, valids in rules.items() if column <= valids})
maybes for i, column in enumerate(columns)]
Izvemo, da bi 15. stolpec lahko ustrezal trem različnim poljem.
15] maybes[
(15, {'arrival platform', 'class', 'row'})
Nekateri ustrezajo tudi več poljem, nekateri pa manj. Preštejmo, koliko poljem ustreza kateri.
len(maybe[1]) for maybe in maybes] [
[16, 6, 18, 15, 19, 9, 4, 1, 20, 17, 2, 7, 5, 11, 10, 3, 14, 8, 13, 12]
Če to reč uredimo, izvemo nekaj zanimivega.
sorted(len(maybe[1]) for maybe in maybes)
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
In zdaj pošpekuliratmo. Mogoče je stvar preprosta. Uredimo seznam
maybe
po številu polj. Za prvi stolpec vemo, kateremu
pravilu ustreza. Temu pravilu ne more ustrezati noben drug stolpec. In
če imamo srečo (izkazalo se bo, da jo res imamo) prav temu pravilu
ustrezajo tudi vsi drugi stolpci. Potemtakem za drugi stolpec ostane le
še eno možno pravilo. In tako naprej.
=lambda x: len(x[1]), reverse=True)
maybes.sort(key= {}
assignments while maybes:
= maybes.pop()
i, fields = (fields - set(assignments)).pop()
field = i assignments[field]
Seznam maybes
smo uredili glede na število pravil.
Zaradi lepšega ga uredimo padajoče. Potem vedno vzamemo zadnji stolpec,
tisti, ki ustreza enemu samemu pravilu. Iz množice pravil, ki jim je
ustrezal v začetku, odštejemo vsa pravila, ki so že zasedena. In nato
zabeležimo, da to pravilo ustreza temu stolpcu.
Naloga hoče, da izračunamo zmnožek tistih številk v naši vozovnici, ki ustrezajo podatkom, katerih ime se začne z departure.
from functools import reduce
from operator import mul
print(reduce(mul, (my_ticket[i]
for field, i in assignments.items()
if field.startswith("departure"))))
953713095011
Ker je bilo tole razreseno po celi beležki, zberimo celoten program še na enem mestu.
from functools import reduce
from operator import mul
# Branje podatkov
= open("input.txt").read().split("\n\n")
rules_part, my_ticket, tickets
= {}
rules for rule in rules_part.splitlines():
= rule.split(":")
field, intervals = set.union(*(set(range(int(f), int(t) + 1))
rules[field] for f, t in (p.split("-") for p in intervals.split(" or "))))
= [int(x) for x in my_ticket.splitlines()[1].split(",")]
my_ticket
= [[int(x) for x in v.split(",")]
tickets for v in tickets.splitlines()[1:]]
# Part 1
= set.union(*rules.values())
all_valid print(sum(sum(x
for x in ticket
if x not in all_valid)
for ticket in tickets))
# Part 2
= [ticket for ticket in tickets if set(ticket) <= all_valid]
valid_tickets
= ({ticket[i] for ticket in valid_tickets}
columns for i in range(len(rules)))
= [(i, {field for field, valids in rules.items() if column <= valids})
maybes for i, column in enumerate(columns)]
=lambda x: len(x[1]), reverse=True)
maybes.sort(key= {}
assignments while maybes:
= maybes.pop()
i, fields = (fields - set(assignments)).pop()
field = i
assignments[field]
print(reduce(mul, (my_ticket[i]
for field, i in assignments.items()
if field.startswith("departure"))))
19060
953713095011
columns
je pravzaprav transponiran
valid_tickets
. Za transponiranje obstaja trik z
zip
-om.
= [(1, 2, 3), (4, 5, 6), (7, 8, 9), (10, 11, 12)]
s list(zip(*s))
[(1, 4, 7, 10), (2, 5, 8, 11), (3, 6, 9, 12)]
Kako to deluje? Preprosto. Vse štiri terke postanejo argumenti
zip
-a, kot da bi napisali
zip((1, 2, 3), (4, 5, 6), (7, 8, 9), (10, 11, 12))
.
zip
gre vzporedno čez vse terke; najprej pobira prve
elemente, nato druge, nato tretje.
V našem primeru torej naredimo zip(*valid_tickets)
. Iz
vsake od dobljenih terk želimo narediti množico, torej jih premapiramo
čez map(set, ...)
.
Na ta način valid_tickets
potrebujemo le enkrat. Tako so
valid_tickets
lahko kar generator.
Še bolj kul pa je nadaljevanje. Vemo, da bomo polje najprej dodelili tistemu stolpcu, ki mu ustreza le eno pravilo, drugi stolpec tistemu, ki mu ustrezata dve in tako naprej. Po drugi strani pa vemo tudi, da bo najprej dodeljeno tisto pravilo, ki se pojavi le pri enem stolpcu, nato tisto, ki se pri dveh...
Potemtakem lahko preprosto uredimo stolpce po številu ustrezajočih polj in polja po številu ustrezajočih stolpcev, pa se bodo natančno ujemali.
# Part 2
from collections import Counter
from itertools import chain
from functools import reduce
from operator import mul
= (ticket for ticket in tickets if set(ticket) <= all_valid)
valid_tickets = map(set, zip(*valid_tickets))
columns
= [(i, {field for field, valids in rules.items() if column <= valids})
maybes for i, column in enumerate(columns)]
= Counter(chain(*(x[1] for x in maybes)))
counts
= (maybe[0] for maybe in sorted(maybes, key=lambda x: len(x[1])))
indices = sorted(counts, key=counts.get, reverse=True)
fields
print(reduce(mul, (my_ticket[i]
for i, field in zip(indices, fields)
if field.startswith("departure"))))
953713095011
Kot vse podobne naloge je tudi ta zanimala vašega asistenta Tomaža Hočevarja. Hitro je našel članek, izrek, dokaz ... da bomo pri vsaki rešitvi, ki je enolična, gotovo imeli srečo. Sestavljalec naloge nam tu preprosto ni mogel otežiti življenja ... razen če bi bilo možnih različnih odgovorov več.