# Swapping numbers [closed]

This is a common puzzle many of you have solved manually. Now this is the time to write an algorithm to solve the same.

There are equal number match sticks lined up in two different side facing each other's direction. There is a single empty space between them. Say something like the following figure (if total number of match sticks are 4).

Each stick can either slide one step in forward direction (if the immediate front space is free), or it can be jumped over one stick in their front, and land into the free space (if that space is free). The move in reverse direction is not possible (even the space is free). No reverse jump is also allowed. Only one move is allowed in one step.

Now, you have to write an algorithm to find the minimum steps required using which all the left hand side match sticks will land in right hand side and all the right hand side match sticks will land in left hand side.

For ex: If there are total 2 match sticks (1 in each side) then steps will be:

Note: In the above figure the left side stick been moved first. Another solution exists when the right side stick moves first. But for this problem, you have to give only one solution and that is also assuming that the left side stick moves first.

The following figure describes the moves with 4 match sticks (2 in each side):

Note: In the above figure the left side stick been moved first. Another solution exists when the right side stick moves first. But for this problem, you have to give only one solution and that is also assuming that the left side stick moves first.

[Assumption: The input can be any even number between 02 to 14 (i.e. 1 to 7 match sticks in each side). For inputs outside this range, you do not need to do any validation, neither need to provide any error message. Note: In the output, each step is separated by a '|' (pipe) character. COBOL programmers should always assume PIC 9(2) as input size & may also assume the output to be fixed maximum length 450 characters, padded with spaces at right.]

Sample Input:

02


Sample Output:

01To02|03To01|02To03|


Sample Input:

04


Sample Output:

02To03|04To02|05To04|03To05|01To03|02To01|04To02|03To04|


Sample Input:

06


Sample Output:

03To04|05To03|06To05|04To06|02To04|01To02|03To01|05To03|07To05|06To07|04To06|02To04|03To02|05To03|04To05|

• If you can't include the images directly, can you supply links for someone else to edit them in? Commented Feb 16, 2013 at 10:17
• I made some quick images. Hopefully they conform to the original author's intent. Commented Feb 16, 2013 at 10:32
• Condition for victory? Commented Feb 20, 2013 at 18:28

## APL 129

The code below takes screen input and outputs to the screen in the format specified:

n←n,n++\1↓z←(⌽z),((¯1*~2|n)×n⍴2),z←⌽∊(¯1*2|⍳n)×¨1,((⍳(n←.5×⍎⍞)-1)⍴¨2),¨1⋄(∊(((¯2↑¨'0',¨⍕¨n),¨⊂'To'),¨(¯2↑¨'0',¨⍕¨n-z)),¨⊂'|')~' '


A good third of the code is taken up formatting the output. The logic is complete by the occurrence of the ⋄ symbol in the code.

Below is the result for an input of 08 as a check:

04To05|06To04|07To06|05To07|03To05|02To03|04To02|06To04|08To06|09To08|07To09|05To07|03To05|01To03|02To01|04To02|06To04|08To06|07To08|05To07|03To05|04To03|06To04|05To06|

• I always feel like APL is cheating >.< Commented Feb 21, 2013 at 0:02
• @Shmiddty I am afraid that any purely symbol based language such as APL, J, GolfScript etc will most likely win code golf against more verbose word based languages ;) Commented Feb 21, 2013 at 10:00

## Javascript 178 174 161

prompts for n then alerts answer. (No 0 padding)

Latest:

t=1+(m=prompt(s=i='')/2);for(z=Math.abs;i++<m*2;)for(j=m-z(m-i),s+=(t+=a=(m%2^z(m+.5-i)%2-.5)*-2+1)+'To'+(t-a)+'|';j--;)s+=(t+=a=i%2*4-2)+'To'+(t-a)+'|';alert(s)


2:

z=Math.abs;t=m=prompt(o=[])/2;t++;for(s=i='';i++<m*2;)for(j=m-z(m-i),o.push((z(m+.5-i)%2-.5)?-1:1);j--;)o.push(i%2?2:-2);o.map(function(a){s+=(t+=a)+'To'+(t-a)+'|'});alert(s)


1:

t=m=prompt(o=[])/2+1;for(s=i='';++i<m;)for(j=i,o.push(i%2?-1:1);j--;)o.push(i%2?2:-2);o.concat(o.slice().reverse().slice(m-1)).map(function(a){s+=(t+=a)+'To'+(t-a)+'|'});alert(s)


This uses the concept that the pattern is mirrored:

Key
R='Jump Right'
r='Shift Right'
L='Jump Left'
l='Shift Left'
m='Move'
j='Jump'


