# Esolang Interpreters #3 - Custom Paintfuck 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

Paintfuck is a [borderline-esoteric programming language/Esolang](http://esolangs.org) which is a derivative of [Smallfuck](http://esolangs.org/wiki/Smallfuck) (itself a derivative of the famous [Brainfuck](http://esolangs.org/wiki/Brainfuck)) that uses a two-dimensional data grid instead of a one-dimensional tape.

Valid commands in Paintfuck include:

- `n` - Move data pointer north (up)
- `e` - Move data pointer east (right)
- `s` - Move data pointer south (down)
- `w` - Move data pointer west (left)
- `*` - Flip the bit at the current cell (same as in Smallfuck)
- `[` - Jump past matching `]` if bit under current pointer is `0` (same as in Smallfuck)
- `]` - Jump back to the matching `[` (if bit under current pointer is nonzero) (same as in Smallfuck)

The specification states that any non-command character (i.e. any character other than those mentioned above) should simply be ignored.  The output of the interpreter is the two-dimensional data grid itself, best as animation as the interpreter is running, but at least a representation of the data grid itself after a certain number of iterations (explained later in task).

In current implementations, the 2D datagrid is finite in size with toroidal (wrapping) behaviour.  This is one of the few major differences of Paintfuck from Smallfuck as Smallfuck terminates (normally) whenever the pointer exceeds the bounds of the tape.

Similar to Smallfuck, Paintfuck is Turing-complete **if and only if** the 2D data grid/canvas were unlimited in size.  However, since the size of the data grid is defined to be finite, it acts like a finite state machine.

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

## The Task

Your task is to implement a custom Paintfuck interpreter `interpreter()`/`Interpret` which accepts the following arguments in the specified order:

1. `code` - **Required**.  The Paintfuck code to be executed, passed in as a string.  May contain comments (non-command characters), in which case your interpreter should simply ignore them.  If empty, simply return the initial state of the data grid.
2. `iterations` - **Required**.  A non-negative integer specifying the number of iterations to be performed before the final state of the data grid is returned.  See notes for definition of 1 iteration.  If equal to zero, simply return the initial state of the data grid.
3. `width` - **Required**.  The width of the data grid in terms of the number of data cells in each row, passed in as a positive integer.
4. `height` - **Required**.  The height of the data grid in cells (i.e. number of rows) passed in as a positive integer.

A few things to note:

- Your interpreter should treat all command characters as **case-sensitive** so `N`, `E`, `S` and `W` are **not** valid command characters
- Your interpreter should initialize all cells within the data grid to a value of `0` regardless of the width and height of the grid
- In this implementation, your pointer must always start at the **top-left hand corner** of the data grid (i.e. first row, first column).  This is important as some implementations have the data pointer starting at the middle of the grid.
- One iteration is defined as one step in the program, i.e. the number of command characters evaluated.  For example, given a program `nessewnnnewwwsswse` and an iteration count of `5`, your interpreter should evaluate `nesse` before returning the final state of the data grid.  **Non-command characters should not count towards the number of iterations.**
- Regarding iterations, the act of skipping to the matching `]` when a `[` is encountered (or vice versa) is considered to be **one** iteration regardless of the number of command characters in between.  The next iteration then commences at the command **right after** the matching `]` (or `[`).
- Your interpreter should terminate normally and return the final state of the 2D data grid whenever **any** of the mentioned conditions become true: (1) All commands have been considered left to right, or (2) Your interpreter has already performed the number of iterations specified in the second argument.
- The return value of your interpreter should be a representation of the final state of the 2D data grid where each row is separated from the next by a CRLF (`\r\n`).  For example, if the final state of your datagrid is

```
[
  [1, 0, 0],
  [0, 1, 0],
  [0, 0, 1]
]
```

... then your return string should be `"100\r\n010\r\n001"`.

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](http://codewars.com/kata/esolang-interpreters-number-2-custom-smallfuck-interpreter)
3. **Esolang Interpreters #3 - Custom Paintfuck Interpreter**
4. [Esolang Interpreters #4 - Boolfuck Interpreter](http://codewars.com/kata/esolang-interpreters-number-4-boolfuck-interpreter)

Difficulty: interview

Starter code:

def interpreter(code, iterations, width, height):
	

Solutions:
def interpreter(code, iterations, width, height):
    code = "".join(c for c in code if c in "[news]*")
    canvas = [ [0] * width for _ in range(height) ]
    row = col = step = count = loop = 0
    
    while step < len(code) and count < iterations:
        command = code[step]
        
        if loop:
            if   command == "[": loop += 1
            elif command == "]": loop -= 1
        
        elif command == "n": row = (row - 1) % height
        elif command == "s": row = (row + 1) % height
        elif command == "w": col = (col - 1) % width
        elif command == "e": col = (col + 1) % width
        elif command == "*": canvas[row][col] ^= 1
        elif command == "[" and canvas[row][col] == 0: loop += 1
        elif command == "]" and canvas[row][col] != 0: loop -= 1
        
        step += 1 if not loop else loop // abs(loop)
        count += 1 if not loop else 0
    
    return "\r\n".join("".join(map(str, row)) for row in canvas)

def interpreter(code, iterations, width, height):
    grid = [[0] * width for _ in range(height)]
    code = [c for c in code if c in '[]nesw*']
    
    jumps, stack = {}, []
    for i, c in enumerate(code):
        if c == '[': stack.append(i)
        if c == ']':
            jumps[i] = stack.pop()
            jumps[jumps[i]] = i

    ptr, x, y = -1, 0, 0
    while iterations > 0 and ptr < len(code) - 1:
        ptr += 1; iterations -= 1; c = code[ptr]
        if c == 'n': y = (y - 1) % height
        if c == 's': y = (y + 1) % height
        if c == 'w': x = (x - 1) % width
        if c == 'e': x = (x + 1) % width
        if c == '*': grid[y][x] = 1 - grid[y][x]
        if c == '[' and not grid[y][x]: ptr = jumps[ptr]
        if c == ']' and grid[y][x]: ptr = jumps[ptr]

    return '\r\n'.join(''.join(map(str, row)) for row in grid)

from collections import defaultdict

def interpreter(code, iterations, w, h):
    
    cp, r, c, p, stk, brackets, grid = 0, 0, 0, 0, [], {}, [[0] * w for _ in range(h)]

    for i, cc in enumerate(code):
        if cc == '[': stk.append(i)
        elif cc is ']':
            brackets[i] = stk.pop()
            brackets[brackets[i]] = i

    while p < iterations and cp < len(code):
        if   code[cp] == '*': grid[r][c] = (0 if grid[r][c] else 1)
        elif code[cp] == '[' and grid[r][c] == 0: cp = brackets[cp]
        elif code[cp] == ']' and grid[r][c] == 1: cp = brackets[cp]
        elif code[cp] == 'n': r = r - 1 if r else h - 1
        elif code[cp] == 'w': c = c - 1 if c else w - 1
        elif code[cp] == 's': r = r + 1 if r < h - 1 else 0
        elif code[cp] == 'e': c = c + 1 if c < w - 1 else 0
        cp, p = cp + 1, p + 1 if code[cp] in '[]nsew*' else p
        
    return '\r\n'.join([''.join(str(e) for e in r) for r in grid])

def interpreter(code, iterations, width, height):
    inter = Inter(code, width, height)
    inter.run(iterations)
    return '\r\n'.join(''.join(map(str, e)) for e in inter.grid)
    
class Inter:
    _instruct = { 'w':'moveW', 'e':'moveE', 'n':'moveN', 's':'moveS', '*':'flip', '[':'jumpP', ']':'jumpB'} 
    _nonC = lambda x:None
    def __init__(self, code, w, h):
        self.grid = [[0]*w for e in range(h)]
        self.com  = code
        self.w, self.h  = w, h
        self.x, self.y  = 0, 0
        self.i, self.it = 0, 0
        
    def countIteration(f):
        def wrap(cls):
            cls.it += 1
            return f(cls)
        return wrap
    
    def run(self, iterat):
        while self.it < iterat and self.i < len(self.com):#
            getattr(self, self._instruct.get(self.com[self.i],'_nonC'))()
            self.i += 1
        
    @countIteration
    def moveE(self):
        self.x = (self.x + 1)%self.w
    
    @countIteration
    def moveW(self):
        self.x = (self.x - 1)%self.w
        
    @countIteration
    def moveN(self):
        self.y = (self.y - 1)%self.h
        
    @countIteration
    def moveS(self):
        self.y = (self.y + 1)%self.h
    
    @countIteration
    def flip(self):
        self.grid[self.y][self.x] = int(not(self.grid[self.y][self.x]))
    
    @countIteration
    def jumpP(self):
        if self.grid[self.y][self.x] == 0:
            self._jump(1,  ']', '[')
    
    @countIteration
    def jumpB(self):
        if self.grid[self.y][self.x] == 1:
            self._jump(-1, '[', ']')
        
    def _jump(self, way, need, past, nest = 0):
        while way:
            self.i += way
            if self.com[self.i] == need and not nest: break
            if self.com[self.i] == need and nest: nest -= 1
            if self.com[self.i] == past: nest += 1

def pairs(code):
    opening = []
    matching = {}

    for i, c in enumerate(code):
        if c == "[":
            opening.append(i)
        elif c == "]":
            j = opening.pop()
            matching[i] = j
            matching[j] = i
    assert not opening
    return matching


def interpreter(code, iterations, width, height):
    matching = pairs(code)

    x = 0
    y = 0
    canvas = [[0 for _ in range(width)] for _ in range(height)]

    index = 0
    iterations_done = 0

    while iterations_done < iterations:
        try:
            c = code[index]
        except IndexError:
            break
        iterations_done += 1
        if c == "n":
            y -= 1
            y %= height
            index += 1
        elif c == "s":
            y += 1
            y %= height
            index += 1
        elif c == "w":
            x -= 1
            x %= width
            index += 1
        elif c == "e":
            x += 1
            x %= width
            index += 1
        elif c == "*":
            canvas[y][x] ^= 1
            index += 1
        elif c == "[":
            if canvas[y][x] == 0:
                index = matching[index]
            index += 1
        elif c == "]":
            if canvas[y][x] != 0:
                index = matching[index]
            index += 1
        else:
            iterations_done -= 1
            index += 1

    return "\r\n".join("".join(map(str, row)) for row in canvas)

def interpreter(code, iterations, width, height):
    inter = Inter(code, width, height)
    inter.run(iterations)
    return '\r\n'.join(''.join(e) for e in inter.grid)
    
class Inter:
    _instruct = { 'w':'moveW', 'e':'moveE', 'n':'moveN', 's':'moveS', '*':'flip', '[':'jumpP', ']':'jumpB'} 
    _nonC = lambda x:None
    def __init__(self, code, w, h):
        self.com = code
        self.grid = [['0']*w for e in range(h)]
        self.x, self.y  = 0, 0
        self.w, self.h  = w, h
        self.i, self.it = 0, 0
        
    def countIteration(f):
        def wrap(cls):
            cls.it += 1
            return f(cls)
        return wrap
    
    def run(self, iterat):
        while self.it < iterat and self.i < len(self.com):#
            getattr(self, self._instruct.get(self.com[self.i],'_nonC'))()
            self.i += 1
        
    @countIteration
    def moveE(self):
        self.x = (self.x + 1)%self.w
    
    @countIteration
    def moveW(self):
        self.x = (self.x - 1)%self.w
        
    @countIteration
    def moveN(self):
        self.y = (self.y - 1)%self.h
        
    @countIteration
    def moveS(self):
        self.y = (self.y + 1)%self.h
    
    @countIteration
    def flip(self):
        self.grid[self.y][self.x] = '10'[int(self.grid[self.y][self.x])]
    
    @countIteration
    def jumpP(self):
        if self.grid[self.y][self.x] == '0':
            self._jump(1,  ']', '[')
    
    @countIteration
    def jumpB(self):
        if self.grid[self.y][self.x] == '1':
            self._jump(-1, '[', ']')
        
    def _jump(self, way, need, past, nest = 0):
        while way:
            self.i += way
            if self.com[self.i] == need and not nest: break
            if self.com[self.i] == need and nest: nest -= 1
            if self.com[self.i] == past: nest += 1


def build_jump_table(code):
    jumps = {}
    stack = []
    for i, c in enumerate(code):
        if c == '[':
            stack.append(i)
        elif c == ']':
            j = stack.pop()
            jumps[i] = j
            jumps[j] = i
    return jumps

class Interpreter:
    def __init__(self, code, width, height):
        self.code = code
        self.jumps = build_jump_table(code)
        self.cells = [[0] * width for _ in range(height)]
        self.width = width
        self.height = height
        self.r = 0
        self.c = 0
        
    @property
    def value(self):
        return self.cells[self.r][self.c]

    @value.setter
    def value(self, val):
        self.cells[self.r][self.c] = val
        
    def run(self, iterations):
        pc = 0
        while pc < len(self.code) and iterations > 0:
            op = self.code[pc]
            if op == '*': self.value = 1 - self.value
            elif op == 'n': self.r = (self.r - 1) % self.height
            elif op == 's': self.r = (self.r + 1) % self.height
            elif op == 'w': self.c = (self.c - 1) % self.width
            elif op == 'e': self.c = (self.c + 1) % self.width
            elif op == '[' and self.value == 0: pc = self.jumps[pc]
            elif op == ']' and self.value == 1: pc = self.jumps[pc]
            pc += 1
            iterations -= op in '*nswe[]'
        return '\r\n'.join(''.join(map(str, row)) for row in self.cells)
    
def interpreter(code, iterations, width, height):
    ip = Interpreter(code, width, height)
    return ip.run(iterations)

class Memory:
    def __init__(self, width, height):
        self.__x = 0
        self.__y = 0
        self.width = width
        self.height = height
        self.mem = [[0] * width for _ in range(height)]

    def flip(self):
        self.mem[self.y][self.x] = (self.get() + 1) % 2

    def get(self):
        return self.mem[self.y][self.x]

    def to_string(self):
        return '\r\n'.join(''.join(map(str, row)) for row in self.mem)

    @property
    def x(self):
        return self.__x

    @x.setter
    def x(self, val):
        self.__x = val % self.width

    @property
    def y(self):
        return self.__y

    @y.setter
    def y(self, val):
        self.__y = val % self.height


def interpreter(code, iterations, width, height):
    op_ptr = 0
    mem = Memory(width, height)
    jumps = {}
    bracket = []

    for i, op in enumerate(code):
        if op == '[':
            bracket.append(i)
        elif op == ']':
            jumps[bracket[-1]] = i
            jumps[i] = bracket.pop()

    while iterations and op_ptr < len(code):
        op = code[op_ptr]
        if op in 'nesw*[]':
            iterations -= 1

        if op == 'n':
            mem.y -= 1
        elif op == 'e':
            mem.x += 1
        elif op == 's':
            mem.y += 1
        elif op == 'w':
            mem.x -= 1
        elif op == '*':
            mem.flip()
        elif op == '[' and mem.get() == 0:
            op_ptr = jumps[op_ptr]
        elif op == ']' and mem.get() != 0:
            op_ptr = jumps[op_ptr]

        op_ptr += 1

    return mem.to_string()

def interpreter(code, iterations, width, height):
    grid = [[0 for r in range(width)] for c in range(height)]
    t = iterations
    w, h = width, height
    stack, bracket_pos = [], {}
    for i, c in enumerate(code):
        if c == "[": 
            stack.append(i)
        elif c == "]": 
            bracket_pos[i] = stack[-1]
            bracket_pos[stack.pop()] = i

    a, b, p = 0, 0, 0    
    while t > 0 and p < len(code):
        if code[p] == "e": b += 1
        elif code[p] == "w": b -= 1
        elif code[p] == "s": a += 1
        elif code[p] == "n": a -= 1
        elif code[p] == "*": grid[a%h][b%w] ^= 1
        
        elif code[p] == "[":
            if grid[a%h][b%w] == 0:
                p = bracket_pos[p]
        elif code[p] == "]":
            if grid[a%h][b%w] == 1: 
                p = bracket_pos[p]
        else: t += 1
        t -= 1
        p += 1
    return "\r\n".join("".join(map(str, g)) for g in grid)

def interpreter(code, iterations, width, height):
    matrix = [[0 for i in range(width)] for i in range(height)]
    i = 0 # code position
    iteration = 0
    p = [0, 0] # data pointer
    s = [] # stack (used for loops)
    mate = {} # Paired [ / ] (used for loops)

    for k in range(len(code)):
        c = code[k]
        if c == '[':
            s.append(k)
        if c == ']':
            m = s.pop()
            mate[m] = k
            mate[k] = m

    while iteration < iterations and i < len(code):
        c = code[i]
        if c == '*':
            matrix[p[1]][p[0]] ^= 1
        elif c == 'n':
            p[1] = (p[1] - 1) % height
        elif c == 'e':
            p[0] = (p[0] + 1) % width
        elif c == 's':
            p[1] = (p[1] + 1) % height
        elif c == 'w':
            p[0] = (p[0] - 1) % width
        elif c == '[':
            if not matrix[p[1]][p[0]]:
                i = mate[i]
        elif c == ']':
            if matrix[p[1]][p[0]]:
                i = mate[i]
        else:
            iteration -= 1 # Ignore iteration on unknown command
        i += 1
        iteration += 1

    return '\r\n'.join([''.join([str(matrix[y][x]) for x in range(width)]) for y in range(height)])