The tools we used were:
- Eclipse 3.1 for our Java IDE.
- Microsoft Remote Assistant for sharing my desktop with Tom.
- Skype for voice over IP.
- Microsoft Messenger to launch Remote Assistant and text chat.
- Firefox browser.
The contest went well. TopCoder provides three problems of increasing difficulty worth 250, 500 and 1000 points max (points decrease over time). The problem set is listed on http://www.topcoder.com/index?t=statistics&c=srm255_prob We jumped into the 500 point problem first called WordCompositionGame. As a pair, Tom was immediately thinking ahead about how to implement the next steps as I coded the steps that we knew. This eliminated some hesitations and pauses that might have slowed down either of us alone.
On the 1000 point problem, KthElement we also quickly hacked out the solution. Our code was more brute force than elegant because we were racing the clock. Our JUnit tests failed showing we had the right sequence, just not the correct KthElement. I immediately guessed we had an "index off by one" bug. So rather than puzzling out the bug, I simply added one to the index and re-ran the unit test... it passed!!! (Thanks to Tom for creating a program that converts the TopCoder problem statement into Unit Tests). We submitted the code.
Next we opened the 250 problem with lots of time left. While reading the problem statement, something bugged us about our solution to the 1000point KthElement problem. KthElement ran a long time for large numbers. Tom checked the rules and realized there is a 8 second limit on runtime. So we reopened KthElement. This cost us more points because the clock was now ticking down points on the 250 problem, and reopened the countdown on KthElement.
A quick look at the data in the KthElement unit tests made us realize the sequences started to repeat. So the solution was to collect the sequence until it repeats and calculate the KthElement from the repeating pattern. This took a bit of effort, but saved us from total failure. At one point in this, Tom and I disagreed about how to find the KthElement from the repeating pattern. Tom started to go off on his own solution (he has two monitors at home), while I was hacking out my solution. Fortunately this split didn't last more than a minute or two. I was able to draw Tom back to look at my solution because I was so close to getting it, but needed another pair of eyes. Together we got the pattern identified and the calculation for the Kth element correct.
Finally back to the 250 problem SequenceOfNumbers. It was a real easy one, but we only had 9 min left on the clock. We got rushed and made some mistakes in our approach. Thankfully as a pair we quickly saw when things were off track and got back together. At one point we went off in a tangent trying to make an elegant solution. It wasn't panning out, so we trashed it and did a quick brute force. Adrenaline was pumping as we compiled and ran unit tests with less than one minute remaining. It pass the tests and we got everything submitted with ony 34 sec left in the contest.
Final score... all our solutions worked and scored. We could have scored higher on KthElement and SequenceOfNumbers if we had looked at the unit tests and realized KthElement involved a repeating pattern. Having both problems opened at the same time was not good.
Remote Pair Programming worked great! We performed as well as we would have sitting right next to each other. In fact we probably performed better being remote because it was easier to swap control since we each had our own mouse and keyboard.
(Yes, we know TopCoder considers collaboration as cheating. Sorry. We were just trying to experiment with Pair Programming and enjoy the contest. We assume this is ok during a *not for money* match. It would be nice if TopCoder had a division for Pair Programmers.)
[Aug 11, 2005. I've posted a follow up article.]
No comments:
Post a Comment