Skip to content

Latest commit

 

History

History
99 lines (91 loc) · 5.95 KB

64-'magic'-recursion-call-depth-number.md

File metadata and controls

99 lines (91 loc) · 5.95 KB
Raw

Problem:

'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:

pn<CODE_HERE>q

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

  • <CODE_HERE> 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

Solution