TopCoder problem "WhatsThisChord" used in TCO10 Qual 3 (Division I Level Two)



Problem Statement

    

In this problem your goal is to convert a description of how a guitar chord is played to its name. For the purpose of this problem we will only consider major and minor chords.

Musical notes are given the following 12 names, in ascending order:

C, C#, D, D#, E, F, F#, G, G#, A, A#, B.

The difference between two succesive notes is called a half-step. The order of notes is cyclic. That is, the note one half-step higher than B is again C, and the note two half-steps lower than C is A#. Notes that are a multiple of 12 half-steps apart have the same name, and for our purposes we will consider them equivalent.

In this problem we will consider a six-string guitar with standard tuning. The six strings of such a guitar are tuned to the following notes, in order: E, A, D, G, B, E. (Guitar players, please note that the order used starts with the lowest string.)

If you play an open string, you will hear the corresponding note. For example, if you play the A string, you will hear the note A.

To change the note the string plays, you can hold it down on one of the frets. If you play a string while holding it down on the K-th fret, you will hear a note that is K half-steps higher. For example, if you play the A string while holding it down on the 4-th fret, you will hear the note C#.

You will be given a guitar chord encoded as a int[] chord with six elements, each of them describing one string of the guitar in the order given above. For each string we are given the fret where to hold it down. The value 0 represents an open string that plays the original note, and the special value -1 is used for a string that is not played in the chord.

For example, suppose that chord = {-1, 3, 2, 0, 1, 0}.

When playing this chord, you will hear the following notes: {none, C, E, G, C, E}.

The above chord contains three distinct notes: C, E, and G. This chord is called the "C Major" chord.

For any note X, the "X Major" chord is formed by three distinct notes. It can be obtained from the "C Major" chord by shifting all three notes by the same number of steps so that C becomes X. For example, if we shift the notes (C,E,G) by three steps, we get the notes (D#,G,A#). These three notes form the "D# Major" chord.

Similarly, the chord "C Minor" is formed by the notes C, D#, and G, and all other minor chords are shifts of this chord.

Given the int[] chord, decide whether it is one of the 12 major or one of the 12 minor chords, as defined above. If it is one of these chords, return its name as a String ("X Major" for major chords, "X Minor" for minor chords). If the chord represented by chord is not one of our chords, return an empty String.

 

Definition

    
Class:WhatsThisChord
Method:classify
Parameters:int[]
Returns:String
Method signature:String classify(int[] chord)
(be sure your method is public)
    
 

Notes

-When classifying a chord the only thing that matters is the set of notes played. The number of times a note is played does not matter as long as each of the required notes is played at least once.
 

Constraints

-chord will contain exactly 6 elements.
-Each element of chord will be between -1 and 12, inclusive.
 

Examples

0)
    
{-1, 3, 2, 0, 1, 0}
Returns: "C Major"
This is the C Major chord, as described in the problem statement.
1)
    
{3,2,0,0,0,3}
Returns: "G Major"
This is another of the basic guitar chords. The strings play the following notes: G, B, D, G, B, G. If we take the C Major chord (C,E,G) and shift it by 7, we get (G,B,D), which is precisely the set of notes in this chord. Hence the chord is G Major.
2)
    
{-1,0,2,2,1,0}
Returns: "A Minor"
This is the most common way of playing the A Minor chord. The three distinct notes we hear in this case are A, C, and E.
3)
    
{-1,4,3,1,2,1}
Returns: "C# Major"
4)
    
{8,10,10,9,8,8}
Returns: "C Major"
There are multiple ways to play each chord.
5)
    
{0,0,0,0,0,0}
Returns: ""
This is not one of our 24 simple chords.
6)
    
{-1,-1,4,-1,-1,7}
Returns: ""
Neither is this.
7)
    
{-1, -1, 2, 0, 1, 0}
Returns: "C Major"
The notes played in this chord are {none, none, E, G, C, E}. The set of notes played is (C,E,G), hence this is again a C Major chord. (In music theory this chord has a more precise name C/E, but this is irrelevant. It is still a C Major chord.)

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10927

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14278&pm=10927

Writer:

misof

Testers:

PabloGilberto , ivan_metelsky , zhuzeyuan

Problem categories:

Brute Force, Simple Search, Iteration