Naloga je res lahka. Zanimiva pa je zaradi lepega trika v drugem delu.
Sedež na letalski karti je opisan z zaporedjem črk F, B, L in R. Prvi del opisuje vrsto:
For example, consider just the first seven characters of FBFBBFFRLR:
Start by considering the whole range, rows 0 through 127.
F means to take the lower half, keeping rows 0 through 63.
B means to take the upper half, keeping rows 32 through 63.
F means to take the lower half, keeping rows 32 through 47.
B means to take the upper half, keeping rows 40 through 47.
B keeps rows 44 through 47.
F keeps rows 44 through 45.
The final F keeps the lower of the two, row 44.
drugi pa sedež znotraj te vrste
Start by considering the whole range, columns 0 through 7.
R means to take the upper half, keeping columns 4 through 7.
L means to take the lower half, keeping columns 4 through 5.
The final R keeps the upper of the two, column 5.
Vrniti je potrebno vsoto številko vrste, pomnožene z 8, in številke sedeža.
Ni potrebno biti posebej pameten, da uvidimo, da dobimo številko
vrste tako, da zaporedje FBFBBFF spremenimo v
0101100 (F spremenimo v 0 in B v 1) in ga interpretiramo
kot dvojiško število. Pythonov int poleg niza prijazno
sprejme še en argument, namreč osnovno številskega sistema,
int("0101100", 2)44
Drugi del je enako dolgočasen, le da L postane 0 in R 1. Še več, ker
je potrebno v končnem rezultatu pomnožiti vrstico z 8, je to isto, kot
če bi v prvotnem nizo pretvorili vse črke, kot je treba, in kar vse
skupaj pretvorili v int.
x = "FBFBBFFRLR"
int(x.replace("F", "0").replace("B", "1").replace("R", "1").replace("L", "0"), 2)357
Podatke preberemo tako, da to storimo z vsako vrstico datoteke.
seats = [int(x.replace("F", "0").replace("B", "1").replace("R", "1").replace("L", "0"), 2)
for x in open("input.txt")]Brez komentarja:
max(seats)885
Zgodba pravi, da prvih toliko in toliko številk ne obstaja. Naloge je odkriti naš sedež (to je, sedež, ki je še prost) med najmanjšo in največjo številko sedeža.
mi, ma = min(seats), max(seats)Ena ideja so množice: od množice vseh sedežev,
set(range(mi, ma + 1)) odštejemo množico zasedenih sedežev,
set(seats). Dobljena množica bo (predvidoma) imela le en
element; ven ga izvlečemo s pop.
(set(range(mi, ma + 1)) - set(seats)).pop()623
Zvitejša je tale: od vsote številk vseh možnih sedežev odštejemo vsoto številk vseh zasedenih sedežev.
Vsota številk vseh sedežev do (vključno) ma je
ma * (ma + 1) // 2. Ker prvih mi (brez
mi) sedežev manjka, moramo od tega odšteti vsoto sedežev do
mi-tega (brez mi-tega),
mi * (mi - 1) // 2. Od tega odštejemo vsoto vseh
sedežev.
(ma * (ma + 1) - mi * (mi - 1)) // 2 - sum(seats)623
Če Pythonov int ne bi znal pretvarjati števil v
dvojiškem zapisu, bi morali pretvarjati sami.
Recimo tako
x = "FBFBBFFRLR"
a = 0
for c in x:
a *= 2
if c in "BR":
a += 1
a357
Če vemo, da je True enak 1 in
False enak 0, to skrajšamo v
a = 0
for c in x:
a = 2 * a + (c in "BR")
a357
In če znamo uporabljati reduce in lambda,
iz tega naredimo
from functools import reduce
reduce(lambda a, c: 2 * a + (c in "BR"), x, 0)357
Celotno datoteko tako preberemo s
seats = [reduce(lambda a, c: 2 * a + (c in "BR"), x.strip(), 0) for x in open("input.txt")]strip je potreben, ker je na koncu vrstice še
\n, ki bi nam vsa števila še enkrat pomnožil z 2.