So, where n=2, the pattern of movement is:

rLr
mjm


Which equates to

+1 -2 +1


This pattern repeats like so (n=8)

rLlRRrLLLlRRRRlLLLrRRlLr
mjmjjmjjjmjjjjmjjjmjjmjm
+1 -2 -1 +2 +2 +1 -2 -2 -2 -1 +2 +2 +2 +2 -1 -2 -2 -2 +1 +2 +2 -1 -2 +1


We can notice a few patterns here:

1. Movement alternates between left and right
2. The number of movements in a particular direction increases from 1 to n/2, which repeats 3 times, then decreases back to 1.
3. The type of movement alternates between shifting and jumping, the number of shifts in a row being a constant 1, and the number of sequential jumps increasing from 1 to n/2 then decreasing back to 1.
4. The summation of the movements is always 0. (Not sure if this is actually relevant)

n=14:

rLlRRrLLLlRRRRrLLLLLlRRRRRRrLLLLLLLrRRRRRRlLLLLLrRRRRlLLLrRRlLr
mjmjjmjjjmjjjjmjjjjjmjjjjjjmjjjjjjjmjjjjjjmjjjjjmjjjjmjjjmjjmjm


Sample output:

f(2):

1To2|3To1|2To3|


f(8):

4To5|6To4|7To6|5To7|3To5|2To3|4To2|6To4|8To6|9To8|7To9|5To7|3To5|1To3|2To1|4To2|6To4|8To6|7To8|5To7|3To5|4To3|6To4|5To6|


f(40):

20To21|22To20|23To22|21To23|19To21|18To19|20To18|22To20|24To22|25To24|23To25|21To23|19To21|17To19|16To17|18To16|20To18|22To20|24To22|26To24|27To26|25To27|23To25|21To23|19To21|17To19|15To17|14To15|16To14|18To16|20To18|22To20|24To22|26To24|28To26|29To28|27To29|25To27|23To25|21To23|19To21|17To19|15To17|13To15|12To13|14To12|16To14|18To16|20To18|22To20|24To22|26To24|28To26|30To28|31To30|29To31|27To29|25To27|23To25|21To23|19To21|17To19|15To17|13To15|11To13|10To11|12To10|14To12|16To14|18To16|20To18|22To20|24To22|26To24|28To26|30To28|32To30|33To32|31To33|29To31|27To29|25To27|23To25|21To23|19To21|17To19|15To17|13To15|11To13|9To11|8To9|10To8|12To10|14To12|16To14|18To16|20To18|22To20|24To22|26To24|28To26|30To28|32To30|34To32|35To34|33To35|31To33|29To31|27To29|25To27|23To25|21To23|19To21|17To19|15To17|13To15|11To13|9To11|7To9|6To7|8To6|10To8|12To10|14To12|16To14|18To16|20To18|22To20|24To22|26To24|28To26|30To28|32To30|34To32|36To34|37To36|35To37|33To35|31To33|29To31|27To29|25To27|23To25|21To23|19To21|17To19|15To17|13To15|11To13|9To11|7To9|5To7|4To5|6To4|8To6|10To8|12To10|14To12|16To14|18To16|20To18|22To20|24To22|26To24|28To26|30To28|32To30|34To32|36To34|38To36|39To38|37To39|35To37|33To35|31To33|29To31|27To29|25To27|23To25|21To23|19To21|17To19|15To17|13To15|11To13|9To11|7To9|5To7|3To5|2To3|4To2|6To4|8To6|10To8|12To10|14To12|16To14|18To16|20To18|22To20|24To22|26To24|28To26|30To28|32To30|34To32|36To34|38To36|40To38|41To40|39To41|37To39|35To37|33To35|31To33|29To31|27To29|25To27|23To25|21To23|19To21|17To19|15To17|13To15|11To13|9To11|7To9|5To7|3To5|1To3|2To1|4To2|6To4|8To6|10To8|12To10|14To12|16To14|18To16|20To18|22To20|24To22|26To24|28To26|30To28|32To30|34To32|36To34|38To36|40To38|39To40|37To39|35To37|33To35|31To33|29To31|27To29|25To27|23To25|21To23|19To21|17To19|15To17|13To15|11To13|9To11|7To9|5To7|3To5|4To3|6To4|8To6|10To8|12To10|14To12|16To14|18To16|20To18|22To20|24To22|26To24|28To26|30To28|32To30|34To32|36To34|38To36|37To38|35To37|33To35|31To33|29To31|27To29|25To27|23To25|21To23|19To21|17To19|15To17|13To15|11To13|9To11|7To9|5To7|6To5|8To6|10To8|12To10|14To12|16To14|18To16|20To18|22To20|24To22|26To24|28To26|30To28|32To30|34To32|36To34|35To36|33To35|31To33|29To31|27To29|25To27|23To25|21To23|19To21|17To19|15To17|13To15|11To13|9To11|7To9|8To7|10To8|12To10|14To12|16To14|18To16|20To18|22To20|24To22|26To24|28To26|30To28|32To30|34To32|33To34|31To33|29To31|27To29|25To27|23To25|21To23|19To21|17To19|15To17|13To15|11To13|9To11|10To9|12To10|14To12|16To14|18To16|20To18|22To20|24To22|26To24|28To26|30To28|32To30|31To32|29To31|27To29|25To27|23To25|21To23|19To21|17To19|15To17|13To15|11To13|12To11|14To12|16To14|18To16|20To18|22To20|24To22|26To24|28To26|30To28|29To30|27To29|25To27|23To25|21To23|19To21|17To19|15To17|13To15|14To13|16To14|18To16|20To18|22To20|24To22|26To24|28To26|27To28|25To27|23To25|21To23|19To21|17To19|15To17|16To15|18To16|20To18|22To20|24To22|26To24|25To26|23To25|21To23|19To21|17To19|18To17|20To18|22To20|24To22|23To24|21To23|19To21|20To19|22To20|21To22|


