SequenceSync | Topcoder Archive

Problem Statement

State machines occur frequently in computer science literature. At any given point in time, a state machine is in a particular state p. After receiving an input symbol, the machine updates its state. The potential input symbols in this problem are 0, 1, 2, or 3. The String[] transitions describes how the state machine M behaves. Each element of transitions will contain 4 space delimited integers. The integers in element i (0-based) describe how M reacts to input while in state i. For example, if element 3 is "0 4 2 3", then M will transition from state 3 to state 0, 4, 2, or 3 depending on whether 0, 1, 2, or 3 are received as input, respectively.

Our state machine M is unfortunately out of control. We do not know which state M is currently in. To rectify the situation, we want to find a string s and a state h such that, after feeding s into M one symbol at a time, M will definitely be in state h. Considering all possible pairs of s and h, return the length of the shortest s. If no such pairs exist, return -1.

Definition

Class:: SequenceSync
Method:: getLength
Parameters:: String[]
Returns:: int
Method signature:: int getLength(String[] transitions)
(be sure your method is public)

Constraints

transitions will contain between 1 and 20 elements inclusive.
Each element of transitions will have the form "w x y z" where w, x, y, and z are integers, without extra leading zeros, between 0 and k-1 inclusive. Here k is the number of elements in transitions.

Examples

```
{"1 1 1 1",
 "1 1 1 2",
 "0 2 2 2"}
```
```
Returns: 2
```
The string "33" forces the machine into state 2.

{"1 1 1 1",
 "2 2 2 2",
 "3 3 3 3",
 "0 0 0 0"}

Returns: -1

There are no strings that work here.

```
{"0 0 0 0"}
```
```
Returns: 0
```
A string of length 0 works here.

{"1 1 1 0",
 "2 2 2 1",
 "3 3 3 2",
 "4 4 4 3",
 "5 5 5 5",
 "6 6 6 6",
 "7 7 7 0",
 "0 0 0 8",
 "8 8 8 8",
 "9 9 9 8"}

Returns: 15

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.