# RoboScript #2 - Implement the RS1 Specification

## Disclaimer

The story presented in this Kata Series is purely fictional; any resemblance to actual programming languages, products, organisations or people should be treated as purely coincidental.

## About this Kata Series

This Kata Series is based on a fictional story about a computer scientist and engineer who owns a firm that sells a toy robot called MyRobot which can interpret its own (esoteric) programming language called RoboScript.  Naturally, this Kata Series deals with the software side of things (I'm afraid Codewars cannot test your ability to build a physical robot!).

## Story

Now that you've built your own code editor for RoboScript with appropriate syntax highlighting to make it look like serious code, it's time to properly implement RoboScript so that our MyRobots can execute any RoboScript provided and move according to the will of our customers.  Since this is the first version of RoboScript, let's call our specification RS1 (like how the newest specification for JavaScript is called ES6 :p)

## Task

Write an interpreter for RS1 called `execute()` which accepts 1 required argument `code`, the RS1 program to be executed.  The interpreter should return a string representation of the smallest 2D grid containing the full path that the MyRobot has walked on (explained in more detail later).

Initially, the robot starts at the middle of a 1x1 grid.  Everywhere the robot walks it will leave a path `"*"`.  If the robot has not been at a particular point on the grid then that point will be represented by a whitespace character `" "`.  So if the RS1 program passed in to `execute()` is empty, then:

```
""  -->  "*"
```

The robot understands 3 major commands:

- `F` - Move forward by 1 step in the direction that it is currently pointing.  Initially, the robot faces to the right.
- `L` - Turn "left" (i.e. **rotate** 90 degrees **anticlockwise**)
- `R` - Turn "right" (i.e. **rotate** 90 degrees **clockwise**)

As the robot moves forward, if there is not enough space in the grid, the grid should expand accordingly. So:

```
"FFFFF"  -->  "******"
```

As you will notice, 5 `F` commands in a row should cause your interpreter to return a string containing 6 `"*"`s in a row.  This is because initially, your robot is standing at the middle of the 1x1 grid facing right.  It leaves a mark on the spot it is standing on, hence the first `"*"`.  Upon the first command, the robot moves 1 unit to the right.  Since the 1x1 grid is not large enough, your interpreter should expand the grid 1 unit to the right.  The robot then leaves a mark on its newly arrived destination hence the second `"*"`.  As this process is repeated 4 more times, the grid expands 4 more units to the right and the robot keeps leaving a mark on its newly arrived destination so by the time the entire program is executed, 6 "squares" have been marked `"*"` from left to right.

Each row in your grid must be separated from the next by a CRLF (`\r\n`).  Let's look at another example:

```
"FFFFFLFFFFFLFFFFFLFFFFFL"  -->  "******\r\n*    *\r\n*    *\r\n*    *\r\n*    *\r\n******"
```

So the grid will look like this:
```
******
*    *
*    *
*    *
*    *
******
```

The robot moves 5 units to the right, then turns left, then moves 5 units upwards, then turns left again, then moves 5 units to the left, then turns left again and moves 5 units downwards, returning to the starting point before turning left one final time.  Note that the marks do **not** disappear no matter how many times the robot steps on them, e.g. the starting point is still marked `"*"` despite the robot having stepped on it twice (initially and on the last step).

Another example:

```
"LFFFFFRFFFRFFFRFFFFFFF"  -->  "    ****\r\n    *  *\r\n    *  *\r\n********\r\n    *   \r\n    *   "
```
So the grid will look like this:
```
    ****
    *  *
    *  *
********
    *
    *
```

Initially the robot turns left to face upwards, then moves upwards 5 squares, then turns right and moves 3 squares, then turns right again (to face downwards) and move 3 squares, then finally turns right again and moves 7 squares.

Since you've realised that it is probably quite inefficient to repeat certain commands over and over again by repeating the characters (especially the `F` command - what if you want to move forwards 20 steps?), you decide to allow a shorthand notation in the RS1 specification which allows your customers to postfix a non-negative integer onto a command to specify how many times an instruction is to be executed:

- `Fn` - Execute the `F` command `n` times (NOTE: `n` *may* be more than 1 digit long!)
- `Ln` - Execute `L` n times
- `Rn` - Execute `R` n times

So the example directly above can also be written as:

```
"LF5RF3RF3RF7"
```

These 5 example test cases have been included for you :)

## Kata in this Series

