8
\$\begingroup\$

Introduction

A common puzzle involves a triangular board with 15 holes for tees/pegs as shown in the image below:

Sample peg board image

Starting with all the pegs in the board except for a hole at the top, the point of the puzzle is to jump pegs over one another like checkers in such a way to leave exactly one peg left. The only valid move is to jump one peg over an adjacent peg in any direction into an empty hole. The peg that was jumped is then removed from the board. Play finishes when there remain no valid moves.

Spec

Your job is to write a program that can find a complete solution to the peg puzzle, i.e., one that leaves exactly one peg left. There are multiple possible solutions, so your program just needs to print one.

  • Your program will receive no input. You are not allowed to read data from any outside source.
  • Print out the list of 13 moves that gives a result of 1 peg remaining using this format:

    Peg 1 jumps Peg 3 to Hole 6.

  • The holes/pegs are numbered from top to bottom, left to right, so that the top peg/hole is 1, numbering until the bottom-right is 15.
  • Your program must find the solution at runtime. Printing out a solution directly by any means other than solving it in the program is an automatic disqualification.
  • Bonus: receive 10 bonus points if you can output multiple unique solutions (can just print separated by blank lines).
  • Bonus: receive 5 bonus points if the number 15 appears nowhere in your source code.

Scoring

This is code-golf, so the shortest solution (by byte count) that prints out a correct answer will be the winner. Bonus points are subtracted from your total byte count. Please provide a sample output of running your program as well as a link to ideone or some similar site if possible demonstrating the execution of your program.

\$\endgroup\$
  • \$\begingroup\$ How do you mingle bonus points with the objective winning criterion, which we can only assume to be character count since this has a code-golf tag? \$\endgroup\$ – J B Apr 20 '12 at 19:49
  • \$\begingroup\$ Added clarification "Bonus points are subtracted from your total byte count.", does that make sense? \$\endgroup\$ – mellamokb Apr 20 '12 at 19:58
  • \$\begingroup\$ second bonus is too easy to obtain, 15=0xff=(1<4)-1=~(-1<<4)=... \$\endgroup\$ – ratchet freak Apr 20 '12 at 21:25
  • 3
    \$\begingroup\$ Some of your representations are >= 5 characters longer than 15 itself ;) \$\endgroup\$ – mellamokb Apr 20 '12 at 21:31
8
+100
\$\begingroup\$

Ruby, score 240 238 234 = 249 - 10 - 5

s=->t,r,c{c>0?(t+t.reverse).gsub(/[A-O]{2}[a-o]/){|j|s[t.tr(j,j.swapcase),r+"Peg #{j[0].ord-64} jumps Peg #{j[1].ord-64} to Hole #{j[2].ord-96}.\n",c-1]}:$><<r+"\n"}
s["aBD,BDG,DGK,CEH,EHL,FIM,aCF,CFJ,FJO,BEI,EIN,DHM,DEF,GHI,HIJ,KLM,LMN,MNO,","",13]

A plain ruby implementation which prints all possible solutions to this puzzle (takes less than a minute on my computer). The first lines of output can be seen here:

Peg 6 jumps Peg 3 to Hole 1.
Peg 4 jumps Peg 5 to Hole 6.
Peg 1 jumps Peg 2 to Hole 4.
Peg 14 jumps Peg 9 to Hole 5.
Peg 7 jumps Peg 8 to Hole 9.
Peg 12 jumps Peg 13 to Hole 14.
Peg 10 jumps Peg 6 to Hole 3.
Peg 4 jumps Peg 5 to Hole 6.
Peg 3 jumps Peg 6 to Hole 10.
Peg 15 jumps Peg 10 to Hole 6.
Peg 6 jumps Peg 9 to Hole 13.
Peg 14 jumps Peg 13 to Hole 12.
Peg 11 jumps Peg 12 to Hole 13.

Peg 6 jumps Peg 3 to Hole 1.
Peg 4 jumps Peg 5 to Hole 6.
Peg 1 jumps Peg 2 to Hole 4.
Peg 14 jumps Peg 9 to Hole 5.
Peg 7 jumps Peg 8 to Hole 9.
...

And the online example can be found here.

\$\endgroup\$
  • \$\begingroup\$ I'm curious how many total solutions there are? \$\endgroup\$ – mellamokb Apr 21 '12 at 18:46
  • \$\begingroup\$ @mellamokb It says there are 29760 solutions. \$\endgroup\$ – Howard Apr 22 '12 at 6:28
  • 4
    \$\begingroup\$ 29760 solutions? When I first found out about this game, it took me forever to find one. \$\endgroup\$ – PhiNotPi Apr 22 '12 at 12:15
  • 2
    \$\begingroup\$ That is odd. There are 2^14 (16384) board states and probably not all of them are reachable. I would've bet there were less solutions than states. \$\endgroup\$ – kaoD May 7 '12 at 1:03
  • 2
    \$\begingroup\$ @kaoD: A solution is actually a sequence of 13 moves (13 successive states from the original board state), of which there are technically (2^15)^13 unique possibilities, and of which a very large majority are incorrect under the rules. There are also actually 2^15 (32768) possible board states because there are 15 holes that could be either filled or empty (of which a handful are irrelevant since the board starts with a hole) \$\endgroup\$ – mellamokb May 7 '12 at 19:19
