# 'Magic' recursion call depth number

This Kata was designed as a Fork to the one from donaldsebleung Roboscript series with a reference to:

https://www.codewars.com/collections/roboscript

It is not more than an extension of Roboscript infinite "single-" mutual recursion handling to a "multiple-" case.

One can suppose that you have a machine that works through a specific language. It uses the script, which consists of 3 major commands:

 - `F` - Move forward by 1 step in the direction that it is currently pointing.

 - `L` - Turn "left" (i.e. rotate 90 degrees anticlockwise).

 - `R` - Turn "right" (i.e. rotate 90 degrees clockwise).

The number n afterwards enforces the command to execute n times.

To improve its efficiency machine language is enriched by patterns that are containers to pack and unpack the script.

The basic syntax for defining a pattern is as follows:

`pnq`

Where:

 - `p` is a "keyword" that declares the beginning of a pattern definition 

 - `n` is a non-negative integer, which acts as a unique identifier for the pattern (pay attention, it may contain several digits).

 - `` is a valid RoboScript code (without the angled brackets)

 - `q` is a "keyword" that marks the end of a pattern definition 

For example, if you want to define `F2LF2` as a pattern and reuse it later:

```
p333F2LF2q
```

To invoke a pattern, a capital `P` followed by the pattern identifier `(n)` is used:

```
P333
```

It doesn't matter whether the invocation of the pattern or the pattern definition comes first. Pattern definitions should always be parsed first.

```
P333p333P11F2LF2qP333p11FR5Lq
```



# ___Infinite recursion___

As we don't want a robot to be damaged or damaging someone else by becoming uncontrolable when stuck in an infinite loop, it's good to considere this possibility in the programs and to build a compiler that can detect such potential troubles before they actually happen.

* ### Single pattern recursion infinite loop

This is the simplest case, that occurs when the pattern is invoked inside its definition:

    p333P333qP333 => depth = 1: P333 -> (P333)


* ### Single mutual recursion infinite loop

Occurs when a pattern calls to unpack the mutual one, which contains a callback to the first:

    p1P2qp2P1qP2  => depth = 2: P2 -> P1 -> (P2)


* ### Multiple mutual recursion infinite loop

Occurs within the combo set of mutual callbacks without termination: 

    p1P2qp2P3qp3P1qP3 => depth = 3: P3 -> P1 -> P2 -> (P3)

* ### No infinite recursion: terminating branch

This happens when the program can finish without encountering an infinite loop. Meaning the depth will be considered 0. Some examples below:

    P4p4FLRq      => depth = 0
    p1P2qp2R5qP1  => depth = 0
    p1P2qp2P1q    => depth = 0 (no call)





# Task


Your interpreter should be able to analyse infinite recursion profiles in the input program, including multi-mutual cases.

Though, rather than to analyse only the first encountered infinite loop and get stuck in it like the robot would be, your code will have continue deeper in the calls to find the depth of any infinite recursion or terminating call. Then it should return the minimal and the maximal depths encountered, as an array `[min, max]`.


### About the exploration of the different possible branches of the program:

* Consider only patterns that are to be executed:

```
p1P1q                 => should return [0, 0], there is no execution
p1P2P3qp2P1qp3P1q     => similarly [0, 0]
p1P1qP1               => returns [1, 1]
```

* All patterns need to be executed, strictly left to right. Meaning that you may encounter several branches:

```
p1P2P3qp2P1qp3P1qP3   => should return [2, 3]

P3 -> P1 -> P2 -> (P1)    depth = 3 (max)
        \-> (P3)          depth = 2 (min)
```



# Input

* A valid RoboScript program, as string.
* Nested definitions of patterns, such as `p1...p2***q...q` will not be tested, even if that could be of interest as a Roboscript improvement.
* All patterns will have a unique identifier.
* Since the program is valid, you won't encounter calls to undefined pattern either.


# Output

* An array `[min, max]`, giving what are the minimal and the maximal recursion depths encountered.

