Rapport sur Brainfuck
Table of Contents
1. Présentation du problème
Brainfuck est un problème du site codingame. On nous donne en entrée une ou plusieurs ligne de caractères, et il faut qu’en fonction du caractères une action soit éxécuté, le but étant d’afficher un mot ou une phrase grace a ce langage de programmation qu’est le brainfuck. On dispose d’un pointeur auxquels on va appliquer des actions en fonctions des caractères reçu, les caractères utilisés en Brainfuck sont ’+’ qui ajoute 1 à la valeur du pointeur, ’-’ pour enlever 1 à la valeur du pointeur, ’>’ pour incrémenter la position du pointeur, ’>’ pour décrementer la position du pointeur, ’.’ pour afficher la valeur du pointeur, ’,’ pour une saisie en console d’un entier, ’[’ qui saute vers le ’]’ correspondant si la valeur du pointeur est 0, ’]’ qui retourne au ’[’ correspondant si la valeur du pointeur est différente de 0.
2. Méthode de résolution
2.1. Détail algorithmique
2.2. code de résolution
initalisation du code avec les #include et les instanciations de variables, les 3 variables d’entrées ainsi que les autres variables qui permettront la réalisation du code
#include <stdlib.h> #include <stdio.h> #include <string.h> #include <stdbool.h> int main(){ //initialisation des variables int L; int S; int N; int tabf[100]={0}; int pointeur=0; char instruction[1025]=""; int i=0, j=0, l=0, ok=1, compteur=0, valeur, crochet; scanf("%d%d%d", &L, &S, &N); fgetc(stdin);
On crée la ligne d’instruction, c’est-à-dire qu’on prend toute les lignes d’instructions données en entrée et on les concatènes en une seule ligne. On utilise en même temps un compteur qui compte le nombre de ’[’ et de ’]’ afin d’analyser la syntaxe.
for (; i < L; i++) { char r[1025]; scanf("%[^\n]", r); fgetc(stdin); j=0; while(r[j]!='\0'){ compteur += r[j]=='[' ? 1 : 0; compteur -= r[j]==']' ? 1 : 0; if(r[j]=='>' || r[j]=='<' || r[j]==']' || r[j]=='+' || r[j]=='-' || r[j]=='.' || r[j]==',' || r[j]=='['){ sprintf(instruction,"%s%c",instruction,r[j]); } j++; } }
on regarde la valeur du compteur modifié plus haut afin d’afficher “SYNTAX ERROR” si il y a une erreur de syntaxe, sinon il ne fait rien.
if (compteur!=0){ printf("SYNTAX ERROR"); return 0; }
On parcours la chaine d’instruction jusqu’à ce qu’un ’\0’ ne soit trouver ou qu’une erreur ne soit trouver dans l’instruction, c’est-à-dire, si le pointeur sort de l’ensemble possible, ou si la valeur n’est pas dans l’ensemble définie. On utilise un switch qui regarde chaque instructions une par une et applique l’instruction donnée si il n’y a pas d’erreur.
j=0; while(instruction[j]!='\0' && ok==1){ switch(instruction[j]){ //on incrémente le pointeur case '>': pointeur+=1; if (pointeur>S-1){ puts("POINTER OUT OF BOUNDS"); ok=0; } break; //on décrémente le pointeur case '<': pointeur-=1; if (pointeur<0){ puts("POINTER OUT OF BOUNDS"); ok=0; } break; //on ajoute 1 à la valeur du tableau correspondante case '+': if (tabf[pointeur]>254){ puts("INCORRECT VALUE"); ok=0; } tabf[pointeur]+=1; break; //on soustrait 1 à la valeur du tableau correspondante case '-': if (tabf[pointeur]<1){ puts("INCORRECT VALUE"); ok=0; } tabf[pointeur]-=1; break; //on saisie un entier dans la console case ',': scanf("%d",&valeur); tabf[pointeur]=valeur; if (tabf[pointeur]<0 || tabf[pointeur]>255){ puts("INCORRECT VALUE"); ok=0; } break; //on affiche la valeur du tableau case '.': printf("%c",tabf[pointeur]); break; //on saute au ']' correspondant si la valeur de la cellule est 0 case '[': if(tabf[pointeur]==0){ j++; crochet=1; while(crochet!=0){ if(instruction[j]=='['){ crochet++; j++; } else{ if(instruction[j]==']'){ crochet--; if(crochet!=0){ j++; } } else{ j++; } } } } break; //on retourne au '[' correspondant si la valeur de la cellule est différente de 0 case ']': if(tabf[pointeur]!=0){ j--; crochet=1; while(crochet!=0){ if(instruction[j]==']'){ crochet++; j--; } else{ if(instruction[j]=='['){ crochet--; if(crochet!=0){ j--; } } else{ j--; } } } } break; } j++;
2.2.1. le code en entier
#include <stdlib.h> #include <stdio.h> #include <string.h> #include <stdbool.h> int main(){ //initialisation des variables int L; int S; int N; int tabf[100]={0}; int pointeur=0; char instruction[1025]=""; int i=0, j=0, l=0, ok=1, compteur=0, valeur, crochet; scanf("%d%d%d", &L, &S, &N); fgetc(stdin); //création de la ligne d'instruction for (; i < L; i++) { char r[1025]; scanf("%[^\n]", r); fgetc(stdin); j=0; while(r[j]!='\0'){ compteur += r[j]=='[' ? 1 : 0; compteur -= r[j]==']' ? 1 : 0; if(r[j]=='>' || r[j]=='<' || r[j]==']' || r[j]=='+' || r[j]=='-' || r[j]=='.' || r[j]==',' || r[j]=='['){ sprintf(instruction,"%s%c",instruction,r[j]); } j++; } } //analyse de la syntaxe if (compteur!=0){ printf("SYNTAX ERROR"); return 0; } //On parcours la chaine d'instruction: j=0; while(instruction[j]!='\0' && ok==1){ switch(instruction[j]){ //on incrémente le pointeur case '>': pointeur+=1; if (pointeur>S-1){ puts("POINTER OUT OF BOUNDS"); ok=0; } break; //on décrémente le pointeur case '<': pointeur-=1; if (pointeur<0){ puts("POINTER OUT OF BOUNDS"); ok=0; } break; //on ajoute 1 à la valeur du tableau correspondante case '+': if (tabf[pointeur]>254){ puts("INCORRECT VALUE"); ok=0; } tabf[pointeur]+=1; break; //on soustrait 1 à la valeur du tableau correspondante case '-': if (tabf[pointeur]<1){ puts("INCORRECT VALUE"); ok=0; } tabf[pointeur]-=1; break; //on saisie un entier dans la console case ',': scanf("%d",&valeur); tabf[pointeur]=valeur; if (tabf[pointeur]<0 || tabf[pointeur]>255){ puts("INCORRECT VALUE"); ok=0; } break; //on affiche la valeur du tableau case '.': printf("%c",tabf[pointeur]); break; //on saute au ']' correspondant si la valeur de la cellule est 0 case '[': if(tabf[pointeur]==0){ j++; crochet=1; while(crochet!=0){ if(instruction[j]=='['){ crochet++; j++; } else{ if(instruction[j]==']'){ crochet--; if(crochet!=0){ j++; } } else{ j++; } } } } break; //on retourne au '[' correspondant si la valeur de la cellule est différente de 0 case ']': if(tabf[pointeur]!=0){ j--; crochet=1; while(crochet!=0){ if(instruction[j]==']'){ crochet++; j--; } else{ if(instruction[j]=='['){ crochet--; if(crochet!=0){ j--; } } else{ j--; } } } } break; } j++; } return 0; }
2.3. tests
2.3.1. premier test
avec la chaine de caractère suivante,
1 4 0 ++++++++++[>+++++++>++++++++++>+++<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.
cela donne:
Hello World!
si on compare le résultat au résultat attendu:
Hello World!
on voit que le code renvoie bien le bon résultat
2.3.2. deuxieme test
on peut obtenir le même résultat en passant par une entrée plus détaillé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)
cela donne:
Hello World!
si on compare le résultat au résultat attendu:
Hello World!
on voit que le code renvoie bien le bon résultat
2.3.3. troisieme test
il y a aussi les sorties d’erreur
1 4 0 ++++++++++[>+++++++>++++++++++>+++><<<--------------------------]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.
cela donne:
POINTER OUT OF BOUNDS
si on compare le résultat au résultat attendu:
POINTER OUT OF BOUNDS
on voit que le code renvoie bien le bon résultat
2.3.4. tests perso
- premier test perso
voici le test crée:
1 5 0 ++++++++++[>+>+++>+++++++>++++++++++<<<<-]>>>>++++++++++++++++++.-------.------.------.++++++.<<++.>>+++.-------.<<.>>+++++++++++++++.---------------.++++++++++++++.+.<<.>>-----------------.+++++++++++++++.-------------..<<.>>+++++++++++.-.++++++.---.<<.>>------.-------.<<.>>+++++++++++++.-----------------.+++++++++++++++..-.+++.++.<<.>>-.++.---.<<.>>----------------.++++++++++++++++.-----------------.++++++++.+++++.--------.+++++++++++++++.------------------.++++++++.
cela donne:
voici le test cree pour le rapport sur brainfuck
si on compare le résultat au résultat attendu:
voici le test cree pour le rapport sur brainfuck
on voit que le code renvoie bien le bon résultat
- deuxième test perso
il y a aussi ce test:
1 5 0 ++++++++++[>+>+++>+++++++>++++++++++<<<<-]>>>+++++++++.+++++++++...<<.>>.---------.+++++++++..<<.>>..---------.+++++++++.<<.>>...---------.
qui donne:
OXXX XOXX XXOX XXXO si on compare le résultat au résultat attendu:
OXXX XOXX XXOX XXXO
on voit que le code renvoie bien le bon résultat
3. Solution de la communauté
J’ai choisi de présenter de MJZ, cette solution utilise les pointeurs, chose que nous n’avions pas vu en cours au moment de la rédaction du rapport et de la création du code.
#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); } }
Il définie une fonction checkBrackets qui regarde la syntaxe et plus précisemment le nombre de ’[’ et ’]’ et renvoie l’erreur de syntaxe si il en manque ou si il y en a trop. Il définie ensuite la fonction search qui applique la condition sur les ’[’ ou sur les ’]’. Enfin il commence le programme principal ou il recoit les variables d’entrées et la/les ligne(s) d’instruction(s), puis il parcours ces instructions tout en regardant le caractère et applique les instructions grace a un switch.
4. Liens
vous pouvez retrouver ce rapport sur ma page personnelle