Here's some pseudo code to demonstrate the method:

var mid=cursor=N/2,delta
cursor++                 // the cursor is where the empty space is.
for(i=0; i++<N;){
delta = (mid%2^abs(mid+.5-i)%2-.5)*-2+1;  // 1 or -1
print((cursor+delta) + 'To' + cursor + '|')
cursor+=delta
for(j=mid-abs(mid-i);j--;)
{
delta = i%2*4-2  // 2 or -2
print((cursor+delta) + 'To' + cursor + '|')
cursor+=delta
}
}

• You're right that the pattern is more clear with l/L/r/R and m/j. I like the idea of separating the distance moved from the direction Commented Feb 22, 2013 at 1:43

# C - 216 213

My solution is based on two facts:

1. The "to" field is the "from" field of the previous move (since you always create an empty slot in the space you move from, and ou always move to an empty slot)

2. There is a very regular pattern to the distances and directions that are moved. For the first 3 test cases, they are:

1 -2 1

1 -2 -1 2 2 -1 -2 1

1 -2 -1 2 2 1 -2 -2 -2 1 2 2 -1 -2 1

With that in mind I basically just wrote a program to produce and continue that pattern. I'm pretty sure there must be a really beautiful and much more elegant recursive way to write this, but I haven't figured it out yet:

#include <stdio.h>

int main(int argc, const char *argv[])
{
int upper_bound = atoi(argv[1]) / 2;
int len;
int from;
int to = upper_bound + 1;
int direction = 1;
int i;

for(len = 1; len <= upper_bound; ++len){
for(i = len-1; i >=0; --i){
from = to - direction*(1 + (i!=0));
printf("%02dTo%02d|",from,to);
to = from;
}
direction*=-1;
}
for(i=1; i < len; ++i){
from = to - direction*2;
printf("%02dTo%02d|",from,to);
to = from;
}
direction*=-1;
for(--len; len >= 0; --len){
for(i = 0; i < len; ++i){
from = to - direction*(1 + (i!=0));
printf("%02dTo%02d|",from,to);
to = from;
}
direction*=-1;
}
return 0;
}


And golfed (even though this was a code-challenge, not golf):

#define B {F=T-D*(1+(i!=0));printf("%02dTo%02d|",F,T);T=F;}D*=-1;
L,F,T,D,i;main(int U,char**A){U=atoi(A[1])/2;T=U+1;D=1;for(L=1;L<=U;++L){for(i=L-1;i>=0;--i)B}for(i=1;i<L;++i)B for(--L;L>=0;--L){for(i=0;i<L;++i)B}}


#define B {F=T-D*(1+(i!=0));printf("%02dTo%02d|",F,T);T=F;}D*=-1;
L,F,T,D,i;main(int U){scanf("%d",&U);U/=2;T=U+1;D=1;for(L=1;L<=U;++L){for(i=L-1;i>=0;--i)B}for(i=1;i<L;++i)B for(--L;L>=0;--L){for(i=0;i<L;++i)B}}

• When I run your golfed version, I get a segfault. Commented Feb 17, 2013 at 10:22
• Oh sorry, I forgot to mention that the input is given as a command line argument - if you run it with no arguments it will segfault. But actually now that you mention it, I don't know why I thought command line arguments would be shorter than scanf. I'm updating my answer with a better version. Commented Feb 17, 2013 at 16:21
• The pattern is more noticeable when you use L/R/l/r (big being "jump"): N(2)=rLr, N(4)=rLlRRlLr, N(6)=rLlRRrLLLrRRlLr, etc. Commented Feb 20, 2013 at 17:38

