Als we de Engelse namen van alle natuurlijke getallen na elkaar in woorden zouden uitschrijven, welke letter komt dan het vaakst voor? Frank Rubin toonde in 1981 aan dat de letter E in deze wedstrijd nooit wordt ingehaald door de letter I. Als we
NINE HUNDRED NINETY-NINE
bereiken, dan is de letter E in totaal 3.130 keer voorgekomen en de letter I slechts 1.310 keer. Na
NINE HUNDRED NINETY-NINE THOUSAND NINE HUNDRED NINETY-NINE
zijn elk van de namen ONE tot NINE HUNDRED NINETY-NINE juist 1.000 keer voorgekomen links van het woord THOUSAND en 999 keer rechts ervan, waardoor bij
ONE MILLION
de letter E in totaal 6.260.000 keer is voorgekomen en de letter I slechts 2.620.000 keer.
Dit gat wordt nooit meer dichtgereden. Het wordt kleiner als een woord dat eindigt op -ILLION twee of meer I's bevat en geen E's, maar als het ook de letter E bevat (SEXTILLION, SEPTILLION) dan wordt het weer groter. Het wordt het kleinst wanneer we bij ONE SEXTILLION in totaal $$2,191 \times 10^{22}$$ keer de letter E en $$2,0159 \times 10^{22}$$ keer de letter I hebben uitgeschreven.
De enige twee letters die we op een bepaald moment vaker hebben uitgeschreven dan de letter E zijn de letter O op het einde van TWO en de letter T aan het begin van THREE. Daarna geeft de letter E de koppositie nooit meer uit handen.
De Engelse naam van een natuurlijke getal wordt uitgeschreven als een reeks woorden, die telkens van elkaar gescheiden worden door één of meer opeenvolgende spaties, koppeltekens (-) en/of komma's (,). Zo wordt het getal 987.654.321 bijvoorbeeld uitgeschreven als deze reeks van 17 woorden:
NINE HUNDRED AND EIGHTY-SEVEN MILLION, SIX HUNDRED AND FIFTY-FOUR THOUSAND, THREE HUNDRED AND TWENTY-ONE
Merk hierbij op dat we EIGHTY-SEVEN als twee afzonderlijke woorden tellen.
Elke regel van het tekstbestand numbers.txt1 bestaat uit een patroon $$p \in \mathcal{P}$$, gevolgd door één spatie en een woord $$w \in \mathcal{W}$$. De verzameling $$\mathcal{P}$$ bevat de namen van alle natuurlijke getallen, uitgeschreven in woorden en in hoofdletters. De verzameling $$\mathcal{W}$$ bevat alle woorden die enkel uit kleine letters bestaan. Gevraagd wordt:
Bepaal zo kort mogelijke reguliere expressies voor de volgende deelverzamelingen van $$\mathcal{P}$$:
$$\mathcal{P}_1 = \{\,p \in \mathcal{P}\,|\,p\ $$bestaat uit zeven, acht of negen woorden$$\,\}$$
| voorbeeld: | |
$$\mathcal{P}_2 = \{\,p \in \mathcal{P}\,|\,$$elk woord van $$p$$ begint met een verschillende letter$$\,\}$$
| voorbeeld: | |
$$\mathcal{P}_3 = \{\,p \in \mathcal{P}\,|\,$$het aantal medeklinkers in $$p$$ is een drievoud$$\ ^{(*)}\,\}$$
(*) de medeklinkers zijn de letters B, C,
D, F, G, H,
J, K, L, M,
N, P, Q, R,
S, T, V, W,
X, Y en Z (dus
inclusief de letter Y)
| voorbeeld: | |
$$\mathcal{P}_4 = \{\,p \in \mathcal{P}\,|\,$$dezelfde reeks van vier of meer opeenvolgende hoofdletters komt minstens drie keer voor in $$p\,\}$$
| voorbeeld: | |
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)$$.
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$$).