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

Difficulty: introductory

Starter code:

def execute(code):
	

Solutions:
from collections import deque
import re

TOKENIZER = re.compile(r'(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(r'([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(r'([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 #pointing right
    # 0-> direita ; 1-> baixo ; 2-> esquerda ; 3->cima
    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
        else:
            if 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(r'([FLR])(\d*)', code)
        code = re.sub(r'^([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"):
    """
    Pads matrix with row or column of blank chars depending on side keyword
    """
    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):
    # modify position
    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.")
    
    # Check if path matrix needs to be modified
    try:
        if any(x < 0 for x in pos):
            raise ValueError
        else:
            mtx[pos[0]][pos[1]] = FILLCHAR
    # Modify it if an error was raised
    except Exception:
        pad_mtx(mtx, side=drxn)
        # Update position to reflect modified matrix
        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):
        # check if command is repeated
        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)