1. [RoboScript #1 - Implement Syntax Highlighting](https://www.codewars.com/kata/roboscript-number-1-implement-syntax-highlighting)
2. **RoboScript #2 - Implement the RS1 Specification**
3. [RoboScript #3 - Implement the RS2 Specification](https://www.codewars.com/kata/58738d518ec3b4bf95000192)
4. [RoboScript #4 - RS3 Patterns to the Rescue](https://www.codewars.com/kata/594b898169c1d644f900002e)
5. [RoboScript #5 - The Final Obstacle (Implement RSU)](https://www.codewars.com/kata/5a12755832b8b956a9000133)

Source: codewars | Difficulty: EASY

Starter code: def execute(code):
	

Solutions:
from collections import deque
import re
TOKENIZER = re.compile('(R+|F+|L+)(\\d*)')

def execute(code):
	(pos, dirs) = ((0, 0), deque([(0, 1), (1, 0), (0, -1), (-1, 0)]))
	seens = {pos}
	for (act, n) in TOKENIZER.findall(code):
		(s, r) = (act[0], int(n or '1') + len(act) - 1)
		if s == 'F':
			for _ in range(r):
				pos = tuple((z + dz for (z, dz) in zip(pos, dirs[0])))
				seens.add(pos)
		else:
			dirs.rotate(r % 4 * (-1) ** (s == 'R'))
	(miX, maX) = (min((x for (x, y) in seens)), max((x for (x, y) in seens)))
	(miY, maY) = (min((y for (x, y) in seens)), max((y for (x, y) in seens)))
	return '\r\n'.join((''.join(('*' if (x, y) in seens else ' ' for y in range(miY, maY + 1))) for x in range(miX, maX + 1)))


import re
DIRS = [(1, 0), (0, 1), (-1, 0), (0, -1)] * 2

def execute(code):
	(grid, (dx, dy)) = ({(0, 0)}, DIRS[0])
	x = y = xm = ym = xM = yM = 0
	for (dir, n) in re.findall('([FLR])(\\d*)', code):
		for _ in range(int(n or '1')):
			if dir == 'L':
				(dx, dy) = DIRS[DIRS.index((dx, dy)) - 1]
			if dir == 'R':
				(dx, dy) = DIRS[DIRS.index((dx, dy)) + 1]
			if dir == 'F':
				x += dx
				y += dy
				grid.add((x, y))
				(xm, ym, xM, yM) = (min(xm, x), min(ym, y), max(xM, x), max(yM, y))
	return '\r\n'.join((''.join((' *'[(x, y) in grid] for x in range(xm, xM + 1))) for y in range(ym, yM + 1)))


import re

def execute(code):
	if code == '':
		return '*'
	turn_right = [[1, 0], [0, -1], [-1, 0], [0, 1]]
	turn_left = [[-1, 0], [0, -1], [1, 0], [0, 1]]
	path = re.findall('F\\d+|F|L\\d+|L|R\\d+|R', code)
	max_size = sum([1 if j == 'F' else int(j[1:]) for j in path if 'F' in j]) * 2
	table = [[' '] * (max_size + 1) for i in range(max_size + 1)]
	(x, y) = (max_size // 2, max_size // 2)
	table[x][y] = '*'
	(f1, f2) = (0, 1)
	for way in path:
		if 'R' in way:
			for i in range(1 if way == 'R' else int(way[1:])):
				cur_pos = [pos for (pos, coords) in enumerate(turn_right) if coords == [f1, f2]][0]
				(f1, f2) = turn_right[0] if cur_pos == 3 else turn_right[cur_pos + 1]
		if 'L' in way:
			for i in range(1 if way == 'L' else int(way[1:])):
				cur_pos = [pos for (pos, coords) in enumerate(turn_left) if coords == [f1, f2]][0]
				(f1, f2) = turn_left[0] if cur_pos == 3 else turn_left[cur_pos + 1]
		if 'F' in way:
			for i in range(1 if way == 'F' else int(way[1:])):
				x += 1 * f1
				y += 1 * f2
				table[x][y] = '*'
	solution = [i for i in table if '*' in i]
	solution = [i for i in zip(*solution[:]) if '*' in i]
	for i in range(3):
		solution = list(zip(*solution[:]))
	final_way = [''.join([j for j in i]) for i in solution]
	return '\r\n'.join(final_way)


import re
from enum import Enum
from operator import itemgetter
from typing import List, Tuple, Set, Generator
Cell = Tuple[int, int]

class Direction(Enum):
	UP = (0, 1)
	DOWN = (0, -1)
	RIGHT = (1, 0)
	LEFT = (-1, 0)

def execute(code: str) -> str:
	visited_cells = visit_cells(code)
	path = draw_path(visited_cells)
	return path

def visit_cells(code: str) -> Set[Cell]:
	visited_cells = [(0, 0)]
	direction = Direction.RIGHT
	for (action, n_times) in code_interpreter(code):
		if action == 'F':
			new_cells = move_forward(visited_cells[-1], direction, n_times)
			visited_cells.extend(new_cells)
		else:
			direction = make_turn(direction, action, n_times)
	return set(visited_cells)

def code_interpreter(code: str) -> Generator[Tuple[str, int], None, None]:
	for move in re.finditer('([LRF])(\\d*)', code):
		action = move.group(1)
		times = int(move.group(2)) if move.group(2) else 1
		yield (action, times)

def move_forward(position: Cell, direction: Direction, n_moves: int) -> List[Cell]:
	(px, py) = position
	(dx, dy) = direction.value
	return [(px + i * dx, py + i * dy) for i in range(1, n_moves + 1)]

def make_turn(start: Direction, side: str, n_turns: int) -> Direction:
	ordering = [Direction.RIGHT, Direction.DOWN, Direction.LEFT, Direction.UP]
	step = 1 if side == 'R' else -1
	return ordering[(ordering.index(start) + step * n_turns) % len(ordering)]

def draw_path(visited_cells: Set[Cell]) -> str:
	(max_x, min_x, max_y, min_y) = find_cells_boundaries(visited_cells)
	rectangle = list()
	for y in range(max_y, min_y - 1, -1):
		row = ['*' if (x, y) in visited_cells else ' ' for x in range(min_x, max_x + 1)]
		rectangle.append(''.join(row))
	return '\r\n'.join(rectangle)

def find_cells_boundaries(visited_cells: Set[Cell]) -> Tuple[int, int, int, int]:
	(max_x, _) = max(visited_cells, key=itemgetter(0))
	(min_x, _) = min(visited_cells, key=itemgetter(0))
	(_, max_y) = max(visited_cells, key=itemgetter(1))
	(_, min_y) = min(visited_cells, key=itemgetter(1))
	return (max_x, min_x, max_y, min_y)


import re
left = {'right': 'up', 'up': 'left', 'left': 'down', 'down': 'right'}
right = {'right': 'down', 'down': 'left', 'left': 'up', 'up': 'right'}

def execute(s):
	(s, direction) = (re.sub('([RFL])(\\d+)', lambda x: x.group(1) * int(x.group(2)), s), 'right')
	(p, p1, li) = (0, 0, [[0, 0]])
	for i in s:
		if i == 'L':
			direction = left[direction]
		if i == 'R':
			direction = right[direction]
		if i == 'F':
			p1 += (1 if direction == 'right' else -1) if direction in ['left', 'right'] else 0
			p += (1 if direction == 'down' else -1) if direction in ['up', 'down'] else 0
			li.append([p, p1])
	(m, n) = (abs(min(li, key=lambda x: x[0])[0]) + max(li, key=lambda x: x[0])[0], abs(min(li, key=lambda x: x[1])[1]) + max(li, key=lambda x: x[1])[1])
	(p, p1, grid) = (abs(min(li, key=lambda x: x[0])[0]), abs(min(li, key=lambda x: x[1])[1]), [[' ' for _ in range(n + 1)] for _ in range(m + 1)])
	for (i, j) in li:
		grid[p + i][p1 + j] = '*'
	return '\r\n'.join([''.join(i) for i in grid])


import numpy as np

def switch(argument):
	switcher = {'F': 0, 'L': -1, 'R': 1}
	return switcher.get(argument, '')

def resize(p_matrix, num, axis, dir):
	if axis == 1:
		right = np.zeros((p_matrix.shape[0], num))
		left = p_matrix
		if dir == 2:
			(right, left) = (left, right)
		re_matrix = np.append(left, right, axis)
	else:
		top = np.zeros((num, p_matrix.shape[1]))
		bot = p_matrix
		if dir == 1:
			(top, bot) = (bot, top)
		re_matrix = np.append(top, bot, axis)
	return re_matrix

def mk_matrix(trace):
	p_matrix = np.full((1, 1), 1)
	pos = [0, 0]
	for i in range(len(trace)):
		dir = trace[i][0]
		step = trace[i][1]
		if step != 0:
			if dir == 0:
				if pos[1] + step + 1 > p_matrix.shape[1]:
					p_matrix = resize(p_matrix, pos[1] + step - p_matrix.shape[1] + 1, 1, dir)
				p_matrix[pos[0], pos[1] + 1:pos[1] + step + 1] = 1
				pos[1] = pos[1] + step
			elif dir == 1:
				if pos[0] + step + 1 > p_matrix.shape[0]:
					p_matrix = resize(p_matrix, pos[0] + step - p_matrix.shape[0] + 1, 0, dir)
				p_matrix[pos[0] + 1:pos[0] + 1 + step, pos[1]] = 1
				pos[0] = pos[0] + step
			elif dir == 2:
				if pos[1] - step < 0:
					p_matrix = resize(p_matrix, step - pos[1], 1, dir)
					pos[1] = step
				p_matrix[pos[0], pos[1] - step:pos[1]] = 1
				pos[1] = pos[1] - step
			else:
				if pos[0] - step < 0:
					p_matrix = resize(p_matrix, step - pos[0], 0, dir)
					pos[0] = step
				p_matrix[pos[0] - step:pos[0], pos[1]] = 1
				pos[0] = pos[0] - step
	return p_matrix

def tracing(path):
	dir = 0
	trace = []
	for j in range(len(path)):
		step = 0
		if path[j][0] == 0:
			if len(path[j]) == 2:
				step = path[j][1]
			else:
				step = 1
		elif len(path[j]) == 2:
			dir = (path[j][0] * path[j][1] + dir) % 4
		else:
			dir = (dir + path[j][0]) % 4
		trace.append([dir, step])
	return trace

def pathing(code):
	path = []
	way = -1
	num = -1
	for i in range(len(code)):
		if i < num:
			continue
		qnt = ''
		num = i
		if code[i].isdecimal():
			if num < len(code):
				while code[num].isdecimal():
					qnt += code[num]
					if num + 1 >= len(code):
						break
					num += 1
				if len(path[way]) < 2:
					length = int(qnt, 10)
					path[way].append(length)
		else:
			way += 1
			path.append([])
			path[way].append(switch(code[i]))
	return path

def str_mx(matrix):
	str = []
	subm = np.full(matrix.shape, ' ')
	for i in range(matrix.shape[0]):
		for j in range(matrix.shape[1]):
			if matrix[i][j]:
				subm[i][j] = '*'
		if i > 0:
			str.append('\r\n')
		str.append(''.join(subm[i]))
	return ''.join(str)

def execute(code):
	path = pathing(code)
	trace = tracing(path)
	matrix = mk_matrix(trace)
	print(matrix)
	str = str_mx(matrix)
	return str


def execute(codes):
	Nums = '0123456789'
	code = ''
	t = 0
	c = 0
	while t < len(codes):
		Char = 0
		c = 1
		if t < len(codes) - 1:
			for g in codes[t + 1:]:
				if g in Nums:
					Char += 1
				else:
					break
				c = int(codes[t + 1:t + Char + 1])
		code += codes[t] * c
		t += 1 + Char
	Xs = 0
	Ys = 0
	X = []
	Y = []
	Ymin = 0
	Step = [[0, 0]]
	Rotation = 0
	Arr = []
	Out = ''
	for i in range(len(code)):
		if code[i] == 'L':
			Rotation += 90
		elif code[i] == 'R':
			Rotation += -90
		if Rotation > 180:
			while Rotation > 180:
				Rotation += -360
		elif Rotation < -180:
			while Rotation < -180:
				Rotation += 360
		if code[i] == 'F':
			if Rotation == 0:
				Xs += 1
			elif Rotation == -180 or Rotation == 180:
				Xs += -1
			elif Rotation == 90:
				Ys += 1
			elif Rotation == -90:
				Ys += -1
			Step.append([Xs, Ys])
	for u in Step:
		X.append(u[0])
		Y.append(u[1])
	for j in range(len(Step)):
		Step[j][0] = Step[j][0] + min(X) * -1
		Step[j][1] = Step[j][1] + min(Y) * -1
	for k in range(max(Y) - min(Y) + 1):
		Arr.append([' '] * (max(X) - min(X) + 1))
	for l in Step:
		Arr[max(Y) - min(Y) - l[1]][l[0]] = '*'
	for n in range(len(Arr)):
		for p in range(max(X) - min(X) + 1):
			Out += Arr[n][p]
		Out += '\r\n'
	Out = Out[:-2]
	return Out


def execute(code):
	(R, r, c, dr, dc) = ({(0, 0)}, 0, 0, 0, 1)
	D = {(1, 0): {'R': (0, -1), 'L': (0, 1)}, (-1, 0): {'R': (0, 1), 'L': (0, -1)}, (0, 1): {'R': (1, 0), 'L': (-1, 0)}, (0, -1): {'R': (-1, 0), 'L': (1, 0)}}
	for cmd in code.replace('R', ' R').replace('L', ' L').replace('F', ' F').strip().split():
		(cmd, n) = (cmd[:1], int(cmd[1:]) if cmd[1:] else 1)
		for _ in range(n):
			if cmd in 'RL':
				(dr, dc) = D[dr, dc][cmd]
			else:
				(r, c) = (r + dr, c + dc)
				R.add((r, c))
	mnr = min((r for (r, _) in R))
	mnc = min((c for (_, c) in R))
	R = {(r - mnr, c - mnc) for (r, c) in R}
	mxr = max((r for (r, _) in R))
	mxc = max((c for (_, c) in R))
	return '\r\n'.join((''.join((' *'[(r, c) in R] for c in range(mxc + 1))) for r in range(mxr + 1)))


import re

def update_grid(px, py, grid):
	height = len(grid)
	width = len(grid[0])
	if px < 0:
		px += 1
		for y in range(height):
			grid[y] = ' ' + grid[y]
	if px >= width:
		for y in range(height):
			grid[y] = grid[y] + ' '
	if py < 0:
		py += 1
		grid.insert(0, ' ' * width)
	if py >= height:
		grid.append(' ' * width)
	grid[py] = grid[py][:px] + '*' + grid[py][px + 1:]
	return (px, py, grid)

def execute(code):
	grid = ['*']
	(x, y) = (0, 0)
	facing = (1, 0)
	while code:
		match = re.match('([FLR])(\\d*)', code)
		code = re.sub('^([FLR])(\\d*)', '', code)
		op = match[1]
		rep = int(match[2] or '1')
		for i in range(rep):
			if op == 'F':
				x += facing[0]
				y += facing[1]
				(x, y, grid) = update_grid(x, y, grid)
			if op == 'L':
				facing = (facing[1], -facing[0])
			if op == 'R':
				facing = (-facing[1], facing[0])
	return '\r\n'.join(grid)


BLANK = ' '
FILLCHAR = '*'

def pad_mtx(M, side='e'):
	if side == 'w':
		for i in range(len(M)):
			M[i] = [BLANK] + M[i][::1]
	elif side == 'e':
		for i in range(len(M)):
			M[i] += [BLANK]
	elif side == 'n':
		M.insert(0, [BLANK for _ in range(len(M[0]))])
	elif side == 's':
		M.append([BLANK for _ in range(len(M[0]))])

def move(mtx, pos, drxn):
	if drxn == 'e':
		pos[1] += 1
	elif drxn == 'w':
		pos[1] -= 1
	elif drxn == 's':
		pos[0] += 1
	elif drxn == 'n':
		pos[0] -= 1
	else:
		raise ValueError('Direction unrecognized.')
	try:
		if any((x < 0 for x in pos)):
			raise ValueError
		else:
			mtx[pos[0]][pos[1]] = FILLCHAR
	except Exception:
		pad_mtx(mtx, side=drxn)
		if drxn == 'n':
			pos[0] += 1
		if drxn == 'w':
			pos[1] += 1
		mtx[pos[0]][pos[1]] = FILLCHAR

def rotate(current, turn):
	directions = ['e', 's', 'w', 'n']
	turns = {'L': -1, 'R': 1}
	idx = directions.index(current)
	return directions[(idx + turns[turn]) % len(directions)]

def execute(code):
	directions = ['e', 's', 'w', 'n']
	path = [[FILLCHAR]]
	pos = [0, 0]
	drxn = 'e'
	i = 0
	while i < len(code):
		num = ''
		if i != len(code) - 1 and code[i + 1].isdigit():
			j = i + 1
			while j < len(code) and code[j].isdigit():
				num += code[j]
				j += 1
			for _ in range(int(num)):
				if code[i] in 'LR':
					drxn = rotate(drxn, code[i])
				elif code[i] == 'F':
					move(path, pos, drxn)
				else:
					break
		elif code[i] == 'F':
			move(path, pos, drxn)
		elif code[i] in 'LR':
			drxn = rotate(drxn, code[i])
		i += 1
	return '\r\n'.join((''.join(row) for row in path))