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](https://en.wikipedia.org/wiki/Befunge)):
- `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 random

def const(n):
    return lambda itp: itp.push(n)

def unary(f):
    return lambda itp: itp.push(f(itp.pop()))

def binary(f):
    return lambda itp: itp.push(f(itp.pop(), itp.pop()))

def direction(x, y):
    return lambda itp: itp.set_vpc(x, y)

def dup(itp):
    x = itp.pop()
    itp.push(x)
    itp.push(x)

def swap(itp):
    x = itp.pop()
    y = itp.pop()
    itp.push(x)
    itp.push(y)

opcodes = {
    '+': binary(lambda a, b: b + a),
    '-': binary(lambda a, b: b - a),
    '*': binary(lambda a, b: b * a),
    '/': binary(lambda a, b: b / a),
    '%': binary(lambda a, b: b % a),
    '!': unary(lambda a: not a),
    '`': binary(lambda a, b: b > a),
    
    '>': direction(1, 0),
    '<': direction(-1, 0),
    'v': direction(0, 1),
    '^': direction(0, -1),
    
    '?': lambda itp: itp.set_vpc(*random.choice(((1, 0), (-1, 0), (0, 1), (0, -1)))),
                          
    '_': lambda itp: itp.set_vpc((-1)**(itp.pop() != 0), 0),
    '|': lambda itp: itp.set_vpc(0, (-1)**(itp.pop() != 0)),
    
    ':': dup,
    '\\': swap,
    
    '$': lambda itp: itp.pop(),
    '.': lambda itp: itp.output(str(itp.pop())),
    ',': lambda itp: itp.output(chr(itp.pop())),
    
    'p': lambda itp: itp.put(itp.pop(), itp.pop(), itp.pop()),
    'g': lambda itp: itp.push(itp.get(itp.pop(), itp.pop())),
    
    '#': lambda itp: itp.advance(),
    '@': lambda itp: itp.end(), 
    ' ': lambda itp: None,
}

for i in range(10):
    opcodes[str(i)] = const(i)

class Interpreter:
    def __init__(self, code):
        self.mem = [list(l) for l in code.split('\n')]
        self.stack = []
        self.pc = 0, 0
        self.vpc = 1, 0
        self.obuf = []
        self.ended = False
        self.stringmode = False
    
    def run(self):
        while not self.ended:
            x, y = self.pc
            op = self.mem[y][x]
        
            if op == '"':
                self.stringmode = not self.stringmode
            elif self.stringmode:
                self.push(ord(op))
            else:
                opcodes[op](self)
        
            self.advance()
    
    def advance(self):
        x, y = self.pc
        vx, vy = self.vpc
        y = (y + vy) % len(self.mem)
        x = (x + vx) % len(self.mem[y])
        self.pc = x, y
    
    def set_vpc(self, x, y):
        self.vpc = x, y
    
    def push(self, x):
        self.stack.append(int(x))
    
    def pop(self):
        try:
            return self.stack.pop(-1)
        except IndexError:
            return 0
    
    def output(self, s):
        self.obuf.append(s)

    def end(self):
        self.ended = True

    def get(self, y, x):
        return ord(self.mem[y][x])

    def put(self, y, x, n):
        self.mem[y][x] = chr(n)

def interpret(code):
    itp = Interpreter(code)
    
    itp.run()
    
    return ''.join(itp.obuf)
import random

def const(n):
    return lambda itp: itp.push(n)

def unary(f):
    return lambda itp: itp.push(f(itp.pop()))

def binary(f):
    return lambda itp: itp.push(f(itp.pop(), itp.pop()))

def direction(x, y):
    return lambda itp: itp.set_vpc(x, y)

def dup(itp):
    x = itp.pop()
    itp.push(x)
    itp.push(x)

def swap(itp):
    x = itp.pop()
    y = itp.pop()
    itp.push(x)
    itp.push(y)

opcodes = {
    '+': binary(lambda a, b: b + a),
    '-': binary(lambda a, b: b - a),
    '*': binary(lambda a, b: b * a),
    '/': binary(lambda a, b: b / a),
    '%': binary(lambda a, b: b % a),
    '!': unary(lambda a: not a),
    '`': binary(lambda a, b: b > a),
    
    '>': direction(1, 0),
    '<': direction(-1, 0),
    'v': direction(0, 1),
    '^': direction(0, -1),
    
    '?': lambda itp: itp.set_vpc(*random.choice(((1, 0), (-1, 0), (0, 1), (0, -1)))),
                          
    '_': lambda itp: itp.set_vpc((-1)**(itp.pop() != 0), 0),
    '|': lambda itp: itp.set_vpc(0, (-1)**(itp.pop() != 0)),
    
    ':': dup,
    '\\': swap,
    
    '$': lambda itp: itp.pop(),
    '.': lambda itp: itp.output(str(itp.pop())),
    ',': lambda itp: itp.output(chr(itp.pop())),
    
    'p': lambda itp: itp.put(itp.pop(), itp.pop(), itp.pop()),
    'g': lambda itp: itp.push(itp.get(itp.pop(), itp.pop())),
    
    '#': lambda itp: itp.advance(),
    '@': lambda itp: itp.end(), 
    ' ': lambda itp: None,
}

for i in range(10):
    opcodes[str(i)] = const(i)

class Interpreter:
    def __init__(self, code):
        self.mem = [list(l) for l in code.split('\n')]
        self.stack = []
        self.pc = 0, 0
        self.vpc = 1, 0
        self.obuf = []
        self.ended = False
        self.stringmode = False
    
    def run(self):
        while not self.ended:
            x, y = self.pc
            op = self.mem[y][x]
        
            if op == '"':
                self.stringmode = not self.stringmode
            elif self.stringmode:
                self.push(ord(op))
            else:
                opcodes[op](self)
        
            self.advance()
    
    def advance(self):
        x, y = self.pc
        vx, vy = self.vpc
        y = (y + vy) % len(self.mem)
        x = (x + vx) % len(self.mem[y])
        self.pc = x, y
    
    def set_vpc(self, x, y):
        self.vpc = x, y
    
    def push(self, x):
        self.stack.append(int(x))
    
    def pop(self):
        try:
            return self.stack.pop(-1)
        except IndexError:
            return 0
    
    def output(self, s):
        self.obuf.append(s)

    def end(self):
        self.ended = True

    def get(self, y, x):
        return ord(self.mem[y][x])

    def put(self, y, x, n):
        self.mem[y][x] = chr(n)

def interpret(code):
    itp = Interpreter(code)
    
    itp.run()
    
    return ''.join(itp.obuf)