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

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

def _disabled_input(*args, **kwargs):
    raise RuntimeError("input() is disabled in callable mode")
builtins.input = _disabled_input

ns = {"__name__": "__judge__"}  # prevent if __name__ == "__main__" blocks
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = "def jumps(code):\n    stack = []\n    skip_to = dict()\n    return_to = dict()\n    for i, c in enumerate(code):\n        if c == '[':\n            stack.append(i)\n        elif c == ']':\n            opening, closing = stack.pop(), i\n            skip_to[opening] = closing\n            return_to[closing] = opening\n    return (skip_to, return_to)\n\ndef run_one_instruction(code, tape, pc, pointer, skip_to, return_to):\n    instruction = code[pc]\n    if instruction == '>':\n        pointer += 1\n    elif instruction == '<':\n        pointer -= 1\n    elif instruction == '*':\n        tape[pointer] ^= 1\n    elif instruction == '[':\n        if tape[pointer] == 0:\n            pc = skip_to[pc]\n    elif instruction == ']':\n        if tape[pointer]:\n            pc = return_to[pc]\n    return (pc, pointer)\n\ndef should_terminate(pc, max_pc, pointer, max_pointer):\n    return pc > max_pc or pointer < 0 or pointer > max_pointer\n\ndef interpreter(code, tape):\n    tape = [int(c) for c in tape]\n    max_pointer = len(tape) - 1\n    pointer = 0\n    max_pc = len(code) - 1\n    pc = 0\n    skip_to, return_to = jumps(code)\n    while not should_terminate(pc, max_pc, pointer, max_pointer):\n        pc, pointer = run_one_instruction(code, tape, pc, pointer, skip_to, return_to)\n        pc += 1\n    return ''.join(str(cell) for cell in tape)"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

_target = None
_fn_name = 'interpreter'
if _fn_name:
    if "Solution" in ns:
        try:
            _obj = ns["Solution"]()
            if hasattr(_obj, _fn_name):
                _target = getattr(_obj, _fn_name)
        except Exception:
            _target = None
    if _target is None and _fn_name in ns and callable(ns[_fn_name]):
        _target = ns[_fn_name]
# Fallback: if there's exactly one user-defined function, use it
if _target is None:
    _cands = [v for k, v in ns.items() if callable(v) and getattr(v, "__module__", "") in ("__judge__", "__main__")]
    _user_funcs = [c for c in _cands if getattr(c, "__name__", "").startswith("_") is False]
    if len(_user_funcs) == 1:
        _target = _user_funcs[0]
if _target is None:
    raise RuntimeError(f"Could not resolve callable '{_fn_name}'")

_raw = sys.stdin.read().strip()
if _raw:
    _parsed = json.loads(_raw)
    if isinstance(_parsed, dict):
        _kwargs = _parsed.get("kwargs", {})
        _args = _parsed.get("args", [])
    else:
        _args, _kwargs = _parsed, {}
else:
    _args, _kwargs = [], {}
if not isinstance(_args, (list, tuple)):
    _args = [_args]
_res = _target(*_args, **_kwargs)
try:
    sys.stdout.write(repr(_res) + "\n")
except Exception:
    pass

```

Measured memory_bytes: 7144