Brainfuck

Table of Contents

prepisima.png 2560px-CodinGame_Logo.svg.png

1. Présentation du puzzle

L’objectif de ce puzzle est de construire un language de programmation minimaliste de 8 commandes. “Brainfuck” comporte 3 éléments. Un tableau de S éléments initialisée pour chaque élément à 0. Un pointeur initialisée à 0 pour pouvoir pointer sur les éléments du tableau. Un programme construit de 8 instructions valide. Ces Instructions sont les suivantes:

  • > Pour incrémenter le pointeur
  • < Pour décrémenter le pointeur
  • + incremente la valeur de cellule ou le pointeur pointe
  • - decremente la valeur de cellule ou le pointeur pointe.
  • , accepte un entier positif d’un octet en entrée et le stocke dans la cellule pointée.
  • [ sauter à l’instruction après le ] correspondant si la valeur de la cellule pointée est 0.
  • ] revenir à l’instruction après le [ correspondant si la valeur de la cellule pointée est différente de 0.

Dans certains cas, des erreurs peuvent être rencontrées. Lorsque cela se produit, vous devez arrêter l’exécution du progra wvmme et afficher le message d’erreur correct parmi la liste suivante :

  • “ERREUR DE SYNTAXE” si un [ semble n’avoir aucun ] vers lequel sauter, ou vice versa. Notez que cette erreur doit être levée avant l’exécution du programme, peu importe sa position dans le code Brainfuck.
  • “POINTER OUT OF BOUNDS” si la position du pointeur passe en dessous de 0 ou au dessus de S - 1.
  • “VALEUR INCORRECTE” si après une opération la valeur d’une cellule devient négative ou supérieure à 255.

2. Présentation de ma méthode de résolution

2.1. Description

Tout d’abord je récupère les valeurs L,S. S correspond à la longueur du tableau. L correspond à la longueur de la chaine de caractère en entrée. J’initialise un tableau de longueur de S à 0. Puis je récupère la ligne de commande sous forme de str. Ensuite je vérifie d’abord si il y a “SYNTAX ERROR”. Cela signifie qu’une boucle ou plusieurs n’a pas été ouverte ou fermée. Pour vérifier cela j’utilise un compteur (variable boucle) qui s’incrémente de 1 lorsque un [ est rencontré et décrémente de 1 si un ] est rencontré. Si ce compteur vaut 0 alors il n’y a pas de “SYNTAX ERROR” sinon il y en a une. Ensuite si il n’y a pas de “SYNTAX ERROR” je boucle sur chaque commande de la ligne. Pour étudier chaque cas j’utilise un switch:

  • > Incrémente le pointeur si pointeur<S-1
  • < Décrémenter le pointeur si pointeur>1
  • + incremente la valeur de cellule ou le pointeur pointe si la valeur ne dépasse pas 255
  • - decremente la valeur de cellule ou le pointeur pointe si la valeur n’est pas en dessous de 0
  • , accepte un entier positif d’un octet en entrée et le stocke dans la cellule pointée.
  • [ stocke dans un tableau la position du [ et se déplace à finboucle si la valeur de la cellule pointée est différente de 0
  • ] revient à l’instruction après le [ stockée dans le tableau debutboucle si la valeur de la cellule pointée est différente de 0

2.2. Graphe de ma méthode algorithmique

mon_graphe.png

2.3. Code

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

int main()
{
    int L;
    int S;
    int N;
    int i;
    char lignecom[10000]=""; //chaine de caractère pour contenir la ligne de commande
    int pointeur=0; //pointeur sur tableau
    int debutboucle[5],finboucle,tmp=1;
    scanf("%d%d%d", &L, &S, &N); fgetc(stdin);
    int valeur[S]; //tableau des valeurs
    for (i=0;i<S;i++){
        valeur[i]=0; //Mise à 0 de toutes les valeurs
    }
    for (i = 0; i < L; i++) {
        char r[1025];
        scanf("%[^\n]", r); fgetc(stdin);   //recuperation de la ligne de commande
        strcat(lignecom,r); //copie de cette ligne de commmande dans lignecom
    }
    int boucle=0;   //variable pour savoir si "SYNTAX ERROR" ou non
    int longlignecom=strlen(lignecom);  //Recuperation de la longueur de la ligne de la commande
    for (i=0;i<longlignecom;i++){   //Pour chaque commande
        if (lignecom[i]=='['){      //si commande='[' alors boucle est incrémenter de 1
            boucle++;
        }
        if (lignecom[i]==']'){      //si commande=']' alors boucle est decrementer de 1
            boucle--;
        }
    }
    if (boucle!=0){     //si boucle est différent de 0 alors il y une "SYNTAX ERROR"
        printf("SYNTAX ERROR");
    }else{
        for (i=0;i<longlignecom;i++){ //sinon on reboucle sur chaque commande
            switch (lignecom[i]){   //un switch pour étudier plus simplement chaque cas
                case '>':
                    pointeur++;
                    if (pointeur>=S){       //si le pointeur pointe plus grand que la longueur du tableau
                        printf("POINTER OUT OF BOUNDS");
                        return 0;
                    }
                    break;
                case '<':
                    pointeur--;
                    if (pointeur<0){    //si le pointeur pointe plus petit que 0
                        printf("POINTER OUT OF BOUNDS");
                        return 0;
                    }
                    break;
                case '+':
                    valeur[pointeur]++;
                    if (valeur[pointeur]>255){      //si la valeur de la ou pointe le pointeur est plus grande que 255
                        printf("INCORRECT VALUE");
                        return 0;
                    }
                    break;
                case '-':
                    valeur[pointeur]--;
                    if (valeur[pointeur]<0){    //si la valeur de la ou pointe le pointeur est plus petite que 0
                        printf("INCORRECT VALUE");
                        return 0;
                    }
                    break;
                case '.':
                    printf("%c",valeur[pointeur]);  //affichage de la valeur de la ou pointe le pointeur
                    break;
                case ',':
                    scanf("%d",&valeur[pointeur]);  //recuperation d'une valeur entrée par l'utilisateur
                    break;
                case '[':
                    debutboucle[tmp]=i; //stocke i dans debut boucle
                    tmp++;
                    if (valeur[pointeur]==0){   //si valeur sous pointeur vaut 0 alors on déplace i à finboucle
                        i=finboucle;
                        tmp--;
                    }
                    break;
                case ']':
                    finboucle=i; //finboucle devient i
                    tmp--;
                    i=debutboucle[tmp]-1;   //on revient au début de la boucle
                    break;
                default:
                    break;
            }
        }
    }
    return 0;
}

2.4. Tests de mon code

2.4.1. Test 1

Entrée:

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

Résultat valide : ABC:

ABC

2.4.2. Test 2

Entrée:

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)

Résultat valide : Hello World!:

Hello World!

2.4.3. Test 3

Entrée:

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

Résultat valide : POINTER OUT OF BOUNDS:

POINTER OUT OF BOUNDS

2.4.4. Test 4

Mon propre test: Entrée:

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

Résultat valide : INCORRECT VALUE:

INCORRECT VALUE

3. Une autre méthode

3.1. méthode de MJZ

J’ai trouvé ce code intéressant car je l’ai rapidement compris. Les noms des fonctions et variables sont très bien choisi. L’idée de placer les instructions de chaque case sur une ligne aide à bien mieux comprendre. La ligne for(;; pProgram++) est une boucle infini qui incrémente à chaque fois pProgram. J’ai trouvé cette manière jolie d’utiliser ainsi la boucle for. La fonction search est peut-être plus approprier pour trouver la ] correspondante à [ ou la [ correspondante à ]. La fonction prend en argument la direction ’dir’, qui indique si l’on doit rechercher la prochaine instruction correspondante à une ouverture de boucle ’[’ (+1) ou à une fermeture de boucle ’]’ (-1). La fonction commence par initialiser une variable ’depth’ à la valeur de ’dir’, puis elle boucle tant que ’depth’ n’est pas égal à zéro. À chaque itération, elle déplace le pointeur de programme ’pProgram’ dans la direction ’dir’, puis elle vérifie si l’instruction à cette position est une ouverture de boucle ’[’ ou une fermeture de boucle ’]’. Si c’est le cas, elle ajuste la valeur de ’depth’ en conséquence. Lorsque ’depth’ atteint zéro, cela signifie que l’on a trouvé l’instruction correspondante à la boucle ’[’ ou ’]’ que l’on recherche, et la fonction se termine. Ainsi, l’appel à la fonction ’search(int dir)’ permet d’optimiser l’exécution du code Brainfuck en sautant toutes les instructions intermédiaires qui ne sont pas nécessaires, ce qui peut réduire considérablement le temps d’exécution du programme.

#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);
        }
}

4. Apprentissage

J’ai appris quand utiliser les switch(Lorsque l’on a beaucoup de cas à traiter). Ce code est intéressant à implémenter car c’est un interpréteur complet pour le langage de programmation Brainfuck, qui est un langage de programmation minimaliste. Le langage ne comporte que huit instructions élémentaires qui permettent de déplacer un pointeur dans une zone de mémoire, d’incrémenter ou de décrémenter la valeur stockée à cette position, de lire ou d’écrire une valeur à partir de l’entrée ou de la sortie, et de créer des boucles à l’aide de crochets. Malgré sa simplicité, Brainfuck peut être utilisé pour créer des programmes complexes.

Le code utilise des tableaux de mémoire pour stocker les données du programme et des entrées utilisateur, et il utilise des boucles pour traiter les instructions du programme Brainfuck. En outre, il effectue des vérifications de syntaxe et de débordement pour garantir que le programme est correctement formé et qu’il ne provoque pas de dépassement de capacité de mémoire.

Author: Antoine Bourdier

Created: 2023-03-05 dim. 22:36