Rapport Brainfuck

Table des matières

1. Introduction
2. Méthode de résolution
- 2.1. Implémentation complète
3. Tests
4. Solution de la communauté
5. Conclusion

1. Introduction

1.1. Principe de focntionnment

Url du challenge : https://www.codingame.com/ide/puzzle/what-the-brainfuck

Mise en situation: Brainfuck est un langage de programmation minimaliste composé de 8 commandes. Cependant c’est un langage Turing complet, ce qui signifie que si l’on est très patient et motivé, on peut écrire un programme qui fait n’importe quoi.

L’objectif de ce challenge est de créer un interpréteur Brainfuck entièrement fonctionnel.

Le modèle Brainfuck est composé de trois éléments :

Un tableau de ’S’ cellules d’un octet initialisé à 0, et indexées à partir de 0.
Un pointeur initialisé pour pointer sur la première cellule (index 0) du tableau.
Un programme composé des 8 instructions valides.

Les instructions valides sont :

’>’ : Incrémente le pointeur de 1
’<’ : Décrémente le pointeur de 1
’+’ : Incrémente la valeur de la cellule pointée de 1
’-’ : Décrémente la valeur de la cellule pointée de 1
’.’ : Affiche la valeur de la cellule pointée en tant que caractère ASCII
’,’ : Lit un caractère ASCII et stocke sa valeur dans la cellule pointée
’[’ : Si la valeur de la cellule pointée est 0, saute à la prochaine instruction ’]’ correspondante
’]’ : Si la valeur de la cellule pointée est différente de 0, saute à la prochaine instruction ’[’ correspondante

Remarque : les instructions ’]’ et ’[’ sont appelées des instructions de saut et viennent toujours par paire.

1.2. Données fournies

On reçoit en entrée trois entiers:

’L’ : le nombre de lignes du programme
’S’ : la taille du tableau
’N’ : le nombre de ligne du texte à fournir en entrée

’L’ ligne de programme Brainfuck ’N’ ligne de texte à fournir en entrée

1.3. Données à fournir

La sortie doit être la séquence de caractères imprimée par le programme Brainfuck, ou le message d’erreur correct si un problème est rencontré.

1.4. Contraintes

’N’ est compris entre : 0 < N <= 100
’L’ est compris entre : 0 < L <= 100
’S’ est compris entre : 0 < S <= 100
Il n’y a pas de limite de temps pour ce challenge

2. Méthode de résolution

On commence par définir les variables que l’on va utiliser et récupère les données d’entrée.

int L, S, N, i;
char code[LONGUEUR_LIGNE * MAX_LIGNE] = "";
int array[MAX_ARRAY] = {0};

// Récupération de la taille des données
scanf("%d%d%d", &L, &S, &N);
fgetc(stdin);

On recupère chaque ligne de code en Brainfuck et on le concatène dans une chaîne de caractère.

char buffer[LONGUEUR_LIGNE];
for (i = 0; i < L; i++)
{
    scanf("%[^\n]", buffer);
    fgetc(stdin);
    strcat(code, buffer);
}

On vérifie que le code est correctement formé. Pour cela on compte le nombre de ’[’ et de ’]’ et on vérifie que le nombre de ’[’ est égal au nombre de ’]’.

int len_code = strlen(code);

int nb_acc = 0;
for (i = 0; i < len_code; i++)
{
    if (code[i] == '[')
    {
        nb_acc++;
    }
    else if (code[i] == ']')
    {
        nb_acc--;
    }
}
if (nb_acc != 0)
{
    printf("SYNTAX ERROR");
    return 0;
}

On parcourt le code en incrémentant un curseur. A chaque instruction on effectue l’action correspondante, à l’aide d’un bloc switch.

int n;
int curseur, array_pos = 0;

for (curseur = 0; curseur < len_code; curseur++)
{
    switch (code[curseur])
    {
    
    case '+':
        array[array_pos]++;
        if (array[array_pos] > 255)
        {
            printf("INCORRECT VALUE");
            return 0;
        }
        break;

    case '-':
        array[array_pos]--;
        if (array[array_pos] < 0)
        {
            printf("INCORRECT VALUE");
            return 0;
        }
        break;

    case '.':
        printf("%c", array[array_pos]);
        break;

    case '>':
        array_pos++;
        if (array_pos >= S)
        {
            printf("POINTER OUT OF BOUNDS");
            return 0;
        }
        break;

    case '<':
        array_pos--;
        if (array_pos < 0)
        {
            printf("POINTER OUT OF BOUNDS");
            return 0;
        }
        break;

    case ',':
        scanf("%d", &n);
        if (n < 0 || n > 255)
        {
            printf("INCORRECT VALUE");
            return 0;
        }
        array[array_pos] = n;
        break;

    case '[':
        if (array[array_pos] == 0)
        {
            int boucle = 1;
            while (boucle > 0)
            {
                curseur++;
                if (code[curseur] == '[')
                {
                    boucle++;
                }
                else if (code[curseur] == ']')
                {
                    boucle--;
                }
            }
        }
        break;

    case ']':
        if (array[array_pos] != 0)
        {
            int boucle = 1;
            while (boucle > 0)
            {
                curseur--;
                if (code[curseur] == '[')
                {
                    boucle--;
                }
                else if (code[curseur] == ']')
                {
                    boucle++;
                }
            }
        }
        break;

    default:
        break;

    }
}

Pour l’instruction ’+’, on incrémente la valeur de la cellule pointée de 1. Si la valeur dépasse 255, on affiche un message d’erreur.

case '+':
    array[array_pos]++;
    if (array[array_pos] > 255)
    {
        printf("INCORRECT VALUE");
        return 0;
    }
    break;

Pour l’instruction ’-’, on décrémente la valeur de la cellule pointée de 1. Si la valeur est inférieure à 0, on affiche un message d’erreur.

case '-':
    array[array_pos]--;
    if (array[array_pos] < 0)
    {
        printf("INCORRECT VALUE");
        return 0;
    }
    break;

Pour l’instruction ’.’, on affiche la valeur de la cellule pointée en tant que caractère ASCII.

case '.':
    printf("%c", array[array_pos]);
    break;

Pour l’instruction ’>’ on incrémente le pointeur de 1. Si le pointeur dépasse la taille du tableau, on affiche un message d’erreur.

case '>':
    array_pos++;
    if (array_pos >= S)
    {
        printf("POINTER OUT OF BOUNDS");
        return 0;
    }
    break;

Pour l’instruction ’<’ on décrémente le pointeur de 1. Si le pointeur est inférieur à 0, on affiche un message d’erreur.

case '<':
    array_pos--;
    if (array_pos < 0)
    {
        printf("POINTER OUT OF BOUNDS");
        return 0;
    }
    break;

Pour l’instruction ’,’ on lit un caractère ASCII et on stocke sa valeur dans la cellule pointée. On vérifie que le caractère lu est bien un caractère ASCII compris entre 0 et 255.

case ',':
    scanf("%d", &n);
    if (n < 0 || n > 255)
    {
        printf("INCORRECT VALUE");
        return 0;
    }
    array[array_pos] = n;
    break;

Pour l’instruction ’[’ on vérifie que la valeur de la cellule pointée est différente de 0. Si c’est le cas, on incrémente un compteur de boucle. Tant que le compteur est différent de 0, on parcourt le code en incrémentant le curseur. Si on rencontre un ’[’ on incrémente le compteur de boucle, si on rencontre un ’]’ on décrémente le compteur de boucle. Si le compteur est égal à 0, on sort de la boucle et on continue l’exécution du code.

case '[':
    if (array[array_pos] == 0)
    {
        int boucle = 1;
        while (boucle > 0)
        {
            curseur++;
            if (code[curseur] == '[')
            {
                boucle++;
            }
            else if (code[curseur] == ']')
            {
                boucle--;
            }
        }
    }
    break;

Pour l’instruction ’]’ on vérifie que la valeur de la cellule pointée est différente de 0. Si c’est le cas, on décrémente un compteur de boucle. Tant que le compteur est différent de 0, on parcourt le code en décrémentant le curseur. Similaire à l’instruction ’[’.

case ']':
    if (array[array_pos] != 0)
    {
        int boucle = 1;
        while (boucle > 0)
        {
            curseur--;
            if (code[curseur] == '[')
            {
                boucle--;
            }
            else if (code[curseur] == ']')
            {
                boucle++;
            }
        }
    }
    break;

Si l’instruction n’est pas reconnue, on passe.

default:
    break;

2.1. Implémentation complète

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define LONGUEUR_LIGNE 1024
#define MAX_LIGNE 100
#define MAX_ARRAY 100
#define MAW_LIGNE 100

int main()
{
    int L, S, N, i;
    char code[LONGUEUR_LIGNE * MAX_LIGNE] = "";
    int array[MAX_ARRAY] = {0};
    
    // Récupération de la taille des données
    scanf("%d%d%d", &L, &S, &N);
    fgetc(stdin);

    char buffer[LONGUEUR_LIGNE];
    for (i = 0; i < L; i++)
    {
        scanf("%[^\n]", buffer);
        fgetc(stdin);
        strcat(code, buffer);
    }

    int len_code = strlen(code);
    
    int nb_acc = 0;
    for (i = 0; i < len_code; i++)
    {
        if (code[i] == '[')
        {
            nb_acc++;
        }
        else if (code[i] == ']')
        {
            nb_acc--;
        }
    }
    if (nb_acc != 0)
    {
        printf("SYNTAX ERROR");
        return 0;
    }

    int n;
    int curseur, array_pos = 0;
    
    for (curseur = 0; curseur < len_code; curseur++)
    {
        switch (code[curseur])
        {
        
        case '+':
            array[array_pos]++;
            if (array[array_pos] > 255)
            {
                printf("INCORRECT VALUE");
                return 0;
            }
            break;
    
        case '-':
            array[array_pos]--;
            if (array[array_pos] < 0)
            {
                printf("INCORRECT VALUE");
                return 0;
            }
            break;
    
        case '.':
            printf("%c", array[array_pos]);
            break;
    
        case '>':
            array_pos++;
            if (array_pos >= S)
            {
                printf("POINTER OUT OF BOUNDS");
                return 0;
            }
            break;
    
        case '<':
            array_pos--;
            if (array_pos < 0)
            {
                printf("POINTER OUT OF BOUNDS");
                return 0;
            }
            break;
    
        case ',':
            scanf("%d", &n);
            if (n < 0 || n > 255)
            {
                printf("INCORRECT VALUE");
                return 0;
            }
            array[array_pos] = n;
            break;
    
        case '[':
            if (array[array_pos] == 0)
            {
                int boucle = 1;
                while (boucle > 0)
                {
                    curseur++;
                    if (code[curseur] == '[')
                    {
                        boucle++;
                    }
                    else if (code[curseur] == ']')
                    {
                        boucle--;
                    }
                }
            }
            break;
    
        case ']':
            if (array[array_pos] != 0)
            {
                int boucle = 1;
                while (boucle > 0)
                {
                    curseur--;
                    if (code[curseur] == '[')
                    {
                        boucle--;
                    }
                    else if (code[curseur] == ']')
                    {
                        boucle++;
                    }
                }
            }
            break;
    
        default:
            break;
    
        }
    }

    return 0;
}

3. Tests

3.1. Compilation

Compilation avec gcc :

✅ Compilation sans erreur/warning OK

3.2. Test de Codingame

3.2.1. Test 1 : A simple start

Input:

1 1 0
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.+.+.

Expected output:

ABC

Actual output:

ABC

Run test:

Test 1: A simple start
✅ Test passed

3.2.2. Test 2 : Hello World!

Input:

1 4 0
++++++++++[>+++++++>++++++++++>+++<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.

Expected output:

Hello World!

Actual output:

Hello World!

Run test:

Test 2: Hello World!
✅ Test passed

3.2.3. Test 3 : Inputs multiplication

Input:

1 4 2
,>,><[<[>>+>+<<<-]>>>[<<<+>>>-]<<-]>.
4
9

Expected output:

Actual output:

Run test:

Test 3: Inputs multiplication
✅ Test passed

3.2.4. Test 4 : Noisy code

Input:

35 4 0
++++++++++          Set the first cell (0) to 10
[                   Start of the initialization loop 
   >                Go to cell 1
   +++++++          Set it to 7
   >                Go to cell 2
   ++++++++++       Set it to 10
   >                Go to cell 3
   +++              Set it to 3
   <<<              Go back to cell 0
   -                Decrement it
]                   Loop until cell 0 value is 0
>++                 Add 2 to cell 1 to set it to 72
.                   Print the 'H' character (72)
>+                  Add 1 to cell 2 to set it to 101
.                   Print the 'e' character (101)
+++++++             Add 7 to cell 2 to set it to 108
..                  Print the 'l' character (108) twice
+++                 Add 3 to cell 2 to set it to 111
.                   Print the 'o' character (111)
>++                 Add 2 to cell 3 to set it to 32
.                   Print the ' ' character (32)
<<                  Go back to cell 1
+++++++++++++++     Add 15 to cell 1 to set it to 87
.                   Print the 'W' character (87)
>                   Go to cell 2
.                   Print the 'o' character (111)
+++                 Add 3 to cell 2 to set it to 114
.                   Print the 'r' character (114)
------              Substract 6 to cell 2 to set it to 108
.                   Print the 'l' character (108)
--------            Substract 8 to cell 2 to set it to 100
.                   Print the 'd' character (100)
>                   Go to cell 3
+                   Add 1 to cell 3 to set it to 33
.                   Print the '!' character (33)

Expected output:

Hello World!

Actual output:

Hello World!

Run test:

Test 4: Noisy code
✅ Test passed

3.2.5. Test 5 : Pointer out of bounds

Input:

1 4 0
++++++++++[>+++++++>++++++++++>+++<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.

Expected output:

POINTER OUT OF BOUNDS

Actual output:

POINTER OUT OF BOUNDS

Run test:

Test 5: Pointer out of bounds
✅ Test passed

3.2.6. Test 6 : Incorrect value

Input:

1 4 2
,>,><[<[>>+>+<<<-]>>>[<<<+>>>-]<<-]>.
50
6

Expected output:

INCORRECT VALUE

Actual output:

INCORRECT VALUE

Run test:

Test 6: Incorrect value
✅ Test passed

3.2.7. Test 7 : Syntax error

Input:

1 4 0
++++++++++[>+++++++>++++++++++>+++<<<->++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.

Expected output:

SYNTAX ERROR

Actual output:

SYNTAX ERROR

Run test:

Test 7: Syntax error
✅ Test passed

3.2.8. Test 8 : Multiple errors

Input:

1 4 0
++++++++++[>+++++++>++++++++++>+++><<<--------------------------]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.

Expected output:

POINTER OUT OF BOUNDS

Actual output:

POINTER OUT OF BOUNDS

Run test:

Test 8: Multiple errors
✅ Test passed

✅ Test 1 : A simple start passed
✅ Test 2 : Hello World! passed
✅ Test 3 : Inputs multiplication passed
✅ Test 4 : Noisy code passed
✅ Test 5 : Pointer out of bounds passed
✅ Test 6 : Incorrect value passed
✅ Test 7 : Syntax error passed
✅ Test 8 : Multiple errors passed
Passed: 8 (100.0%)
Failed: 0 (0.0%)

3.3. Test Valgrind

✅ Valgrind check

4. Solution de la communauté

Solution de MJZ :

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

char output[10000], prog[100*1025];
int  storage[100], pStorage, pProgram, pOutput;

void checkBrackets(char* p){
    int depth = 0;
    for(; *p; p++){
        if(*p == '[') depth++;
        if(*p == ']') depth--;
        if(depth < 0) exit(puts("SYNTAX ERROR"));
    }
    if(depth) exit(puts("SYNTAX ERROR"));
}

void search(int dir){
    int depth = dir;
    while(depth){
        pProgram += dir;
        if(prog[pProgram] == '[') depth++;
        if(prog[pProgram] == ']') depth--;
    }
}

int main(){
    int lines, storageSize, inputs;
    scanf("%d%d%d\n", &lines, &storageSize, &inputs);
    for(int i = 0; i < lines; i++) {
        char line[1025];
        fgets(line, 1025, stdin);
        strcat(prog, line);
    }
    checkBrackets(prog);
    for(;; pProgram++) switch(prog[pProgram]){
        case '>': if(++pStorage >= storageSize) return puts("POINTER OUT OF BOUNDS"); break;
        case '<': if(--pStorage < 0)            return puts("POINTER OUT OF BOUNDS"); break;
        case '+': if(++storage[pStorage] > 255) return puts("INCORRECT VALUE");       break;
        case '-': if(--storage[pStorage] < 0)   return puts("INCORRECT VALUE");       break;
        case '.': output[pOutput++] = storage[pStorage];                              break;
        case ',': scanf("%d", &storage[pStorage]);                                    break;
        case '[': if(storage[pStorage] == 0) search(+1);                              break;
        case ']': if(storage[pStorage] != 0) search(-1);                              break;
        case 0:   return puts(output);
        }
}

J’ai trouvé ce code intéressant car il est très bien structuré ce qui facilite grandement la compréhension. De plus il utilise des fonctions pour séparer les différentes actions. Cela permet d’éviter la répétition de code et rendre le code plus lisible. Le code utilise une fonction de recherche pour trouver la fin d’une boucle, ce qui permet de gérer les boucles imbriquées facilement et de réutiliser la fonction pour rechercher le début ou la fin d’une boucle simplement en changeant le paramètre de la fonction avec un +1 ou -1.

Enfin il utilise une boucle infinie pour éviter de devoir gérer la fin du programme. Et toutes les instructions sont dans un seul switch, bien aligné ce qui rend le code plus lisible.

5. Conclusion

Lors de cet exercice, j’ai mis en pratique l’utilisation de switch et des pointeurs. L’exercice m’a permis de découvrir le langage Brainfuck et le principe de langage Turing complet, qui permet avec seulement 8 instructions de faire tout ce que l’on veut, contre un peu de temps

Voici un exemple personnel :

++++++++++[>+>+++>+++++++>++++++++++<<<<-]>>>----.>+++++++++++.-.----.+++++.++++++.---.<<++++++++++++++.------------.>>------.-----------.<<.>++++++++++++++.>+++++++++++++++++.-------------.+++++++++++.<<.>-------.++++++++++.----------.++++.------------.<.+.

Bonjour, la Prep ISIMA !

Retour vers ma page Web personnelle

Crédits :

Template : github