Connection Status:
Competition Arena > DeadCode

DeadCode

SRM 228 · 2005-01-27 · by dgoodman

SRM 228 · 2005-01-27 · by dgoodman · Recursion, Search
Class Name: DeadCode
Return Type: int
Method Name: deadCount
Arg Types: (vector<string>)
Problem Statement

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

We want to find all the dead code. A statement is "dead" if there is no execution path that contains it, where an execution path must start at the first statement (statement 0) in the segment and conclude by executing a RETURN statement. Create a class DeadCode that contains a method deadCount that is given a String[] code containing the sequence of statements and that returns the number of dead statements.

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
0)
{"RETURN", "IF 0 ELSE 1"}
Returns: 1

Execution immediately returns, so statement 1 cannot be reached.

1)
{"IF 1 ELSE 2","IF 1 ELSE 2","RETURN"}
Returns: 0

The sequence 0, 2 and the sequence 0, 1, 1, 2 are examples of legal execution paths. Every statement is in a legal execution path so there is no dead code.

2)
{"IF 1 ELSE 2","RETURN", "IF 3 ELSE 2", "IF 2 ELSE 3"}
Returns: 2

Statements 2 and 3 are dead. No execution path that includes either of them can ever reach a RETURN statement.

3)
{"IF 1 ELSE 2","IF 1 ELSE 1","RETURN","IF 3 ELSE 4","IF 0 ELSE 1"}
Returns: 3
4)
{"IF 1 ELSE 2","IF 1 ELSE 1","RETURN","IF 3 ELSE 4",
 "IF 0 ELSE 1","RETURN","RETURN","RETURN","RETURN","RETURN","RETURN","RETURN","RETURN","RETURN","RETURN","RETURN","RETURN","RETURN","RETURN","RETURN","RETURN","RETURN","RETURN","RETURN","RETURN","RETURN","RETURN","RETURN","RETURN","RETURN","RETURN","RETURN","RETURN","RETURN","RETURN","RETURN","RETURN","RETURN","RETURN","RETURN","RETURN","RETURN","RETURN","RETURN","RETURN","RETURN","RETURN","RETURN"}
Returns: 46

Submissions are judged against all 32 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class DeadCode with a public method int deadCount(vector<string> code) · 32 test cases · 2 s / 256 MB per case

Submitting as anonymous