In 1993 stelde Robert A. Hayden van de Minnesota State University¹ (Mankato, VS) een eenvoudige code voor waarmee zelfverklaarde geeks elkaar in e-mailhandtekeningen² en Usenet berichten³ konden informeren over hun interesses, meningen en vaardigheden.

Hayden's specificatie van Geek Code⁶ versie 3.12 werd hier⁷ gearchiveerd. De code bestaat uit 34 categorieën, elk met een uniek label van één of meer letters of cijfers. De specificatie legt voor elke categorie een verzameling kwalificaties vast die telkens bestaan uit het label van de categorie, mogelijks voorafgegaan en/of gevolgd door leestekens en/of letters (geen spaties).

Om een persoonlijke Geek Code te construeren, moet men alle categorieën overlopen in de volgorde zoals ze in de specificatie vastgelegd zijn en telkens een kwalificatie kiezen die het best de (voorkeur van de) geek beschrijft. Al deze kwalificaties worden samengevoegd tot één regel — met een spatie als scheidingsteken — om andere geeks over de hele wereld te informeren over wat een geweldige nerd de persoon eigenlijk wel is.

Opgave

Een Geek Code begint met de letter G (voor geek) gevolgd door de specialisatie(s) van de geek (type of geek). Zo staat GMU bijvoorbeeld voor geek of music (muziek). Voor geeks met meerdere specialisaties worden de specialisaties van elkaar gescheiden door slashes. Zo staat GMD/TW bijvoorbeeld voor een geek of medicine (geneeskunde) en een geek of technical writing (technisch schrijven⁸). Er zijn 28 verschillende specialisaties waaruit kan gekozen worden.

Hieronder geven we nog enkele verzamelingen van kwalificaties voor categorieën die in deze opgave vermeld worden. De categorieën staan opgelijst in de volgorde waarin ze ook in de Geek Code voorkomen. Bij de categorie age (a) die de leeftijd van een geek omschrijft, is het belangrijk om te vermelden dat ook de exacte leeftijd kan aangegeven worden door de leeftijd in jaren na het label a te plaatsen. Zo omschrijft a42 bijvoorbeeld een geek van 42 jaar.

