Na letališču imajo neka pravila v zvezi s tem, kakšne torbe morajo biti v kakšnih torbah.
light red bags contain 1 bright white bag, 2 muted yellow bags.
dark orange bags contain 3 bright white bags, 4 muted yellow bags.
bright white bags contain 1 shiny gold bag.
muted yellow bags contain 2 shiny gold bags, 9 faded blue bags.
shiny gold bags contain 1 dark olive bag, 2 vibrant plum bags.
dark olive bags contain 3 faded blue bags, 4 dotted black bags.
vibrant plum bags contain 5 faded blue bags, 6 dotted black bags.
faded blue bags contain no other bags.
dotted black bags contain no other bags.
Če izpustimo zgodbico, sta vprašanji preprosto:
Advent of Code 2019 se je sukal okrog programiranja nekega navideznega stroja, poln je bil drobnih algoritmičnih cukrčkov. Letošnji bo žal očitno na temo branja podatkov. Veliko užitkov želim vsem, ki ste se ga odločili delati v čistem C-ju.
Shranimo eno od vrstic v niz in poglejmo, kako jo zmrcvariti v ustrezne dele.
= "light red bags contain 1 bright white bag, 2 muted yellow bags." line
Dan bo rešila metoda nizov partition(x)
. Kot argument
dobi podniz x
in vrne del originalnega niza pred
x
, x
in del za x
. Torej:
= line.partition(" bags contain ") outer, _, inners
outer
'light red'
inners
'1 bright white bag, 2 muted yellow bags.'
inner
zdaj razsekamo glede na vejico, podnize pa na
presledke. Od podnizov vzamemo prvi kos, in ostale, zadnjega pa zavržemo
v _
.
for inner in inners.split(", "):
*color, _ = inners.split()
n, print(n, color)
1 ['bright', 'white', 'bag,', '2', 'muted', 'yellow']
1 ['bright', 'white', 'bag,', '2', 'muted', 'yellow']
Kdor ne razume tistega z zvezdico, naj se spomni razpakiranja terk.
*d, e, f = (1, 2, 3, 4, 5, 6, 7, 8, 9) a, b, c,
c
3
d
[4, 5, 6, 7]
e
8
f
9
n
je potrebno pretvoriti v int
,
color
pa z " ".join
združiti nazaj v en
niz.
Zložimo vse skupaj, pa imamo branje.
= {}
rules for line in open("example.txt"):
= line.partition(" bags contain ")
outer, _, inners = {}
inn_bags for inner in inners.split(","):
*color, _ = inner.split()
n, if n != "no":
" ".join(color)] = int(n)
inn_bags[= inn_bags rules[outer]
Za if n != "no"
smo poskrbeli za torbe, ki ne vsebujejo
drugih torb. Kaj je v tem primeru v color
in _
nam je očitno popolnoma vseeno.
rules
{'light red': {'bright white': 1, 'muted yellow': 2},
'dark orange': {'bright white': 3, 'muted yellow': 4},
'bright white': {'shiny gold': 1},
'muted yellow': {'shiny gold': 2, 'faded blue': 9},
'shiny gold': {'dark olive': 1, 'vibrant plum': 2},
'dark olive': {'faded blue': 3, 'dotted black': 4},
'vibrant plum': {'faded blue': 5, 'dotted black': 6},
'faded blue': {},
'dotted black': {}}
Izbrana oblika - slovar slovarjev bo najbolj praktična za obe funkciji, ki ju moramo napisati.
Z regularnim izrazom je praktično zgrabiti posamično notranjo torbo.
Izraz, ki ga potrebujemo, je (\d+?) (.+?) bags?[,.]
.
Regularni izrazi imajo metodo findall
, ki vrne skupine v
vseh ponovitvah regularnega izraza, takole:
import re
= re.compile(r"(\d+?) (.+?) bags?[,.]")
re_content
= "1 bright white bag, 2 muted yellow bags."
inners
re_content.findall(inners)
[('1', 'bright white'), ('2', 'muted yellow')]
Podatke tako preberemo z
= {outer: {g[1]: int(g[0]) for g in re_content.findall(inners)}
rules for outer, _, inners in (line.partition(" bags contain ") for line in open("input.txt"))}
Izraz preberimo od zadaj (kot vedno v Pythonu - Kotlin je tu lepši prav zato, ker gredo stvari naprej, ne nazaj!).
Najprej imamo
line.partition(" bags contain ") for line in open("input.txt")
,
ki gre čez datoteko in vsako vrstico prelomi okrog
" bags contain "
. Čez ta generator spustimo zanko
for outer, _, inners
.
To je bila druga vrstica. V prvi pa iz teh outer
in
inners
sestavimo ključe in vrednosti slovarja. Ključ je
očitno outer
. V inner
moramo najti vse
pojavitve vzorca, ki ga opisuje regularni izraz,
for g in re_content.findall(inners)
. Barvo
(g[0]
) bomo uporabili kot ključ, število
(int(g[0])
) bo vrednost.
Najbolj klasična, najbolj začetniška rekurzija.
Ni kaj komentirati.
def contains(t, x):
return t == x or any(contains(y, x) for y in rules[t])
def count(t):
return 1 + sum(n * count(x) for x, n in rules[t].items())
print(sum(contains(bag, "shiny gold") for bag in rules) - 1)
print(count("shiny gold") - 1)
233
421550