[CodeKata] My smallest code interpreter (aka Brainf**k) - 5 kyu

[CodeKata] My smallest code interpreter (aka Brainf**k) - 5 kyu

728x90

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 #include #include std::string brainLuck(const std::string& code, const std::string& input) { std::string result; std::string imput(input); std::stack brack; std::vector 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 #include std::string brainLuck(std::string code, std::string input) { // stored mapped brace positions to prevent repeated string parsing std::map open_brace, close_brace; std::vector 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 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/)

from http://anothel.tistory.com/55 by ccl(A) rewrite - 2021-11-04 19:01:34