Saturday, August 16, 2008
A couple of folks were discussing the need for a Lisp equivalent to Ruby's Ruby Quiz the other day on LispForum. Ruby Quiz was a great way to learn Ruby. It presented a series of programming tasks that were somewhere between a simple exercise at the back of a textbook and a full ICFP Programming Contest challenge. The goal was to give budding Rubyists a meaty problem on which to test their skills, while not serving up something so difficult that it would take weeks to accomplish.
Well, I'm pleased to say that yesterday we took the plunge with the first quiz. The challenge is to write a simple algorithm (AI?) for playing Minesweeper. The game engine is delivered as part of the challenge, so there is no need to actually worry about the mechanics of Minesweeper. Just focus on creating an algorithm that will work its way through the minefield without choosing a mine.
The 48-hour No-Spoiler Period expires at ~5:00 PM PDT tomorrow. Check out LispForum to post your solution or discuss others.
I think its great that you guys started out with an NP complete problem.
Nothing like a little challenge to prove that Lisp programmers are hardcore
Of course, you might be making a sneaky attempt to claim the million dollar prize. Check out http://www.claymath.org/Popular_Lectures/Minesweeper/
So what if it's NP complete? Boolean SAT is NP complete, and yet for small sizes backtracking works fairly well for real world cases. Huge improvements are possible with some simple formula transforms.
Time/Space complexity != Programming difficulty.
Post a Comment
Links to this post: