De opgave van een Letter Boxed¹ puzzel bestaat uit een vierkant met drie letters langs elke zijde. Daarbij komt dezelfde letter nooit meer dan één keer voor.

Je vindt een oplossing door de letters rond het vierkant met elkaar te verbinden en zo een reeks woorden te vormen waarvoor geldt dat:

• de reeks is volledig: alle letters rond het vierkant worden gebruikt

• de reeks is opeenvolgend: de laatste letter van elk woord (behalve het laatste) is gelijk aan de eerste letter van het volgende woord

• de reeks is kruisend: opeenvolgende letters van elk woord staan telkens langs twee verschillende zijden

Dezelfde letter mag in de oplossing wel meerdere keren gebruikt worden. Zo vormen de drie kleuren MYSTIC, CORAL en LIVER een oplossing van bovenstaande puzzel.

We hebben de opeenvolgende letters van deze woorden verbonden met een lijn waarvan de kleur correspondeert met het woord van de oplossing waarin de twee letters na elkaar voorkomen. Ook de cirkels bij de beginletters van elk woord hebben we ingekleurd met die kleur.

Opgave

Elke regel van het tekstbestand letter_boxed.txt² bevat een patroon $$p$$ uit de verzameling $$\mathcal{P}$$ van alle strings die bestaan uit een mogelijke oplossing voor een Letter Boxed puzzel, gevolgd door een spatie en de opgave van een puzzel. Zowel de opgave als de mogelijke oplossing worden voorgesteld als een reeks woorden: één of meer woorden die van elkaar gescheiden worden door koppeltekens (-). Daarbij bestaat een woord uit één of meer hoofdletters. Bij de opgave bestaan de woorden uit de letters die langs dezelfde zijde van de puzzel staan.

Zo stellen we de opgave van de puzzel uit de inleiding voor als YOI-RCM-VSA-LTE en de oplossing van die puzzel als MYSTIC-CORAL-LIVER. Deze combinatie zou dus resulteren in het patroon

MYSTIC-CORAL-LIVER YOI-RCM-VSA-LTE

Gevraagd wordt:

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

   • $$\mathcal{P}_1 = \{\,p \in \mathcal{P}\,|\,$$de mogelijke oplossing van $$p$$ is circulair$$\,\}$$

     definitie: een reeks woorden is circulair als de laatste letter van het laatste woord gelijk is aan de eerste letter van het eerste woord

     voorbeelden:	TRICK-BUST-PIGSKIN-SUNSET-INTERNET IUT-KGE-CRS-PNB $$\in \mathcal{P}_1$$
     	MATURED-CATNAP-ENZYME-DANCE-DUE-ADAMANT PET-CRM-UAZ-NDY $$\not \in \mathcal{P}_1$$

   • $$\mathcal{P}_2 = \{\,p \in \mathcal{P}\,|\,$$de mogelijke oplossing van $$p$$ is opeenvolgend$$\,\}$$

     definitie: een reeks woorden is opeenvolgend als de laatste letter van elk woord (behalve het laatste) is gelijk aan de eerste letter van het volgende woord

     voorbeelden:	SANDING-GARNET-TWELVES-SLAVERED-DRAIN-NEWEL ASG-TWR-LND-EVI $$\in \mathcal{P}_2$$
     	GUEST-PLUCKING-PIECE-PECANS-LANCE-LETS KEN-ASP-TUI-CGL $$\not \in \mathcal{P}_2$$

   • $$\mathcal{P}_3 = \{\,p \in \mathcal{P}\,|\,$$de mogelijke oplossing van $$p$$ is beknopt$$\,\}$$

     definitie: een reeks woorden is beknopt als dezelfde letter nooit meerdere keren in de reeks voorkomt, behalve eventueel één keer als laatste letter van een woord en als eerste letter van het volgende woord

     voorbeelden:	CREW-WANT-OLD-DUG GRA-CTE-DNU-WLO $$\in \mathcal{P}_3$$
     	SEISMIC-BELTWAYS-LEAKY-BASAL YEW-IKL-MBS-TCA $$\not \in \mathcal{P}_3$$

   • $$\mathcal{P}_4 = \{\,p \in \mathcal{P}\,|\,$$de mogelijke oplossing van $$p$$ is kruisend$$\,\}$$

     definitie: een oplossing is kruisend als opeenvolgende letters van elk woord in de opgave van de puzzel telkens langs twee verschillende zijden staan

     voorbeelden:	OBDURACY-BARGES-VERY-RESCUE-CURER OEA-CGD-SYU-VRB $$\in \mathcal{P}_4$$
     	SCROTA-ARTWORK-MINICAMS WNT-KRS-AOC-IMG $$\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:

   • woord $$w_1$$ bestaat uit het eerste woord van de oplossing op de unieke regel waarvan $$p$$ behoort tot $$\mathcal{P}_1 \cap \mathcal{P}_2$$

   • woord $$w_2$$ bestaat uit het eerste woord van de oplossing op de unieke regel waarvan $$p$$ behoort tot $$ \mathcal{P}_2 \cap \mathcal{P}_3$$

   • woord $$w_3$$ bestaat uit het eerste woord van de oplossing op de unieke regel waarvan $$p$$ behoort tot $$\mathcal{P}_3  \cap \mathcal{P}_4$$

   • woord $$w_4$$ bestaat uit het eerste woord van de oplossing 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 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 woord $$w_j$$ letterlijk uit te schrijven (bv. echo $$w_j$$).