Gene Splicing Winners

The Fall 2008 MATLAB® Programming Contest has come to an end. We hope you enjoyed it as much as we did.

Thanks to all the participants and spectators who have helped make the Gene Splicing Contest such a great success. Congratulations to all our winners! We also want to give a special "high-five" to those winners who are already in our MATLAB Contest Hall of Fame, yet made the effort to participate again in this contest.

• Grand Prize & Twilight Winner: Markus Buehren
• Best Result by 5:00 PM Winner: Abhisek Ukil
• Late Twilight and Early Bird Winner: Sergey Yurgenson
• LeapWinner: Jan Langer
• Darkness Winner: Nick Howe

Markus Buehren
Grand Prize & Twilight Winner

His current employer is Daimler, the German car company, where he works as a member of the research department. In this new role, he continues to use MATLAB. He has also started using Simulink and Stateflow in the development and continual improvement of an emergency braking system for trucks.

This was the fourth Matlab Programming Contest I participated in. The idea of my solver finishing first place during twilight was as stupid as it could be: Compute (nearly) all possible single next moves and select the best one. The crucial thing was to do this fast. As a move has the dimensions origin position, target position and splice length (plus swap/no swap), the number of possible moves was very large, much larger than in the problems of the last contests. I saw that I could check the score of possible moves very fast by pre-computing distance values using function cumsum. With this, evaluating the possible moves only required a small number of additions. Adding some criteria to leave some of the possible moves unchecked lead to an additional reduction in processing time.

After twilight, I had less time to work on the problem. As many other contestants, I had the idea to check swap moves. But here I was not very lucky and other contestants came up with a much better solution. Besides swapping, I submitted the nearly unnoticed "code cleanup 4". Here I removed all M-Lint messages shown in the Matlab editor and thus improved the code quality.

At the end of the contest, I came home from work only half an hour before deadline. I was lucky to see that nobody had the idea to replace the repmat function by indexing with ones. So I started an incredible session of "copy & paste", randomly choosing submissions from the queue and pasting the repmat-tweak. Minutes before the deadline I clicked the "submit" button in about 40 open browser tabs. In the late evening (Central European time) I saw that "M07" took the lead and that I had luckily selected and tweaked that submission from the queue before. My entry "ones 8" was even picked up from srach and altered again, but to my luck he was not able to improve the score and finished only in second place.

For winning the contest, I only needed to apply a small tweak. Of course I am happy about winning the "grand prize", but as a programmer I am much more happy about the fact that code written by me during twilight survived until the end and is contained in the winning submission (as subfunction "markussolver").

A great thank you goes again to the contest team! I have searched for other programming contests in other programming languages, but the concept of the Matlab Programming Contest seems to be unique. Let's just hope that it will get a bit more attention in the future. I am looking forward to the next contest!

-- Markus Buehren

Abhisek Ukil
Best Result before Five

Abhisek Ukil is from Calcutta, India. He received his PhD on signal processing for power systems disturbance analysis from Tshwane University Pretoria, South Africa. Currently he is a Research Scientist at ABB Corporate Research, Baden-Daettwil, Switzerland, part of the 'Integrated Sensor Systems' group. This team works in the field of signal processing, embedded systems, machine learning, power systems, automation instrumentation.

He first began using MATLAB in 2000, his final year of bachelor study in EE at Jadavpur Univ in Calcutta. Continuing ever since, throughout studies and through current research and development work in ABB, he has used MATLAB for development and validation of different signal processing and machine learning algorithms before embedding them into microcontroller, DSP or FPGA. In this group, they also use Simulink for modeling/device simulation and embed M-files into LabView for real-time prototyping. 

Abhisek Ukil recently published his first book entitled "Intelligent Systems and Signal Processing in Power Engineering" by Springer, Heidelberg, containing numerous MATLAB examples demonstrating practical applications of machine learning and signal processing techniques for different power systems problems.

