TopCoder problem "CircleBugs" used in SRM 166 (Division I Level Two)

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.



Method signature:int cycleLength(String formation)
(be sure your method is public)


-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.


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.
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.
Returns: 1
Formations where all bugs are red will always lead to the same formation.
Returns: 6
Returns: 511
Returns: 16383
This is the worst case

Problem url:

Problem stats url:




lbackstrom , brett1479

Problem categories: