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 |
Your submission must meet the ITrianglePegSolitaireSolver interface and must arrive in my email before midnight (GMT – 5) on Friday September 8th in order to be run through the tests.
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 :P
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.