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

Source: codewars | Difficulty: MEDIUM_HARD

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 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
	iteration = 0
	p = [0, 0]
	s = []
	mate = {}
	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
		i += 1
		iteration += 1
	return '\r\n'.join([''.join([str(matrix[y][x]) for x in range(width)]) for y in range(height)])