Statistics

Problem Statement for "PresentationComp"

Problem Statement

In algebra, a presentation is a convenient way to describe a set. The presentation includes what the atomic elements of the set are, and what relations are used to simplify strings of atoms. These atoms are usually called generators. In this problem we will be looking at a set whose generators are x and y. You will be given a String expression consisting of x's and y's. The simplifying rules are:
  • 1) Any occurrence of yyyyyy can be deleted from the string.
  • 2) Any occurrence of xxxxxxxx can be deleted from the string.
  • 3) Any occurrence of xy can be replaced by yyyyyx.
Two strings A and B are equivalent if there is a string C such that A can be simplified into C and B can be simplified into C by applying the rules above 0 or more times. Return the shortest string equivalent to expression. If there are multiple possible solutions, return the one that comes first alphabetically.

Definition

Class:
PresentationComp
Method:
simplify
Parameters:
String
Returns:
String
Method signature:
String simplify(String expression)
(be sure your method is public)

Constraints

  • expression will contain between 1 and 50 characters inclusive.
  • Each character in expression will be x or y.

Examples

  1. "xyxyxyxyxyx"

    Returns: "xxxxxyx"

  2. "xxxx"

    Returns: "xxxx"

  3. "yyyy"

    Returns: "yyyy"

  4. "xyxyxyxyxyxyxyxyxxyyxyxyxyxxyyxyxyx"

    Returns: "xyx"

  5. "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxy"

    Returns: "y"

  6. "xxxy"

    Returns: "xxxy"

  7. "xxxxxxxxyyyyyy"

    Returns: ""

    Simplifies greatly.

  8. "xy"

    Returns: "xy"

    Doesn't get much simpler.

  9. "yyxx"

    Returns: "xxyy"

    Use the one that comes first alphabetically.

  10. "yyyyyyyyyyyyyyyyyyyyyyyyyyyxxxxxxxxxx"

    Returns: "xxyyy"

  11. "yyyyyyxxxxxxx"

    Returns: "xxxxxxx"

  12. "yyyyyxxxxxxx"

    Returns: "xxxxxxxy"

  13. "xxxxxxxyyyyy"

    Returns: "xxxxxxyx"

  14. "yyyyyxx"

    Returns: "xyx"

  15. "yyyyyxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxy"

    Returns: "xx"

  16. "yyyyyxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxy"

    Returns: ""

  17. "xxxyyxxyxyxxxyyyyxxxxxxxxyyxxxyyxxxxyyxxyxxy"

    Returns: "xxxyyx"

  18. "yyyyyxyxyyxxyyyxyyyyxyyyyxxyyyxxyyxxyyyyyxxyyx"

    Returns: "xxxxxxxyyy"

  19. "yxyyyxyyyxxxxxyyxyxxyxxyxxyyxyxyyxxxyxyxxyxxxxxx"

    Returns: "xxxx"

  20. "yyxyyyxyyxyxyxyyxyxyxxxxyxyyxyxxyyxyyxyyyyxxxyyyxx"

    Returns: "xxxxxyyx"

  21. "yxyxyyxyyxxxyyyyyyxxyyyyyyyyxxyxxxxyyxyyxxyyx"

    Returns: "xxy"

  22. "yxxyxxyyyxxxyyxxxyxxxxyyxxyyxyyyyxxyyyyxxxyxxxxyx"

    Returns: "xxyyx"

  23. "yyxxxyyxxxyxxxyyyxyyyyxyxxxyxyxyyyxxyxyyxx"

    Returns: "xxxxxyyy"

  24. "yyxxxyxyxxyyyxxyxyyyxxxxxyyxyxxxxyxyxyyx"

    Returns: "xxxxxxyy"

  25. "xxyyyxyyxxxxyyyyxyxyyxyxxxyyyxxxyyyxxxyyxyyxxyxyyy"

    Returns: "xxxxxxyx"

  26. "yxxxxyxyyxxyxxyyxyxxxyyxxxxyxyyxxxxyyxyxxy"

    Returns: "xyyy"

  27. "xyyxxxxyxyxyxxxxyyxxyyyyxxxxxyxxyyxxxxyyyxx"

    Returns: "xxyyy"

  28. "xyxxxyxxyxyyyyyxyyyxyyyyxyyyyxxyxyyyxxyyxx"

    Returns: "yx"

  29. "xxyyyyyxyyyxxxxyyyyxxxyxyyxyxxyyxxyyyyxyxxxy"

    Returns: "xxxyyx"

  30. "xxyyyyyxyxyxxyxyxxyxyxxxyyyxyyyyyyxyyxxyyxx"

    Returns: "xxxyy"

  31. "yxyyxxxyyxyxyxxxxxxxxyyxyyxyyyyxxyxyxyyxyxyxyxxyx"

    Returns: "xyx"

  32. "yxyyyxxyxyyyxxxyyyyyxyyxxxxxxyxxyyxxyxxxyyxx"

    Returns: "xxxxxxxy"

  33. "xyxyxxxyxyxyxyyxyyxyyxyyyxyyxyxxyxyyxxyxxyyyxxyxy"

    Returns: "xxxxxxxyy"

  34. "xxyxxyxxxxxxxxxxyyyyyyyxxyxyxyyxyyxyyyxxyxxyyx"

    Returns: "xyyy"

  35. "yyyxyxxxyxxxyxyxyxyyyxxxyxyxxyxyxyxyxyxxyxyyyxyxy"

    Returns: "xyy"

  36. "yxxyyxyxyyxxxxxxyyyxxxxyyxyxyyxyxxxxxyyyyyyyxxyy"

    Returns: ""

  37. "xxxyxxxyxxxxyyyxyyyyyyyxxxyxyxyyyyxyxxxx"

    Returns: "xxxxxy"

  38. "yyxyyxxxxyxyxyyyyyyxxyxxyxxyyxxxxxxyyyxyyxyyxyxx"

    Returns: ""

  39. "xxxxxyyxxyyxyyyyyxxxxxxxxyxxxyyyxyyyxyyyxxxxxxyy"

    Returns: "xxxyyy"

  40. "xyxyxyyyyxxxyxyyyxxxyyxxyyxxyxxxxxyyxxyxxxyxyyx"

    Returns: "xxy"

  41. "yyxyxyyyxyyyyyyxxyyxyyxxxxxyyyxyyyyxxyxyyxyyxyx"

    Returns: "xyx"

  42. "xyxyyxxxxyxxyxyxyxxyxyxyxxxyxxxyxxxyyyxyx"

    Returns: "yyx"

  43. "xyxxxxyxxxyxyxxyxyxyxyxyxxxxxyyxxyxxxyxyy"

    Returns: "xxy"

  44. "yyyyyyxyyxxxxxxxyyxxxxxxyyyxxyxxyyyxyyxyyx"

    Returns: "xxxxyx"

  45. "yxxxxxxyyyyyxxyxxyyyyyxxyyxyxyxxxyxxyyyyxyyxyxyxx"

    Returns: "yyyyy"

  46. "xyxxyyyxyxxxyyxxyxxxyyxxxyyxxyxyxxyyxxxxx"

    Returns: "yyx"

  47. "yxxyyxyxxyyyxxxxyyxyxxxyyyxyxxyxxxxyyyxyyy"

    Returns: "xxxxxyyy"

  48. "yxxyyyxxyxxyxxyyyxxxxxyyxyyyxxxyxxyxyxxxxxxxx"

    Returns: "xxxxyyy"

  49. "xxxxxxyxxxyxxxyyxyxyyyxxyxxxyxxyxyyxyyxyx"

    Returns: "xyy"

  50. "xyyxxyxxxxxyyyxxxxxxxxxxxyxxyxxxxyyxyyxyyxyyy"

    Returns: "xxxyx"

  51. "yyxxxxyyyyyyxxxyyxyxyyyxyyxxyxyxyyxyyxyxxxyyy"

    Returns: "xxxyy"

  52. "yyyyxyyyxyyxyyxyxxyyyyxyyyxxyxxyxyyyyyxxxxxyyy"

    Returns: "xyyy"

  53. "xyxxxxyxxxxyyxyxxyyxyxxxxyxyxyyxyyxyxyyxxy"

    Returns: ""

  54. "xyxyyxxyxxyxyxyxyxxyxxyyxyyxyxyyyyyxyxxyyxyyyyxyy"

    Returns: "xxxxxyy"

  55. "yyxxxyxxxyyxxyyyyxxxyyyyxyxyxyxyyxyyxxxy"

    Returns: "xxxyyy"

  56. "yxxxyyxyyyyxyxxyyxyyxyyyxyxxxxyxyyxxxxyyxyyyy"

    Returns: "xxxxy"

  57. "yyyxyxxxyxyxxyxxyyyxyyyxyyyyxyxxyxyxyyyyxx"

    Returns: "xxyy"

  58. "yyyyyyyyyyyxyyyyyyyyyyxxyyxxxyyyxyxxxxyxxyyxxyxyxx"

    Returns: "xyyx"

  59. "yxxxyyyxxyxyyyyxyxxyyyyxxxyxyyyxxyxyyyyxxxxx"

    Returns: "xxxxxyyy"

  60. "yxyxyyyyxxxxxxxxyxyyxyxyxyyyxyxyxxxyxyxxxxxxyyxxyy"

    Returns: "xxxyyx"

  61. "yyyxyxxxxxxxxyyxyyxyxyyxxxxyxyxyyxyxxxyx"

    Returns: "xxxxxxxy"

  62. "yyyyyxyxxyyxyxyyxxxyxyyxyxxxyyyyyyyxyxxxyxyxyyyx"

    Returns: "xxxyyx"

  63. "yyyxxxxyyyyxxxyyyxyxxxyxyxyxyxyyxyxyxyxxxxx"

    Returns: "xxxxxxxyy"

  64. "yyyyxxyyxxxxxxyxxxxyxxxyyxxyxyxyyxxyxxxxyyyxyxxyyy"

    Returns: "xxxyyx"

  65. "yxxyyyxyxxxyxyyyxyxyxyyxyyxyxxxxyxyyyyyxyyxyxx"

    Returns: "xxxxxy"

  66. "xyyxyxxyxxxxyxyyxyxyyxyxxyyyxxyyyxyyxxxxyxx"

    Returns: "xxxxxxyyx"

  67. "x"

    Returns: "x"

  68. "xx"

    Returns: "xx"

  69. "xxx"

    Returns: "xxx"

  70. "xxxx"

    Returns: "xxxx"

  71. "xxxxx"

    Returns: "xxxxx"

  72. "xxxxxx"

    Returns: "xxxxxx"

  73. "xxxxxxx"

    Returns: "xxxxxxx"

  74. "y"

    Returns: "y"

  75. "yx"

    Returns: "yx"

  76. "yxx"

    Returns: "xxy"

  77. "yxxx"

    Returns: "xxyx"

  78. "yxxxx"

    Returns: "xxxxy"

  79. "yxxxxx"

    Returns: "xxxxyx"

  80. "yxxxxxx"

    Returns: "xxxxxxy"

  81. "yxxxxxxx"

    Returns: "xxxxxxyx"

  82. "yy"

    Returns: "yy"

  83. "yyx"

    Returns: "yyx"

  84. "yyxx"

    Returns: "xxyy"

  85. "yyxxx"

    Returns: "xxyyx"

  86. "yyxxxx"

    Returns: "xxxxyy"

  87. "yyxxxxx"

    Returns: "xxxxyyx"

  88. "yyxxxxxx"

    Returns: "xxxxxxyy"

  89. "yyxxxxxxx"

    Returns: "xxxxxxyyx"

  90. "yyy"

    Returns: "yyy"

  91. "yyyx"

    Returns: "xyyy"

  92. "yyyxx"

    Returns: "xxyyy"

  93. "yyyxxx"

    Returns: "xxxyyy"

  94. "yyyxxxx"

    Returns: "xxxxyyy"

  95. "yyyxxxxx"

    Returns: "xxxxxyyy"

  96. "yyyxxxxxx"

    Returns: "xxxxxxyyy"

  97. "yyyxxxxxxx"

    Returns: "xxxxxxxyyy"

  98. "yyyy"

    Returns: "yyyy"

  99. "yyyyx"

    Returns: "xyy"

  100. "yyyyxx"

    Returns: "xyyx"

  101. "yyyyxxx"

    Returns: "xxxyy"

  102. "yyyyxxxx"

    Returns: "xxxyyx"

  103. "yyyyxxxxx"

    Returns: "xxxxxyy"

  104. "yyyyxxxxxx"

    Returns: "xxxxxyyx"

  105. "yyyyxxxxxxx"

    Returns: "xxxxxxxyy"

  106. "yyyyy"

    Returns: "yyyyy"

  107. "yyyyyx"

    Returns: "xy"

  108. "yyyyyxx"

    Returns: "xyx"

  109. "yyyyyxxx"

    Returns: "xxxy"

  110. "yyyyyxxxx"

    Returns: "xxxyx"

  111. "yyyyyxxxxx"

    Returns: "xxxxxy"

  112. "yyyyyxxxxxx"

    Returns: "xxxxxyx"

  113. "yyyyyxxxxxxx"

    Returns: "xxxxxxxy"

  114. "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxy"

    Returns: "xy"

  115. "xxxxxyyyyyxxxxxyyyyyxxxxxyyyyyxxxxxyyyyyxxxxxyyyyy"

    Returns: "yx"

  116. "yyyyyxxxxxx"

    Returns: "xxxxxyx"

  117. "yyyyx"

    Returns: "xyy"

  118. "xyyyyyxy"

    Returns: "xxyy"

  119. "yyyyyx"

    Returns: "xy"

  120. "yyyyyyyyyyyx"

    Returns: "xy"

  121. "yx"

    Returns: "yx"

  122. "yxxxxyxxxxyyxxxxyxxxyyxxxyxyxxxyxxxxyxxxxxyxxxyxx"

    Returns: "xxxyx"

  123. "yxyxyxyxyxyxyxyxyxyxyx"

    Returns: "xxyx"

  124. "xxyyyy"

    Returns: "xyyx"

  125. "xxxxxxyyyyy"

    Returns: "xxxxxyx"

  126. "yyxxyyxxyyxxyyxx"

    Returns: "yy"

  127. "yxyy"

    Returns: "xy"

  128. "xxxyyyyy"

    Returns: "xxyx"

  129. "xxxxxxxyyyyy"

    Returns: "xxxxxxyx"

  130. "xxxxxyyyyyxxxxxyyyyyxxxxxyyyyyxxxxxyyyyyxxxxxyyyyy"

    Returns: "yx"

  131. "yyyyyxxxxxx"

    Returns: "xxxxxyx"

  132. "yyyyx"

    Returns: "xyy"

  133. "xyyyyyxy"

    Returns: "xxyy"

  134. "yyyyyx"

    Returns: "xy"

  135. "yyyyyyyyyyyx"

    Returns: "xy"

  136. "yx"

    Returns: "yx"

  137. "yxxxxyxxxxyyxxxxyxxxyyxxxyxyxxxyxxxxyxxxxxyxxxyxx"

    Returns: "xxxyx"

  138. "yxyxyxyxyxyxyxyxyxyxyx"

    Returns: "xxyx"

  139. "xxyyyy"

    Returns: "xyyx"

  140. "xxxxxxyyyyy"

    Returns: "xxxxxyx"

  141. "yyxxyyxxyyxxyyxx"

    Returns: "yy"

  142. "yxyy"

    Returns: "xy"

  143. "xxxyyyyy"

    Returns: "xxyx"

  144. "xxxxxxxyyyyy"

    Returns: "xxxxxxyx"

  145. "xxxxxyyyyyxxxxxyyyyyxxxxxyyyyyxxxxxyyyyyxxxxxyyyyy"

    Returns: "yx"

  146. "yyyyyxxxxxx"

    Returns: "xxxxxyx"

  147. "yyyyx"

    Returns: "xyy"

  148. "xyyyyyxy"

    Returns: "xxyy"

  149. "yyyyyx"

    Returns: "xy"

  150. "yyyyyyyyyyyx"

    Returns: "xy"

  151. "yx"

    Returns: "yx"

  152. "yxxxxyxxxxyyxxxxyxxxyyxxxyxyxxxyxxxxyxxxxxyxxxyxx"

    Returns: "xxxyx"

  153. "yxyxyxyxyxyxyxyxyxyxyx"

    Returns: "xxyx"

  154. "xxyyyy"

    Returns: "xyyx"

  155. "xxxxxxyyyyy"

    Returns: "xxxxxyx"

  156. "yyxxyyxxyyxxyyxx"

    Returns: "yy"

  157. "yxyy"

    Returns: "xy"

  158. "xxxyyyyy"

    Returns: "xxyx"

  159. "xxxxxxxyyyyy"

    Returns: "xxxxxxyx"

  160. "xxxxxyyyyyxxxxxyyyyyxxxxxyyyyyxxxxxyyyyyxxxxxyyyyy"

    Returns: "yx"

  161. "yyyyyxxxxxx"

    Returns: "xxxxxyx"

  162. "yyyyx"

    Returns: "xyy"

  163. "xyyyyyxy"

    Returns: "xxyy"

  164. "yyyyyx"

    Returns: "xy"

  165. "yyyyyyyyyyyx"

    Returns: "xy"

  166. "yx"

    Returns: "yx"

  167. "yxxxxyxxxxyyxxxxyxxxyyxxxyxyxxxyxxxxyxxxxxyxxxyxx"

    Returns: "xxxyx"

  168. "yxyxyxyxyxyxyxyxyxyxyx"

    Returns: "xxyx"

  169. "xxyyyy"

    Returns: "xyyx"

  170. "xxxxxxyyyyy"

    Returns: "xxxxxyx"

  171. "yyxxyyxxyyxxyyxx"

    Returns: "yy"

  172. "yxyy"

    Returns: "xy"

  173. "xxxyyyyy"

    Returns: "xxyx"

  174. "xxxxxxxyyyyy"

    Returns: "xxxxxxyx"

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.
This problem was used for: