The previous contest went pretty well so here is the second incarnation of the performance contest. Hopefully I can keep from wasting hours of time by running all the results with JIT optimizations disabled!
I am not providing a naïve solution to this problem, I wrote one and it is around 100 lines of code. The reason I am not providing a naïve solution is two-fold. This problem is a good brain challenge if you have never tackled a problem like this before, by giving a naïve solution I would be taking away the experience from people who have not dealt with this type of problem. Secondly the ability to test behavior in this problem is extraordinarily easy (you can quite easily generate positions, just remove one peg)
The Problem
Have you ever eaten at Cracker Barrel? I have … While waiting for my heart attack on a plate breakfast the other morning I picked up a little game they have sitting on their tables. The game is a small logic problem that falls into the category of peg solitaires.
The board is setup in a triangle with n holes (a row has previous rows + 1 holes in it). Into these holes pegs are placed, to being a game all holes are filled except for one. To move a piece you must jump over another piece (like in checkers) into an empty square. You can only jump diagonally or horizontally and you must end up in an empty hole. When you jump a piece that piece is removed from the board. The goal is to only have a single piece remaining.
You can identify the holes on a board as is done in the picture above. This is how the initial board will be given to your solver (an array of integers with 1 representing a peg and 0 representing no peg).
Your challenge should you choose to accept it is to create a program that can solve an arbitrary position. You will be given a board represented as a series of integers, a zero means that the hole at that position is empty, a non-zero value means that there is a peg in that hole. From this board your job is to return whether or not a board is solvable.
Submission Process
public interface ITrianglePegSolitaireSolver { bool IsSolvable(int[] _Board); } |
Interface for the solver |
Submissions are to be EMAILED to me at Gregory<insertmylastname>1@gmail.com. Do not post your submission in comments or I will be forced to delete it. Also it is not your best interest to do this as someone could come through and optimize one line of your code to beat you 
I will the Sunday after the contest ends create a post including performance results for all code. I will also post a zip file of all submissions (including my performance harness & unit tests so others can view it).
Scoring
Thousands of problems will be run through your solver some on big boards, some on little boards. Some problems will be very simple, some will be very complex. Any incorrect answer will result in a disqualification. Entries who have all items correct will be scored based upon the time they spent coming up with their answer.
The Prizes
CodeBetter.com has sponsored this performance contest and supplied the prizes! Everyone give a big thanks to
First Place:
“Zen of Code Optimization: The Ultimate Guide to Writing Software That pushes PC’s to the Limit” by Michael Abrash
Abrash is an optimization god … This book is considered a religious text in art of writing efficient code.
Second Place:
“How to Solve It” by George Polya … A classic work on how to solve problems (you can solve it next time!)
Best Safe Entry:
A copy of “Algorithms” by Robert Sedgewick (this book was printed in 1988 and 95% of it still applies!)
If you are unfamiliar with any of these books I highly recommend reading every one of them at least five times. Every winning submission will also receive a real world copy of the game we will be modeling.
I will do a submission but I cannot win a prize.
Two of these books are in used condition as I could not possibly buy new ones
Additional Rules
1) Only one submission per person to be evaluated, you can submit multiples for discussion if you come across an interesting tidbit that you think is worth sharing
2) Items will be run on the MS 2.0.50727 Commercial CLR (there can be no tricks such as adding IL instructions to mono)
3) You may not call out to unmanaged code!
4) You CAN use unsafe code
5) No you can’t know what the data is beforehand.
6) You must pass all tests in order to win (what good is fast if it doesn’t work?)
If you have any questions, need clarification, or have thoughts on the overall idea of these competitions please post them here.
“Are we there yet?”
Sorry I didn’t get as much time as I wanted over the weekend … I think next time I will give myself a week in case unexpected items come up.
I will put up results tomorrow night .. the question is if I put up my analysis or not as I have alot and it takes a very long time to type up (I am expecting over 20 pages in word of analysis on this problem).
Any results yet? Huh, huh? Anything?
How about now? Got anything yet? Huh? Do ya?? Well!?
Aaahhh! I’m going crazy!
Received entry from Steve Bushman will be known as Bushman
Wil Laan will be known as Laan.
received submission from Michael Brooks will be known as Brooks
Received submission from Joe Rustad, will be known as Rustad
ok I am giving the 28 hour warning because I hope to not be sitting at my computer as midnight (like usual) to give a 24 hour warning
Received submission from Eric Bowen will be known as Bowen.
*insert evil laugh* welcome to the world of NP Complete problems
http://en.wikipedia.org/wiki/Complexity_classes_P_and_NP
It is expected that big boards will take alot of time (the problem space is exponential) .. that is the hard part
I think you will do ok (a board with <> 50 pieces and no solution could take a very long time to find) ..
So… what kind of times are realistic? I can nail down thousands of traditional boards per second, but a 45 pin board crawls, and anything bigger is just rediculously slow. If I’m way off the mark, then I’ll just throw in the towel now
First submission received from Rasmus Faber-Espensen. It will be known as “Rasmus”.
Yeay a working (I think) semi optimized version…
btw: while you are attempting this puzzle … if you come up with a major break through you may just end up winning a whole lot more ..
You may just be able to collect $1,000,000 from the Clay Mathematics Institute. http://www.ams.org/notices/200606/fea-jaffe.pdf
http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf
hmm
interesting… Remember to look for algorithmic improvements.
I have a working solution. I’m running into problems similar to Michael’s where my optimized versions run slower than my non-optimized version. I think the CLR is pretty smart about optimizing but only if the code is simple enough for it to understand.
Seems better to keep it arbitrary, both in size and starting position.
Well only having 1 hole empty wouldn’t be much fun … You could just create a map of every single hole starting position up to a board size of 1000 pretty easily. George Bell has also written a very interesting paper on solving these particular types of problems (although there are some very tough ones on a board size of 7)
The hard problems are the ones without a solution
I would like to keep it as an arbitrary size but if everyone wants to change it to a a capped size I wouldn’t be opposed to it (it does offer some nice micro-optimizations). I will only change it with an overwhelming majority though. This is really focused on macro optimizations though. Just for kicks I am considerring porting mine to VB.NET
Yes. It’s a pretty simple problem using brute force, although I’m having a tough time optimizing it heavily. Oddly, my optimized version runs three times slower than my original… go figure
Is there a maximum size the puzzles may be, or must we accurately handle any arbitrarily large game board?
Also, will they always start with one peg empty, or must we be able to handle a board in any possible starting configuration?
I am curious .. does anyone have a working solution yet?
Best would probably be to throw an exception but I will not be passing any malformed puzzles (one could assume that the puzzles are in good order). The cost associated with handling a malformed puzzle should just be an if statement prior to any solving so if you do implement it I don’t think it will really hurt performance.
Are we to assume that all arrays will be complete (i.e. 15, 21, 28 etc elements)? If not, how would you like us to handle incomplete arrays?
Just a clarification .. the puzzles are dynamically size (not all will be 15 holes some will be larger).
Yes I left that out the array being passed in will be 0 based. I would however recommend if you print your board (or move combinations) that you print it out in a 1 based format for clarity.
so, array index of 0 means hole No.1 ?