Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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.

share|improve this question
    
Shouldn't "You may only swap any two pairs in each move" read "You may only swap any two letters in each move"? –  David Carraher Jan 26 '13 at 22:12
    
@dude very good, I'll correct that. –  Thomas O Jan 26 '13 at 22:21
    
Any requirement that a particular letter start the sorted sequence? –  dmckee Jan 27 '13 at 0:56
    
@dmckee From the question - "You may position either Red or Green first, and you don't have to be consistent." –  Thomas O Jan 27 '13 at 1:05
2  
Nice problem to work on. I suggest that you ask folks to post several examples of their input and output. This way, those who don't program in the language chosen can make an evaluation about the suitabiity of the outputs for the respective inputs. –  David Carraher Jan 27 '13 at 10:43
show 1 more comment

8 Answers 8

Python, 140 122 119 115

r=raw_input()
f=lambda x:[i for i in range(x,len(r),2)if x-(r[i]!=max('RG',key=r[::2].count))]
print zip(f(0),f(1))
share|improve this answer
1  
Technically you don't need the assignment of s. It'd save you a couple more characters. –  kojiro Jan 27 '13 at 0:17
    
Thanks; updated. –  grc Jan 27 '13 at 0:31
    
Yeah, you're welcome. I had to do something clever after you trounced what I was working on. –  kojiro Jan 27 '13 at 0:41
add comment

APL 46

((2|y)/y←(i≠↑i)/n),[.1](~2|y)/y←(i=↑i)/n←⍳⍴i←⍞

Running the given test cases yields:

GGGGGGGGGGRRRRRRRRRR
11 13 15 17 19
 2  4  6  8 10

GGRRGGRRGGRRGGRRGGRR
3 7 11 15 19
2 6 10 14 18

RRGGGGRRRRGGGGRRRRGG
3 5 11 13 19
2 8 10 16 18

GRRGRGGGGRRRGGGGRRRR
3 5 11 17 19
4 6  8 14 16

GRGGGRRRRGGGRGRRGGRR
7  9 13 15 19
4 10 12 14 18

RGRGRGRGRGRGRGRGRGRG

The above solution uses index origin 1 with the swaps given in the columns of the results matrix. Two characters can be saved if the input vector i is initialised with the input string prior to execution rather than being input at the time of execution.

share|improve this answer
add comment

GolfScript (47 chars)

