مساله:
برنامه نویسی زبانهای Esoteric بسیار دشوار است ، اما نوشتن مفسر برای آنها بسیار جالب است!
وظیفه شما نوشتن روشی است که کد Befunge-93 را تفسیر کند! Befunge-93 زبانی است که در آن کد نه به عنوان یک سری دستورالعمل پشت سر هم، بلکه به عنوان دستورالعملهای پراکنده در صفحه دو بعدی ارائه می شود. نشانگر شما از گوشه بالا سمت چپ شروع می شود و به طور پیش فرض به سمت راست کد حرکت می کند. توجه داشته باشید که نشانگر دستورالعمل به دور صفحه می پیچد! یک پشته منفرد وجود دارد که تصور می کنیم نامحدود است و فقط شامل اعداد صحیح است. در حالی که قرار است کد Befunge-93 به 80×25 محدود شود ، شما نیازی به اهمیت کد ندارید.
Description:
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 80×25, you need not be concerned with code size. Befunge-93 supports the following instructions (from Wikipedia):
0-9 Push this number onto the stack. + Addition: Pop a and b, then push a+b. - Subtraction: Pop a and b, then push b-a. * Multiplication: Pop a and b, then push a*b. / Integer division: Pop a and b, then push b/a, rounded down. If a is zero, push zero. % Modulo: Pop a and b, then push the b%a. If a is zero, push zero. ! Logical NOT: Pop a value. If the value is zero, push 1; otherwise, push zero. ` (backtick) Greater than: Pop a and b, then push 1 if b>a, otherwise push zero. > Start moving right. < Start moving left. ^ Start moving up. v Start moving down. ? Start moving in a random cardinal direction. _ Pop a value; move right if value = 0, left otherwise. | Pop a value; move down if value = 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 a 0. \ Swap two values on top of the stack. If there is only one value, pretend there is an extra 0 on 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. p A "put" call (a way to store a value for later use). Pop y, x and v, then change the character at the position (x,y) in the program to the character with ASCII value v. g A "get" call (a way to retrieve data in storage). Pop y and x, 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.
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();
}
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 != '@');
}
}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();
}
}import java.util.Stack;
import java.util.concurrent.ThreadLocalRandom;
public class BefungeInterpreter {
public static final int WIDTH = 80;
public static final int HEIGHT = 25;
public String interpret(String code) {
String[] codeLines = code.split("\\n");
char[][] grid = new char[HEIGHT][WIDTH];
for (int i = 0, len = codeLines.length; i < len; i++) {
char[] codeChars = codeLines[i].toCharArray();
System.arraycopy(codeChars, 0, grid[i], 0, codeChars.length);
}
int x = 0, y = 0, dx = 1, dy = 0;
boolean stringMode = false;
Stack<Integer> stack = new Stack<>();
StringBuilder output = new StringBuilder();
while (true) {
char c = grid[y][x];
if (stringMode)
if (c == '"')
stringMode = false;
else
stack.push((int)c);
else
switch (c) {
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
stack.push(c - '0');
break;
case '+':
stack.push(stack.pop() + stack.pop());
break;
case '-':
int a = stack.pop();
int b = stack.pop();
stack.push(b - a);
break;
case '*':
stack.push(stack.pop() * stack.pop());
break;
case '/':
a = stack.pop();
b = stack.pop();
stack.push(a == 0 ? 0 : b / a);
break;
case '%':
a = stack.pop();
b = stack.pop();
stack.push(a == 0 ? 0 : b % a);
break;
case '!':
stack.push(stack.pop() == 0 ? 1 : 0);
break;
case '`':
stack.push(stack.pop() < stack.pop() ? 1 : 0);
break;
case '>':
dx = 1;
dy = 0;
break;
case '<':
dx = -1;
dy = 0;
break;
case '^':
dx = 0;
dy = -1;
break;
case 'v':
dx = 0;
dy = 1;
break;
case '?':
dx = 0;
dy = 0;
switch (ThreadLocalRandom.current().nextInt(4)) {
case 0:
dx = 1;
break;
case 1:
dy = 1;
break;
case 2:
dx = -1;
break;
case 3:
dy = -1;
break;
}
break;
case '_':
dx = stack.pop() == 0 ? 1 : -1;
dy = 0;
break;
case '|':
dx = 0;
dy = stack.pop() == 0 ? 1 : -1;
break;
case '"':
stringMode = true;
break;
case ':':
stack.push(stack.empty() ? 0 : stack.peek());
break;
case '\\':
a = stack.pop();
b = stack.empty() ? 0 : stack.pop();
stack.push(a);
stack.push(b);
break;
case '$':
stack.pop();
break;
case '.':
output.append(stack.pop());
break;
case ',':
output.append((char)(int)stack.pop());
break;
case '#':
x += dx;
y += dy;
break;
case 'p':
grid[stack.pop()][stack.pop()] = (char)(int)stack.pop();
break;
case 'g':
stack.push((int)grid[stack.pop()][stack.pop()]);
break;
case '@':
return output.toString();
case ' ':
break;
default:
throw new IllegalArgumentException(
"Invalid Befunge instruction: '" + c + "'");
}
x += dx;
if (x < 0)
x += WIDTH;
else if (x >= WIDTH)
x -= WIDTH;
y += dy;
if (y < 0)
y += HEIGHT;
else if (y >= HEIGHT)
y -= HEIGHT;
}
}
}import java.util.Stack;
import java.util.Random;
import java.util.ArrayList;
public class BefungeInterpreter {
public static String interpret(String code) {
Random rand = new Random();
ArrayList<Integer> widths = new ArrayList<Integer>();
// construct 2d array
// remove newlines
code = code.replace("\n", "s");
// get width
int size = 0;
int width = 0;
int height = 1;
for (int i = 0; i < code.length(); i++) {
if (code.charAt(i) == 's') {
height++;
widths.add(width);
if (width > size)
size = width;
width = 0;
} else
width++;
}
widths.add(width);
if (width > size)
size = width;
code = code.replace("s", "");
// insert into 2d array
char[][] grid = new char[size][height];
int countW = 0;
int countH = 0;
for (int i = 0; i < code.length(); i++) {
grid[countW][countH] = code.charAt(i);
countW++;
if (countW == widths.get(countH)) {
countW = 0;
countH++;
}
}
// interpret section
// setup
String output = "";
char direction = '>';
Stack<Integer> stack = new Stack<Integer>();
int x = 0;
int y = 0;
char symbol = ' ';
while (symbol != '@') {
symbol = grid[x][y];
// direction
if (symbol == '<' || symbol == '>' || symbol == '^' || symbol == 'v')
direction = symbol;
// push 0-9
else if (Character.isDigit(symbol))
stack.push(Character.getNumericValue(symbol));
// addition
else if (symbol == '+')
stack.push(stack.pop() + stack.pop());
// subtraction
else if (symbol == '-') {
int a = stack.pop();
int b = stack.pop();
stack.push(b - a);
}
// multiplication
else if (symbol == '*')
stack.push(stack.pop() * stack.pop());
// division
else if (symbol == '/') {
int a = stack.pop();
int b = stack.pop();
int value = (a == 0) ? 0 : b / a;
stack.push(value);
}
// modulo
else if (symbol == '%') {
int a = stack.pop();
int b = stack.pop();
int value = (a == 0) ? 0 : b % a;
stack.push(value);
}
// logical NOT
else if (symbol == '!') {
int value = stack.pop();
int pushVal = (value == 0) ? 1 : 0;
stack.push(pushVal);
}
// backtick
else if (symbol == '`') {
int a = stack.pop();
int b = stack.pop();
int value = (b > a) ? 1 : 0;
stack.push(value);
}
// random direction
else if (symbol == '?') {
int val = rand.nextInt(4);
if (val == 0)
direction = '>';
else if (val == 1)
direction = '<';
else if (val == 2)
direction = '^';
else if (val == 3)
direction = 'v';
}
// horizontal switch
else if (symbol == '_')
direction = (stack.pop() == 0) ? '>' : '<';
// vertical switch
else if (symbol == '|')
direction = (stack.pop() == 0) ? 'v' : '^';
// string mode
else if (symbol == '"') {
if (direction == '>') {
x++;
if (x == widths.get(y))
x = 0;
} else if (direction == '<') {
x--;
if (x < 0)
x = widths.get(y) - 1;
} else if (direction == '^') {
y--;
if (y < 0)
y = height - 1;
} else if (direction == 'v') {
y++;
if (y == height)
y = 0;
}
symbol = grid[x][y];
while (symbol != '"') {
stack.push((int) symbol);
if (direction == '>') {
x++;
if (x == widths.get(y))
x = 0;
} else if (direction == '<') {
x--;
if (x < 0)
x = widths.get(y) - 1;
} else if (direction == '^') {
y--;
if (y < 0)
y = height - 1;
} else if (direction == 'v') {
y++;
if (y == height)
y = 0;
}
symbol = grid[x][y];
}
}
// duplicate
else if (symbol == ':') {
int val = (stack.empty()) ? 0 : stack.peek();
stack.push(val);
}
// swap
else if (symbol == '\\') {
int a = stack.pop();
int b = (stack.empty()) ? 0 : stack.pop();
stack.push(a);
stack.push(b);
}
// discard
else if (symbol == '$')
stack.pop();
// pop integer output
else if (symbol == '.')
output = output + stack.pop();
// pop ASCII output
else if (symbol == ',') {
char val = (char) ((int) (stack.pop()));
output = output + val;
}
// skip
else if (symbol == '#') {
if (direction == '>') {
x++;
if (x == widths.get(y))
x = 0;
} else if (direction == '<') {
x--;
if (x < 0)
x = widths.get(y) - 1;
} else if (direction == '^') {
y--;
if (y < 0)
y = height - 1;
} else if (direction == 'v') {
y++;
if (y == height)
y = 0;
}
}
// put call
else if (symbol == 'p') {
int yP = stack.pop();
int xP = stack.pop();
char v = (char) ((int) (stack.pop()));
grid[xP][yP] = v;
}
// get call
else if (symbol == 'g') {
int yP = stack.pop();
int xP = stack.pop();
stack.push((int) grid[xP][yP]);
}
// manage movement
if (direction == '>') {
x++;
if (x == widths.get(y))
x = 0;
} else if (direction == '<') {
x--;
if (x < 0)
x = widths.get(y) - 1;
} else if (direction == '^') {
y--;
if (y < 0)
y = height - 1;
} else if (direction == 'v') {
y++;
if (y == height)
y = 0;
}
}
return output;
}
}
