Statistics

Problem Statement for "Loopy"

Problem Statement

We have a program segment and want to analyze the control flow through it. We have already replaced the actual code with simpler code that captures just the control logic. The code we want to analyze consists of a sequence of statements in which each statement is one of the following two types:
  • IF target1 ELSE target2
  • RETURN
Execution of an IF statement is followed by execution of one of its two targets. Each target is an integer referring to a zero-based position in the code sequence. The two targets may be identical. Execution of a RETURN statement ends the execution.

Execution of the program segment starts at the first statement (statement 0) and concludes when it reaches a RETURN statement. We call such a sequence an "execution path."

In order to optimize the code, we want to find the smallest loop in the program segment that can be executed. A loop is defined to be a set of statements such that

  1. Only one statement in the loop (the entry point) may be immediately preceded in an execution path by a statement that is not in the loop.
  2. If a loop contains statement 0, then statement 0 must be the entry point for that loop.
  3. If a statement S is in the loop, then there is an execution path that executes S and then, without executing any statement outside the loop, executes every statement (including S) in the loop at least once.
Create a class Loopy that contains a method minLoop that is given a String[] code containing the sequence of statements and that returns the smallest number of statements in code that form a loop. If code contains no loop, return 0.

Definition

Class:
Loopy
Method:
minLoop
Parameters:
String[]
Returns:
int
Method signature:
int minLoop(String[] code)
(be sure your method is public)

Constraints

  • code will contain between 1 and 50 elements inclusive.
  • Each element of code will be one of the two forms above.
  • Each RETURN statement has no spaces.
  • Each IF statement has exactly 3 spaces.
  • Each target1 and target2 will be an integer with no extraneous leading zeroes.
  • Each target1 and target2 will be between 0 and n-1 inclusive, where n is the number of elements in code.

