Het alfabet bestaat uit 26 karakters, terwijl het toetsenbord van een mobiele telefoon of een GPS doorgaans veel minder toetsen bevat. Om op dergelijke toestellen toch makkelijk woorden te kunnen intoetsen, werd oorspronkelijk gebruik gemaakt van de zogenaamde MultiTap techniek. Het principe is eenvoudig: op elke toets worden drie of meer letters afgebeeld (2=ABC, 3=DEF, 4=GHI, 5=JKL, 6=MNO, 7=PQRS, 8=TUV, 9=WXYZ). Om de gewenste letter te krijgen, moet je de toets waarop de letter wordt afgebeeld één of meer keer indrukken, afhankelijk van de positie van de letter op de toets.

Multitap keyboard

Stel dat je bijvoorbeeld de letter A wilt typen. Dan moet je één keer op toets 2 drukken. Wil je echter een B typen, dan moet je twee keer kort na elkaar op toets 2 drukken. Om na elkaar twee letters te typen die op dezelfde toets worden afgebeeld, moet de gebruiker een korte pauze inlassen alvorens dezelfde toets opnieuw in te drukken. We zullen een spatie (␣) gebruiken om een dergelijke pauze voor te stellen. Op die manier staat 2␣2 voor AA, terwijl 22 staat voor B.

Opgave

Elke regel van het tekstbestand multitap.txt1 bevat de multitapcodering van een woord dat enkel bestaat uit letters van het alfabet, gevolgd door een spatie en het woord zelf. Aangezien de multitapcodering zelf ook spaties kan bevatten, kan het dus gebeuren dat er meerdere spaties voorkomen op één enkele regel. Gevraagd wordt:

  1. Bepaal reguliere expressies voor elk van onderstaande verzamelingen. Daarbij staat $$\mathcal{M}$$ voor de verzameling van alle multitapcoderingen van woorden die enkel bestaat uit letters van het alfabet. Als $$m$$ de multitapcodering van een woord voorstelt, dan stelt $$m'$$ de multitapcodering voor waaruit de spaties verwijderd zijn. Probeer de reguliere expressies bovendien zo kort mogelijk te houden

    • $$\alpha = \{ m \in \mathcal{M}\,|\,$$ bij elke spatie in $$m$$ staan er 2 posities daarvoor en 2 posities daarachter 2 verschillende cijfers waarvan de som gelijk is aan 8; als $$m$$ meerdere spaties heeft, dan zijn opeenvolgende spaties minstens gescheiden door 4 cijfers $$\}$$

      voorbeelden: 222 266222 266 $$\in \alpha$$
        6444 44555 5777, 6444 44444 4477, 6444 444 4477 $$\not\in \alpha$$

    • $$\beta = \{ m \in \mathcal{M}\,|\,$$ opeenvolgende cijfers van $$m'$$ vormen steeds een stijgende rij $$\}$$

      voorbeelden: 22335566 66678 $$\in \beta$$
        444663 33997777 7 777666 664 $$\not\in \beta$$

    • $$\gamma = \{ m \in \mathcal{M}\,|\,$$ $$m'$$ bevat minstens 2 reeksen van minstens 4 opeenvolgende gelijke cijfers $$\}$$

      voorbeelden: 55533 33777799992 2555, 777666877 77777 7833 3366 $$\in \gamma$$
        777444777744422266677733 388222844433 $$\not\in \gamma$$

    • $$\delta = \{ m \in \mathcal{M}\,|\,$$ elk cijfer van $$m'$$ is gelijk aan het vorige of volgende cijfer (of beide) $$\}$$

      voorbeelden: 3366 666777 7777883 3 33777 $$\in \delta$$
        77778666 666 68882 27778 88444 4 $$\not\in \delta$$

    Gebruik een commando uit de grep familie om enkel die regels van het bestand multitap.txt2 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 de unieke regel met het patroon uit de verzameling $$\alpha \cap \beta$$

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

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

    • het vierde woord staat op de 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).