Performance Contest #2: Triangle Solitaire


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 😛


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.

This entry was posted in Contests. Bookmark the permalink. Follow any comments here with the RSS feed for this post.

23 Responses to Performance Contest #2: Triangle Solitaire

  1. Greg says:

    “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).

  2. Michael says:

    Any results yet? Huh, huh? Anything?

    How about now? Got anything yet? Huh? Do ya?? Well!?

    Aaahhh! I’m going crazy!

  3. Greg says:

    Received entry from Steve Bushman will be known as Bushman
    Wil Laan will be known as Laan.

  4. Greg says:

    received submission from Michael Brooks will be known as Brooks

  5. Greg says:

    Received submission from Joe Rustad, will be known as Rustad

  6. Greg says:

    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

  7. Greg says:

    Received submission from Eric Bowen will be known as Bowen.

  8. Greg says:

    *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) ..

  9. Michael says:

    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 😉

  10. Greg says:

    First submission received from Rasmus Faber-Espensen. It will be known as “Rasmus”.

  11. bushmango says:

    Yeay a working (I think) semi optimized version…

  12. Greg says:

    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

  13. Greg says:

    hmm :) interesting… Remember to look for algorithmic improvements.

  14. anderdb says:

    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.

  15. Michael says:

    Seems better to keep it arbitrary, both in size and starting position.

  16. Greg says:

    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 :)

  17. Michael says:

    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?

  18. Greg says:

    I am curious .. does anyone have a working solution yet?

  19. Greg says:

    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.

  20. Chaosian says:

    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?

  21. Greg says:

    Just a clarification .. the puzzles are dynamically size (not all will be 15 holes some will be larger).

  22. Greg says:

    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.

  23. areisinger says:

    so, array index of 0 means hole No.1 ?

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>