Examples

  1. {"RETURN", "IF 0 ELSE 1"}

    Returns: 0

    Execution immediately returns, so there is no loop.

  2. {"IF 1 ELSE 2","IF 1 ELSE 2","RETURN"}

    Returns: 1

    Statement 1 forms a loop.

  3. {"IF 1 ELSE 2","RETURN", "IF 3 ELSE 2", "IF 2 ELSE 3"}

    Returns: 0

    No execution path that includes either statement 2 or 3 can ever reach a RETURN statement. The only legal execution path is statement 0 followed by statement 1 so there is no loop.

  4. {"IF 1 ELSE 2","IF 3 ELSE 3","IF 4 ELSE 1", "IF 4 ELSE 5","RETURN","IF 0 ELSE 6", "IF 6 ELSE 6","IF 7 ELSE 2"}

    Returns: 5

    Statements 0, 1, 2, 3, and 5 form a loop whose entry point is statement 0. Note that no execution path contains statement 7, so statement 2 is never preceded by a non-loop statement.

  5. {"IF 1 ELSE 2","IF 0 ELSE 2","RETURN"}

    Returns: 2

  6. {"IF 1 ELSE 2","IF 2 ELSE 8","IF 3 ELSE 3","RETURN","RETURN","RETURN", "RETURN","RETURN","IF 9 ELSE 10","IF 11 ELSE 11","IF 9 ELSE 11", "IF 14 ELSE 12","IF 13 ELSE 13","IF 1 ELSE 1","IF 0 ELSE 0"}

    Returns: 7

    1: 8 9 10 11 12 13

  7. {"IF 1 ELSE 2","IF 2 ELSE 8","IF 14 ELSE 3","RETURN","RETURN","RETURN", "IF 1 ELSE 1","RETURN","IF 9 ELSE 10","IF 11 ELSE 11","IF 9 ELSE 11", "IF 14 ELSE 12","IF 13 ELSE 13","IF 1 ELSE 1","IF 0 ELSE 0"}

    Returns: 7

  8. {"IF 1 ELSE 2","IF 2 ELSE 8","IF 12 ELSE 3","RETURN","RETURN","RETURN", "RETURN","RETURN","IF 9 ELSE 10","IF 11 ELSE 11","IF 9 ELSE 11", "IF 14 ELSE 12","IF 13 ELSE 13","IF 1 ELSE 1","IF 0 ELSE 0"}

    Returns: 10

    10 0:1 2 8 9 10 11 12 13 14

  9. {"IF 7 ELSE 6","IF 2 ELSE 2","IF 3 ELSE 6","RETURN","IF 5 ELSE 5", "IF 4 ELSE 3","IF 2 ELSE 1","IF 6 ELSE 8","IF 10 ELSE 10", "RETURN","IF 8 ELSE 8"}

    Returns: 3

    6: 1,2 (4,5 loop is dead no entry. 8,10 is dead no return)

  10. {"IF 7 ELSE 6","IF 2 ELSE 2","IF 3 ELSE 6","RETURN","IF 5 ELSE 5", "IF 4 ELSE 3","IF 2 ELSE 1","IF 6 ELSE 8","IF 10 ELSE 10", "RETURN","IF 1 ELSE 8"}

    Returns: 2

    8:10

  11. {"IF 7 ELSE 6","IF 10 ELSE 2","IF 3 ELSE 6","RETURN","IF 5 ELSE 5", "IF 4 ELSE 3","IF 2 ELSE 1","IF 6 ELSE 8","IF 10 ELSE 10", "RETURN","IF 1 ELSE 8"}

    Returns: 0

  12. {"IF 1 ELSE 2","IF 1 ELSE 1","IF 5 ELSE 3", "IF 2 ELSE 2","IF 5 ELSE 2","RETURN"}

    Returns: 2

    2:3

  13. {"IF 1 ELSE 2","IF 4 ELSE 1","IF 5 ELSE 3", "IF 2 ELSE 2","IF 5 ELSE 2","RETURN"}

    Returns: 1

    1:

  14. {"IF 1 ELSE 1","IF 2 ELSE 2","IF 3 ELSE 48","IF 4 ELSE 4","IF 5 ELSE 5", "IF 6 ELSE 6","IF 7 ELSE 7","IF 8 ELSE 8","IF 9 ELSE 9","IF 10 ELSE 10", "IF 11 ELSE 11","IF 12 ELSE 12","IF 13 ELSE 13","IF 14 ELSE 14", "IF 15 ELSE 15","IF 16 ELSE 16","IF 17 ELSE 17","IF 18 ELSE 18", "IF 19 ELSE 19","IF 20 ELSE 20","IF 21 ELSE 21","IF 22 ELSE 22", "IF 23 ELSE 23","IF 24 ELSE 24","IF 25 ELSE 25","IF 26 ELSE 26", "IF 27 ELSE 27","IF 28 ELSE 28","IF 29 ELSE 29","IF 30 ELSE 30", "IF 31 ELSE 31","IF 32 ELSE 32","IF 33 ELSE 33","IF 34 ELSE 34", "IF 35 ELSE 35","IF 36 ELSE 36","IF 37 ELSE 37","IF 38 ELSE 38", "IF 39 ELSE 39","IF 40 ELSE 49","IF 41 ELSE 41","IF 42 ELSE 42", "IF 43 ELSE 43","IF 44 ELSE 44","IF 45 ELSE 45","IF 46 ELSE 46", "IF 47 ELSE 47","IF 0 ELSE 0","IF 35 ELSE 35","RETURN"}

    Returns: 49

    0:allbut49

  15. {"IF 1 ELSE 1","IF 2 ELSE 2","IF 3 ELSE 48","IF 4 ELSE 4","IF 5 ELSE 5", "IF 6 ELSE 6","IF 7 ELSE 7","IF 8 ELSE 8","IF 9 ELSE 9","IF 10 ELSE 10", "IF 11 ELSE 11","IF 12 ELSE 12","IF 13 ELSE 13","IF 14 ELSE 14", "IF 15 ELSE 15","IF 16 ELSE 16","IF 17 ELSE 17","IF 18 ELSE 18", "IF 19 ELSE 19","IF 20 ELSE 20","IF 21 ELSE 21","IF 22 ELSE 22", "IF 23 ELSE 23","IF 24 ELSE 24","IF 25 ELSE 25","IF 26 ELSE 26", "IF 27 ELSE 27","IF 28 ELSE 28","IF 29 ELSE 29","IF 30 ELSE 30", "IF 31 ELSE 31","IF 32 ELSE 32","IF 33 ELSE 33","IF 34 ELSE 34", "IF 35 ELSE 35","IF 36 ELSE 36","IF 37 ELSE 37","IF 38 ELSE 38", "IF 39 ELSE 39","IF 40 ELSE 49","IF 41 ELSE 41","IF 42 ELSE 42", "IF 43 ELSE 43","IF 44 ELSE 44","IF 45 ELSE 45","IF 46 ELSE 46", "IF 47 ELSE 47","IF 1 ELSE 0","IF 35 ELSE 35","RETURN"}

    Returns: 48

    1: allbut 0,49

  16. {"IF 8 ELSE 6","IF 2 ELSE 2","IF 3 ELSE 48","IF 4 ELSE 4","IF 5 ELSE 5", "IF 6 ELSE 6","IF 7 ELSE 7","IF 8 ELSE 8","IF 9 ELSE 9","IF 10 ELSE 10", "IF 11 ELSE 11","IF 12 ELSE 12","IF 13 ELSE 13","IF 14 ELSE 14", "IF 15 ELSE 15","IF 16 ELSE 16","IF 17 ELSE 17","IF 18 ELSE 18", "IF 19 ELSE 19","IF 20 ELSE 20","IF 21 ELSE 21","IF 22 ELSE 22", "IF 23 ELSE 23","IF 24 ELSE 24","IF 25 ELSE 25","IF 26 ELSE 26", "IF 27 ELSE 27","IF 28 ELSE 28","IF 29 ELSE 29","IF 30 ELSE 30", "IF 31 ELSE 31","IF 32 ELSE 32","IF 33 ELSE 33","IF 34 ELSE 34", "IF 35 ELSE 35","IF 36 ELSE 36","IF 37 ELSE 37","IF 38 ELSE 38", "IF 39 ELSE 39","IF 40 ELSE 49","IF 41 ELSE 41","IF 42 ELSE 42", "IF 43 ELSE 43","IF 44 ELSE 44","IF 45 ELSE 45","IF 46 ELSE 46", "IF 47 ELSE 47","IF 1 ELSE 0","IF 35 ELSE 35","RETURN"}

    Returns: 16

    35:

  17. {"IF 48 ELSE 48","IF 49 ELSE 2","IF 1 ELSE 1","IF 2 ELSE 2","IF 3 ELSE 3","IF 4 ELSE 4","IF 5 ELSE 5","IF 6 ELSE 6","IF 7 ELSE 7","IF 8 ELSE 8","IF 9 ELSE 9","IF 10 ELSE 10","IF 11 ELSE 11","IF 12 ELSE 12","IF 13 ELSE 13","IF 14 ELSE 14","IF 15 ELSE 15","IF 16 ELSE 16","IF 17 ELSE 17","IF 18 ELSE 18","IF 19 ELSE 19","IF 20 ELSE 20","IF 21 ELSE 21","IF 22 ELSE 22","IF 23 ELSE 23","IF 24 ELSE 24","IF 25 ELSE 25","IF 26 ELSE 26","IF 27 ELSE 27","IF 28 ELSE 28","IF 29 ELSE 29","IF 30 ELSE 30","IF 31 ELSE 31","IF 32 ELSE 32","IF 33 ELSE 33","IF 34 ELSE 34","IF 35 ELSE 35","IF 36 ELSE 36","IF 37 ELSE 37","IF 38 ELSE 38","IF 39 ELSE 39","IF 40 ELSE 40","IF 41 ELSE 41","IF 42 ELSE 42","IF 43 ELSE 43","IF 44 ELSE 44","IF 45 ELSE 45","IF 46 ELSE 46","IF 47 ELSE 47","RETURN"}

    Returns: 2

  18. {"IF 48 ELSE 48","IF 49 ELSE 47","IF 1 ELSE 1","IF 2 ELSE 2","IF 3 ELSE 3","IF 4 ELSE 4","IF 5 ELSE 5","IF 6 ELSE 6","IF 7 ELSE 7","IF 8 ELSE 8","IF 9 ELSE 9","IF 10 ELSE 10","IF 11 ELSE 11","IF 12 ELSE 12","IF 13 ELSE 13","IF 14 ELSE 14","IF 15 ELSE 15","IF 16 ELSE 16","IF 17 ELSE 17","IF 18 ELSE 18","IF 19 ELSE 19","IF 20 ELSE 20","IF 21 ELSE 21","IF 22 ELSE 22","IF 23 ELSE 23","IF 24 ELSE 24","IF 25 ELSE 25","IF 26 ELSE 26","IF 27 ELSE 27","IF 28 ELSE 28","IF 29 ELSE 29","IF 30 ELSE 30","IF 31 ELSE 31","IF 32 ELSE 32","IF 33 ELSE 33","IF 34 ELSE 34","IF 35 ELSE 35","IF 36 ELSE 36","IF 37 ELSE 37","IF 38 ELSE 38","IF 39 ELSE 39","IF 40 ELSE 40","IF 41 ELSE 41","IF 42 ELSE 42","IF 43 ELSE 43","IF 44 ELSE 44","IF 45 ELSE 45","IF 46 ELSE 46","IF 47 ELSE 47","RETURN"}

    Returns: 47

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: