Code 39 is een techniek voor het opstellen van barcodes die in 1974 door Dr. David Allais and Ray Stevens werd ontwikkeld voor het bedrijf Intermec. Bij code 39 wordt elk letterteken voorgesteld door vijf verticale zwarte stroken, die van elkaar worden gescheiden door vier verticale witte stroken. Barcodes van opeenvolgende lettertekens worden steeds van elkaar gescheiden door een smalle witte strook. Onderstaande figuur illustreert hoe het woord COMPUTERGEBRUIK eruitziet als code 39 barcode.

Code 39 barcode

Code 39 barcodes worden in ASCII-formaat gecodeerd door vier symbolen te gebruiken die de vier combinaties van smalle/brede zwarte/witte banden voorstellen. De twee formaten $$\sum_1$$ en $$\sum_2$$ (zie onderstaande tabel) die hiervoor gebruikt worden, zijn niets anders dan twee verschillende manieren om dezelfde onderliggende codering te omschrijven. Het gaat dus niet om twee varianten van code 39. Zo kan het letterteken A worden voorgesteld door de tekenreeks BsSsSbSsB of door de tekenreeks ZwzwzWzwZ. Ook een hybride voorstelling die gebruik maakt van een combinatie van de symbolen uit $$\sum_1$$ en $$\sum_2$$ is toegelaten. De tekenreeks ZszszbzsZ is dus ook een geldige code 39 voorstelling van het letterteken A. Bij de voorstelling van code 39 barcodes in ASCII-formaat wordt geen symbool opgenomen dat de scheiding van lettertekens aangeeft.

Strook $$\sum_1$$ $$\sum_2$$
breed-zwart B Z
smal-zwart S z
breed-wit b W
smal-wit s w

Opgave

Het bestand barcodes.txt1 bevat op elke regel de code 39 barcode in ASCII-formaat van een woord, gevolgd door een spatie en het woord zelf. Sommige ASCII-barcodes zijn ongeldig omdat hun aantal stroken geen veelvoud is van negen, of omdat ze symbolen bevatten die niet in de formaten $$\sum_1$$ of $$\sum_2$$ voorkomen (waardoor ze niet tot $$B$$ behoren; zie hieronder). Gevraagd wordt:

  1. Bepaal reguliere expressies voor elk van de onderstaande verzamelingen, waarbij $$\mathcal{B}$$ de verzameling van alle tekenreeksen voorstelt waarvan de symbolen voorkomen in $$\sum_1$$ of $$\sum_2$$, en waarvan het aantal symbolen een veelvoud is van negen. Probeer deze reguliere expressies zo kort mogelijk te houden.

    • $$\alpha = \{ b \in \mathcal{B}\,|\,$$ aantal smalle witte banden in $$b$$ is oneven $$\}$$

    • $$\beta = \{ b \in \mathcal{B}\,|\,$$ $$b$$ bevat minstens tien opeenvolgende stroken met dezelfde breedte $$\}$$

    • $$\gamma = \{ b \in \mathcal{B}\,|\,$$ in $$b$$ wordt elke letter uitsluitend vertaald door symbolen uit $$\sum_1$$ of $$\sum_2$$ $$\}$$

      voorbeelden: ZwzwzWzwZ|BsSsSbSsB|zwZwzwzWZ|SsBsSbSsB $$\in \gamma$$
        ZwSsSWSsZ|zwBsSbzsZ|BsSszWzwB|BwBszWSwz $$\not\in \gamma$$

    • $$\delta = \{ b \in \mathcal{B}\,|\,$$ voor en na een letterovergang in $$b$$ staat hetzelfde symbool $$\}$$

      voorbeelden: ZwzwzWzwZ|ZwZwzWzwz|zwZwzWZwz|zwzwZWzwZ $$\in \delta$$
        BsSwzbSwZ|BszsSbSwZ|BsSwzsZbS|SwzsZbzwB $$\not\in \delta$$

    Gebruik een commando uit de grep familie om enkel die regels van het bestand barcodes.txt2 te selecteren, waarvan de multitapcodering behoort tot de opgegeven verzameling.

  2. Beschouw de verzamelingen $$\alpha$$, $$\beta$$, $$\gamma$$ en $$\delta$$ zoals hierboven gedefinieerd. Gebruik nu deze verzamelingen om op de volgende manier een boodschap bestaande uit vier woorden te achterhalen:

    • het eerste woord staat op de unieke regel met multitapcodering uit de verzameling $$\alpha \cap \beta$$

    • het tweede woord staat op de unieke regel met multitapcodering uit de verzameling $$\beta \cap \gamma$$

    • het derde woord staat op de unieke regel met multitapcodering uit de verzameling $$\gamma \cap \delta$$

    • het vierde woord staat op de unieke regel met multitapcodering uit de verzameling $$\delta \cap \alpha$$

    Geef telkens een Unix commando dat elk van deze woorden opzoekt in het bestand en uitschrijft naar standaard uitvoer (zonder het patroon dat aan het woord voorafgaat). Hierbij is het dus niet toegelaten om het woord letterlijk uit te schrijven (bv. echo xxx).