Tell me more ×
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.
up vote 9 down vote favorite

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

enter image description here

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:

enter image description here

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

enter image description here

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|
share|improve this question
If you can't include the images directly, can you supply links for someone else to edit them in? – Peter Taylor Feb 16 at 10:17
2  
I made some quick images. Hopefully they conform to the original author's intent. – primo Feb 16 at 10:32
+1 for taking care of COBOL programmers – belisarius Feb 18 at 3:51
1  
Condition for victory? – Shmiddty Feb 20 at 18:28

5 Answers

up vote 3 down vote

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|
share|improve this answer
1  
I always feel like APL is cheating >.< – Shmiddty Feb 21 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 ;) – Graham Feb 21 at 10:00
up vote 3 down vote

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
  }
}
share|improve this answer
2  
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 – Gordon Bailey Feb 22 at 1:43
up vote 2 down vote

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}}
share|improve this answer
When I run your golfed version, I get a segfault. – artistoex Feb 17 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. – Gordon Bailey Feb 17 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. – Shmiddty Feb 20 at 17:38
up vote 2 down vote

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.

matches

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]

swaps1

swapMatches displays the states in a grid.

swapMatches[2]

swaps2

swapMatches[3]

swaps3

share|improve this answer
up vote 0 down vote

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

share|improve this answer
1  
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? – Gordon Bailey Feb 17 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. – artistoex Feb 17 at 10:07
You do need to count relevant whitespace (e.g. newlines) towards your total. – Shmiddty Feb 20 at 23:22
@shmiddty tr -d \ |wc -c takes newlines into account – artistoex Feb 20 at 23:37

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.