TopCoder problem "Poetry" used in SRM 170 (Division II Level Three)



Problem Statement

    

Given a poem, determine its rhyme scheme.

To simplify things, because English is such a fickle language, there are some constraints:

A legal word is a sequence of lower or uppercase letters, containing at least one vowel, where a vowel is 'a', 'e', 'i', 'o', or 'u'. Also, 'y' is considered a vowel if it is not at the start or end of a word. Words are delimited by spaces.

Two words are considered rhyming if they have the same ending pattern (defined below). This comparison is case-insensitive (see Example 1.)

An ending pattern is a substring of a word such that:

  1. The word ends with that substring,
  2. The substring contains exactly one contiguous string of vowels,
  3. The first letter of the substring is a vowel, and
  4. The substring must either be the whole string, or the letter immediately preceding the start of the substring must be a nonvowel.

For example, the ending pattern of "bought" is "ought", the ending pattern of "spying" would be "ying", and the ending pattern of "all" would be "all". (Note that "spy" has no vowels, and thus is not a legal word.)

Two lines rhyme if their corresponding last words rhyme, and a line is empty if it contains no words.

The procedure for determinining rhyme scheme is as follows: The first non-empty line in the poem should be labeled with the lowercase letter 'a'. Every line that rhymes with that line should also be labeled with that letter. The next unlabeled non-empty line should be labeled with the letter 'b', and any rhyming lines should also be labeled in this manner. When you run out of lowercase letters, continue by using the uppercase letters 'A' to 'Z'. Empty lines should be labeled with ' ' (the space character).

The 0th character of the returned String should be the rhyme scheme label of the 0th line, the 1st character should be the label of the 1st line, and so on. This means that the returned String will have the same number of characters as there are elements in poem. Thus, given a String[] poem, then your method should return a String detailing the rhyme scheme.

 

Definition

    
Class:Poetry
Method:rhymeScheme
Parameters:String[]
Returns:String
Method signature:String rhymeScheme(String[] poem)
(be sure your method is public)
    
 

Notes

-If there is a blank line in the poem, there must be a corresponding space in the output. A blank line is one with no words. (See Example 1.)
 

Constraints

-poem will have between 1 and 50 elements, inclusive.
-each element of poem will contain between 0 and 50 characters, inclusive.
-the only allowable characters in poem will be upper and lowercase characters ('a'-'z' and 'A'-'Z') and the space character (' ').
-there will be only legal words in poem
 

Examples

0)
    
{"I hope this problem",
 "is a whole lot better than",
 "this stupid haiku"}
Returns: "abc"
Doesn't even conceivably rhyme.
1)
    
{"     ",
 "Measure your height",
 "AND WEIGHT      ",
 "said the doctor",
 "",
 "And make sure to take your pills",
 "   to   cure   your    ills",
 "Every",
 "DAY"}
Returns: " aab ccde"
Even though "height" and "weight" don't actually rhyme in English, they do by the rules laid out above.
2)
    
{"One bright day in the middle of the night",
 "Two dead boys got up to fight",
 "Back to back they faced each other",
 "Drew their swords and shot each other",
 "",
 "A deaf policeman heard the noise",
 "And came to arrest the two dead boys",
 "And if you dont believe this lie is true",
 "Ask the blind man he saw it too"}
Returns: "aabb cdef"
3)
    
{"",
 "",
 "",
 ""}
Returns: "    "
Four lines from the mind of a blank poet.
4)
    
{"This poem has uppercase letters",
 "In its rhyme scheme",
 "Alpha", "Blaster", "Cat", "Desert", "Elephant", "Frog", "Gulch", 
 "Horse", "Ireland", "Jam", "Krispy Kreme", "Loofah", "Moo", "Narf",
 "Old", "Pink", "Quash", "Rainbow", "Star", "Tour", "Uvula", "Very",
 "Will", "Xmas", "Young", "Zed", "deception", "comic", "grout",
 "oval", "cable", "rob", "steal", "steel", "weak"}
Returns: "abcdefghibjkblmnopqrstcuvwxyzABCbDEFG"
5)
    
{" ",
 "     ",
 "This poem",
 "         ",
 " ",
 " ",
 "",
 "Has lots of blank lines",
 " ",
 "      ",
 "                                            ",
 "         ",
 " ",
 "              ",
 "                                                  ",
 "  in      it           "}
Returns: "  a    b       c"
6)
    
{"too bad   your",
 "     solution went   sour"}
Returns: "aa"

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4655&pm=1835

Writer:

antimatter

Testers:

lbackstrom , schveiguy

Problem categories:

String Manipulation