Befunge Interpreter, CodeWars Kata
Befunge Interpreter
Esoteric languages are pretty hard to program, but it's fairly interesting to write interpreters for them!
Your task is to write a method which will interpret Befunge-93 code! Befunge-93 is a language in which the code is presented not as a series of instructions, but as instructions scattered on a 2D plane; your pointer starts at the top-left corner and defaults to moving right through the code. Note that the instruction pointer wraps around the screen! There is a singular stack which we will assume is unbounded and only contain integers. While Befunge-93 code is supposed to be restricted to 80x25, you need not be concerned with code size. Befunge-93 supports the following instructions (from Wikipedia):
0-9Push this number onto the stack.+Addition: Popaandb, then pusha+b.-Subtraction: Popaandb, then pushb-a.*Multiplication: Popaandb, then pusha*b./Integer division: Popaandb, then pushb/a, rounded down. Ifais zero, push zero.%Modulo: Popaandb, then push theb%a. Ifais zero, push zero.!Logical NOT: Pop a value. If the value is zero, push1; otherwise, push zero.- \
`` (backtick) Greater than: Popaandb, then push1ifb>a`, otherwise push zero. >Start moving right.<Start moving left.^Start moving up.vStart moving down.?Start moving in a random cardinal direction._Pop a value; move right ifvalue = 0, left otherwise.|Pop a value; move down ifvalue = 0, up otherwise."Start string mode: push each character's ASCII value all the way up to the next".:Duplicate value on top of the stack. If there is nothing on top of the stack, push a0.\Swap two values on top of the stack. If there is only one value, pretend there is an extra0on bottom of the stack.$Pop value from the stack and discard it..Pop value and output as an integer.,Pop value and output the ASCII character represented by the integer code that is stored in the value.#Trampoline: Skip next cell.pA "put" call (a way to store a value for later use). Popy,xandv, then change the character at the position(x,y)in the program to the character with ASCII valuev.gA "get" call (a way to retrieve data in storage). Popyandx, then push ASCII value of the character at that position in the program.@End program.- ``(i.e. a space) No-op. Does nothing.
The above list is slightly modified: you'll notice if you look at the Wikipedia page that we do not use the user input instructions and dividing by zero simply yields zero.
Here's an example:
>987v>.v
v456< :
>321 ^ _@
will create the output 123456789.
So what you must do is create a function such that when you pass in the Befunge code, the function returns the output that would be generated by the code. So, for example:
"123456789".equals(new BefungeInterpreter().interpret(">987v>.v\nv456< :\n>321 ^ _@")
This test case will be added for you.
문제해석
Befunge라고 하는 language의 인터프리터를 작성하는 문제입니다. 위에 정의된 룰에 의해 인터프리터는 커서를 이동시켜가면서 Befunge를 해석하게 됩니다.
Befunge에서는 방향키처럼 커서를 이동시키는 문법이 존재하고요. 이전 두 수를 더하거나 빼거나 점프하는 등 입력 문자열에 따라 다양한 처리가 존재합니다. 해석을 위해서는 Stack을 사용해야 하고요. 문제의 지시대로 하나하나 문자에 대한 처리방법만 잘 기술하면 해결할 수 있는 문제입니다.
p와 g가 가장 해석이 힘들었습니다. put 과 get 액션이라고 하는데요. 지시에서 x와 y가 주어지는데 이 순서를 잘 보셔야 합니다. 입력문자열을 공백과 줄바꿈을 기준으로 잘라서 배열을 만들었을 때 (x, y)는 [y][x]에 대응됩니다. 이 점만 유의하시면 크게 어렵지 않습니다.
입력값
String code: Befunge 코드
출력값
String result: Befunge 코드를 해석한 문자열
My Solution
편리하게 코드를 작성하기 위해서 출력버퍼와 스택을 전역변수로 선언했습니다. 그리고 입력 문자열을 배열로 변형한 후 재귀호출을 이용해서 커서를 이동하며 해석 결과를 stack과 output에 쌓았습니다. 종료 시그널인 '@'를 만나면 재귀함수가 종료되고 output에 담긴 값을 문자열로 반환합니다.
<, >, ^, v를 만나면 방향이 바뀌고 다시 이들을 만나지 않는 이상 방향을 유지해야 하기 때문에 int directionX, int directionY변수를 통해서 방향을 처리했습니다. ascii 모드도 유지해야할 일이 생기기 때문에 boolean mode 를 통해 처리했습니다.
지시어들의 처리에는 case문을 활용했습니다. 코드를 깔끔하게 유지하기 위해서 이렇게 많은 조건을 처리할 때는 case를 사용하는 것이 좋은 것 같아요.
import java.util.Random;
import java.util.Stack;
public class BefungeInterpreter {
StringBuffer output = new StringBuffer();
Stack<Integer> stack = new Stack<Integer>();
public String interpret(String code) {
String[] lines = code.split("\n");
char[][] plane = new char[lines.length][];
for (int i = 0; i < lines.length; i++) {
plane[i] = lines[i].toCharArray();
}
next(plane, 0, 0, 1, 0, false);
return output.toString();
}
/**
*
* @param plane befunge plane
* @param line Nth line: indicate plane[line]
* @param index Nth index of a line: indicate plane[line][index]
* @param directionX horizontal direction. 1 to right, -1 to left. 0 means
* vertical move.
* @param directionY vertical direction. 1 to down, -1 to up. 0 means horizontal
* move.
*/
public void next(char[][] plane, int line, int index, int directionX, int directionY, boolean mode) {
char value = plane[line][index];
do {
if (mode & value != '"') {
stack.push((int) value);
} else {
switch (value) {
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9': {
if (!mode) {
stack.push(Character.getNumericValue(value));
} else {
stack.push((int) value);
}
break;
}
case '+': {
int a = stack.pop();
int b = stack.pop();
stack.push(a + b);
break;
}
case '-': {
int a = stack.pop();
int b = stack.pop();
stack.push(b - a);
break;
}
case '*': {
int a = stack.pop();
int b = stack.pop();
stack.push(b * a);
break;
}
case '/': {
int a = stack.pop();
int b = stack.pop();
stack.push(b / a);
break;
}
case '%': {
int a = stack.pop();
int b = stack.pop();
stack.push(b % a);
break;
}
case '!': {
int a = stack.pop();
if (a == 0) {
stack.push(1);
} else {
stack.push(0);
}
break;
}
case '`': {
int a = stack.pop();
int b = stack.pop();
if (b > a) {
stack.push(1);
} else {
stack.push(0);
}
break;
}
case '>': {
directionX = 1;
directionY = 0;
break;
}
case '<': {
directionX = -1;
directionY = 0;
break;
}
case '^': {
directionX = 0;
directionY = -1;
break;
}
case 'v': {
directionX = 0;
directionY = 1;
break;
}
case '?': {
directionX = new Random().nextInt(3) - 1;
if (directionX == 0) {
directionY = new Random().nextBoolean() ? 1 : -1;
} else {
directionY = 0;
}
break;
}
case '_': {
int a = stack.pop();
if (a == 0) {
directionX = 1;
directionY = 0;
break;
} else {
directionX = -1;
directionY = 0;
break;
}
}
case '|': {
int a = stack.pop();
if (a == 0) {
directionX = 0;
directionY = 1;
break;
} else {
directionX = 0;
directionY = -1;
break;
}
}
case '"': {
mode = !mode;
break;
}
case ':': {
if (stack.empty()) {
stack.push(0);
} else {
stack.push(stack.peek());
}
break;
}
case '\\': {
if (!stack.empty()) {
int a = stack.pop();
if (stack.isEmpty()) {
stack.push(a);
stack.push(0);
} else {
int b = stack.pop();
stack.push(a);
stack.push(b);
}
}
break;
}
case '$': {
stack.pop();
break;
}
case '.': {
output.append(stack.pop());
break;
}
case ',': {
output.append((char) stack.pop().intValue());
break;
}
case '#': {
directionX = directionX * 2;
directionY = directionY * 2;
break;
}
case 'p': {
int y = stack.pop();
int x = stack.pop();
int v = stack.pop();
plane[y][x] = (char) v;
break;
}
case 'g': {
int y = stack.pop();
int x = stack.pop();
stack.push((int) plane[y][x]);
break;
}
case '@': {
while (!stack.empty()) {
int a = stack.pop();
if (a < 10) {
output.append(a);
} else {
output.append((char) a);
}
}
return;
}
case ' ': {
break;
}
default: {
if (mode) {
stack.push((int) value);
}
break;
}
}
}
line = line + directionY;
index = index + directionX;
value = plane[line][index];
if (Math.abs(directionX) > 1) {
directionX = directionX / 2;
}
if (Math.abs(directionY) > 1) {
directionY = directionY / 2;
}
} while (value != '@');
}
}
Best Practice
BP는 객체지향 설계를 통해서 이 문제를 해결했습니다. enum Direction을 이용해서 임의 방향 움직임을 처리한 것이 눈에 띕니다.
State클래스와 inner클래스 Location 클래스도 눈여겨 봐야 합니다. 상수를 활용해서 초기값과 방향 등을 가독성 있게 잘 처리한 솔루션입니다.
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.Random;
public class BefungeInterpreter {
private enum Direction {
UP, DOWN, LEFT, RIGHT;
private static Random random = new Random();
static Direction random() {
Direction[] values = Direction.values();
return values[random.nextInt(values.length)];
}
}
private static class State {
private static class Location {
private static final int STARTING_X = 0;
private static final int STARTING_Y = 0;
private static final Direction STARTING_DIRECTION = Direction.RIGHT;
private int x = STARTING_X;
private int y = STARTING_Y;
private Direction direction = STARTING_DIRECTION;
private StringBuilder[] codePlane;
Location(String[] codePlane) {
this.codePlane = Arrays.stream(codePlane).map(StringBuilder::new).toArray(StringBuilder[]::new);
}
public char currentInstruction() {
return getInstruction(x, y);
}
public char getInstruction(int x, int y) {
return codePlane[y].charAt(x);
}
public void setInstruction(int x, int y, char instruction) {
codePlane[y].setCharAt(x, instruction);
}
public void setDirection(Direction direction) {
this.direction = direction;
}
private void move() {
switch (direction) {
case UP:
moveUp();
break;
case DOWN:
moveDown();
break;
case LEFT:
moveLeft();
break;
case RIGHT:
moveRight();
break;
}
}
private void moveUp() {
if(y == 0) {
y = codePlane.length - 1;
} else {
y--;
}
}
private void moveDown() {
if(y == codePlane.length - 1) {
y = 0;
} else {
y++;
}
}
private void moveLeft() {
if(x == 0) {
x = codePlane[y].length() - 1;
} else {
x--;
}
}
private void moveRight() {
if(x == codePlane[y].length() - 1) {
x = 0;
} else {
x++;
}
}
}
private Location location;
private boolean stringMode = false;
private Deque<Integer> stack = new ArrayDeque<>();
private StringBuilder output = new StringBuilder();
private boolean done = false;
public State(String code) {
location = new Location(code.split("\n"));
}
public char currentInstruction() {
return location.currentInstruction();
}
public String output() {
return output.toString();
}
public boolean done() {
return done;
}
public void processInstruction(char instruction) {
if (stringMode) {
if (instruction == '"') {
flipStringMode();
} else {
instructionActiveStringMode(instruction);
}
} else {
switch (instruction) {
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
instructionNumber(instruction);
break;
case '+':
instructionPlus();
break;
case '-':
instructionMinus();
break;
case '*':
instructionMultiply();
break;
case '/':
instructionDivide();
break;
case '%':
instructionModulus();
break;
case '!':
instructionNot();
break;
case '`':
instructionGreaterThan();
break;
case '>':
instructionRight();
break;
case '<':
instructionLeft();
break;
case '^':
instructionUp();
break;
case 'v':
instructionDown();
break;
case '?':
instructionRandom();
break;
case '_':
instructionHorizontal();
break;
case '|':
instructionVertical();
break;
case '"':
flipStringMode();
break;
case ':':
instructionDuplicate();
break;
case '\\':
instructionSwap();
break;
case '$':
instructionDiscard();
break;
case '.':
instructionOutputInt();
break;
case ',':
instructionOutputAscii();
break;
case '#':
instructionTrampoline();
break;
case 'p':
instructionPut();
break;
case 'g':
instructionGet();
break;
case '@':
instructionEnd();
break;
case ' ': // No-op
default:
// Do nothing
}
}
location.move();
}
private void flipStringMode() {
stringMode = !stringMode;
}
private void instructionNumber(char instruction) {
stack.push(instruction - '0');
}
private void instructionPlus() {
int a = stack.pop();
int b = stack.pop();
stack.push(a + b);
}
private void instructionMinus() {
int a = stack.pop();
int b = stack.pop();
stack.push(b - a);
}
private void instructionMultiply() {
int a = stack.pop();
int b = stack.pop();
stack.push(a * b);
}
private void instructionDivide() {
int a = stack.pop();
int b = stack.pop();
stack.push(a == 0 ? 0 : b / a);
}
private void instructionModulus() {
int a = stack.pop();
int b = stack.pop();
stack.push(a == 0 ? 0 : b % a);
}
private void instructionNot() {
int a = stack.pop();
stack.push(a == 0 ? 1 : 0);
}
private void instructionGreaterThan() {
int a = stack.pop();
int b = stack.pop();
stack.push(b > a ? 1 : 0);
}
private void instructionRight() {
location.setDirection(Direction.RIGHT);
}
private void instructionLeft() {
location.setDirection(Direction.LEFT);
}
private void instructionUp() {
location.setDirection(Direction.UP);
}
private void instructionDown() {
location.setDirection(Direction.DOWN);
}
private void instructionRandom() {
location.setDirection(Direction.random());
}
private void instructionHorizontal() {
if (stack.pop().intValue() == 0) {
location.setDirection(Direction.RIGHT);
} else {
location.setDirection(Direction.LEFT);
}
}
private void instructionVertical() {
if (stack.pop().intValue() == 0) {
location.setDirection(Direction.DOWN);
} else {
location.setDirection(Direction.UP);
}
}
private void instructionActiveStringMode(char instruction) {
stack.push((int) instruction);
}
private void instructionDuplicate() {
stack.push(stack.isEmpty() ? 0 : stack.peek());
}
private void instructionSwap() {
int a = stack.pop();
int b = stack.isEmpty() ? 0 : stack.pop();
stack.push(a);
stack.push(b);
}
private void instructionDiscard() {
stack.pop();
}
private void instructionOutputInt() {
output.append(stack.pop());
}
private void instructionOutputAscii() {
output.append((char) stack.pop().intValue());
}
private void instructionTrampoline() {
location.move();
}
private void instructionPut() {
int y = stack.pop();
int x = stack.pop();
char newInstruction = (char) stack.pop().intValue();
location.setInstruction(x, y, newInstruction);
}
private void instructionGet() {
int y = stack.pop();
int x = stack.pop();
stack.push((int)location.getInstruction(x, y));
}
private void instructionEnd() {
done = true;
}
}
public String interpret(String code) {
State state = new State(code);
for (char instruction = state.currentInstruction(); !state.done(); instruction = state.currentInstruction()) {
state.processInstruction(instruction);
}
return state.output();
}
}
728x90
'IT Contents > 프로그래밍 팁' 카테고리의 다른 글
| Path Finder #1: can you reach the exit?, CodeWars Kata 자바 솔루션 (0) | 2021.04.21 |
|---|---|
| Breadcrumb Generator, CodeWars Kata 자바 솔루션 (0) | 2021.04.20 |
| Codewars style ranking system, CodeWars Kata 자바 솔루션 (0) | 2021.04.18 |
| Sum by Factors, CodeWars Kata 자바 솔루션 (0) | 2021.04.17 |
| Strip Comments, CodeWars Kata 자바 솔루션 (0) | 2021.04.16 |
최근댓글