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
.
= "FBFBBFFRLR"
x
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.
= [int(x.replace("F", "0").replace("B", "1").replace("R", "1").replace("L", "0"), 2)
seats 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.
= min(seats), max(seats) mi, ma
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 + 1) - mi * (mi - 1)) // 2 - sum(seats) (ma
623
Če Pythonov int
ne bi znal pretvarjati števil v
dvojiškem zapisu, bi morali pretvarjati sami.
Recimo tako
= "FBFBBFFRLR"
x
= 0
a for c in x:
*= 2
a if c in "BR":
+= 1
a
a
357
Če vemo, da je True
enak 1
in
False
enak 0
, to skrajšamo v
= 0
a for c in x:
= 2 * a + (c in "BR")
a
a
357
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
= [reduce(lambda a, c: 2 * a + (c in "BR"), x.strip(), 0) for x in open("input.txt")] seats
strip
je potreben, ker je na koncu vrstice še
\n
, ki bi nam vsa števila še enkrat pomnožil z 2.