Brainfuck1 is een esoterische programmeertaal die in 1993 werd ontwikkeld door Urban Muller. Müllers doel was een Turing-complete programmeertaal te maken die met de kleinst mogelijke compiler zou kunnen geïmplementeerd worden, geïnspireerd op de 1024-byte compiler voor de programmeertaal FALSE. Er werden dan ook verschillende brainfuck compilers ontwikkeld die kleiner zijn dan 200 bytes. Zoals de naam reeds doet vermoeden zijn brainfuck programma's over het algemeen moeilijk te begrijpen. Daar staat tegenover dat elke Turingmachine — en daardoor ook brainfuck — elke rekentaak kan volbrengen.
De taal is gebaseerd op een zeer eenvoudige virtuele machine die — buiten het programma — bestaat uit een rij van bytes die op nul zijn gezet, een data-pointer die wijst naar een element van de rij (startwaarde van de data-pointer is de eerste byte) en twee rijen bytes die de invoer en uitvoer vormen. De acht statements waaruit de taal bestaat en die elk worden voorgesteld door één enkel karakter, staan opgelijst in onderstaande tabel.
| karakter | betekenis |
|---|---|
| > | verhoog data-pointer |
| < | verlaag data-pointer |
| + | verhoog byte waarnaar data-pointer wijst |
| - | verlaag byte waarnaar data-pointer wijst |
| . | geef byte waarnaar data-pointer wijst als ASCII-uitvoer |
| , | gebruik volgende ASCII-invoerbyte om byte waarnaar data-pointer wijst in te vullen |
| [ | spring voorwaarts naar statement na corresponderende ] indien byte waarnaar pointer wijst nul is |
| ] | spring terug naar statement achter corresponderende [ indien byte waarnaar pointer wijst nul is |
Zoals dat gebruikelijk is bij haakjes, moeten ook in brainfuck de vierkante haakjes matchen. Onderstaande brainfuck programmacode genereert bijvoorbeeld de tekst Hello World!
++++++++++[ >+++++++ >++++++++++ >+++ >+ < < < < -] >++. >+.+++++++..+++. >++. < <+++++++++++++++. > .+++.------.--------.>+.>.
Op elke regel van het tekstbestand brain.txt2 staat een stukje brainfuck programmacode, gevolgd door een spatie en een woord dat enkel bestaat uit letters van het alfabet. Dit woord is de uitvoer die gegenereerd wordt door de voorafgaande brainfuck programmacode. Elk stukje brainfuck code bevat telkens één paar overeenkomstige vierkante haakjes. In onderstaande uitleg zullen we het codefragment tussen de vierkante haakjes benoemen als de lus, het codefragment voor het openende vierkante haakje als de initialisatie en het codefragment dat volgt op het afsluitende vierkante haakjes als de uitvoer.
Gevraagd wordt:
Bepaal reguliere expressies voor elk van onderstaande verzamelingen, waarbij $$\mathcal{B}$$ de verzameling voorstelt van alle brainfuck programma's met één paar overeenkomstige vierkante haakjes. Probeer deze reguliere expressies bovendien zo kort mogelijk te houden.
$$\alpha = \{ b \in \mathcal{B}\,|\,$$ codefragment tussen eerste twee punten van uitvoer van $$b$$ is minstens negen karakters lang, en komt ook voor in lus van $$b$$ $$\}$$
| voorbeelden: | |
$$\beta = \{ b \in \mathcal{B}\,|\,$$ uitvoer van $$b$$ bevat puntloze reeks $$r$$ van minstens twee karakters lang die minstens drie keer na elkaar herhaald wordt met tussenliggende punten $$\}$$
opmerking: puntloze reeks $$r$$ is substring van uitvoer die zelf geen punten bevat, en die start aan het begin van de uitvoer of begint met een punt en stopt aan het einde van de uitvoer of eindigt met een punt (longest match principe)
| voorbeeld: |
$$\gamma = \{b \in \mathcal{B}\,|\,$$ elke reeks opeenvolgende <-tekens heeft steeds oneven lengte, en ook elke reeks opeenvolgende >-tekens heeft steeds oneven lengte $$\}$$
$$\delta = \{ b \in \mathcal{B}\,|\,$$ elk zevende symbool van $$b$$ is een plusteken $$\}$$
| voorbeeld: |
Gebruik een commando uit de grep familie om enkel die regels van het bestand brain.txt3 te selecteren met het patroon dat behoort tot de opgegeven verzameling.
Beschouw de verzamelingen $$\alpha$$, $$\beta$$, $$\gamma$$ en $$\delta$$ zoals hierboven gedefinieerd. Gebruik nu deze verzamelingen om op de volgende manier een boodschap bestaande uit vier woorden te achterhalen:
het eerste woord staat op de unieke regel met het patroon uit de verzameling $$\alpha \cap \beta$$
het tweede woord staat op de unieke regel met het patroon uit de verzameling $$\beta \cap \gamma$$
het derde woord staat op de unieke regel met het patroon uit de verzameling $$\gamma \cap \delta$$
het vierde woord staat op de unieke regel met het patroon uit de verzameling $$\delta \cap \alpha$$
Geef telkens een Unix commando dat elk van deze woorden opzoekt in het bestand en uitschrijft naar standaard uitvoer (zonder het patroon dat aan het woord voorafgaat). Hierbij is het dus niet toegelaten om het woord letterlijk uit te schrijven (bv. echo xxx).