# '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
```

Difficulty: interview

Starter code:

def magic_call_depth_number(pattern):
	

Solutions:
from collections import defaultdict
from itertools import chain
import re

PARSE = re.compile(r'[pP]\d+|q')

def magic_call_depth_number(prog):
    
    def parse(it, p=''):
        for m in it:
            if m[0].startswith('p'): parse(it, m[0])
            elif m[0]=='q':          return
            else:                    pCmds[p].append(m[0].lower())
    
    def travel(p, seen, d=1):
        if not pCmds[p]:
            yield 0
        else:
            for n in pCmds[p]:
                if n in seen: yield d
                else:         yield from travel(n, seen|{n}, d+1)
    
    pCmds = defaultdict(list)
    parse(PARSE.finditer(prog))
    inf = list(chain.from_iterable(travel(p, {p}) for p in pCmds['']))
    
    return [min(inf, default=0), max(inf, default=0)]


import re
from collections import defaultdict, deque
def magic_call_depth_number(s):
    adjacent = defaultdict(list)
    for i, j, k in re.findall(r'(p\d+)(.+?)(q)', s):
        for n in re.findall(r'P\d+', j):
            adjacent[i.upper()].append(n)
    
    s, depths = re.sub(r'p.+?q', '', s), []
    
    def BFS(start):
        Q = deque([[start, 1, []]])
        while Q:
            node, depth, path = Q.popleft()
            path.append(node)
            if not adjacent[node] : depths.append(0)
            for i in adjacent[node]:
                if i not in path : Q.append([i, depth + 1, path[:]])
                else : depths.append(depth)
                
    [BFS(i) for i in re.findall(r'P\d+', s)]
    return [min(depths), max(depths)] if depths else [0,0]

import re
def functrion_L(Q):
     findall_elements = {F : re.findall('P(\d+)',V) for F,V in re.findall('p(\d+)([^q]+)',Q)}
     return findall_elements

def H(Q) :
  M = functrion_L(Q)
  R = [9E9,0]
  def H(V,S = set(),C = 0) :
    if V in S :
      R[:] = min(R[0],C),max(R[1],C)
      return 9
    S.add(V)
    T = 0
    for B in M[V] : T = H(B,S,-~C) or T
    R[0] = R[0] if T else 0
    S.remove(V)
    return R[0]
  for V in re.findall('P(\d+)',re.sub('p(\d+)([^q]+)','',Q)) : H(V)
  return [R[0] if R[0] < 9E9 else 0,R[1]]
magiCallDepthNumber = magic_call_depth_number = H

import re
def H(Q) :
    M,R = {F : re.findall('P(\d+)',V) for F,V in re.findall('p(\d+)([^q]+)',Q)},[9E9,0]
    def H(V,S = set(),C = 0) :
        if V in S :
            R[:] = min(R[0],C),max(R[1],C)
            return 9
        S.add(V)
        T = 0
        for B in M[V] : T = H(B,S,-~C) or T
        R[0] = R[0] if T else 0
        S.remove(V)
        return R[0]
    for V in re.findall('P(\d+)',re.sub('p(\d+)([^q]+)','',Q)) : H(V)
    return [R[0] if R[0] < 9E9 else 0,R[1]]
magiCallDepthNumber = magic_call_depth_number = H

from re import compile
build = compile(r"P(\d+)").findall
read = compile(r"p(\d+)(.*?)q").sub

def magic_call_depth_number(pattern):
    P = {}
    def filling(w):
        k, v = w.groups()
        P[k] = set(build(v))
        return ""
    
    def minimum(id1, S):
        if id1 in S: return (False, -1)
        if not P[id1]: return (True, 0)
        mini = float('inf')
        for id2 in P[id1]:
            b, x = minimum(id2, S|{id1})
            if b: return (True, 0)
            mini = min(mini, x+1)
        return (False, mini)
    
    def maximum(id1, S):
        if id1 in S: return (True, -1)
        if not P[id1]: return (False, 0)
        res, maxi = (False, 0)
        for id2 in P[id1]:
            b, x = maximum(id2, S|{id1})
            if b: res, maxi = res or b, max(maxi, x+1)
        return (res, maxi)
    
    P[None] = set(build(read(filling, pattern)))
    return [minimum(None, set())[1], maximum(None, set())[1]]

def magic_call_depth_number(program):
    templates = dict()
    code = str()
    
    i = 0
    while i < len(program):
    
        if program[i] != 'p':
            code += program[i]
        else:
            i += 1
            n = str()
            while program[i].isdigit():
                n += program[i]
                i += 1
            
            template = str()
            while program[i] != 'q':
                template += program[i]
                i += 1
            
            templates[n] = template
        
        i += 1
    
    mymin = 999
    mymax = 0
    
    i = 0
    while i < len(code):
        while code[i] == 'F' or code[i] == 'L' or code[i] == 'R':
            i += 1
            while code[i].isdigit():
                i += 1
        
        i += 1
        n = str()
        while i < len(code) and code[i].isdigit():
            n += code[i]
            i += 1
        
        # обрарботать вызов Pn
        min_max = calc_min_max([n], n, templates, 0)
        mymin = min(mymin, min_max[0])
        mymax = max(mymax, min_max[1])
        
    if mymax == 0:
        mymin = 0
    
    return [mymin, mymax]

def calc_min_max(used, c, templates, depth):
    mymin = 999
    mymax = 0
    
    flag = 0
    i = 0
    while i < len(templates[c]):
        while i < len(templates[c]) and (templates[c][i] == 'F' or templates[c][i] == 'L' or templates[c][i] == 'R'):
            i += 1
            while i < len(templates[c]) and (templates[c][i].isdigit()):
                i += 1
        
        if not (i < len(templates[c])):
            break
        
        i += 1
        n = str()
        while i < len(templates[c]) and templates[c][i].isdigit():
            n += templates[c][i]
            i += 1
        
        # в вызове Pc произошёл вызов Pn
        flag = 1
        if used.count(n):
            loop_with_depth = depth + 1
            mymin = min(mymin, loop_with_depth)
            mymax = max(mymax, loop_with_depth)
        else:
            used_copy = used.copy()
            used_copy.append(n)
            min_max = calc_min_max(used_copy, n, templates, depth + 1)
            mymin = min(mymin, min_max[0])
            mymax = max(mymax, min_max[1])
    
    return [mymin if flag else 0, mymax]


import re

class Pattern:
    def __init__(self, definition, patterns):
        self._name = re.findall("p([0-9]+)", definition)[0]
        self._calls = re.findall("P([0-9]+)", definition)
        patterns[self._name] = self
    
    def simulate(self, patterns, visited, depths, depth=0):
        if self._name in visited:
            depths.append(depth)
            return
            
        if len(self._calls) == 0:
            depths.append(0)
            return
            
        visited.add(self._name)
        for call in self._calls:
            patterns[call].simulate(patterns, visited, depths, depth+1)
        visited.remove(self._name)

def magic_call_depth_number(pattern):
    patterns = {}
    while True:
        match = re.search("p[0-9]+[^q]*q", pattern)
        if match == None:
            break
        (start, end) = match.span()
        pattern = pattern[0:start] + pattern[end:]
        Pattern(match.group(0), patterns)
        
    depths = []
    for e in re.findall("P([0-9]+)", pattern):
        visited = set()
        patterns[e].simulate(patterns, visited, depths)
    
    if len(depths) == 0:
        return [0, 0]
    else:
        return [min(depths), max(depths)]

import re

def magic_call_depth_number(pattern):
    subroutines = {} # list them by number
    s = re.compile(r'p(\d+)((P\d+|[FLR]*\d*)+)q')
    subrout = s.search(pattern)
    while subrout:
        # put the subroutine in the dictionary
        subroutines["P" + subrout.group(1)] = tokens(subrout.group(2))
        # extract this subroutine from the pattern and see if there are more
        pattern = pattern.replace(subrout.group(0), "")
        subrout = s.search(pattern)
    # Make a tree
    depths = walk_tree(tokens(pattern), [], subroutines)
    return [min(depths), max(depths)]
    
def tokens(pattern):
    return re.findall(r'([PFLR]\d*)', pattern)
    
def walk_tree(token_list, stack, subroutine_dict):
    depths = []
    stops_here = True
    for t in token_list:
        if t.startswith("P"):
            stops_here = False
            if t in stack:
                depths.append(len(stack))
            else:
                depths.extend(walk_tree(subroutine_dict[t], stack + [t], subroutine_dict))
    if stops_here:
        depths.append(0)
    return depths

UPPER_BOUND = 1000000000

def test_call (current_function: str, functions: dict, stack: set):
    min_n = UPPER_BOUND
    max_n = 0

    stack.add(current_function)
    #print("    " * len(stack), current_function, ' ', functions,
    #        current_function in stack, sep='')
    for next_funcion in functions[current_function]:
        if next_funcion in stack:
            min_n = min(min_n, 1)
            max_n = max(max_n, 1)

        else:
            current_min, current_max = \
                    test_call(next_funcion, functions, stack)
            current_min += 1
            current_max += 1
            if current_min < min_n:
                min_n = current_min
            if current_min == 1:
                min_n = 0
            if current_max != 1 and current_max > max_n:
                max_n = current_max
    stack.remove(current_function)
    if min_n == UPPER_BOUND:
        min_n = 0
    if max_n < min_n:
        max_n = min_n
    return (min_n, max_n)

def read_function(s: str):
    """
    return:
        (function_#, [functions called])
    """
    i = 0;
    while (s[i] in "0123456789"):
        i += 1

    function_no = int(s[0:i])
    function_calls = []

    #print("Reading", function_no)

    while 1:
        i = s.find('P', i)
        if i < 0:
            break;
        nums = i + 1
        i += 1
        while i < len(s) and s[i] in "0123456789":
            i += 1
        nume = i
        #print("    call from", nums, "to", nume)
        function_call = int(s[nums:nume])
        function_calls.append(function_call)

    return (function_no, function_calls)

def parse_program (program_s: str):
    i = 0;
    functions = {}

    while 1:
        i = program_s.find('p', i)
        if i < 0:
            break
        funs = i + 1
        i = program_s.find('q', i)
        fune = i
        func_no, fun_calls = read_function(program_s[funs:fune])
        functions[func_no] = fun_calls


    #print("Finish parsing")
    i = 0;
    min_n, max_n = UPPER_BOUND, 0

    while 1:
        next_sof = program_s.find('p', i)
        next_eof = program_s.find('q', i)
        if (next_sof < 0):
            next_sof = len(program_s)

        #print("WTF", next_sof, next_eof)

        while 1:
            i = program_s.find('P', i)
            if i < 0 or i >= next_sof:
                break;
            nums = i + 1
            i += 1
            while i < len(program_s) and program_s[i] in "0123456789":
                i += 1
            nume = i
            #print("Calling", nums, nume)
            function_call = int(program_s[nums:nume])
            c_min_n, c_max_n = test_call(function_call, functions, set())
            if c_min_n < min_n:
                min_n = c_min_n
            if c_max_n > max_n:
                max_n = c_max_n

        if i < 0 or next_eof < 0:
            break
        i = next_eof + 1


    if min_n == UPPER_BOUND:
        min_n = 0
        max_n = 0

    return [min_n, max_n]


def magic_call_depth_number(pattern):
    return parse_program(pattern)