Undecidable | Topcoder Archive

Problem Statement

We have a list of possible string mutations. Each mutation specifies a starting string of characters and the string it may change into. A mutation may increase or decrease the string's length.

Given strings start and finish, we want to know if there is a sequence of these mutations that could transform start into finish. Each mutation in the sequence can be applied to any substring. For example, given the possible mutations

 
    ACG -> CT, ACTA -> CGA, and T -> G

it would be possible to transform AACTAG into CGAG by a sequence of 3 mutations

   AACTAG -> AACGAG -> ACTAG -> CGAG

This problem is undecidable -- there is no algorithm to solve it, not even a brute force algorithm! But we can devise algorithms that will solve some instances of the problem. Let's try to analyze the problem just based on the lengths of the strings involved. We may be able to determine that the answer to an instance of the problem is NO.

Your method will be given int[]s from and to. The lengths of the start and finish strings are given by the first elements. For i greater than 0, the i-th elements give the lengths in a possible mutation. Return -1 if no sequence of mutations could transform the start string into the finish string. Otherwise, return the length of the shortest mutation sequence that could conceivably make the transformation.

Definition

Class:: Undecidable
Method:: possible
Parameters:: int[], int[]
Returns:: int
Method signature:: int possible(int[] from, int[] to)
(be sure your method is public)

Constraints

from will contain between 2 and 50 elements, inclusive.
to will contain the same number of elements as from.
Each element in to and from will be between 1 and 10,000, inclusive.

Examples

```
{6,3,4,1}
```
```
{4,2,3,1}
```
```
Returns: 2
```
This would be the length analysis for the example above. Is it possible that mutations that change 3 characters to 2, 4 characters to 3, and 1 character to 1 could change a 6 character string into a 4 character string? The answer is that it might happen in as few as 2 mutations, changing 6 characters to 5, and then changing 5 to 4.
```
{6000,1,2,3,17}
```
```
{4000,4,101,9,8}
```
```
Returns: -1
```
Every one of the mutations changes the length by a multiple of 3. Since 6000 and 4000 don't differ by a multiple of 3, no sequence of mutations could transform the start string into the finish string.
```
{119,1}
```
```
{118,2}
```
```
Returns: -1
```
The only mutation increases the length. So no sequence can reduce the length from 119 to 118.

{2, 2,5,10000}

{3, 9999,4,1}

Returns: 9997

```
{3,7,8}
```
```
{3,8,7}
```
```
Returns: 0
```

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.