The Spring 2012 MATLAB® Programming Contest has come to an end. Thanks to all the participants and spectators who have helped make the Tiles Contest a success.
Congratulations to all of our prize winners!
Sergey Yurgenson has a Ph.D. in physics from Leningrad State University (Russia). Currently Sergey works at Harvard Medical School. He uses MATLAB for data analysis and control of data acquisition in Neurobiology research.
An interesting specific of Tile Contest was a very fast conversion of leading code from single solution to ensemble of multiple solutions. That opens a way to make a contribution to code development without actually writing a lot of code. One just needs to find a novel way of utilizing already existing code. That was extremely convenient for me as I was in the middle of another competition, and was not able to dedicate a lot of time to new code development.
Friday afternoon the best algorithm consisted of eight runs of the same algorithms with different order of tiles placement. It was similar to a "classical" trick in Matlab competitions: run algorithm, then flip the board and run the same algorithm again (hence my submission name: FlipCat). I realized that those eight versions do not cover all possible variation of filling borders and the middle of the board and decided to check some other tile placement orders. To my surprise, I immediately got significant score improvement. Unfortunately, I soon realized that majority of the gain was due to one single board, and one cannot count on such a luck on test dataset. Still I decided that the idea worth trying and prepared five submissions with various modifications of tile order placement. I submitted them shortly before the deadline and the last modification provided me with improvement I was hoping for and Early Bird prize. I am happy that that modification survived as a part of the code until the end of the contest.
Close to the end of competition code consisted of numerous runs of several algorithms and some postprocessing. That postprocessing improved result but was not very fast and, thus, was run only on the best of 18 subresults. One definitely could try to apply postprocessing to more results to see if it helped. I was able to do it during Best Result competition when time of code running was not important. I observed score improvement and was able to estimate extra time necessary to run more postprocessing.
Fortunately for me closer to the end of the contest the best code was not in optimal point on result vs. cpu time surface (see Statistics). That fact made an introduction of postprocessing for second best submodel feasible because some code slowdown was not that critical. My calculations proved to be correct and that modification was enough to win Grand Prize. (Really, if one participates in Matlab Contest sufficiently many time, one should win Grand Prize just by pure luck, right?)
Michael Campbell is a systems engineer and has been working for the past 4 years in the defense industry. He recently finished his master’s degree at Johns Hopkins and currently works with Matlab extensively for various modeling and simulation type activities.
This was my second Matlab contest and the first in which I was able to dedicate an appreciable amount of time. I was hooked after the “Vines” competition, when I was proud to see my contribution end up in the winning entry and even get mentioned in Alfonso’s hall of fame write up.
My darkness and twilight entries were overly complex and slow and didn’t do well on the large board in the test suite; however once daylight began, I noticed that my approach of placing tiles starting at the corners and working towards the center was not currently in use. I was able to incorporate my method by leveraging a lot of Vitor’s original code and noticed that it was adding value on at least a few boards. The winning entry for the Saturday Leap was created when I tried giving my method multiple chances to produce the best result. The name was in reference to the fact that I was introducing some random variation to the order in which the tiles were being placed and I didn’t want to see the contest decided by some random number tweaking (thus I was happy to see that Nick’s “prayers to the Gods of Pseudorandom Numbers” went unanswered).
I wasn’t able to participate as much during the next few days, but tried to make a push for the grand prize. I noticed a submission by Oliver that was submitted about an hour before the end of the contest had improved on the overall score. I believe Gwendolyn also took notice, so I worked off some of her entries to reduce complexity and improve the run time. Sadly, my version of Matlab wouldn’t run the code and without any time to make it compatible for testing, I was making changes on the fly in the clone window. I had hope for my final two entries, but alas was done in by a typo which caused them to fail. Congrats to Sergey though on a well deserved victory and thanks to the contest team for another enjoyable experience. (Also a special thank you to Yi Cao for waiting till Sunday to unleash his “local optimal” entry!)
When not participating in our contests, Yi is also a university lecturer in
I am currently doing a Ph.D. in Electrical Engineering at the School of Electrical and Computer Engineering of Univerity of Campinas (Unicamp), in Brazil. During my undergraduate and Master course I've been using MATLAB for almost everything, including data acquisition, numerical computation, stochastic processes simulation, digital signal and image processing, neural networks and genetic algorithms.
This was my first participation on a MATLAB Programming Contest. I discovered it by accident, while searching for something on MathWorks website, so I decided to try. The Darkness period had already passed, so I could compare all my results to the others. My first attempts were pretty bad and I thought I wouldn't have any chances on the contest. I was almost giving up, when I found a mistake in a statement of my code. Suddenly, my submissions were among the first ones. It was very interesting to participate on the contest, I've learned a lot. It is very grateful to see the people basing their codes on yours, using your functions and logic. I've never had this experience and I want to participate on the next contests.
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
This year, the contest came at a very busy point of the semester for me, so I didn't have much time to compete. As a result I made an effort in Darkness but was unable to follow the contest beyond that.
I wrote a program that places tiles greedily in some predetermined sequence -- at each move it picked the best tile remaining, but it had no ability to look ahead and save tiles that would be more useful later.
At least it ran fairly quickly, and so I was able to improve the score somewhat by trying multiple variants that place the tiles in a different orders and choosing the best result.
Unfortunately missed the final spurt due to professional activity. But I was really impressed which progress it does in the last hours of the contest.
David Felguera lives in Madrid, Spain. He works for the Airborne Radar Department at Indra. David is pursuing a Ph.D. degree at the Microwave and Radar Group of Polytechnic University of Madrid researching in Interferometric Radar Imaging techniques. He has used MATLAB since 2004 for Radar Signal Simulation and Radar Algorithm Design.
As in previous contests, this year I focused in the weekend prices. I like this stage of the contest because you can make some significant improvements in efficiency or discover some improvements to already submitted code. I followed my typical approach trying to understand and improving the efficiency of the previous winners and then combine them all to select best solutions for each board. However this year that approach was not enough to win any of the weekend prices because of the impressive submissions made by Michael C on Saturday and Yi Cao on Sunday.
After that, I was less involved in the contest, however I noticed the 11K mini-contest on Monday and I decided to give a try. My approach was to systematically test the contribution of each solver to the final score. Having that information, I was able to figure out which factors, in each solver, were penalizing the score apart from the result. I deleted some of the solvers and made modifications to the others in order to simultaneously reduce the processing time, the nodes and the complexity (I really missed the formula that Alan Chalker used to post in the blog...) and finally reduced the score below 11K (or below -262.15 ºC converting from Kelvin to Celsius) in a really fast sprint.
Congratulations to all the team for another great contest!