CMajor

Problem Statement

A musician has composed several melody fragments and wants you to make a program to create a complete melody by appending those fragments. A fragment is described as a sequence of key jumps on a piano keyboard. A piano keyboard looks like this:

For instance, to go from the leftmost C key to the F key, a jump of 5 keys is needed (note that the black keys are counted), and to go back requires a jump of -5 keys. A fragment does not specify a starting position. It could be "2 3 -1" meaning that after the initial key we should move two keys to the right, then three and finally one to the left.

But there is a problem: the musician has set the restriction that the resulting melody must not use (including the starting position) black keys. Then, the fragment shown above could be used either starting on a G key (and then A, C and B) or starting on a C key (and then D, F and E). Each fragment can be used only once in the melody and cannot be used partially.

You are given a String[] fragments, the melody fragments, and you must return the number of fragments in the longest melody that can be created by appending those fragments.

Definition

Class:

CMajor

Method:

getLongest

Parameters:

String[]

Returns:

int

Method signature:

int getLongest(String[] fragments)

(be sure your method is public)

Notes

• Assume that the piano keyboard is infinite.

Constraints

• fragments will contain between 1 and 19 elements, inclusive.
• Each element of fragments will contain between 1 and 50 characters, inclusive.
• Each element of fragments will be a list of integers, each separated by a single space, with no additional leading or trailing spaces.
• Each integer in fragments will be between -10000 and 10000, inclusive, with no leading zeros.

Examples

1. {"2 2 1 2 2 2 1","2 1 2 2 2 1 2"}

   Returns: 1

   The first fragment can only be played starting from C and ending on the next C, and the second fragment can only be played starting from D and ending on the next D. Therefore, they cannot be appended.

2. {"2","2","1","2","2","2","1","2","2","1","2","2","2","1","2","2","1","2","2"}

   Returns: 19

   All these fragments can be played in order starting from a C key.

3. {"2 2 2 2","1 1","5 -4 12 -11","0 2 -2 5 -1 -4 2 -2 7 -2"}

   Returns: 1

   The only fragment that can be played, without using black keys, is the last one.

4. {"2 0 2 0 -2 -2 -1 5 1 2 2 2 1"}

   Returns: 1

5. {"5748 -4385 -790 5294 3349","-3279 -1783 3768 -2459 6066 2556 -8138 -4982 1435",
    "2951","-2405 2104 3756","5578 -5040 -9497 -4868 7407 9305 -6701",
    "-3339 9514 -787 7209 7467 -4467", "7496 3011 9941 -8340 3012"}

   Returns: 4

6. {"72","1872","8916","-288","2208","-4716","2328","9516",
    "-5472","9840","6420","3492","-1608","4176","264","-6264",
    "1176","-684","3984"}

   Returns: 19