Elke regel van het tekstbestand geek.txt¹⁴ bestaat uit een woord $$w \in \mathcal{W}$$, gevolgd door een hekje (#) en een patroon $$p \in \mathcal{P}$$. De verzameling $$\mathcal{W}$$ bevat alle woorden die enkel bestaan uit letters. De verzameling $$\mathcal{P}$$ bevat alle mogelijke persoonsomschrijvingen die voldoen aan de specificatie van de Geek Code. De kwalificatie voor de categorie met label $$\texttt{c}$$ uit Geek Code $$p \in \mathcal{P}$$ wordt aangeduid met $$p(\texttt{c})$$. De notatie $$p'(\texttt{c})$$ wordt gebruikt voor de kwalificatie $$p(\texttt{c})$$ waarin het label wordt vervangen door een universeel karakter. Bijvoorbeeld, voor $$p(\texttt{PGP}) = \texttt{--PGP++}$$ wordt $$p'(\texttt{PGP}) = \texttt{--#++}$$ met een hekje (#) als universeel karakter. Gevraagd wordt:

1. Bepaal zo kort mogelijke reguliere expressies voor de volgende deelverzamelingen van $$\mathcal{P}$$:

   • $$\mathcal{P}_1 = \{\,p \in \mathcal{P}\,|\,p(\texttt{a})\ $$omschrijft een leeftijd tussen 30 en 39 jaar$$\,\}$$

     voorbeeld:	GMD d- s+: a C+++ UU+++ P++++ L? E+ W? N+ o- K w+++ O++ M- V++ PS+ PE-- Y+++ PGP- t+++ 5- X++ R++ tv++>- b-- DI-- D+++ G+ e- h--- r+ y-- $$\in \mathcal{P}_1$$
     	GCA d- s--:- a35 C- UO++ P L E+++ W+ N---- o K+++++ w+(++++) O? M-- V++ PS PE+++ Y--- PGP+ t++ 5-- X++ R tv- b DI--- D++ G++ e+++ h+ r++ z-- $$\in \mathcal{P}_1$$
     	GCC d--- s+++:++ a-- C+++ U++ P-- L- E-- W+++ N-- o+++ K w--- O M$ V PS--- PE? Y+++ PGP++++ t+ 5-- X+ R tv+>$ b++++ DI-- D G+ e h---- r* x-- $$\not \in \mathcal{P}_1$$

   • $$\mathcal{P}_2 = \{\,p \in \mathcal{P}\,|\,p'(\texttt{t}) = p'(\texttt{X}) = p'(\texttt{DI})\ ^{(*)} \,\}$$

     (*) met andere woorden: op het label na heeft $$p$$ dezelfde kwalificatie voor Star Trek (t), X-files (X) en Dilbert (DI); hou rekening met het feit dat er in een kwalificatie zowel karakters (geen spaties) voor als na het label kunnen staan, bijvoorbeeld !t of t+++
     

     voorbeeld:	GMC/PA d--->+ s+++:--- a--- C+++ U--- P- L+ E+++ W N+ o++ K+++ w+@ O+++ M- V++ PS- PE++ Y+ PGP- t++ 5- X++ R* tv+ b++ DI++ D+ G+++++ e++++ h !r x? $$\in \mathcal{P}_2$$
     	GED/TW !d s+:+ a-- C UI++++ P--- L--- E+ W++ N---- o+ K++ w++ O--- !M V+++ PS PE-- Y+++ PGP t+++$ 5-- X++ R tv++ b-- DI++++ D G- e+++ h+ r--- !z+ $$\not \in \mathcal{P}_2$$

   • $$\mathcal{P}_3 = \{\,p \in \mathcal{P}\,|\,p\ $$bevat minstens zes kwalificaties waarvan het deel na het label gelijk is aan +++$$\,\}$$

     voorbeeld:	GL/MU/IT/PA d- s++:+ a94 C+++ U- P++++ L+++ E W- N+ o++($) K-- w+ O-- M-- V-$ PS PE++ Y-- PGP++++ t+++ 5+++ X+++ R* tv b++ DI+ D+++ !G e++ h++ r- z** $$\in \mathcal{P}_3$$
     	GB/ED/M !d s+:+++ a56 C++ U++ P L+ E--- W++ N---- o++ K+++ w++ O---- M? V- PS--$ PE Y--- PGP t* 5++++ X-- R tv+$ b++ DI--$ D---- G-- e++ h- !r z+ $$\not \in \mathcal{P}_3$$

   • $$\mathcal{P}_4 = \{\,p \in \mathcal{P}\,|\,p\ $$omschrijft een geek met juist drie specialisaties, maar geen computer science (CS), information technology (IT), math (M) of science (S)$$\,\}$$

     voorbeeld:	GJ/AT/CA d? s+++:- a-- C++ U- P++ L-- E---- W- N o K++ w O+++ M++ V++ PS- PE+ Y PGP t++ 5+ X++++ R++ tv- b+++ DI+++ D++++ G-- e++ h++ r-- y $$\in \mathcal{P}_4$$
     	GSS/C dpu s:-- a42 C+++ U+ P+ L+++ E--- W-- N--- !o K+++++ w+++++ O@ M++ V+ PS--- PE+ Y-- PGP-- t 5++++ X R* tv+ b- DI+++ D--- G+++++ e+ h--- r-- z++++ $$\not \in \mathcal{P}_4$$
     	GCM/CS/C dpu s++:-- a !C U+ P++++ L--- E---- W+++ N o+ K w- O- M- V-- PS+>--- PE+ Y+ PGP--- t->$ 5++++ X+ R-- tv-->++ b-- DI+(+++) D++++ G e++ h r+ z $$\not \in \mathcal{P}_4$$

   Geef telkens een Unix commando waarin de reguliere expressie gebruikt wordt door een commando uit de grep familie om enkel de regels van het tekstbestand naar stdout te schrijven waarvan het patroon $$p$$ behoort tot $$\mathcal{P}_i\ (i = 1, 2, 3, 4)$$.

2. Bepaal als volgt de woorden $$w_1\ w_2\ w_3\ w_4$$ van een geheime boodschap:

   • het woord $$w_1$$ staat op de unieke regel waarvan $$p$$ behoort tot $$\mathcal{P}_1 \cap \mathcal{P}_2$$

   • het woord $$w_2$$ staat op de unieke regel waarvan $$p$$ behoort tot $$ \mathcal{P}_2 \cap \mathcal{P}_3$$

   • het woord $$w_3$$ staat op de unieke regel waarvan $$p$$ behoort tot $$\mathcal{P}_3  \cap \mathcal{P}_4$$

   • het woord $$w_4$$ staat op de unieke regel waarvan $$p$$ behoort tot $$\mathcal{P}_4 \cap \mathcal{P}_1$$

   Geef telkens een Unix commando waarin de reguliere expressies voor de verzamelingen $$\mathcal{P}_i\ (i = 1, 2, 3, 4)$$ gebruikt worden door commando's uit de grep familie om het woord $$w_j\ (j = 1, 2, 3, 4)$$ op te zoeken in het tekstbestand en uit te schrijven naar stdout. Hierbij is het niet toegelaten om het woord $$w_j$$ letterlijk uit te schrijven (bv. echo $$w_j$$).