What the brainfuck !

1. Présentation
2. Résolution
- 2.1. Input
- 2.2. Ouput
3. Code
- 3.1. Programme principale
- 3.2. Fonction interpret
4. Tests
- 4.1. Test simple
  - 4.1.1. Input
  - 4.1.2. Output
- 4.2. Test multiplication
  - 4.2.1. Input
  - 4.2.2. Output
5. Conclusion

1. Présentation

Brainfuck est un language de programmation minimaliste comportant 8 opérateurs. Et c’est tout !

Bien que primaire au premier abord, ce language est Turing complete, ce qui signifie que l’on peut théoriquement tout ce qui est possible de coder avec un ordinateur avec ce language.

Notre but est de créer un interpréteur complêtement opérationnel en C.

Regardons de plus prêt comment cela fonctionne : Le modèle Brainfuck est composé de 3 éléments :

Un tableau de S octets initialisées à 0 et indéxées depuis 0.
Un pointeur pointant sur la première case du tableau. (Indice 0)
Un programme écrit à partir des 8 instructions qui suivent.
- > incrémente la position du pointeur.
- < décrémente la position du pointeur.
- + incrémente la valeur de la case sur laquelle pointe le pointeur.
- - décrémente la valeur de la case sur laquelle pointe le pointeur.
- . affiche la valeur de la case sur laquelle pointe le pointeur.
- , accepte une entrée d’un entier positif sur un octet que l’on stocke à l’adresse du pointeur.
- [ saute à l’instruction ] si la valeur de la case sur laquelle on pointe est 0.
- ] reviens à l’instruction [ si la valeur de la case sur laquelle on pointe est 0.

Notre interpréteur doit aussi être capable de détécter certaines erreurs :

“SYNTAX ERROR” si des accolades ne sont pas fermées par exemple.
“POINTER OUT OF BOUNDS” si la position du pointeur va en deçà ou au dessus du tableau.
“INCORRECT VALUE” si la valeur d’une case si trouve en deçà de 0 ou au dessus de 255.

2. Résolution

La résolution s’avère assez simple car s’agit plus ou moins de suivre à la lettre l’énoncé.

2.1. Input

Il nous est donné en input :

L le nombre de lignes du programme.
S la taille nécéssaire au tableau pour le bon fonctionnement du programme.
N le nombre d’input que le programme va demander

2.2. Ouput

Les sorties standard générées par l’instruction .

3. Code

3.1. Programme principale

int main() {
  int number_of_line;
  int memory_size;
  int number_of_input;
  int error;
  scanf("%d%d%d", &number_of_line, &memory_size, &number_of_input);
  fgetc(stdin);
  int inputs[number_of_input];
  int *memory = malloc(memory_size * sizeof(int));
  int *ptr = memory;

  char *code = malloc(number_of_line * 500 * sizeof(char));
  char *output = malloc(memory_size * sizeof(char));
  for (int i = 0; i < number_of_line; i++) {
    char line[1025];
    scanf("%[^\n]", line);
    fgetc(stdin);
    strcat(code, line);
  }

  for (int i = 0; i < number_of_input; ++i) {
    scanf("%d", &inputs[i]);
  }

  error = interpret(code, ptr, memory, memory_size, inputs, output);

  switch (error) {
  case 1:
    printf("POINTER OUT OF BOUNDS\n");
    break;
  case 2:
    printf("INCORRECT VALUE\n");
    break;
  case 3:
    printf("SYNTAX ERROR\n");
    break;
  }

  free(memory);
  free(code);
  free(output);

  return 0;
}

3.2. Fonction interpret

int interpret(char *code, int *ptr, int *memory, int memory_size, int *inputs, char *output) {
  int i = 0, j = 0, k = 0;
  int call_stack = 0;
  while (code[i] != '\000') {
    switch (code[i]) {
    case '>':
      ++ptr;
      if (ptr >= memory + memory_size) {
        return 1;
      }
      break;
    case '<':
      --ptr;
      if (ptr < memory) {
        return 1;
      }
      break;
    case '+':
      if (*ptr == 255) {
        return 2;
      }
      ++(*ptr);
      break;
    case '-':
      if (*ptr == 0) {
        return 2;
      }
      --(*ptr);
      break;
    case '.':
      output[k] = *ptr;
      ++k;
      break;
    case ',':
      *ptr = inputs[j];
      ++j;
      break;
    case '[':
      ++call_stack;
      if (!*ptr) {
        ++i;
        while (code[i] != ']' || call_stack > 1) {
          if (code[i] == '[') {
            ++call_stack;
          } else if (code[i] == ']') {
            --call_stack;
            ++i;
          }
        }
        --call_stack;
      }
      break;
    case ']':
      --call_stack;
      if (*ptr) {
        --i;
        while (code[i] != '[' || call_stack < 0) {
          if (code[i] == ']') {
            --call_stack;
          } else if (code[i] == '[') {
            ++call_stack;
          } else if (i == 0) {
            return 3;
          }
          --i;
        }
        ++call_stack;
      }
      break;
    }
    ++i;
  }
  if (call_stack) {
    return 3;
  }
  output[k] = '\000';
  printf("%s\n", output);
  return 0;
}

4. Tests

4.1. Test simple

4.1.1. Input

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

4.1.2. Output

ABC

4.2. Test multiplication

4.2.1. Input

Ce test comprend 2 inputs (Les nombres à multiplier)

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

4.2.2. Output

5. Conclusion

J’ai beaucoup aprécié faire ce codingame qui sort un peu de l’ordinaire. JE penes avoir appris beaucoup de chose et il m’a permi de me familliariser un peu plus avec le concepte de pointeur.