Drugi del zahteva, da najprej vzamemo vse podatke.
00100
11110
10110
10111
10101
01111
00111
11100
10000
11001
00010
01010
Nato jih prefiltriramo; obdržimo samo tiste, katerih prvi bit je enak večinskemu. Večinska vrednost je 1, torej bomo obdržali samo vrstice, pri katerih je prvi bit enak 1.
11110
10110
10111
10101
11100
10000
11001
Vajo ponovimo z drugim bitom. Tu so v večini enice, torej vzamemo vrstice, ki imajo na drugem mestu enico.
10110
10111
10101
10000
In tako naprej, dokler ne ostane ena sama vrstica.
Preberimo podatke.
import numpy as np
= np.array([[int(x) for x in v.strip()] for v in open("example.txt")]) data
Pri reševanju bomo morali znati prebrati posamični stolpec. Ničtega, recimo, preberemo tako:
= data[:, 0]
column
column
array([0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0])
Poleg tega bomo morali znati izbrati vrstice, pri katerih ima bit določeno vrednost. Za vajo recimo, da nas zanimajo vrstice, pri kateri je v tem stolpcu ničla. Katere so, izvemo tako:
== 0 column
array([ True, False, False, False, False, True, True, False, False,
False, True, True])
Ta column == 0
lahko uporabimo za indeksiranje. Takole
izberemo vse vrstice, pri katerih je prvi bit enak 0
:
== 0] data[column
array([[0, 0, 1, 0, 0],
[0, 1, 1, 1, 1],
[0, 0, 1, 1, 1],
[0, 0, 0, 1, 0],
[0, 1, 0, 1, 0]])
Zdaj poznamo vse delčke. Le še v program jih moramo zložiti.
= np.array([[int(x) for x in v.strip()] for v in open("example.txt")])
data
= 0
bit while len(data) > 1:
= data[:, bit]
column = np.sum(column) >= data.shape[0] / 2
majority = data[column == majority]
data += 1
bit
data
array([[1, 0, 1, 1, 1]])
Naprej pa tudi znamo.
= 2 ** np.arange(data.shape[1])[::-1]
powers
sum(powers * data) np.
23
Če smo čisto natančni: data
je še vedno dvodimenzionalna
tabela, čeprav z eno samo vrstico. powers * data
bo
pomnožil vsako vrstico z s potencami dvojke. Vemo pa, da bo
np.sum
, če mu ne podamo osi, vrnil vsoto vseh elementov
tabele, se pravi, prek vseh vrstic. Ker je vrstica ena sama, pa je to
itak eno in isto.
Drugi del naloge zahteva, da na podoben način iščemo vrstice, ki
vsebujejo manjšinski bit. Tega ne moramo najti kar kot komplement
data
, temveč moramo ponoviti celoten program tako, da
>=
zamenjamo z <
ali pa se znajdemo kako
drugače.