Programming Contest: Topswaps

Al Zimmermann's latest programming challenge asks up to arrange a deck of n cards numbered 1 .. n to maximise the number of swaps. Each swap looks at the value x on the top card and reverses the top x cards.

For n=4 the sequence 3, 1, 4, 2 requires 4 swaps:

3

1

4

2

4

1

3

2

2

3

1

4

3

2

1

4

1

2

3

4

Al challenges us to find the best solution for the first 25 primes, n=2, 3, 5 .. 97. Even a simple program which tests random combinations can throw out some reasonable scores:

10 rem setup array
20 input z
30 dim x(z)
40 for a=1 to z
50 x(a)=a
60 next a
70 h=0

100 rem shuffle array
110 for a=1 to z
120 r=int(rnd*z+1)
130 t=x(a)
140 x(a)=x(r)
150 x(r)=t
160 next a

200 rem remember order
210 a$=""
220 for a=1 to z
230 a$=a$+","+str$(x(a))
240 next a

300 rem swap until done
310 c=0

400 q=x(1)
410 for a=1 to int(q/2)
420 t=x(a)
430 x(a)=x(q+1-a)
440 x(q+1-a)=t
450 next a

500 c=c+1
510 if x(1)>1 then goto 400

600 rem display highscore
610 if c>h then h=c:print c;" : ";a$
620 goto 100

Are you planning to take part in the contest?