### Examples
```
p1F2RF2LqP1         =>  should return [0, 0], no infinite recursion detected

p1F2RP1F2LqP1       =>  should return [1, 1], infinite recursion detection case

P2p1P2qp2P1q        =>  should return [2, 2], single mutual infinite recursion case

p1P2qP3p2P3qp3P1q   =>  should return [3, 3], twice mutual infinite recursion case

p1P2P1qp2P3qp3P1qP1 =>  should return [1, 3], mixed infinite recursion case
```

```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 = 'UPPER_BOUND = 1000000000\n\ndef test_call (current_function: str, functions: dict, stack: set):\n    min_n = UPPER_BOUND\n    max_n = 0\n\n    stack.add(current_function)\n    #print("    " * len(stack), current_function, \' \', functions,\n    #        current_function in stack, sep=\'\')\n    for next_funcion in functions[current_function]:\n        if next_funcion in stack:\n            min_n = min(min_n, 1)\n            max_n = max(max_n, 1)\n\n        else:\n            current_min, current_max = \\\n                    test_call(next_funcion, functions, stack)\n            current_min += 1\n            current_max += 1\n            if current_min < min_n:\n                min_n = current_min\n            if current_min == 1:\n                min_n = 0\n            if current_max != 1 and current_max > max_n:\n                max_n = current_max\n    stack.remove(current_function)\n    if min_n == UPPER_BOUND:\n        min_n = 0\n    if max_n < min_n:\n        max_n = min_n\n    return (min_n, max_n)\n\ndef read_function(s: str):\n    """\n    return:\n        (function_#, [functions called])\n    """\n    i = 0;\n    while (s[i] in "0123456789"):\n        i += 1\n\n    function_no = int(s[0:i])\n    function_calls = []\n\n    #print("Reading", function_no)\n\n    while 1:\n        i = s.find(\'P\', i)\n        if i < 0:\n            break;\n        nums = i + 1\n        i += 1\n        while i < len(s) and s[i] in "0123456789":\n            i += 1\n        nume = i\n        #print("    call from", nums, "to", nume)\n        function_call = int(s[nums:nume])\n        function_calls.append(function_call)\n\n    return (function_no, function_calls)\n\ndef parse_program (program_s: str):\n    i = 0;\n    functions = {}\n\n    while 1:\n        i = program_s.find(\'p\', i)\n        if i < 0:\n            break\n        funs = i + 1\n        i = program_s.find(\'q\', i)\n        fune = i\n        func_no, fun_calls = read_function(program_s[funs:fune])\n        functions[func_no] = fun_calls\n\n\n    #print("Finish parsing")\n    i = 0;\n    min_n, max_n = UPPER_BOUND, 0\n\n    while 1:\n        next_sof = program_s.find(\'p\', i)\n        next_eof = program_s.find(\'q\', i)\n        if (next_sof < 0):\n            next_sof = len(program_s)\n\n        #print("WTF", next_sof, next_eof)\n\n        while 1:\n            i = program_s.find(\'P\', i)\n            if i < 0 or i >= next_sof:\n                break;\n            nums = i + 1\n            i += 1\n            while i < len(program_s) and program_s[i] in "0123456789":\n                i += 1\n            nume = i\n            #print("Calling", nums, nume)\n            function_call = int(program_s[nums:nume])\n            c_min_n, c_max_n = test_call(function_call, functions, set())\n            if c_min_n < min_n:\n                min_n = c_min_n\n            if c_max_n > max_n:\n                max_n = c_max_n\n\n        if i < 0 or next_eof < 0:\n            break\n        i = next_eof + 1\n\n\n    if min_n == UPPER_BOUND:\n        min_n = 0\n        max_n = 0\n\n    return [min_n, max_n]\n\n\ndef magic_call_depth_number(pattern):\n    return parse_program(pattern)\n\n\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

_target = None
_fn_name = 'magic_call_depth_number'
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: 7330