Day 5: Binary Boarding

(Povezava na nalogo)

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.

Pretvarjanje v število

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")]

Prvi del: največja številka sedeža

Brez komentarja:

max(seats)
885

Drugi del: manjkajoči sedež

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

Dodatek: ročno pretvarjanje

Č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

a
357

Č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")
    
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

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.