Podatki so v obliki
1-3 a: abcde
1-3 b: cdefg
2-9 c: ccccccccc
Vsaka vrstica vsebuje dve števili, črko in niz. Prvi del pravi, da je
geslo (zadnji niz) veljavno, če je število ponovitev podanega znaka
znotraj meja, ki jih opisujeta prvi številki. Drugi del pa spremeni
pravilo tako, da mora biti podani znak na enem (in le enem) izmed mest,
ki ga določata števili; v prvem primeru, recimo, hočemo a
na prvem ali tretjem mestu.
V obeh delih je naloga, da izpišemo število veljavnih gesel.
Tole je predvsem naloga iz branja podatkov, zato se poigrajmo s tem.
Sorry za stereotip. Ampak, pač, tole bo zgledna, netvegana rešitev.
Gremo prek vseh vrstic. Vsako razsekamo glede na presledke in to
razpakiramo v terke. Prvi element razbijemo še glede na -
.
Vse skupaj zložimo v terko, pri čemer prva niza pretvorimo v števili, od
znaka pa odbijemo odvečni :
.
= []
passwords for line in open("example.txt"):
= line.split()
interval, character, password = interval.split("-")
fr, to int(fr), int(to), character.strip(":"), password)) passwords.append((
Lepota te rešitve je, da smo števili pretvorili v int
. V
rokohitrskem branju spodaj bosta ostala niza, tako da ju bo potrebno
pretvarjati kasneje, sproti.
passwords
[(1, 3, 'a', 'abcde'), (1, 3, 'b', 'cdefg'), (2, 9, 'c', 'ccccccccc')]
Če zamenjamo -
s presledkom in :
z ničemer,
se niz spremeni v, na primer, "1 3 a abcde"
. Odtod
potrebujemo le še najobičajnejši split
, pa dobimo štiri
elemente, ki jih potrebujemo.
= [line.replace("-", " ").replace(":", "").split() for line in open("example.txt")]
passwords
passwords
[['1', '3', 'a', 'abcde'],
['1', '3', 'b', 'cdefg'],
['2', '9', 'c', 'ccccccccc']]
Prva dva sta zdaj očitno niza in ne števili. Not good, ampak ne bo hudega.
Refleks vsakega resnega programerja, ki pred seboj zagleda takole reč, so regularni izrazi. V redno snov Programiranja 1 le-ti ne sodijo, vendar jih mnogi študenti že poznajo iz kakega drugega vica. Tu jih na hitro predstavimo in uporabimo.
Nizi, ki jih imamo se začnejo z nekaj števkami. Števko predstavimo z
\d
; če hočemo povedati, da se števke ponavljajo, in to vsaj
enkrat, dodamo +
, torej \d+
. Sledil bo znak
-
in potem spet števke. Torej imamo \d+-\d+
.
Sledi presledek in potem poljubna črka med a in z, kar opišemo z
[a-z]
. Sledi dvopičj in potem poljubno število ponovitev
poljubnih črk, [a-z]+
. Vse skupaj je torej
\d+-\d+ [a-z]: [a-z]+
.
Tisti, ki to vidite prvič: temu rečemo regularni izraz. Z njim opišemo obliko niza. Regularne izraze je pogosto težko brati; tale je pravzaprav izjemno berljiv.
Na tem mestu se od vseh, ki to vidite prvič, najbrž poslavljamo; spet se vidimo v naslednjem razdelku.
V regularnem izrazu bomo morali še označiti skupine, ki jih želimo
razbrati. Skupine bi bilo možno tudi poimenovati, ta izraz pa je tako
preprost, da tega ne bomo storili, niti to ni potrebno, saj bomo vedno
potrebovali preprosto vse štiri skupine v njihovem originalnem vrstnem
redu. Naš izraz je torej (\d+)-(\d+) ([a-z]): ([a-z]+)
.
Z njim bomo takole prebrali datoteko.
import re
= [re.match(r"(\d+)-(\d+) ([a-z]): ([a-z]+)", line).groups() for line in open("example.txt")]
passwords
passwords
[('1', '3', 'a', 'abcde'),
('1', '3', 'b', 'cdefg'),
('2', '9', 'c', 'ccccccccc')]
Niz vsebuje vzvratne poševnice, \
. Te moramo seveda
podvojiti (\\n
je v resnici poševnica in n, medtem kot je
\n
znak za novo vrstico). Regularni izrazi so navadno polni
vzvratnih poševnic in so dovolj neberljivi že brez njihovega
podvojevanja, hvala. Zato v Pythonu radi uporabimo r-nize
(r-string, raw string). Pred narekovaj damo
r
in Python bo pustil poševnice pri miru.
Funkciji re.match
podatmo regularni izraz in niz; kot
rezultat vrne MatchObject
ali None
. Mi se
delamo, da bodo vse vrstice oblikovane pravilno, zato lepo pokličemo
metodo groups()
, ki vrne vsebino vseh skupin.
Če bi vas najel kot programerje, bi si želel, da mi napišete tole.
import re
from typing import NamedTuple
class PassData(NamedTuple):
int
fr: int
to: str
character: str
password:
@classmethod
def from_seq(cls, s):
return cls(int(s[0]), int(s[1]), s[2], s[3])
= re.compile(r"(\d+)-(\d+) ([a-z]): ([a-z]+)")
re_pass = [PassData.from_seq(re_pass.match(line).groups()) for line in open("example.txt")] passwords
Spet imamo regularni izraz. To bo najbrž hitreje in pravilneje od
split
-ov. Spet tudi predpostavimo, da je datoteka
oblikovana pravilno. Če bi šlo čisto čisto zares, bi morali seveda
preveriti še to in če naletite na napako, to seveda povedati na primeren
način.
Novost je, da podatke shranjujemo v NamedTuple
. Ta ima
polja fr
in to
, ki sta lepo zgledno
int
-a, ter character
in password
,
ki sta niza.
Dodali smo tudi poimenovan konstruktor, from_seq
, ki kot
argument prejme zaporedje elementov iz vrstice in jih lepo zloži v novi
objekt. Kaj je @classmethod
se pri tem predmetu ne bomo
učili; to je bolj pythonovska zadeva. To kodo torej kažem samo zato, da
malo nakažem, kaj se še da.
Zdaj so podatki sestavljeni res zgledno. Vedejo se kot terke, obenem pa lahko do njih dostopamo tudi po imenih.
passwords
[PassData(fr=1, to=3, character='a', password='abcde'),
PassData(fr=1, to=3, character='b', password='cdefg'),
PassData(fr=2, to=9, character='c', password='ccccccccc')]
= passwords[0]
prvi
prvi.fr
1
prvi.password
'abcde'
-1] prvi[
'abcde'
V rešitvah bomo predpostavili, da so podatki prebrati v najlepšo,
zadnjo obliko, saj bodo rešitve tako najčitljivejše. Če ni tako, boste,
recimo, pwd.character
zamenjali s pwd[2]
,
pwd.to
pa z int(pwd[1])
.
V prejšnjih primerih smo brali le datoteko s tremi primeri (example.txt); zdaj preberimo prave podatke.
= [PassData.from_seq(re_pass.match(line).groups()) for line in open("input.txt")] passwords
= 0
valid for pwd in passwords:
if pwd.fr <= pwd.password.count(pwd.character) <= pwd.to:
+= 1
valid print(valid)
569
Ni posebne umetnosti. Omembe vreden je le pogoj v if
:
ali je nek x
znotraj intervala [a, b], izvemo z
a <= x <= b
in ne
x >= a and x <= b
, ki bi v gornjem primeru zahteval,
da dvakrat štejemo pwd.password.count(pwd.character)
(ali
pa posebej za to naredimo ločeno spremenljivko).
Ker gre v bistvu za vsoto, jo lahko izračunamo s sum
.
Tipično študenti napišejo:
sum(1 for pwd in passwords if pwd.fr <= pwd.password.count(pwd.character) <= pwd.to)
569
Kdor se spomni, da je True
isto kot 1
in
False
isto kot 0
, pa ne sešteva enic.
sum(pwd.fr <= pwd.password.count(pwd.character) <= pwd.to
for pwd in passwords)
569
Kako preveriti, ali je nek znak c
na i
-tem
ali j
-tem mestu niza s
, ne pa na obeh? Recimo
tako: pogledamo s[i] == c
in s[j] == c
. Eden
od teh dveh mora biti False
, eden True
. Se
pravi: biti morata različna: (s[i] == c) != (s[j] == c)
.
Oklepaji so potrebni: brez njih bi Python preveril ali veljajo vse
naštete relacije, nas pa zanima, ali je resničnost prve različna od
resničnosti druge.
Tako dobimo
= 0
valid for pwd in passwords:
if (pwd.password[pwd.fr - 1] == pwd.character) != (pwd.password[pwd.to - 1] == pwd.character):
+= 1
valid print(valid)
346
ali
sum((pwd.password[pwd.fr - 1] == pwd.character) != (pwd.password[pwd.to - 1] == pwd.character)
for pwd in passwords)
346