3
\$\begingroup\$

Python, 324 chars, score = 319

f=0xf
x=0x12413624725935836a45647b48d58c59e69d6af78989abcdcdedef
Z=[(x>>12*i&f,x>>12*i+4&f,x>>12*i+8&f)for i in range(18)]
M=[[65532,'']]
for i in' '*13:
 Q=[]
 for p,m in M:
  for a,b,c in[x[::-1]for x in Z]+Z:
   if p>>a&p>>b&~p>>c&1:Q+=[[p^2**a^2**b^2**c,m+"Peg %d jumps Peg %d to Hole %d.\n"%(a,b,c)]]
 M=Q
print M[0][1]

The peg state is kept as a bitmask. M contains a list of peg states and the instructions to get to that state.

I could make it print out all of the solutions as well (there are 29760 of them), but it would cost more than 10 characters to do it.

I can't post it on ideone as it takes about 90 seconds to run.

Output:

Peg 6 jumps Peg 3 to Hole 1.
Peg 4 jumps Peg 5 to Hole 6.
Peg 1 jumps Peg 2 to Hole 4.
Peg 14 jumps Peg 9 to Hole 5.
Peg 12 jumps Peg 13 to Hole 14.
Peg 7 jumps Peg 8 to Hole 9.
Peg 10 jumps Peg 6 to Hole 3.
Peg 4 jumps Peg 5 to Hole 6.
Peg 3 jumps Peg 6 to Hole 10.
Peg 15 jumps Peg 10 to Hole 6.
Peg 6 jumps Peg 9 to Hole 13.
Peg 14 jumps Peg 13 to Hole 12.
Peg 11 jumps Peg 12 to Hole 13.
\$\endgroup\$
  • \$\begingroup\$ You only have to print out a minimum of 2 solutions in order to receive the 10-point bonus. \$\endgroup\$ – mellamokb Apr 23 '12 at 17:24
3
\$\begingroup\$

C, 386 chars, score = 371

int f[37],o[36],t[36],r[14],i[14],m=1,s=~3,j=18;main(){while(j--)o[j]=o[18+j]=(f[j]=t[18+j]="AABBCCDDDEEFFGHKLM"[j]-64)+(t[j]=f[18+j]="DFGIHJKMFLNMOIJMNO"[j]-64)>>1;while(m)if(!f[++j])s=r[--m],j=i[m];else if(s>>f[j]&s>>o[j]&~s>>t[j]&1)if(r[m]=s,s^=1<<f[j]|1<<o[j]|1<<t[i[m]=j],j=-1,++m>13)for(m=printf("\n");m<14;++m)printf("Peg %d jumps Peg %d to Hole %d.\n",f[i[m]],o[i[m]],t[i[m]]);}

Prints out all 29760 solutions, in well under a second.

This version assumes (among other things) that the compiler will permit the implicit declaration of printf(). About six more characters could be saved by making use of implicit-int, but that feature was technically removed from C99.

Also, four more bytes can be saved by replacing the capital letters in the two strings with the corresponding control characters. I didn't do that here because compilers aren't required to permit such strings, and it makes already-dense source code completely illegible.

For clarity, here's the same algorithm without the more obfuscatory size-optimizations:

#include <stdio.h>
int f[37], o[36], t[36], r[14], i[14], m, j, s = ~3;
int main(void)
{
    for (j = 0 ; j < 18 ; ++j) {
        f[j] = t[18+j] = "AABBCCDDDEEFFGHKLM"[j] - 64;
        t[j] = f[18+j] = "DFGIHJKMFLNMOIJMNO"[j] - 64;
        o[j] = o[18+j] = (f[j] + t[j]) >> 1;
    }
    j = 0;
    for (m = 1 ; m ; ++j) {
        if (!f[j]) {
            --m;
            s = r[m];
            j = i[m];
        } else if ((s >> f[j]) & (s >> o[j]) & (~s >> t[j]) & 1) {
            r[m] = s;
            i[m] = j;
            s ^= (1 << f[j]) | (1 << o[j]) | (1 << t[j]);
            j = -1;
            ++m;
            if (m > 13) {
                printf("\n");
                for (m = 1 ; m < 14 ; ++m)
                    printf("Peg %d jumps Peg %d to Hole %d.\n",
                           f[i[m]], o[i[m]], t[i[m]]);
            }
        }
    }
    return 0;
}

f, o, and t are the list of legal jumps initialized in the first loop. r and i form the history that the program uses to backtrack and explore all possible games.

I'm sure this can be improved!

\$\endgroup\$
  • \$\begingroup\$ There's a one-char saving in the initialisation replacing >>1 by /2. \$\endgroup\$ – Peter Taylor May 7 '12 at 9:03
  • \$\begingroup\$ Using / instead of >> would need parens around the addition. \$\endgroup\$ – breadbox May 7 '12 at 9:09
  • \$\begingroup\$ Ah, misread the parens because they're different in the ungolfed one. \$\endgroup\$ – Peter Taylor May 7 '12 at 9:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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