# Esolang Interpreters #2 - Custom Smallfuck Interpreter

## About this Kata Series

"Esolang Interpreters" is a Kata Series that originally began as three separate, independent esolang interpreter Kata authored by [@donaldsebleung](http://codewars.com/users/donaldsebleung) which all shared a similar format and were all somewhat inter-related.  Under the influence of [a fellow Codewarrior](https://www.codewars.com/users/nickkwest), these three high-level inter-related Kata gradually evolved into what is known today as the "Esolang Interpreters" series.

This series is a high-level Kata Series designed to challenge the minds of bright and daring programmers by implementing interpreters for various [esoteric programming languages/Esolangs](http://esolangs.org), mainly [Brainfuck](http://esolangs.org/wiki/Brainfuck) derivatives but not limited to them, given a certain specification for a certain Esolang.  Perhaps the only exception to this rule is the very first Kata in this Series which is intended as an introduction/taster to the world of esoteric programming languages and writing interpreters for them.

## The Language

Smallfuck is an [esoteric programming language/Esolang](http://esolangs.org) invented in 2002 which is a sized-down variant of the famous [Brainfuck](http://esolangs.org/wiki/Brainfuck) Esolang.  Key differences include:

- Smallfuck operates only on bits as opposed to bytes
- It has a limited data storage which varies from implementation to implementation depending on the size of the tape
- It does not define input or output - the "input" is encoded in the initial state of the data storage (tape) and the "output" should be decoded in the final state of the data storage (tape)

Here are a list of commands in Smallfuck:

- `>` - Move pointer to the right (by 1 cell)
- `<` - Move pointer to the left (by 1 cell)
- `*` - Flip the bit at the current cell
- `[` - Jump past matching `]` if value at current cell is `0`
- `]` - Jump back to matching `[` (if value at current cell is nonzero)

As opposed to Brainfuck where a program terminates only when all of the commands in the program have been considered (left to right), Smallfuck terminates when any of the two conditions mentioned below become true:

- All commands have been considered from left to right
- The pointer goes out-of-bounds (i.e. if it moves to the left of the first cell or to the right of the last cell of the tape)

Smallfuck is considered to be Turing-complete **if and only if** it had a tape of infinite length; however, since the length of the tape is always defined as finite (as the interpreter cannot return a tape of infinite length), its computational class is of bounded-storage machines with bounded input.

More information on this Esolang can be found [here](http://esolangs.org/wiki/Smallfuck).

## The Task

Implement a custom Smallfuck interpreter `interpreter()` (`interpreter` in Haskell and F#, `Interpreter` in C#, `custom_small_fuck:interpreter/2` in Erlang) which accepts the following arguments:

1. `code` - **Required**.  The Smallfuck program to be executed, passed in as a string.  May contain non-command characters.  Your interpreter should simply ignore any non-command characters.
2. `tape` - **Required**.  The initial state of the data storage (tape), passed in **as a string**.  For example, if the string `"00101100"` is passed in then it should translate to something of this form within your interpreter: `[0, 0, 1, 0, 1, 1, 0, 0]`.  You may assume that all input strings for `tape` will be non-empty and will only contain `"0"`s and `"1"`s.

Your interpreter should return the final state of the data storage (tape) **as a string** in the same format that it was passed in.  For example, if the tape in your interpreter ends up being `[1, 1, 1, 1, 1]` then return the string `"11111"`.

*NOTE: The pointer of the interpreter always starts from the first (leftmost) cell of the tape, same as in Brainfuck.*

Good luck :D

## Kata in this Series

1. [Esolang Interpreters #1 - Introduction to Esolangs and My First Interpreter (MiniStringFuck)](https://www.codewars.com/kata/esolang-interpreters-number-1-introduction-to-esolangs-and-my-first-interpreter-ministringfuck)
2. **Esolang Interpreters #2 - Custom Smallfuck Interpreter**
3. [Esolang Interpreters #3 - Custom Paintfuck Interpreter](http://codewars.com/kata/esolang-interpreters-number-3-custom-paintf-star-star-k-interpreter)
4. [Esolang Interpreters #4 - Boolfuck Interpreter](http://codewars.com/kata/esolang-interpreters-number-4-boolfuck-interpreter)

Difficulty: introductory

Starter code:

def interpreter(code, tape):
	

Solutions:
def interpreter(code, tape):
    tape = list(map(int, tape))
    ptr = step = loop = 0
    
    while 0 <= ptr < len(tape) and step < len(code):
        command = code[step]
        
        if loop:
            if   command == "[": loop += 1
            elif command == "]": loop -= 1
        
        elif command == ">": ptr += 1
        elif command == "<": ptr -= 1
        elif command == "*": tape[ptr] ^= 1        
        elif command == "[" and tape[ptr] == 0: loop += 1
        elif command == "]" and tape[ptr] == 1: loop -= 1
    
        step += 1 if not loop else loop // abs(loop)
    
    return "".join(map(str, tape))

def interpreter(code, tape):

    p, tapeP, tape = 0, 0, list(tape)
    
    stack, bracketMove = [], {}
    for i,c in enumerate(code):
        if c == '[': stack.append(i)
        elif c == ']':
          bracketMove[i] = stack[-1]
          bracketMove[stack.pop()] = i
    
    while p < len(code) and 0 <= tapeP < len(tape):
        if   code[p] == "*":                            tape[tapeP] = "0" if tape[tapeP] == "1" else "1"
        elif code[p] == "<":                            tapeP -= 1
        elif code[p] == ">":                            tapeP += 1
        elif (code[p] == "[" and tape[tapeP] == "0") \
             or (code[p] == "]" and tape[tapeP] != "0"):  p = bracketMove[p]
        p += 1
    
    return "".join(tape)

def jumps(code):
    stack = []
    skip_to = dict()
    return_to = dict()
    for i, c in enumerate(code):
        if c == '[':
            stack.append(i)
        elif c == ']':
            opening, closing = stack.pop(), i
            skip_to[opening] = closing
            return_to[closing] = opening
    return (skip_to, return_to)

def run_one_instruction(code, tape, pc, pointer, skip_to, return_to):
    instruction = code[pc]
    if instruction == '>':
        pointer += 1
    elif instruction == '<':
        pointer -= 1
    elif instruction == '*':
        tape[pointer] ^= 1
    elif instruction == '[':
        if tape[pointer] == 0:
            pc = skip_to[pc]
    elif instruction == ']':
        if tape[pointer]:
            pc = return_to[pc]
    return (pc, pointer)

def should_terminate(pc, max_pc, pointer, max_pointer):
    return pc > max_pc or pointer < 0 or pointer > max_pointer

def interpreter(code, tape):
    tape = [int(c) for c in tape]
    max_pointer = len(tape) - 1
    pointer = 0
    max_pc = len(code) - 1
    pc = 0
    skip_to, return_to = jumps(code)
    while not should_terminate(pc, max_pc, pointer, max_pointer):
        pc, pointer = run_one_instruction(code, tape, pc, pointer, skip_to, return_to)
        pc += 1
    return ''.join(str(cell) for cell in tape)

def interpreter(code, tape):
    p = 0
    c = 0
    li = list(tape)
    left = {}
    right = {}
    stk = []
    for x in range(len(code)):
        if code[x] == '[':
            stk.append(x)
        elif code[x] == ']':
            sb = stk.pop()
            left[str(sb)] = x
            right[str(x)] = sb
    while c < len(code):
        if p < 0 or p >= len(tape):
            return ''.join(li)
        if code[c] == '[':
            if li[p] == '0':
                c = left[str(c)]
        elif code[c] == ']':
            if li[p] != '0':
                c = right[str(c)]
        elif code[c] == '*':
            li[p] = str(abs(int(li[p])-1))
        elif code[c] == '>':
            p += 1
        elif code[c] == '<':
            p -= 1
        c += 1
    return ''.join(li)

def interpreter(code, tape):
    t = list(map(int, tape))
    position = address = depth = 0
    while -1 < position < len(tape) and address < len(code):
        if depth:
            depth       += code[address] is "["
            depth       -= code[address] is "]"
        else:
            t[position] ^= code[address] is "*"
            depth       += code[address] is "[" and not t[position]
            depth       -= code[address] is "]" and     t[position]
            position    += code[address] is ">"
            position    -= code[address] is "<"
        address += 1 - 2 * (depth < 0)
    return "".join(map(str, t))


def interpreter(code, tape):
    pointer = 0
    pointer_stack = []
    code_pointer = 0
    tape_length = len(tape)
    code_length = len(code)
    tape = [c for c in tape]
    
    while True:
        if code_pointer >= code_length:
            break
        command = code[code_pointer]
        
        if command == '>':
            pointer += 1
            if pointer >= tape_length: break
        elif command == '<':
            pointer -= 1
            if pointer < 0: break
        elif command == '*':
            tape[pointer] = '0' if tape[pointer] == '1' else '1'
        elif command == '[':
            if tape[pointer] == '0':
                counter = 1
                while counter != 0:
                    code_pointer += 1
                    if code[code_pointer] == '[':
                        counter += 1
                    elif code[code_pointer] == ']':
                        counter -= 1
            else:
                pointer_stack.append(code_pointer)
        elif command == ']':
            if tape[pointer] == '1':
                code_pointer = pointer_stack[-1]
            else:
                pointer_stack.pop()
        code_pointer += 1
        
    return ''.join(tape)


def interpreter(code, tape):
    cells = list(map(int, tape))
    cell_p, command_p = 0, -1
    scope_stack = [(0, len(code))]
    while True:
        command_p += 1
        if command_p >= len(code) or cell_p >= len(cells) or cell_p < 0: break
        command = code[command_p]
        if command == '>': cell_p += 1
        elif command == '<': cell_p -= 1
        elif command == '*': cells[cell_p] = int(not cells[cell_p])
        elif command == '[':
            scope_end_p = code.rfind(']', scope_stack[-1][0], scope_stack[-1][1])
            if not cells[cell_p]: command_p = scope_end_p
            else: scope_stack.append((command_p, scope_end_p))
        elif command == ']': 
            if cells[cell_p]: command_p = scope_stack[-1][0]
            else: scope_stack.pop()
    return ''.join(list(map(str, cells)))


def interpreter(s, tape):
    m, pointer, j = list(map(int, tape)), 0, 0
    find, find_ = [i for i, j in enumerate(s) if j == '['],[i for i, j in enumerate(s) if j == ']']
    opened, closed = {i: j for i, j in zip(find, find_[::-1])}, {i: j for i, j in zip(find_[::-1], find)} # open and closed braces
    while j < len(s) and 0<=pointer<len(m):
        if s[j] == "*" :             m[pointer] ^= 1
        elif s[j] == '>' :           pointer += 1
        elif s[j] == '<' :           pointer -= 1
        elif s[j] == "[":
            if m[pointer] == 0 :  j = opened[j]
        elif s[j] == ']':
            if m[pointer] == 1 :  j = closed[j]
        j += 1
    return "".join(map(str, m))

def interpreter(code, t):
    print((code,t))
    tape = list(t)
    f = [n for n,x in enumerate(list(code)) if x=='[']
    l = [n for n,x in enumerate(list(code)) if x==']']
    l.reverse()
    print((f,l))
    i, x, curr = 0, 0, 0
    while i!=len(code) and x>-1 and x<len(tape):
        if x>-1 and x<len(tape): curr = int(tape[x])
        if code[i]=='>': x+=1
        if code[i]=='<': x-=1
        if code[i]=='*' and x>-1 and x<len(tape): 
            if tape[x]=='1': tape[x]='0'
            else: tape[x]='1'
        if code[i]=='[' and curr==0: 
            if f!=None:
                i = l[f.index(i)]
            else: break
        elif code[i]==']' and curr==1: 
            if l!=None:
                i = f[l.index(i)]
            else: break
        i+=1
    return ''.join(tape)


def interpreter(code, tape):
    pos = 0
    tape = list(map(int, list(tape)))
    pos_code = 0
    while pos_code < len(code) and pos < len(tape) and pos > -1:
        instruction = code[pos_code]
        if instruction == '>':
            pos += 1
        elif instruction == '<':
            pos -= 1
        elif instruction == '*':
            if tape[pos] == 0:
                tape[pos] = 1
            else:
                tape[pos] = 0
        elif instruction == '[':
            if tape[pos] == 0:
                open = 1
                for i in range(pos_code + 1, len(code)):
                    if code[i] == '[':
                        open += 1
                    elif code[i] == ']':
                        open -= 1
                        if open == 0:
                            pos_code = i
                            break
                            
        elif instruction == ']':
            if tape[pos] != 0:
                closed = 1
                for i in range(pos_code - 1, -1, -1):
                    if code[i] == ']':
                        closed += 1
                    elif code[i] == '[':
                        closed -= 1
                        if closed == 0:
                            pos_code = i
                            break
        pos_code += 1
    return ''.join(map(str, tape))