gregoryyoung is the Page Editor for two of Experts Exchange's programming topic areas. He was recently named a Microsoft Most Valuable Professional; this article is reprinted from his blog.

I tried a contest on my blog that 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, so 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.

 
 
 

Your submission must meet the ITrianglePegSolitaireSolver interface and must arrive in my email before midnight (GMT - 5) on Friday, September 8 in order to be run through the tests.

Submissions are to be emailed to me at gregoryyoung@experts-exchange.com. Do not post your submission in comments on the blog; they will be deleted. It is also not your best interest to do this as someone could come through and optimize one line of your code to beat you.

The Sunday after the contest ends I will create a post including performance results for all code. I will also post a zip file of all submissions (including my performance harness and unit tests so others can view it). The results will also be sent out in the Experts Exchange newsletter, and the link to the file will be available as well.

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!

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: "Algorithms" by Robert Sedgewick. This book was printed in 1988 and 95 per cent 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?)

Additional notes

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. The puzzles are dynamically sized (not all will be 15 holes -- some will be larger). You should assume that all arrays will be complete (i.e., 15, 21, 28 etc. elements) but you should probably handle incomplete arrays by throwing an exception. 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.

If you have any questions, need clarification, or have thoughts on the overall idea of these competitions please email me.

ericpete is the editor of the Experts Exchange newsletter. He considers the main benefit to doing that job to be the opportunity to write -- something he has done professionally since he was a young boy.

Headline: NYC Fires Man For Web Surfing At Work

There is a lot of bad behavior at work. A recent study by the American Management Association and the ePolicy Institute found that 26 per cent of employers have fired workers for misusing email; a few years ago, a coworker of ours was fired for sending her boyfriend leads, even though he was a leasing agent, and the company had no interest in being in the leasing business.

We can't think of the number of stories we've seen about people whose surfing activities have gotten them into trouble; there's enough material there to keep Law & Order going for years. But it's not just that; companies are being subpoenaed about employee emails, both for what the emails say, and for what they said before they were deleted. And let's not forget that your search queries are stored by almost every search company -- and it only takes a one bad decision to make them public.

But what's getting to companies now is blogging. Some estimates are that there are about 20,000 new blogs created every day; we've been writing since our pre-teen days, and we can guarantee that it isn't easy to come up with something original, let alone interesting, every week, let alone every day, so we can't help but wonder if anyone is paying attention to most of them. Still, we'll grant that we would rather someone took out their frustrations on a blog than have him head down to the local post office with an automatic rifle.

But writing about the company, the boss, the HR department secretary, or that wierd guy who delivers the mail might not be the most prudent course of action -- even if the company doesn't have a formal policy on blogging in place. It's not just that you might get fired; it's that you might have trouble getting another job if you seem more interested in writing about your job than doing it. (Of course, turnabout is fair play.)

Fortunately, there are enough people making enough mistakes (and enough people getting close to retirement age) that there will probably be jobs available if you mess up in your youth. Just don't make a habit of it; your history will be online somewhere. It might also be worthwhile to get some counseling.

I'm glad I don't have to worry about this for a while. After signing a new anti-predator law into effect last week, the Bush Administration is also going to start a new public service campaign aimed at telling children about online creeps. Speaking of kids, that means it's back to school time. All I ever had to worry about was whether Mom would let me wear my new clothes every day for the first two weeks.

Now, all I ever took to school was a new notebook -- the kind that had three-holed lined pieces of paper and a few plastic dividers -- along with pencils and erasers (lots of those) and things like that. But if you're going to get your child one of those nice machines mentioned above, make sure you teach him or her a few things about them.

Keep an eye on the battery

The screen uses a lot of power when it's really bright, so dim it a little. Also, things like USB mouse use up power, so leave the graphics-heavy games at home where you can plug in, and if you can use the touch pad, do it.

You don't have to be connected all the time

Being online is fun, but it uses up a lot of your power, and probably is more of a distraction than your kids' teachers like. So teach them how to save web pages and such so they can go back to them off line.

nico5038 will love this: Backup, backup, and backup

If the new laptop is like everything else your kids have, it's going to get tossed, dropped, and generally abused, so it's important that you teach your kids the value of having their work backed up somewhere else. The computer can be replaced; the two weeks' work on the term paper on Greek mythology can't.

Keep the computer clean

Three essentials for your child's computer: a keyboard cover, some post-it notes (to get the crumbs from the tuna sandwich out from between the keys), and a can of compressed air.

Make sure the computer is secure

This is good advice for anyone, but children need to learn what can happen if their computer, with all of their browsing history, and all of their email, gets picked up by the wrong person. Get a good firewall, and teach them why they want to be smart about their computers.

Laptops get hot

If you've never actually had one on your lap, try it for a few hours, especially if you're working on line. It might not be a bad idea to give your child an old towel to put on their legs before settling down to work.

20 lbs. is a lot to carry

Last year, I saw a story about the problems kids are having because they have to carry all of their books around, and most parents don't think about a kid's back when they're buying a new SpongeBob SquarePants backpack. Get a good one, especially if your child is now also carrying a new laptop.

A few weeks ago, I wrote about the latest spam scheme -- the "pump and dump" scam, where people buy a ton of worthless stock and then send out millions of emails getting people to buy it at a higher price. Well, the Securities and Exchange Commission has sued a Connecticut couple and the CEO of the company whose stock they sold. It probably won't stop the spam, but maybe a few people will think twice.

And one last thing: there's a new worm that is causing an increase in the number of zombie computers out there, which may be where all that new spam is coming from.