wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> New problem: Peg Solitaire
        
(Message started by: Garzahd on Nov 18^th, 2002, 4:10pm)

Title: New problem: Peg Solitaire
Post by Garzahd on Nov 18^th, 2002, 4:10pm

The following is from topcoder.com, from the only problem set that I wrote for them. :-) For the contest, you had an 8 second program execution limit (on a P3/700mhz or so). Unlike many of the "hard" problems on the site that fit the "let's-see-how-hard-we-can-make-this-and-still-cram-it-into-75-minutes" category, this one required a fairly interesting inspiration.
--------

In the game of Peg Solitaire, you are given a arrangement of pegs that fit into a line of equally-spaced holes. In order to win the game, you must reduce the number of pegs to one, by using a series of jumps. Each jump occurs according to the following rules:

- A peg may only jump over those immediately adjacent to it on the left or right.
- A jumping peg must jump exactly one other peg, no more, no less.
- Once the jump is completed, the peg that was jumped over is removed.

For example, given the configuration of pegs and holes

...1234.5....

where a period represents an empty hole, and where a digit represents a peg, the legal moves are as follows:

...12..35....

[peg 3 jumped over peg 4, which was then removed]
or

..2..34.5....

[peg 2 jumped over peg 1, which was then removed]
These are the only two legal moves on that configuration.

A position is defined as "winnable" if, through a series of jumps, it can be reduced to one peg. For example, the above position is winnable, since it can be reduced to one peg by the following set of jumps:


...1234.5.... [initial]
...12..35.... [peg 3 jumped over peg 4]
.....1.35.... [peg 1 jumped over peg 2]
.....15...... [peg 5 jumped over peg 3]
....5........ [peg 5 jumped over peg 1]

Given a number N of pegs, write a method that returns the number of winnable positions that consist of N pegs.

NOTES
- When considering whether two positions are identical, disregard excess empty holes on the left and right side.
- Note that there is no "edge" of the playing field; there are essentially infinitely many empty holes.

An input is valid if the following criterion is met:
- size will be an integer between 2 and 35, inclusive

Test cases:
Input: 2
Output: 1
There is only one winnable case with 2 pegs; when they are adjacent.

Input: 4
Output: 3
The patterns containing 4 pegs are


..12.3.4..
..12..34..
..1.2.34..

Input: 8
Output: 23

Title: Re: New problem: Peg Solitaire
Post by towr on Nov 19^th, 2002, 2:07pm

doh.. silly me wanted to figure out how you can remove the pegs.. But it just occured to me it is much easier to see how you can add pegs.

start with 1 peg
..1..
add 1 (reverse jump)
32...
...23
(which are the same)

..12..
=>
43.2..
..1.34

etc

all you need to add a peg by reverse jump is a peg with two holes next to it.. Much easier than trying every configuration of pegs and holes and check which are solvable..
With something like hashing, and going breadth-first you can check at every node for doubles and use that to trim the tree and optimize..

Title: Re: New problem: Peg Solitaire
Post by towr on Nov 20^th, 2002, 10:35am

I made a prolog program that goes up to 12 (then it hits a stack overflow :P )
the sequence so far is (starting with 2 pegs):
1 2 3 6 9 16 23 34 45 60 75
the difference is:
1 1 3 3 7 7 11 11 15 15

hmm.. maybe I should try another prolog.. (or other progarmming language :P )

[edit]
more of the sequence: 94 113 136 159 186 213

it seems like x_n = 4 * floor((n+1)/2) - 9 + x_n-1 for n > 4
and x_n = n-1 for 2 < x <=4
[/edit]

Title: Re: New problem: Peg Solitaire
Post by towr on Nov 20^th, 2002, 1:09pm

closed formula for n > 4 : x_n = n² - 7n +15 + odd(n)
( odd(n) = 1 if n is odd, 0 otherwise)

Title: Re: New problem: Peg Solitaire
Post by James Fingas on Nov 20^th, 2002, 1:31pm

It seems to me that there are at least two different approaches to this problem which could be called simple. The first approach I thought of is the same a towr's:

1) Find all the different winning positions for n-1 pegs.

2) Generate all possible winning positions for n pegs by performing every possible anti-jump from every n-1 peg position (there are a maximum of 4 such jumps per position, so this isn't too memory-intensive).

3) Sort all of these, and eliminate duplicates.

This would not take a very long time! Well, not for small n, which probably includes n <= 35.

However, there is another way that I've thought of. Simply notice that all winning combinations for 3 or more pegs are of the following form (sorry about the poor regular expression syntax!), or its left-to-right reversal:

11(01)*(11)*{0,10111}(01)*1

An asterisk after a bracket indicates that the contents in the bracket can be repeated any number of times (including zero times). The curly braces indicate that you must select one of the items inside them.

It should be pretty easy to calculate the total number of winning positions using this regular expression, and noticing that the only duplicates created by left-to-right reversal are of the following form:

11(01)*00(10)*11

This should probably be algorithmically faster than the simpler game tree method, but will require more thinking before coding.

Title: Re: New problem: Peg Solitaire
Post by Garzahd on Nov 20^th, 2002, 5:10pm

towr has my intended solution.

This problem originally came from a class I took, and yes, all winnable bitstrings do indeed fit into a handful of regular expressions.

The closed-form is clearly the most optimal, however for the contest I didn't expect people to derive that in the 75 minutes they were given to solve this (and two other problems).