Smallf*ck (simple brainfuck dialect) interpreter endless loop

Question

I'm trying to implement a Smallf*ck interpreter.

Smallfuck is an even more laconic dialect of Brainfuck, which operates on bits instead of bytes, has a limited size of memory tape and has no I/O commands. Thus, it is left with only 5 commands:

* : flip the current bit;
> : increment the data pointer (move it to the next cell to the right);
< : decrement the data pointer (move it to the next cell to the left);
[ : “begin loop”:
    if the current bit is 1, increment the instruction pointer
    (move it to the next command to the right), otherwise,
    move it to the next command to the right of the matching ] command;
] : “end loop”:
    if the current bit is 0, increment the instruction pointer,
    otherwise move it to the next command to the right of the matching [ command.
    Can also be interpreted as unconditional jump to the matching [ command,
    since [ performs an extra check itself.

Example input: "*>*>*>*>*>*>*>*", "00101100" should return "11010011"

My implementation so far:

def interpreter(code, tape):
    ptr, cmd_pos = 0, 0
    tape = [int(num) for num in tape]
    while ptr < len(tape) and cmd_pos < len(code):
        if code[cmd_pos] == ">":
            ptr += 1
        elif code[cmd_pos] == "<":
            ptr -= 1
        elif code[cmd_pos] == "*":
            tape[ptr] = 1 if tape[ptr] == 0 else 0
        elif code[cmd_pos] == "[":
            if tape[ptr] == 0:
                found = False
                while not found:
                    cmd_pos += 1
                    if code[cmd_pos] == "]":
                        found = True
        elif code[cmd_pos] == "]":
            found = False
            while not found:
                cmd_pos -= 1
                if code[cmd_pos] == "[":
                    found = True
        cmd_pos += 1
    return ''.join([str(num) for num in tape])

There is also a codewars question, which is the reason I'm doing this: https://www.codewars.com/kata/58678d29dbca9a68d80000d7/train/python

I don't know what's wrong with my code... The basic stuff works, but loops don't. At some test cases on codewars I create an endless loop and I don't know why.

Help would be really appreciated, maybe someone has even a lot of fun implementing this:

Answer 1

You also need to consider nested loops. For example if you take the code "[*[>]]", when your implementation reaches the end of the outer loop, it will look for the first "[" left of it and continue from there. But because it was the "]" of the outer loop it should instead continue at the "[" of the same outer loop (the second one it finds when searching to the left of "]"). To achieve this you could for example count the number of "]" you encounter while looking to the left:

    elif code[cmd_pos] == "]" and tape[ptr]==1:
        found = False
        nestedLoopCounter = 1
        while not found:
            cmd_pos -= 1
            if code[cmd_pos] == "]":
                nestedLoopCounter+=1
            elif code[cmd_pos] == "[":
                nestedLoopCounter-=1
                if nestedLoopCounter==0:
                    found = True
        cmd_pos-=1

Also note that you need to check if the value in the current cell is 1 first. The same holds for "[". If you encounter the beginning of a loop and the current cell value is 0, so you want to skip the loop, you need to find the matching "]" and not just the first one you encounter.