I just finished creating a project on CodePlex for the Code Camp Room Planner, a little app I wrote to help me plan the schedule at CodeStock 2009. I’ve also created some basic documentation.
Background: CodeStock is involving attendees in the planning of the conference. We started out with attendees voting on submissions, and used those votes to select sessions and speakers – the top 20 have ribbons on the sessions list page. The next step is asking attendees what sessions from the accepted list did they want to attend. We can use this data to plan a schedule with the least amount of conflicts.
It sounds simple, until I realized this is a P = NP type of problem. In simple terms, there are problems that are easy to verify a solution yet hard to calculate one. Imagine you had to select 5 prime numbers that add up to zero (negative primes allowed). This would be easy to verify that a set of 5 primes fulfill the requirements by adding them up – the trick is in how to figure out what those five numbers are, and if it’s even possible.
The question is if there is a problem, who's solution is easily checked, does that mean there is a set of steps to find the answer to the solution? Put another way, since I know how to see if one schedule is better than another (by having lower number of conflicts, with the ideal of zero) does that mean there is a method to tell me the best schedule? It’s been called the greatest problem of computer science today, but since Alan Turing isn’t answering his phone I’ll have to put off finding the solution until CodeStock 2010.
So what I did was to schedule sessions by overall popularity, then adjust to see if the total conflicts went up or down. When I started, there were 460 conflicts and I now have it down to 304 (the final schedule is out for review by speakers and should be public Monday). If you download the app you get the CodeStock data as an example – if you can beat 304 let me know! (Email me the “save” data, and also let me know your approach)
06-08-2009 8:08 PM
Michael C. Neel