Statistics

Problem Statement for "CircleBugs"

Problem Statement

A group of social bugs lives in a circular formation. These bugs are either red or green. Once every minute, a new green bug appears between each pair of adjacent bugs of different colors, and a new red bug appears between each pair of adjacent bugs of the same color. After that, all the original bugs die and the process is repeated. It is known that every initial formation of bugs will always lead to a cycle. The cycle length of the formation is defined as the amount of time between any of its two identical formations. Two formations are considered identical if one formation can be achieved by rotating and/or reversing the other one. For example via rotation, "RRGG" is identical to "RGGR", but it is NOT identical to "RGRG". Via reversal, "RRGGRG" is identical to "GRGGRR" and now via rotation it is also identical to "RRGRGG".

Given a String formation of bugs on a circle return the length of the cycle for that formation. Each character in formation will be either 'R' or 'G' representing the red and green bugs respectively. The formation is circular, so the bug represented by the first character is adjacent to the bug represented by the last character in formation.

Definition

Class:
CircleBugs
Method:
cycleLength
Parameters:
String
Returns:
int
Method signature:
int cycleLength(String formation)
(be sure your method is public)

Constraints

  • formation will only contain 'R' and 'G' characters, where 'R' is a red bug and 'G' is a green bug.
  • formation will have between 3 and 30 characters inclusive.

Examples

  1. "RRG"

    Returns: 1

    A red bug appears between the first and second bugs, a green bug appears between the second and third bugs, and a green bug appears between the third and first bugs. Thus the formation of the second generation is RGG. By repeating the process, we find that third generation is GRG. Notice that RGG and GRG are identical formations and thus we have a cycle of length 1.

  2. "RRGRG"

    Returns: 3

    RRGRG goes to RGGGG. RGGGG goes to GRRRG. GRRRG goes to GRRGR. Now, GRRGR is identical to RRGRG - our starting formation. There were 3 transformations, so the method should return 3.

  3. "RRRRRRRRRR"

    Returns: 1

    Formations where all bugs are red will always lead to the same formation.

  4. "RGGGGGGGGG"

    Returns: 6

  5. "RGGRGRG"

    Returns: 7

  6. "GRRRRRGRRR"

    Returns: 6

  7. "GRGR"

    Returns: 1

  8. "RRGRRGR"

    Returns: 7

  9. "RGRRRRR"

    Returns: 7

  10. "GRRGGGRG"

    Returns: 1

  11. "RGRGRGGR"

    Returns: 1

  12. "RRRGRRGRGGGRG"

    Returns: 63

  13. "RGRGRRGRRRRRGRRRG"

    Returns: 15

  14. "GRRRGGGGRGG"

    Returns: 31

  15. "RGRRGRRRGGGGRGRGRR"

    Returns: 14

  16. "RGRRRRGRRRGG"

    Returns: 4

  17. "RRRGGGRRRRRRGRRR"

    Returns: 1

  18. "RGRRGGRRRGGG"

    Returns: 4

  19. "RGGRGRGRGGGRGRRRRR"

    Returns: 14

  20. "GGRGGGRGRGRRRRRRRG"

    Returns: 14

  21. "GRGGGRGGGGRGRRRGGG"

    Returns: 14

  22. "RRGGRGRRRRRRRRRGR"

    Returns: 15

  23. "RRRGRRGGRRGGGRGRG"

    Returns: 15

  24. "RGRGGRGRGRGRGGRGG"

    Returns: 15

  25. "GRGRGGRGGRGGR"

    Returns: 63

  26. "RGRRGGGGRGGRR"

    Returns: 63

  27. "RRRRRRRRGGRGG"

    Returns: 63

  28. "RGGRGRGGGRRGGR"

    Returns: 14

  29. "RGRGGGRRRGRRRG"

    Returns: 14

  30. "GGRGRGRRGRGRGR"

    Returns: 14

  31. "RGRGGGRGGGGGRGR"

    Returns: 15

  32. "RGGRGRRRGRRRRRR"

    Returns: 15

  33. "RGGGGGGRRGGRGGR"

    Returns: 15

  34. "RGRRRGRGGGGGGRRR"

    Returns: 1

  35. "GGGRRGRRRRGRRRGGRGRRRRRRGGGGR"

    Returns: 16383

  36. "GRGGRRGGRGGRGGRRRGRGRRRGGRRGG"

    Returns: 16383

  37. "GRGGGRGRRRRGGGGRGRGGGGRGRGRGG"

    Returns: 16383

  38. "GRRGGRGRGRRGGRGGGRRGRRRGRGGG"

    Returns: 28

  39. "GGRRGRRRGGRRGRRRRRGRGGGGR"

    Returns: 1023

  40. "GRGRRRGRGRGRRRRGGGRGGRGG"

    Returns: 8

  41. "RRGGRGGGRGRGGGRRGGRG"

    Returns: 12

  42. "GRRRRGRGRGGRGGRGGGGGRRRRRR"

    Returns: 126

  43. "RGGRGGGGRGRGGGRGGRRGRGRGRGGRGG"

    Returns: 30

  44. "GGRRGGRGRGRRGRRRGGR"

    Returns: 511

  45. "GGRRRRGGGGRGRRRRGRRG"

    Returns: 12

  46. "GRGRRRRRRGGRGRRRRRGRRRGGGGRG"

    Returns: 28

  47. "RGGGGGGGGGGGGGGGGGGGGGGGGGGGR"

    Returns: 16383

    This is the worst case

  48. "RGGGGGGGGGGGGGGGGGRGGGGGGGGGR"

    Returns: 16383

  49. "RGGGGGGGGGGGGGGGGGGGGGGGGGGGR"

    Returns: 16383

  50. "RGGGGGGGGGGGGGGGGGGGGGGGGGGGG"

    Returns: 16383

  51. "RGGGGGGGGGRGGGGGGGGGGGGGGGGGR"

    Returns: 16383

  52. "RGGGGGGGGGGGGRRGGGGGGGGGGGGGG"

    Returns: 16383

  53. "GRRRRRRRRRRRRRRRRRRRRRRRRRRRG"

    Returns: 16383

  54. "RRRRRRGGGGGGGRRRRRGGGRG"

    Returns: 2047

  55. "RGGGGGGGGG"

    Returns: 6

  56. "RRGG"

    Returns: 1

  57. "RGRR"

    Returns: 1

  58. "RRGR"

    Returns: 1

  59. "RRGRG"

    Returns: 3

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: