My smallest code interpreter (aka Brainf**k)

Inspired from real-world Brainf**k, we want to create an interpreter of that language which will support the following instructions:

• > increment the data pointer (to point to the next cell to the right).
• < decrement the data pointer (to point to the next cell to the left).
• + increment (increase by one, truncate overflow: 255 + 1 = 0) the byte at the data pointer.
• - decrement (decrease by one, treat as unsigned byte: 0 - 1 = 255 ) the byte at the data pointer.
• . output the byte at the data pointer.
• , accept one byte of input, storing its value in the byte at the data pointer.
• [ if the byte at the data pointer is zero, then instead of moving the instruction pointer forward to the next command, jump it forward to the command after the matching ] command.
• ] if the byte at the data pointer is nonzero, then instead of moving the instruction pointer forward to the next command, jump it back to the command after the matching [ command.

The function will take in input...

• the program code, a string with the sequence of machine instructions,
• the program input, a string, eventually empty, that will be interpreted as an array of bytes using each character's ASCII code and will be consumed by the , instruction

... and will return ...

• the output of the interpreted code (always as a string), produced by the . instruction.

Implementation-specific details for this Kata:

• Your memory tape should be large enough - the original implementation had 30,000 cells but a few thousand should suffice for this Kata
• Each cell should hold an unsigned byte with wrapping behavior (i.e. 255 + 1 = 0, 0 - 1 = 255), initialized to 0
• The memory pointer should initially point to a cell in the tape with a sufficient number (e.g. a few thousand or more) of cells to its right. For convenience, you may want to have it point to the leftmost cell initially
• You may assume that the , command will never be invoked when the input stream is exhausted
• Error-handling, e.g. unmatched square brackets and/or memory pointer going past the leftmost cell is not required in this Kata. If you see test cases that require you to perform error-handling then please open an Issue in the Discourse for this Kata (don't forget to state which programming language you are attempting this Kata in).

 

Solution

#include <iostream>
#include <stack>
#include <vector>

std::string brainLuck(const std::string& code, const std::string& input) {
  std::string result;

  std::string imput(input);

  std::stack<int> brack;
  std::vector<char> bytes;
  int pointer = 0;

  bytes.push_back((char)0);

  for (unsigned long i = 0; i < code.length(); i++) {
    switch (code.at(i)) {
      case '>': {
        pointer++;
        if (pointer == bytes.size()) {
          bytes.push_back((char)0);
        }
        break;
      }
      case '<': {
        pointer--;
        if (pointer == -1) {
          bytes.push_back((char)0);
          pointer = 0;
        }
        break;
      }
      case '+': {
        bytes[pointer]++;
        break;
      }
      case '-': {
        bytes[pointer]--;
        break;
      }
      case '.': {
        result += bytes[pointer];
        break;
      }
      case ',': {
        if (imput.empty() == false) {
          bytes[pointer] = imput.at(0);
          imput = imput.substr(1);
        }
        break;
      }
      case '[': {
        if (bytes[pointer] == 0) {
          int left = 1, k = i;
          while (left != 0) {
            k++;
            if (code.at(k) == '[') {
              left++;
            } else if (code.at(k) == ']') {
              left--;
            }
          }
          i = k;
        } else {
          brack.push(i);
        }

        break;
      }
      case ']': {
        if (bytes[pointer] != 0) {
          i = brack.top();
        } else {
          brack.pop();
        }
        break;
      }
      default: {
        break;
      }
    }
  }

  return result;
}

 

ds13의 코드

#include <string>
#include <vector>

std::string brainLuck(std::string code, std::string input)
{
    // stored mapped brace positions to prevent repeated string parsing
    std::map<size_t, size_t> open_brace, close_brace;
    std::vector<size_t> open_brace_stack;

    size_t pos = code.find_first_of( "[]" );
    while( pos != std::string::npos )
    {
        if( code[pos] == '[' )
        {
            open_brace_stack.push_back( pos );
        }
        else // ']':
        {
            open_brace.insert( std::make_pair( pos, open_brace_stack.back() ) );
            close_brace.insert( std::make_pair( open_brace_stack.back(), pos ) );
            open_brace_stack.pop_back();
        }

        pos = code.find_first_of( "[]", pos+1 );
    }

    // Iterate through instructions
    std::string output;
    std::vector<char> data = { (char)0 };
    size_t data_ptr=0;

    for( size_t code_ptr=0; code_ptr < code.size() && code_ptr != std::string::npos; code_ptr++ )
    {
        switch( code[code_ptr]  )
        {
            case ',':
                      data[data_ptr] = input.back();  
                      input.pop_back(); 
                      break;
            case '>': 
                      if( ++data_ptr == data.size() )
                          data.push_back( (char)0 );
                      break;

            case '<': --data_ptr; break;
            case '.': output.push_back( (char)data[data_ptr] ); break;
            case '+': data[data_ptr] = data[data_ptr] ==(char)255 ? (char)0 : (char)data[data_ptr]+1; break;
            case '-': data[data_ptr] = data[data_ptr] ==(char)0 ? (char)255 : (char)data[data_ptr]-1; break;
            case '[': 
                      if( data[data_ptr] == (char)0 )
                          code_ptr = close_brace.find( code_ptr )->second;
                      break;
            case ']':
                      if( data[data_ptr] != (char)0 )
                          code_ptr = open_brace.find( code_ptr )->second;;
                      break;
            default:
                      break;
        }
    }
    
    if( output.size() > 0 )
        return output;
    else
        return input;
}

 

후기

인터프리터를 만들어내는 문제였다. 그런데 사실 input에서 값을 어떻게 들고 오는지부터 이해를 못했었기 때문에 너무나도 오랜 시간이 걸렸고, 결국엔 남이 만든 자바 코드를 보고 C++로 옮겨봤다. 분명 포인터를 옮기거나 해당 값을 증가시키는 등의 프로세스는 이해했고 구현했는데, [ 혹은 ]의 반복문을 만들어내는 구문에서 너무나도 어려웠다. 우여곡절 끝에 만들어내니 테스트 케이스를 한 개는 통과하고 다음 것은 통과를 못했다. 정말 어려웠다. 심지어 반복문을 만들어내는 쪽은 아직도 잘 이해가 안 간다.. 이것만 붙잡고 있다가 다른 것은 하나도 못해볼 거 같아서 도저히 안 되겠어서 남의 코드를 검색해서 참조해서 내 코드를 만들어냈다.

문제를 통과 후에야 볼 수 있는 남의 코드들은 음.. 아주 엄청난 사람들이었다. 난 아직 너무나도 많이 부족하고 더 보고 배워야 할 것들이 많다.

 

(url: https://www.codewars.com/kata/526156943dfe7ce06200063e, https://ao.ms/my-smallest-code-interpreter-aka-brainfk-in-java/)