There’s a Lot to Learn From Even Simple Puzzles

Phil Factor, 2009-08-11

"There’s a lot to learn from even simple puzzles"

SQLServerCentral has long had a reputation for lively, egalitarian debate but there are occasions, when it’s working at its very best, that are worth singling out for special mention. A short while ago, Joe Celko suggested to me that we run a competition on SQL Server Central and Simple-Talk to write the simplest, most elegant code to find all the primes below 1000. I was a bit dubious.

"What would you ever want prime numbers for?" I asked.

"Don’t you just like to read them? Am I the only guy who stays awake for leap-second every year, looking at his NIST radio controlled d clock jump forward or hang back?" Joe replied

Yes, Joe, you probably are. I was rather missing the point.

"There are some check digit schemes that use primes for weights, and some numbering schemes that use prime factors so that you need (k) of (n) numbers to crack the key." he added, kindly.

His point was that here was a tricky programming problem for which there was no established SQL solution. Database developers love that sort of challenge. We duly set the Summer SQL Stumpers challenge on July 27, having no idea that, ultimately, a team of SSC members would develop algorithms that would find not only the first 1000 primes, but also the first million primes, and with routines that ran in less than 5 seconds!

This was SSC at its finest. Twenty-four pages of discussion, argument and needling fired up several programmers to come up with a solution. Pleitch was early into the race, soon to be joined by Mike Ross, Mike Dougherty, Steve Munson and Paul Ramster. Some contestants submitted multiple solutions, whereas others were content to chip in with suggested improvements to submitted contributions. It soon became apparent that the contestants felt that the challenge of finding all primes below 10000 wasn’t hard enough, and went for a million instead. Tim Shay led the way with a very clever algorithm that took 11 seconds, which was later corrected by Pleitch. Tim noted,

"I spend a good part of the day working and reworking queries looking for the ‘sweet spots’ in performance. Looking at the results of the variations I tried, and the others posted, there’s a lot to learn from even ‘simple’ puzzles."

Then Peso produced a ‘Sieve of Atkins’ solution that ran in 7 seconds. Jeff Moden‘s effort was stunning for the excellent level of its documentation, but others such as andriy.zabavskyy were taking up the challenge with code that was hitting similar times. Joe and I were really impressed with the entries that were able to make the Sieve of Atkins and Aristophanes solutions work quickly. They were portable too. At various points, every one of the major contestants looked be in pole position. Peso’s continuous refinements brought the time down to the 5 second mark but Barry Young‘s final entry was awe-inspiring, and finally tipped the balance in his favor.

After executing, and timing, countless versions of code from a large number of contestants over the two weekends, we were somewhat cross-eyed, but never overwhelmed. We learned something about SQL from judging the contest. It was great work by all the ‘contestants’ and the 24 pages of the forum provide a fascinating insight into how a group of people can work together to solve a problem.


5 (2)




5 (2)

Related content