Make a pattern alternate

Question

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.

Shouldn't "You may only swap any two pairs in each move" read "You may only swap any two letters in each move"? — DavidC, Jan 26 '13 at 22:12
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
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. — DavidC, Jan 27 '13 at 10:43

grc · Accepted Answer · 2013-01-27 00:23:55Z

5

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

edited Jan 27 '13 at 0:23

answered Jan 26 '13 at 23:16

grc

18.5k9 gold badges31 silver badges77 bronze badges

1

\$\begingroup\$ Technically you don't need the assignment of s. It'd save you a couple more characters. \$\endgroup\$ – kojiro Jan 27 '13 at 0:17
\$\begingroup\$ Yeah, you're welcome. I had to do something clever after you trounced what I was working on. \$\endgroup\$ – kojiro Jan 27 '13 at 0:41

add a comment |

Graham · Accepted Answer · 2013-01-28 19:11:15Z

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.

Peter Taylor · Accepted Answer · 2013-01-28 22:44:54Z

3

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.

edited Jan 28 '13 at 22:44

answered Jan 28 '13 at 14:06

Peter Taylor

41.7k4 gold badges57 silver badges151 bronze badges

\$\begingroup\$ If [[1 2]] means to swap letters at positions 1 and 2, the result would appear to be identical to the input. Please clarify. \$\endgroup\$ – DavidC Jan 28 '13 at 22:43
4

\$\begingroup\$ @dude, what kind of weirdo starts counting at 1? \$\endgroup\$ – Peter Taylor Jan 28 '13 at 22:43
3

\$\begingroup\$ (My hand is raised). \$\endgroup\$ – DavidC Jan 28 '13 at 22:45

add a comment |

Keith Randall · Accepted Answer · 2013-01-26 23:05:03Z

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.

DavidC · Accepted Answer · 2013-01-28 02:23:52Z

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}}
{}
{}

Dr. belisarius · Accepted Answer · 2013-01-28 13:58:43Z

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}}}
{}
{}

@dude Thanks :). I'm sure the PadLeft[{}, 20, {y}], #, 1] can be compressed a bit more — Dr. belisarius, Jan 28 '13 at 13:46

codeporn · Accepted Answer · 2013-01-30 10:04:21Z

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:

2 revs Aurel300 · Accepted Answer · 2013-01-31 17:31:50Z

1

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

edited Jan 31 '13 at 17:31

community wiki

2 revs
Aurel300

\$\begingroup\$ it could be better to use $argv[0] instead, saving you 2 bytes/each. And will be more valid, since $argv is often used for input via CMD \$\endgroup\$ – RedClover Jan 5 '18 at 13:32

add a comment |

Stack Exchange Network

current community

your communities

more stack exchange communities

Make a pattern alternate

8 Answers 8

Python, 140 122 119 115

APL 46

GolfScript (47 chars)

Python, 213 chars

Mathematica 238

Mathematica 134 or 124

Javascript - 173 characters

PHP - 34 moves - 193 characters

Your Answer

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

Hot Network Questions

Make a pattern alternate

8 Answers 8

Python, 140 122 119 115

APL 46

GolfScript (47 chars)

Python, 213 chars

Mathematica 238

Mathematica 134 or 124

Javascript - 173 characters

PHP - 34 moves - 193 characters

Your Answer

Sign up or log in

Post as a guest

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

Related

Hot Network Questions