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

```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 = "import re\nfrom enum import Enum\nfrom operator import itemgetter\nfrom typing import List, Tuple, Set, Generator\n\n\nCell = Tuple[int, int]\n\n\nclass Direction(Enum):\n    UP = (0, 1)\n    DOWN = (0, -1)\n    RIGHT = (1, 0)\n    LEFT = (-1, 0)\n\n\ndef execute(code: str) -> str:\n    visited_cells = visit_cells(code)\n    path = draw_path(visited_cells)\n    return path\n    \n    \ndef visit_cells(code: str) -> Set[Cell]:\n    visited_cells = [(0, 0)]\n    direction = Direction.RIGHT\n    \n    for action, n_times in code_interpreter(code):\n        if action == 'F':\n            new_cells = move_forward(visited_cells[-1], direction, n_times)\n            visited_cells.extend(new_cells)\n        else:\n            direction = make_turn(direction, action, n_times)\n    return set(visited_cells)\n\n\ndef code_interpreter(code: str) -> Generator[Tuple[str, int], None, None]:\n    for move in re.finditer(r'([LRF])(\\d*)', code):\n        action = move.group(1)\n        times = int(move.group(2)) if move.group(2) else 1\n        yield action, times\n    \n\ndef move_forward(position: Cell, direction: Direction, n_moves: int) -> List[Cell]:\n    px, py = position\n    dx, dy = direction.value\n    return [(px + i * dx, py + i * dy) for i in range(1, n_moves + 1)]\n\n\ndef make_turn(start: Direction, side: str, n_turns: int) -> Direction:\n    ordering = [Direction.RIGHT, Direction.DOWN, Direction.LEFT, Direction.UP]\n    step = 1 if side == 'R' else -1\n    return ordering[(ordering.index(start) + step * n_turns) % len(ordering)]\n    \n    \ndef draw_path(visited_cells: Set[Cell]) -> str:\n    max_x, min_x, max_y, min_y = find_cells_boundaries(visited_cells)\n    \n    rectangle = list()\n    for y in range(max_y, min_y - 1, -1):\n        row = ['*' if (x, y) in visited_cells else ' ' for x in range(min_x, max_x + 1)]\n        rectangle.append(''.join(row))\n    \n    return '\\r\\n'.join(rectangle)\n    \n    \ndef find_cells_boundaries(visited_cells: Set[Cell]) -> Tuple[int, int, int, int]:\n    max_x, _ = max(visited_cells, key=itemgetter(0))\n    min_x, _ = min(visited_cells, key=itemgetter(0))\n    \n    _, max_y = max(visited_cells, key=itemgetter(1))\n    _, min_y = min(visited_cells, key=itemgetter(1))\n    return max_x, min_x, max_y, min_y\n    \n    \n        \n"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

_target = None
_fn_name = 'execute'
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: 39861