I took the approach to minimize the maximum differences between the target and the test sequences. So, I considered the element in test causing the maximum difference (between test & target)  and matched its counterpart in target. Then estimated the optimum chain in between, which gives minimum score . with this approach, on the example testsuite I could reduce the error by 55% in 4 seconds. And this eventually got the third and fourth place during darkness and twilight phase. Then, I combined this with the entry by Markus (markus7b15), and version of this approach was consistently part of the subsequent developments, often put as 'oldconvolutedsolver'. With some adjustments in the chain formation I could still improve the score during the second twilight and best result before 5.

Sergey Yurgenson
Early Bird and Late Twilight

Sergey Yurgenson has a Ph.D. in physics from Leningrad State University (Russia). His previous wins in the MATLAB Central Contest include the Tuesday Leap and the 10000 Character Challenge Winner in Peg Solitaire (May 2007).

Currently Sergey works at Harvard Medical School. He uses MATLAB for data analysis and control of data acquisition in Neurobiology research.

My Twilight submission, as usual, did not score very well. So, when codes became visible, I decided to spend my lunch time studying Markus's solution. I had found a way to accelerate the algorithm. Based on accelerated code, I prepared several modifications, trying to find the best combination of result and time. I submitted them just before the deadline, and some got to the top.

Before the start of Late Twilight, code optimization was done mainly by running several solvers and choosing best final result. Majority of solvers were one-step deep, and I was waiting for somebody to find an efficient way to look deeper. Only swapper solver considered some specific two-step moves. When Late Twilight started, I incorporated swapper algorithm inside Markus's solver, which provided significant result improvement. Even with slightly slower code, it was enough to win Late Twilight.

-- Sergey Yurgenson

Jan Langer
Saturday Leap

Jan is from the Saxon city of Chemnitz in Germany. He is a research assistant at the System and Circuit Design Group at the Chemnitz University of Technology.

He says he uses "MATLAB only occassionally", which is quite remarkable as he has definitely shown his skills in previous contests. Previous wins include Sunday Push in the Blackbox (November 2006) and Ants (May 2005).

This time, I didn't have much time for the contest and I was just lucky.

On Saturday, I looked at Markus' leading entry at the end of Twilight. As I tried to understand his code, I noticed a bug and an opportunity for performance improvements in the calculation of cumSumFromRight. Later the day, I submitted a slowed down version of the leading entry with the correct cumSumFromRight. Surprisingly, this worked very well and came close to the current best Saturday Leap. To actually get on top of the list, I had some luck tweaking the parameters in markussolver.

-- Jan Langer

Nick Howe
Darkness Winner

Nick Howe teaches computer science at Smith College in western Massachusetts. He uses MATLAB extensively to conduct research on problems in computer vision.

The Gerrymandering contest (April 2004) was his first MATLAB Central Contest. He has been participating on and off ever since.

I knew I wasn't going to have a lot of free time during this contest, so I figured I would put in a good effort in the Darkness phase and see how far it got me. I ended up staying up late working on my solver, but I felt like I was close to a good solution and wanted to see it through. I got something working at 2:30 AM and went to bed intending to work more in the morning, but as things turned out that was my last contribution before Twilight.

The Darkness winner was conceptually pretty simple. It does a brute-force search of all possible non-reversing shifts, choosing the best move at each step in a greedy fashion. I was able to make this fast enough that it ran in reasonable time on the test suite, although I didn't know it until darkness lifted. (As faster variants, I also submitted some versions that deliberately computed fewer moves than they were allowed.) Unfortunately, it wasn't really fast enough to do much searching for alternative move sequences.

I had intended to expand the program to search all possible reversing shifts, but that proved harder than I had thought and I only partially implemented it, allowing in-place reversal moves to improve the score by a little bit. By the end of Twilight, Markus's top entry was better than mine and I spent the remaining competition watching from the sidelines.

-- Nick Howe