:S;4,{S,,{.S=1&3*\1&2*^1$=},\;}%2/{zip}%{,}$0=`

E.g. (using a test case which is far easier to check for correctness than any of the suggested ones, which all have lots of correct answers):

< RRGGRGRGRGRGRGRGRGRG
> [[1 2]]

Output is a list of zero-indexed pairs to swap.

share|improve this answer
    
If [[1 2]] means to swap letters at positions 1 and 2, the result would appear to be identical to the input. Please clarify. –  David Carraher Jan 28 '13 at 22:43
2  
@dude, what kind of weirdo starts counting at 1? –  Peter Taylor Jan 28 '13 at 22:43
3  
(My hand is raised). –  David Carraher Jan 28 '13 at 22:45
add comment

Python, 213 chars

I=raw_input()
def M(S,T):
 S=list(S);m=[]
 while S!=list(T):z=zip(S,T);x=z.index(('R','G'));y=z.index(('G','R'));m+=[(x,y)];S[x],S[y]='GR'
 return m
N=len(I)/2
x=M(I,N*'RG')
y=M(I,N*'GR')
print[x,y][len(x)>len(y)]

M finds the moves required to convert S to T. It does this by repeatedly finding an R and a G out of position and swapping them. We then find the shorter move sequence to get to either RGRG...RG or GRGR...GR.

Should find an optimal sequence of moves for every input.

share|improve this answer
add comment

Mathematica 238

Code

f[x_] := With[{g = "GRGRGRGRGRGRGRGRGRGR", c = Characters, p = Position},
y = c[x]; s = c[g]; {v = Equal @@@ ({s, y}\[Transpose]), 
w = Not /@ v}; {vv = Thread[{y, v}], ww = Thread[{y, w}]};
((Flatten /@ {p[#, {"R", False}], p[#, {"G", False}]}) &[If[Count[Equal @@@ 
({s, y}\[Transpose]), False] < 10, vv, ww]])\[Transpose]]

N.B.: \[Transpose] is a single character, a superscripted "t", in Mathematica]

Examples

f@"GGGGGGGGGGRRRRRRRRRR"
f@"GGRRGGRRGGRRGGRRGGRR"
f@"RRGGGGRRRRGGGGRRRRGG"
f@"GRRGRGGGGRRRGGGGRRRR"
f@"GRGGGRRRRGGGRGRRGGRR"
f@"RGRGRGRGRGRGRGRGRGRG"
f@"GRGRGRGRGRGRGRGRGRGR"

{{12, 1}, {14, 3}, {16, 5}, {18, 7}, {20, 9}}
{{4, 1}, {8, 5}, {12, 9}, {16, 13}, {20, 17}}
{{2, 3}, {8, 5}, {10, 11}, {16, 13}, {18, 19}}
{{2, 1}, {10, 7}, {12, 9}, {18, 13}, {20, 15}}
{{2, 1}, {6, 3}, {8, 5}, {16, 11}, {20, 17}}
{}
{}

share|improve this answer
add comment

Mathematica 134 or 124

Depending on how you count "Transpose[]" which on Mathematica is just one char (no representation here). Spaces added for clarity

G = 0; R = 1; 
x_~ d ~ y__:= Transpose[Position[Symbol /@ Characters@x - PadLeft[{}, 20, {y}], #, 1] &
                                                                                 /@ {1, -1}]
f = SortBy[{d[#, 0, 1], d[#, 1, 0]}, Length][[1]] &

Sample:

f@"GGGGGGGGGGRRRRRRRRRR"
f@"GGRRGGRRGGRRGGRRGGRR"
f@"RRGGGGRRRRGGGGRRRRGG"
f@"GRRGRGGGGRRRGGGGRRRR"
f@"GRGGGRRRRGGGRGRRGGRR"
f@"RGRGRGRGRGRGRGRGRGRG"
f@"GRGRGRGRGRGRGRGRGRGR"

Output

{{{11}, {2}}, {{13}, {4}}, {{15},  {6}}, {{17},  {8}}, {{19}, {10}}}
{{{3},  {2}}, {{7},  {6}}, {{11}, {10}}, {{15}, {14}}, {{19}, {18}}}
{{{1},  {4}}, {{7},  {6}}, {{9},  {12}}, {{15}, {14}}, {{17}, {20}}}
{{{2},  {1}}, {{10}, {7}}, {{12},  {9}}, {{18}, {13}}, {{20}, {15}}}
{{{2},  {1}}, {{6},  {3}}, {{8},   {5}}, {{16}, {11}}, {{20}, {17}}}
{}
{}
share|improve this answer
    
Very economical coding. Nice use of pure functions. –  David Carraher Jan 28 '13 at 13:28
    
@dude Thanks :). I'm sure the PadLeft[{}, 20, {y}], #, 1] can be compressed a bit more –  belisarius Jan 28 '13 at 13:46
add comment

Javascript - 173 characters

a=prompt(w=[[],[]]).split('');for(i=a.length,f=a[0];i--;)if(i%2<1&&a[i]!=f)w[0].push(i);else if(i%2>0&&a[i]==f)w[1].push(i);for(i=w[0].length;i--;)alert(w[0][i]+','+w[1][i])

A great challenge, kept me busy for some time.
Here the codes results for the test cases:

GGGGGGGGGGRRRRRRRRRR: [10, 1] [12, 3] [14, 5] [16, 7] [18, 9]
GGRRGGRRGGRRGGRRGGRR: [ 2, 1] [ 6, 5] [10, 9] [14,13] [18,17]
RRGGGGRRRRGGGGRRRRGG: [ 2, 1] [ 4, 7] [10, 9] [12,15] [18,17]
GRRGRGGGGRRRGGGGRRRR: [ 2, 3] [ 4, 5] [10, 7] [16,13] [18,15]
GRGGGRRRRGGGRGRRGGRR: [ 6, 3] [ 8, 9] [12,11] [14,13] [18,17]
RGRGRGRGRGRGRGRGRGRG:
share|improve this answer
add comment

PHP - 34 moves - 193 characters

$l=strlen($a=$_GET["a"]);$n=$a[0]=="R"?"G":"R";while($i<$l){if($a[++$i]!=$n){echo$o."
";$o=$a=substr($a,0,$i).$n.preg_replace("/".$n."/",$n=="R"?"G":"R",substr($a,$i+1),1);}$n=$n=="R"?"G":"R";}

Might still try to improve this...

red_green.php?a=GGGGGGGGGGRRRRRRRRRR

GRGGGGGGGGGRRRRRRRRR
GRGRGGGGGGGGRRRRRRRR
GRGRGRGGGGGGGRRRRRRR
GRGRGRGRGGGGGGRRRRRR
GRGRGRGRGRGGGGGRRRRR
GRGRGRGRGRGRGGGGRRRR
GRGRGRGRGRGRGRGGGRRR
GRGRGRGRGRGRGRGRGGRR
GRGRGRGRGRGRGRGRGRGR
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.