August 30, 2006
Experts Exchange Community News
You are receiving this because you are an Experts-Exchange.com member who has opted-in to receive newsletters.
What's New at Experts Exchange
Click here to unsubscribe from the newsletter.
Performance Contest: Triangle Solitaire

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.

triangle

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.

solver
 
 
 

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.

The Premium Services include a number of features not available to "limited" members. Among them:
> Unlimited question points
> VIP Search
> Bookmarks
> Quick Links
> Collapsible menu
> No ads
You can purchase Premium Services on a month-to-month, semi-annual or annual basis, and take full advantage of all that Experts Exchange has to offer!
Who is the fastest?

A couple of weeks ago, nafis_devlpr asked "who is the fastest Masters Certifcate Acheiver In EE all TA and in C++ and in how much time." We turned to the man who is best at finding these things out: ameba. His response:

"This is not official data from EE and it might be inaccurate. Data is collected once a day, usually at 1AM PST. And I don't have cert. data for period before 11 March 2004. On 11 March 2004 there were 915 certifications, now there are 3772 certifications." We have been looking at his statistics for quite a while now, and we'd be willing to vouch that if they're off, it's not by enough to matter. So here you are:

The fastest is scolja - ASP.NET Master in 7 days, and in C++ it's novitiate, 83 days.

Fastest to Master's Certificate
Member Points TA Days
novitiate dbkruger stefan73 routinet 0tacon Jokra_the_Barbarian Raynard7 rafrancisco BillAn1 DireOrbAnt aneeshchopra ccarey madgett Ramy_atef smaccari nabsol gregoryyoung esteban_felipe RCorfman rorya alextr2003fr mkline71 RCorfman 50,893 51,140 51,008 51,974 50,185 53,165 50,025 74,475 50,107 50,520 55,250 53,120 51,750 57,958 54,560 52,640 50,988 70,220 53,410 54,700 51,565 53,387 50,940 C++ C++ C++ MS Access MS Access MS Access MS Access MS SQL MS SQL MS SQL Flash Flash Flash Flash Javascript Javascript .NET .NET Oracle Excel PHP Win 2000 ColdFusion 83 108 167 25 9 22 22 8 11 29 10 30 17 22 12 12 24 28 16 16 16 18 22
Fastest to Master's Certificate
Member Points TA Days
scolja GavinMannion bsdotnet Justin_W DotNetLover_Baan aki4u xgeno Maher-Jendasi AgentSmith007 John_Lennon Lord_McFly gpriceee nowonderla 0xSaPx0 purplepomegranite ClickCentric ashishg55 Expert4XP NiclasH idmisk mahesh1402 BillAn1 56,616 51,775 50,135 50,904 51,515 53,895 51,595 51,790 54,480 51,340 51,374 50,552 52,109 53,975 50,550 51,398 51,149 51,290 50,825 50,660 51,705 50,874 ASP.NET ASP.NET ASP.NET ASP.NET ASP.NET ASP.NET ASP.NET ASP.NET ASP ASP ASP Networking Networking Networking Networking Web Dev. Web Dev. Windows XP Exchange Linux C# Prog. Databases 7 19 10 19 23 12 30 23 24 28 15 30 26 27 29 21 23 26 28 28 29 30
Losing -- and finding -- a job

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.

Tip from the Moderators - Three from Community Support

Where should I ask my question?

There are around 250 topic areas at Experts Exchange, and we will be adding quite a few more in the near future. The one place you don't want to ask your question is in the Community Support topic areas, because the Experts who can help you solve your problem don't look there. Take a few seconds and look through the All Topics page, or, if you think you have (for example) a hardware question, then click on the Hardware tab at the top of the page. When the page loads, you'll see a list of subtopics to the left of the page; one of them (for example, Desktops) might be more appropriate.

I need to get ahold of an Expert. Can you give me the email address?

In a word, no. Neither the Moderators nor the Page Editors have access to email addresses; that's for your protection under the Privacy policy. Your best bet is to look at the Expert's profile -- just click on the username -- and see if the email address is posted. Most of them will tell you they don't answer EE questions by email, but you can post your question and ask them to look in. The other way to find an Expert is to go to his Comment History and see if he has posted in a question. You can leave a comment asking him to look at yours.

I asked my question in the wrong topic area. What do I do?

That depends on a few things. For the busy topic areas, like Access or Visual Basic, you should probably leave it where it is and post a pointer question (a 20-point question that has the link to your original question) in the correct topic area. If it should have gone into a topic area that isn't as busy, then post a request in the Community Support topic area, and we'll move it for you. The issue, for you, is where it will wind up on the question list. If it winds up on page three of the Questions Awaiting Answers, then moving it has done you more harm than good. The questions are listed in the order they were asked, so check the new TA before you do anything.

Page Two: More News and Notes
Nata's Corner: Striking back at predators

woman in specticalsI'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.

Inside the numbers
ameba, one of EE's prominent Experts, provides us with a list of newly earned Certificates. His list of all of the Certified Experts is located at his site. The list below covers the period from August 14 through August 28.
Expert Certified in Topic Area
MNelson831 carl_tawn aikimark rockiroads justchat_1 Chris-Dent imran_fast ptjcb Einstine98 pai_prasad QPR matthewspatrick TheLearnedOne Jojo1771 acperkins huji The--Captain RPPreacher xuserx2000 SteveJ venom96737 callrs rpggamergirl Craig_200X Geisrud Master Guru Guru Master Master Master Sage Sage Guru Guru Master Master Sage Master Sage Guru Guru Guru Master Master Guru Guru Guru Master Master MS Access Visual Basic Visual Basic Visual Basic Visual Basic Visual Basic Microsoft SQL Microsoft SQL Microsoft SQL Microsoft SQL Microsoft SQL Microsoft SQL ASP.NET ASP.NET ASP ASP Networking Networking Networking Networking Windows XP Windows XP Windows XP Windows XP Windows XP
Expert Certified in Topic Area
DireOrbAnt callrs TedInAK gops1 devsolns vo1d TransBind athapa hstiles graye angelIII lojk cubixSoftware JRossi1 dragon-it rpartington ciuly Autogard tusharashah tncbbthositg rorya mwharff Metanil johnsone rob_lorentz Guru Guru Master Master Guru Guru Master Master Master Wizard Guru Master Master Master Master Master Wizard Master Master Master Sage Master Guru Guru Guru JavaScript JavaScript JavaScript JavaScript C# C# C# C# Exchange_Server VB.NET VB.NET VB.NET VB.NET VB.NET Win. Server 2003 Win. Server 2003 Delphi PHP Web Development Web Development Excel Excel Oracle Oracle ColdFusion
Expert Certified in Topic Area
RobWill wpadron aneeshattingal Mr_Peerapol Zeffer furmiga DonConsolio ast2550 simsjrg rindi jamietoner JohnModig trinzia richrumble war1 pjtemplin rsivanandan Cyclops3590 meverest DireOrbAnt desertcities Merete sachinwadhwa suppsaws billmercer Wizard Master Guru Master Wizard Master Master Master Master Guru Master Master Master Sage Wizard Master Guru Master Genius Master Guru Master Master Master Wizard Microsoft Network Operating Systems Databases Databases Flash Flash Linux Crystal Reports Storage Desktops Desktops HTML CSS Windows Security Miscellaneous Routers Firewalls Firewalls IIS IIS Online Marketing MultiMedia Apps IBM UDB SBS Small Bus. Server FileMaker
2281 experts have 3843 certifications: Genius: 105 Sage: 177 Wizard: 248 Guru: 690 Master: 2623
Copyright ? 2006. All rights reserved.