Author |
Topic: New problem: Peg Solitaire (Read 2688 times) |
|
Garzahd
Junior Member
Gender: 
Posts: 130
|
 |
New problem: Peg Solitaire
« on: Nov 18th, 2002, 4:10pm » |
 Quote  Modify
|
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
|
| « Last Edit: Nov 18th, 2002, 4:11pm by Garzahd » |
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: New problem: Peg Solitaire
« Reply #1 on: Nov 19th, 2002, 2:07pm » |
Quote Modify
|
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..
|
| « Last Edit: Nov 19th, 2002, 2:08pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: New problem: Peg Solitaire
« Reply #2 on: Nov 20th, 2002, 10:35am » |
Quote Modify
|
I made a prolog program that goes up to 12 (then it hits a stack overflow  )
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 )
[edit]
more of the sequence: 94 113 136 159 186 213
it seems like xn = 4 * floor((n+1)/2) - 9 + xn-1 for n > 4
and xn = n-1 for 2 < x <=4
[/edit]
|
| « Last Edit: Nov 20th, 2002, 10:58am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: New problem: Peg Solitaire
« Reply #3 on: Nov 20th, 2002, 1:09pm » |
Quote Modify
|
closed formula for n > 4 : xn = n2 - 7n +15 + odd(n)
( odd(n) = 1 if n is odd, 0 otherwise)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: New problem: Peg Solitaire
« Reply #4 on: Nov 20th, 2002, 1:31pm » |
Quote Modify
|
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.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Garzahd
Junior Member
Gender:
Posts: 130
|
|
Re: New problem: Peg Solitaire
« Reply #5 on: Nov 20th, 2002, 5:10pm » |
Quote Modify
|
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).
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print