Een universally unique identifier¹ (UUID) is een getal van 128 bits dat door computersystemen gebruikt wordt om wereldwijd de identiteit van objecten te kunnen bepalen. Daarom wordt dit concept soms ook aangeduid met de term globally unique identifier (GUID).

In tegenstelling tot de meeste andere identificatieprotocols is het genereren van UUIDs niet afhankelijk van een centraal register en vraagt het ook geen coördinatie tussen de partijen die ze genereren. Als UUIDs volgens de standaardmethoden gegenereerd worden, dan kunnen ze in de praktijk als wereldwijd uniek beschouwd worden. Hoewel het niet onmogelijk is dat dezelfde UUID meerdere keren gegenereerd wordt, ligt de kans daarop dicht genoeg bij nul om verwaarloosbaar te zijn.

Daarom kan iedereen onafhankelijk van anderen UUIDs genereren en gebruiken als wereldwijde identiteit van objecten. Er wordt immers met quasi zekerheid gegarandeerd dat de identiteit van de objecten geen duplicaat is van de identiteit die door iemand anders aan een andere object wordt toegekend. Daardoor hebben objecten die door onafhankelijke partijen met UUIDs geïdentificeerd worden een verwaarloosbare kans om door elkaar gehaald te worden als ze later in één enkele databank gecombineerd worden of als ze over hetzelfde communicatiekanaal verzonden worden.

De structuur en de tekstuele voorstelling van UUIDs worden vastgelegd in de RFC 4122² standaard. In de canonieke tekstuele voorstelling worden de zestien octetten ($16\times 8$ bits = $128$ bits) van een UUID weergegeven in vijf groepen die van elkaar gescheiden worden door koppeltekens:

550e8400-e29b-41d4-a716-446655440000

De groepen bestaan respectievelijk uit 8, 4, 4, 4 en 12 hexadecimale cijfers³, voor een totaal van 36 tekens (32 alfanumerieke tekens en vier koppeltekens). Onder de hexadecimale cijfers maken we onderscheid tussen cijfers (0-9) en letters (a-f). RFC 4122 legt ook vast dat kleine letters moeten gebruikt worden voor de hexadecimale cijfers.

Opgave

Elke regel van het tekstbestand uuid.txt⁴ bestaat uit een patroon $p\in \mathcal{P}$, gevolgd door een spatie en een woord $w\in \mathcal{W}$. De verzameling $\mathcal{P}$ bevat de canonieke tekstuele voorstelling (volgens RFC 4122) van alle mogelijke UUIDs. De verzameling $\mathcal{W}$ bevat alle woorden die enkel bestaan uit letters. Gevraagd wordt:

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

   • ${\mathcal{P}}_1=\{p\in \mathcal{P}|$in elke groep van $p$ zijn alle hexadecimale cijfers verschillend$\}$

     voorbeeld:	a91e35fd-b0d4-b95a-fdb0-f0d7b839c645 $\in {\mathcal{P}}_1$
     	0fa05af9-87e9-49d0-bfdd-463e9993f90f $\notin {\mathcal{P}}_1$

   • ${\mathcal{P}}_2=\{p\in \mathcal{P}|$de tweede en de derde groep van $p$ hebben geen enkel hexadecimaal cijfer gemeenschappelijk$\}$

     voorbeeld:	6482cf60-dbf8-412c-a63c-d2b50e92ed6d $\in {\mathcal{P}}_2$
     	7b17ccef-f9f2-4597-aa0d-5f186d206a36 $\notin {\mathcal{P}}_2$

   • ${\mathcal{P}}_3=\{p\in \mathcal{P}|$in elke groep van $p$ staan de letters in strikt alfabetische volgorde$\}$

     voorbeeld:	9a578cf1-bc9f-49ad-8294-a61b736088c5 $\in {\mathcal{P}}_3$
     	64efc3d9-448a-4902-a6c6-61849ac6c7ef $\notin {\mathcal{P}}_3$

   • ${\mathcal{P}}_4=\{p\in \mathcal{P}|$er is een hexadecimaal cijfer dat in elke groep van $p$ minstens één keer voorkomt$\}$

     voorbeeld:	2beb1c38-8158-4448-a280-28c46a515b87 $\in {\mathcal{P}}_4$
     	cd53e91b-4bce-4e58-ad28-9416cf468d71 $\notin {\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}}_{\mathcal{2}}$

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

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

   • het woord $w_4$ staat op de unieke regel waarvan $p$ behoort tot ${\mathcal{P}}_4\cap {\mathcal{P}}_{\mathcal{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$).