DWITE Online Computer Programming Contest

New type of wordplay

February 2011
Problem 4

Over the years, many word games have been invented. However, most of them involve actually knowing the definitions of these words, and this can get kind of frustrating. So you decided to create a word game that doesn’t involve knowing what words actually mean:

  1. You start out with a word.
  2. If there is a run of length 2 or more of some letter, you can remove the whole run from the word altogether. (For example, in the word “GREEN”, you can remove the two E’s to get “GRN”.)
  3. You keep removing runs of the same letters like above until you can’t find any such runs.
  4. If the word is now empty, then you call the word you started with “solvable”. If what remains isn’t empty, then the word you started with is “unsolvable”.

You then decide to make a program to help determine whether certain given words are solvable or not.

The input file DATA4.txt will contain 5 test cases. Each test case is a single line with 5 words separated by a single space, where each of these words consists of up to 150 uppercase characters.

The output file OUT4.txt should contain 5 lines. Each line consists of some 5 letter combination of “S” or “U”, where the ith letter is “S” if the ith word in the input was solvable, or “U” if the ith word in the input was unsolvable.

Note: There might be more than one solution to a particular word.

Explanation of the first test case: “GREEN” is clearly unsolvable, since after removing the E’s you are left with the string “GRN”. As for “ABBA”, removing the B’s yields “AA”. You can then remove the A’s to get rid of the whole word (making it solvable). “POST” and “LEMONADE” aren’t solvable either, as there aren’t any runs to remove in the first place. “ROAAAOR” is solvable, as you can remove the A’s to get “ROOR”, and then you can remove the O’s to get “RR”, and finally you remove the R’s to get rid of the whole word.

Sample Input (only first case shown):
Sample Output (only first case shown):