# Mathematica

This approach builds a Nested sequence of the size and direction of the moves, formatted as {fromPosition,toPosition}, beginning with position n, where n refers to the number of match pairs. It then Folds the sequence into a function that begins with move {n, n+1}.

z@n_:=(p=1;h@t_:=Append[{Table[2 (-1)^t,{t}]},{(-1)^(t+1)}];
k=Join[Reverse@Drop[#,n],#]&[Flatten@Nest[Prepend[#,h[p++]]&,{},n]];
Fold[Append[#,{#[[-1,1]]-#2,#[[-1,1]]}]&,{{n,n+k[[1]]}},Rest@k])


z[1]


{{1, 2}, {3, 1}, {2, 3}}

z[4]


{{4, 5}, {6, 4}, {7, 6}, {5, 7}, {3, 5}, {2, 3}, {4, 2}, {6, 4}, {8, 6}, {9, 8}, {7, 9}, {5, 7}, {3, 5}, {1, 3}, {2, 1}, {4, 2}, {6, 4}, {8, 6}, {7, 8}, {5, 7}, {3, 5}, {4, 3}, {6, 4}, {5, 6}}

z[7]


{{7, 8}, {9, 7}, {10, 9}, {8, 10}, {6, 8}, {5, 6}, {7, 5}, {9, 7}, {11, 9}, {12, 11}, {10,12}, {8, 10}, {6, 8}, {4, 6}, {3, 4}, {5, 3}, {7, 5}, {9, 7}, {11, 9}, {13, 11}, {14, 13}, {12, 14}, {10, 12}, {8, 10}, {6, 8}, {4, 6}, {2, 4}, {1, 2}, {3, 1}, {5, 3}, {7, 5}, {9, 7}, {11, 9}, {13, 11}, {15, 13}, {14, 15}, {12, 14}, {10, 12}, {8, 10}, {6, 8}, {4, 6}, {2, 4}, {3, 2}, {5, 3}, {7, 5}, {9, 7}, {11, 9}, {13, 11}, {12, 13}, {10, 12}, {8, 10}, {6, 8}, {4, 6}, {5, 4}, {7, 5}, {9, 7}, {11, 9}, {10, 11}, {8, 10}, {6, 8}, {7, 6}, {9, 7}, {8, 9}}

Visualizing the Swaps

r, b, and o are images or a red match, a blue match, and no match, respectively.

The following formats the output from z to display the swaps with matches.

swaps[n_]:=FoldList[Grid[{Permute[#[[1,1]],Cycles[{#2}]],Range[2n+1]}]&,
Grid[{Join[Table[r,{n}],{o},Table[b,{n}]],Range[2n+1]}],z[n]]

swapMatches[n_]:=Grid[Partition[swaps[n],2,2,1,""],Dividers->All]


swaps produces a list of states by using the ordered pairs of z as commands to permute the initial list and subsequent lists.

swaps[1]


swapMatches displays the states in a grid.

swapMatches[2]


swapMatches[3]


## Javascript 191

function f(N) {
n=N>>=i=c=a='1';n++
s=z='0'
for(k=b='34';i<N;k=i%2?a+=z+z:b+='44',i++)c=k+c
t=''
i=N*(N+1)/2
l=2*i+N
for(;l;n+=(i>=1?r=c[i-1]:i<=-N?c[-i-N]:k[1])-2,t+=(s=n>9?'':z)+n+a+'|',--l,--i)a='To'+s+n
return t
}


Characters counted using grep =|tr -d \ |wc -c

• Hi and welcome to codegolf! I think you'll find your solution doesn't produce the correct output for any of the test cases (jsfiddle.net/SJwaU). For the input 02, the values are correct, but it's missing the trailing |. For the other two cases, the values are way off, and the formatting of 10 is also wrong. Also not sure about your character counting method. Why are you only counting the function body minus the return? Commented Feb 17, 2013 at 0:37
• @gordon Oops, seems I made a mistake in my most recent optimization. Thanks for pointing out. I count the body only because on a REPL, that's all you need. I've put the function decoration only for the sake of convenience. Commented Feb 17, 2013 at 10:07
• You do need to count relevant whitespace (e.g. newlines) towards your total. Commented Feb 20, 2013 at 23:22
• @shmiddty tr -d \ |wc -c takes newlines into account Commented Feb 20, 2013 at 23:37