Een QR-code is een tweedimensionale streepjescode die in 1994 werd ontwikkeld door Denso Wave, een dochteronderneming van het Japanse bedrijf Denso. De letters QR zijn een afkorting van Quick Response (snel antwoord). QR-codes zijn vierkant en worden opgebouwd uit zwarte en witte vierkante blokjes. Daardoor kunnen QR-codes ook makkelijk tekstueel voorgesteld worden. In deze opgave worden witte blokjes van een QR-code voorgesteld door spaties, en zwarte blokjes door hekjes (#).

Opgave

Het tekstbestand qr.txt¹ bevat een aantal QR-codes. Elke regel van het bestand correspondeert met één enkele rij van een QR-code, en wordt gevolgd door een verticale streep (|) en een woord dat enkel bestaat uit kleine letters. Gevraagd wordt:

1. Bepaal reguliere expressies voor elk van onderstaande verzamelingen. Daarbij staat $$\mathcal{Q}$$ voor de verzameling van alle mogelijke rijen van QR-codes (strings die enkel bestaan uit spaties en hekjes). Probeer de reguliere expressies bovendien zo kort mogelijk te houden.

   • $$\alpha = \{ q \in \mathcal{Q}\,|\,$$ reeksen hekjes worden telkens van elkaar gescheiden door één enkele spatie $$\}$$

     opmerking: voor de eerste reeks hekjes en na de laatste reeks hekjes mag dus een willekeurig aantal spaties voorkomen.

     voorbeelden:	##␣##␣#␣######␣###␣###␣########␣␣ $$\in \alpha$$
     	␣#␣#␣␣␣␣␣␣###␣###␣###␣####␣###␣␣␣ $$\not\in \alpha$$

   • $$\beta = \{ q \in \mathcal{Q}\,|\,$$ $$q$$ bevat een patroon van lengte 6 dat minstens drie keer voorkomt $$\}$$

     opmerking: herhaalde voorkomens van het patroon mogen elkaar niet overlappen.

     voorbeeld:

     ###␣␣##␣###␣␣##␣␣##␣␣##␣␣####␣␣## $$\in \beta$$

   • $$\gamma = \{ q \in \mathcal{Q}\,|\,$$ reeksen hekjes hebben altijd een even lengte $$\}$$

     voorbeelden:	##␣␣####␣##␣␣##␣␣##␣##␣␣##␣##␣␣␣ $$\in \gamma$$
     	#␣␣#␣␣␣#␣#␣#␣␣##␣##␣␣##␣␣␣#␣␣␣## $$\not\in \gamma$$

   • $$\delta = \{ q \in \mathcal{Q}\,|\,$$ lengte van opeenvolgende reeksen hekjes is dalend $$\}$$

     opmerking: niet noodzakelijk strikt dalend, m.a.w. opeenvolgende reeksen hekjes met gelijke lengte mogen ook.

     voorbeelden:	#######␣######␣###␣###␣##␣#␣␣␣#␣# $$\in \delta$$
     	###␣␣##␣##␣###␣###␣###␣######␣␣## $$\not\in \delta$$

   Gebruik een commando uit de grep familie om enkel die regels van het bestand qr.txt² te selecteren, waarvan het patroon 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 unieke regel met het patroon uit de verzameling $$\alpha \cap \beta$$

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

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

   • Het vierde woord staat op unieke regel met het patroon 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).