In 2004 verscheen op verschillende plaatsen in de Verenigde Staten een mysterieus reclamebord:

De meeste mensen weten wel dat de wiskundige constante $$e$$ het grondtal is van de natuurlijke logaritme¹, maar zoeken naar priemgetallen van 10 cijfers is geen eenvoudige opdracht. Gelukkig is het eerste priemgetal van 10 cijfers in $$e$$ al te vinden vanaf positie 101:

2.718281828459045235360287471352662497757247093699959574966967627724076630353
  547594571382178525166427427466391932003059921817413596629043572900334295260
  595630738132328627943490763233829880753195251019011573834187930702154089149
  934884167509244761460668082264800168477411853742345442437107539077744992069
  551702761838606261331384583000752044933826560297606737113200709328709127443

Wie het mysterie had opgelost en de website http://7427466391.com² bezocht, vond er een nog moeilijker probleem. De oplossing van dat probleem leidde naar een pagina bij Google Labs … waarop een uitnodiging stond om een CV in te dienen.

Opgave

We zijn niet op zoek naar priemgetallen maar naar iets eenvoudiger patronen die voorkomen in de cijfers van de wiskundige constante $$e$$. Elke regel van het tekstbestand digits.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 alle reeksen van opeenvolgende cijfers. De patronen die in het bestand staan zijn telkens de volgende 60 decimale cijfers van de wiskundige constante $$e$$. De verzameling $$\mathcal{W}$$ bevat alle woorden die enkel bestaan uit kleine letters. Gevraagd wordt:

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

   • $$\mathcal{P}_1 = \{\,p \in \mathcal{P}\,|\,$$som van eerste en laatste cijfer van $$p$$ is gelijk aan 12$$\,\}$$

     voorbeeld:	312189912421733955068877864313075002482336183273872969737659 $$\in \mathcal{P}_1$$
     	317454432906113834427768225511953359450964542974965387300552 $$\not \in \mathcal{P}_1$$

   • $$\mathcal{P}_2 = \{\,p \in \mathcal{P}\,|\,p$$ bevat quadruplet¹ dat direct gevolgd wordt door omgekeerde quadruplet$$\,\}$$

     ¹ een quadruplet is een reeks van vier opeenvolgende cijfers; het omgekeerde quadruplet heeft de cijfers in omgekeerde volgorde

     voorbeeld:	182546821879197195775913646990334225861823363434184764460488 $$\in \mathcal{P}_2$$
     	817395598341290884664992191254332273554246324185540434071023 $$\not \in \mathcal{P}_2$$

   • $$\mathcal{P}_3 = \{\,p \in \mathcal{P}\,|\,$$alle tripletten² van $$p$$ zijn verschillend$$\,\}$$

     ² een triplet is een reeks van drie opeenvolgende cijfers; tripletten van $$p$$ kunnen elkaar overlappen

     voorbeeld:	915333276744766778516698071719343932220310951004535113777124 $$\in \mathcal{P}_3$$
     	720384504322443540078746749456696455310882062002538066754500 $$\not \in \mathcal{P}_3$$

   • $$\mathcal{P}_4 = \{\,p \in \mathcal{P}\,|\,p$$ bevat een oneven aantal even cijfers$$\,\}$$

     voorbeeld:	617592982744463332097958931321177673952240461419211613357318 $$\in \mathcal{P}_4$$
     	058982406762373406449857531714631332550639355128465018723271 $$\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$$).