def befunge93(program):
    height = len(program)
    weigth = len(program[0])

    prog_count = 0
    output = ''
    stack = []
    current = program[0][0]

    strmode = False
    location = [0, 0]
    direction = (0, 1)
    step = ()

    directions = {
        '>': (0, 1),
        '<': (0, -1),
        'v': (1, 0),
        '^': (-1, 0)
    }
    operations = ['+', '-', '*', '/', '%', '`']

    def ops(a, b, op):
        if op == '+':
            return a + b
        elif op == '-':
            return b - a
        elif op == '*':
            return a * b
        elif op == '/':
            return b // a
        elif op == '%':
            return b % a
        elif op == '`':
            return int(a < b)

    def safepop():
        if stack:
            return stack.pop()
        return 0

    while prog_count < 100000 and len(output) < 100:
        if strmode:
            if current == '"':
                strmode = False
            else:
                stack.append(ord(current))
        else:
            if current in directions:
                direction = directions[current]

            elif current == '#':
                step = (direction[0] * 2, direction[1] * 2)
            elif current == '_':
                direction = (0, 1) if safepop() == 0 else (0, -1)
            elif current == '|':
                direction = (1, 0) if safepop() == 0 else (-1, 0)

            elif current in operations:
                stack.append(ops(safepop(), safepop(), current))
            elif current == '!':
                stack.append(int(safepop() == 0))

            elif current == ':':
                stack += [safepop()] * 2
            elif current == '\\':
                stack += [safepop(), safepop()]
            elif current == '$':
                safepop()
            elif current == '.':
                output += str(safepop()) + ' '
            elif current == ',':
                a = safepop()
                output += chr(a)
            elif current.isdigit():
                stack.append(int(current))
            elif current == '"':
                strmode = True
            elif current == '@':
                break

        if step:
            location[0] += step[0]
            location[1] += step[1]
            step = ()
        else:
            location[0] += direction[0]
            location[1] += direction[1]

        location = [(height + location[0]) % height, (weigth + location[1]) % weigth]
        current = program[location[0]][location[1]]
        prog_count += 1

    return output



prg =   ["               v",
         "v  ,,,,,\"Hello\"<",
         ">48*,          v",
         "\"!dlroW\",,,,,,v>",
         "25*,@         > "]
print(befunge93(prg))


'''
While exploring the ruins of a golden lost city, you discovered an ancient manuscript containing 
series of strange symbols. 
Thanks to your profound knowledge of dead languages, you realized that the text was written 
in one of the dialects of Befunge-93. 
Looks like the prophecy was true: 
you are the one who can find the answer to the Ultimate Question of Life! 
Of course you brought your futuristic laptop with you, so now you just need a function 
that will run the encrypted message and make you the all-knowing human being.

Befunge-93 is a stack-based programming language, the programs for which are arranged in 
a two-dimensional torus grid. The program execution sequence starts at the top left corner 
and proceeds to the right until the first direction instruction is met 
(which can appear in the very first cell). 
The torus adjective means that the program never leaves the grid: when it encounters a border, 
it simply goes to the next command at the opposite side of the grid.

You need to write a function that will be able to execute the given Befunge-93 program. 
Unfortunately your laptop, futuristic that it is, can't handle more than 105 instructions and will 
probably catch on fire if you try to execute more, so the function should exit after 105 commands. 
The good news is, the prophesy said that the answer to the Ultimate Question of Life contains 
no more than 100 symbols, so the function should return the program output once it contains 100 symbols.

The dialect of Befunge-93 in the manuscript consists of the following commands:

    direction instructions:
        >: start moving right
        <: start moving left
        v: start moving down
        ^: start moving up
        #: bridge; skip next cell
    conditional instructions:
        _: pop a value; move right if value = 0, left otherwise
        |: pop a value; move down if value = 0, up otherwise
    math operators:
        +: addition; pop a, pop b, then push a + b
        -: subtraction; pop a, pop b, then push b - a
        *: multiplication; pop a, pop b, then push a * b
        /: integer division; pop a, pop b, then push b / a
        %: modulo operation; pop a, pop b, then push b % a
    logical operators:
        !: logical NOT; pop a value, if the value = 0, push 1, otherwise push 0
        `: greater than; pop a and b, then push 1 if b > a, otherwise 0
    stack instructions:
        :: duplicate value on top of the stack
        \: swap the top stack value with the second to the top
        $: pop value from the stack and discard it
    output instructions:
        .: pop value and output it as an integer followed by a space
        ,: pop value and output it as ASCII character
    digits 0-9: push the encountered number on the stack
    ": start string mode; push each character's ASCII value all the way up to the next "
    (whitespace character): empty instruction; does nothing
    @: end program; the program output should be returned then

If the stack is empty and it is necessary to pop a value, no exception is raised; instead, 0 is produced.

Example

For

program = [
    "               v",
    "v  ,,,,,"Hello"<",
    ">48*,          v",
    ""!dlroW",,,,,,v>",
    "25*,@         > "
]

the output should be befunge93(program) = "Hello World!\n".

Note, that in the tests tab you will see a \ as an escape symbol before each ".

Here is how the program is executed:

    the program starts executing at the top left corner, doing nothing according to the command until it meets the v command, which makes the instructions direct it downward;
    the < makes it go left;
    the " starts the string mode; "Hello" is pushed backwards on the stack;
    six , symbols produce the "Hello" word, emptying the stack;
    since the v symbol is encountered, the third line starts executing;
    4 and 8 are pushed on the stack; the * operator pops them, multiplies and puts the result (4 * 8 = 32) back on the stack;
    the , operator produces the character with the ASCII value of 32, which is a whitespace character;
    all the empty (' ') instructions are then executed, until the v command is encountered; then, the fourth line starts to execute;
    the > command forces instructions to the right to execute; since there is a border to the right, the leftmost instruction in the fourth line is executed next;
    another string " mode starts, which pushes "World!" backwards on the stack;
    next, the , commands output the "World!" string;
    the v command moves command execution to the next line;
    the > command moves command execution to the very beginning of the fifth line;
    2 * 5 = 10 is pushed on the stack, and produced as a character \n;
    finally, @ finishes the program execution.
'''
