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

Source: codewars | Difficulty: MEDIUM_HARD
Tags: Complete search

Starter code: def magic_call_depth_number(pattern):
	

Solutions:
from collections import defaultdict
from itertools import chain
import re
PARSE = re.compile('[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('(p\\d+)(.+?)(q)', s):
		for n in re.findall('P\\d+', j):
			adjacent[i.upper()].append(n)
	(s, depths) = (re.sub('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('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 = [9000000000.0, 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] < 9000000000.0 else 0, R[1]]
magiCallDepthNumber = magic_call_depth_number = H


from re import compile
build = compile('P(\\d+)').findall
read = compile('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
		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
		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 = {}
	s = re.compile('p(\\d+)((P\\d+|[FLR]*\\d*)+)q')
	subrout = s.search(pattern)
	while subrout:
		subroutines['P' + subrout.group(1)] = tokens(subrout.group(2))
		pattern = pattern.replace(subrout.group(0), '')
		subrout = s.search(pattern)
	depths = walk_tree(tokens(pattern), [], subroutines)
	return [min(depths), max(depths)]

def tokens(pattern):
	return re.findall('([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)
	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):
	i = 0
	while s[i] in '0123456789':
		i += 1
	function_no = int(s[0:i])
	function_calls = []
	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
		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
	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)
		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
			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)