Problem
You are given a sequence of coloured balls (red R
and green G
). One such possible sequence is:
RGGGRRGGRGRRRGGGRGRRRG
In as few moves as possible, you must make it so that each ball is a different colour to its neighbours (i.e. the sequence alternates.)
RGRGRGRGRGRGRGRGRGRGRG
You should write a program that can convert an unordered sequence (in this case a string) with equal numbers of "R" and "G" into a sequence where the items alternate. One example session is below, for a naive algorithm (<
is input to program, >
is output. It isn't necessary to include the carets on the input or output.)
< RGGGRRGGRGRRRGGGRGRRRG
> RGGRGRGGRGRRRGGGRGRRRG
> RGRGGRGGRGRRRGGGRGRRRG
> RGRGRGGGRGRRRGGGRGRRRG
> RGRGRGGRGGRRRGGGRGRRRG
> RGRGRGGRGRGRRGGGRGRRRG
> RGRGRGGRGRGRGRGRGGRRRG
> RGRGRGGRGRGRGRGRGRGRRG
> RGRGRGGRGRGRGRGRGRGRGR
> RGRGRGRGGRGRGRGRGRGRGR
> RGRGRGRGRGGRGRGRGRGRGR
> RGRGRGRGRGRGGRGRGRGRGR
> RGRGRGRGRGRGRGGRGRGRGR
> RGRGRGRGRGRGRGRGGRGRGR
> RGRGRGRGRGRGRGRGRGGRGR
> RGRGRGRGRGRGRGRGRGRGGR
> RGRGRGRGRGRGRGRGRGRGRG (15 moves)
Another possibility is outputting "5,7" for example to indicate swapping of positions 5 and 7.
You may position either Red or Green first, and you don't have to be consistent. Each sequence will be the same length as every other sequence.
You may only swap any two letters in each move (they do not need to be adjacent.)
Winning Criteria
The program must show each step of the sort process. The program which makes the fewest total moves for all the below strings, wins. If there is a tie, the shortest code will win.
Input Strings
The following strings will be used to test the programs:
GGGGGGGGGGRRRRRRRRRR
GGRRGGRRGGRRGGRRGGRR
RRGGGGRRRRGGGGRRRRGG
GRRGRGGGGRRRGGGGRRRR
GRGGGRRRRGGGRGRRGGRR
RGRGRGRGRGRGRGRGRGRG
The last sequence should result in zero moves.