Befunge-93 interpreter in Python

Question

I was doing some CodeFights and had alot of fun with this Befunge challange

Problem statement

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 10^5 instructions and will probably catch on fire if you try to execute more, so the function should exit after 10^5 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:

1. direction instructions:

   • >: start moving right
   • <: start moving left
   • v: start moving down
   • ^: start moving up
   • #: bridge; skip next cell

2. conditional instructions:

   • _: pop a value; move right if value = 0, left otherwise
   • |: pop a value; move down if value = 0, up otherwise

3. 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

4. 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

5. 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

6. output instructions:

   • .: pop value and output it as an integer followed by a space
   • ,: pop value and output it as ASCII character digits

7. Other instructions:

   • 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
   • ?: start moving in a random cardinal direction

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

---

My code

import random
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 = ()

    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 == '>':
                direction = (0, 1)
            elif current == '<':
                direction = (0, -1)
            elif current == 'v':
                direction = (1, 0)
            elif current == '^':
                direction = (-1, 0)
            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 == '+':
                stack.append(safepop() + safepop())
            elif current == '-':
                a, b = safepop(), safepop()
                stack.append(b - a)
            elif current == '*':
                stack.append(safepop() * safepop())
            elif current == '/':
                a, b = safepop(), safepop()
                stack.append(b // a)
            elif current == '%':
                a, b = safepop(), safepop()
                stack.append(b % a)
            elif current == '!':
                stack.append(int(safepop() == 0))
            elif current == '`':
                stack.append(int(safepop() < safepop()))
            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 == '?':
                direction = random.choice([(0, 1), (1, 0), (0, -1), (-1, 0)])
            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

---

Note

Missing standard befunge-93 operations are:

(Added for completeness sake but not needed for tests)

• p: a put call. Pop a, b, and v, then change the character at (x,y) in the program to the character with ASCII value v
• g: a get call. Pop a and b, then push ASCII value of the character at that position in the program
• &: ask user for a number and push it
• ~: ask user for a character and push its ASCII value

---

Tests

This link does not contain correct test data (codefights and wiki does), if need be I'll add a few more examples.

print(befunge93(["               v", 
"v  ,,,,,\"Hello\"<", 
">48*,          v", 
"\"!dlroW\",,,,,,v>", 
"25*,@         > "]))
# >>> Hello world\n

Any review would be welcome. :)

Answer 1

Here are some improvement you can do

• gather the four directions >,<,^,v
• gather the operations +, -, *, /, %, `

here are my sample code

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)
...

#in the while loop, replace the original code
if current in directions:
        direction = directions[current]
elif current in operations:
        stack.append(ops(safepop(), safepop(), current))