We've come to the end of another exciting MATLAB Contest. Congratulations to Paulo and all our winners! This contest included slight changes in format with the addition of Darkness and Twilight phases. In these phases, competitors could submit code without their entries being visible to others. If you want find out who the Kristine entry was dedicated to and why Ken Crounce named his winning entry Mg3Si2O5(OH)4, read on to hear it from our winners.
You might find Paolo's name familiar. After all, he is the first person to win the coveted grand prize in three MATLAB Contests. This is certainly no small achievement. Congratulations Paulo!
You can find out more about Paulo from his profile in the Molecule Contest winner's page. Paulo also won the Grand Prize in the Mars Surveyor Contest. Read on to find out how Paulo went from never having placed first in the course of the contest to winning the grand prize.
Other than for several minutes during the middle of the contest my submissions were never ranked first until my final and winning entry was submitted at exactly 5:00 PM. I would like to thank all hackers and spammers for not clogging the network at that time; otherwise my last submission would have missed the deadline. I am also very proud that my algorithm entered during Darkness Phase was ranked in the top five. It was a rudimentary combination of a "snake" and "growing" algorithms but as with most entries ranked below one, it never made it into the mix. However I noticed some of my contributions in the top entries even though it had not claimed the top spot and was quite intrigued. Perhaps somebody picked them up from the queue or searched second place entries for inspiration. Whoever it was, thanks for making me part of the genetic code.
The modification that produced the winning entry was inspired by the mid-contest analysis by Lucio. He provided some examples of convex and non-convex homogeneous maps where the current leaders were failing. I created a snake algorithm that could spawn several “heads” and could completely solve those types of maps. It became a 200+ line monster but would crash with certain maps. I then realized that with a small modification to the sub function crystallise6, I could achieve the same result. After testing it “undercover” in the official test suite I knew I had something valuable. It was just a matter of tuning it for speed and holding it until the end. That was the hardest part as I was really tempted to use it during the "60 Second Showdown". I am glad I did not succumb to temptation as that was the difference between winning a shirt and a jacket!
Ken is our very first End of Darkness prize winner. His was able to develop the best scoring entry without feedback from the official test suite or viewing any other submissions. Congratulations Ken!
Ken lives in Somerville, MA and works for Agfa Monotype Corp. He is an imaging scientist working primarily on algorithms for halftoning and color reproduction. Off the clock he uses MATLAB to solve mathematical puzzles, such as those found at IBM Research "Ponder This".
Ken recalls first using MATLAB more than ten years ago in grad school at UC Berkeley, where he was studying the computation capabilities and pattern-formation properties of certain retina-like processing chips called cellular neural networks. His other technical interests include cellular automata, image compression, and trying to understand the amazing human visual system.
I've been following the MATLAB contest since Gene Sequencing and have made a few submissions, but mostly amused myself by watching how people were attempting to reverse engineer it, and trying a few such ideas myself. Although I would usually spend some time thinking about a good approach to solving the contest problem, I felt there was no way I could keep up with the relentless group evolution of the mainstream approach. Instead, I tended to go for simple, uniform approaches that cover all the cases, but may not be all that efficient. That allowed me to get the first passing entry in the Infection round of the Golf Contest. Also, I don't feel like I have much to offer in solving discrete, combinatorial problems, which the contest problems tend to be.
The darkness phase of the Gerrymandering Contest also allowed me an opportunity to try a simple approach without having it evolved. I drew heavily on approaches I had seen previous contests, most notably converting two-dimension problems into one-dimension by using a snake. From the program names I could tell during the darkness phase that some others were using a similar approach. I think the only novelty of mine is that it would step-back-one along the snake if it were locally beneficial to do so. By the way, the name Mg3Si2O5(OH)4 was supposed to be a kind of hint, since it is the chemical formula of a type of Serpentine rock (common in the San Francisco Bay Area).
Also, a note about The Great Rumpuscat: although he is usually known from the musical Cats, the best source of information on him can be found in Old Possum's Book of Practical Cats by T.S. Eliot. "You never saw anything Fiercer or Hairier!"
-- Ken Crounse
Our first contest winner from down under, Klaas is a new name to the MATLAB Contest Hall of Fame. Klaas recently completed his Bachelors with Honors in Mathematics at James Cook University in North Queensland, Australia. His academic interest is in mathematical ecology and he hopes to pursue a PhD in the near future. Klaas currently works at CSIRO Marine Research in Hobart, Tasmania. He uses MATLAB on a daily basis in various applications ranging from analyzing species diversity throughout the Indo-Pacific region to calculating orbital elements of binary star systems.
Klaas also enjoys the great outdoors. When not at work, you can find him out in the wilderness, hiking or hanging off a cliff. A little known fact about Klaas is that he's spent five years of his life aboard a sailing yacht, cruising the oceans with his parents and sister, instilling in him a love of nature.
In the Darkness phase of the contest I mistakenly put excessive emphasis on optimizing the speed of my simple algorithm. My algorithm broke down the problem into a single one dimensional problem for which it was quite easy to find a good solution. Once the entries were scored I realized that it was much more important to increase the quality of the solution than the algorithm efficiency -- at least at this stage of the contest.
The one dimensional problem that I was solving is only one of many that the full problem can be broken into, each of which generally has a different maximum score. A few hours before the end of Twilight deadline I submitted an entry that solved a few different 1D versions of the 2D problem, and returned the best solution. This algorithm produced an unexpectedly large increase in my score and over the next 2 hours I hurriedly (and messily!) incorporated a whole swag of new methods for generating 1D problems, thus stealing the lead from François Glineur. My entry was named after my wife, Kristine, who was very understanding about not getting any attention from me during these first stages of the contest!
-- Klaas Hartmann
Another of our contest veterans, Mike (a.k.a. MR Keenan) finished with not one but two prizes in the Gerrymandering Contest. His previous wins include the Grand Prize in the MATLAB Protein Contest. You can find out more about Mike Keenan on the winners page.
In his contest anecdote, Mike tells us more about the minutes leading up to his two winning submissions.
I implemented the mysolver method during Twilight or Darkness, but I found that it wasn't very effective without a good starting condition. During Daylight, I grafted it onto Klaas Hartmann's Kristine and was lucky enough to win the Early Bird prize. I had thought to save it to the end of the contest but you never know if that will work!
One the last day of the contest, it was time for the 60 second showdown. I noticed that my function (mysolver) was virtually unchanged since the previous Friday and that it was still an integral part of the leading entry. I noticed an entry from Paulo that scored a 0.209 and knew that I could tweak mysolver to beat that. I got it down to 0.201 and then with some help from an entry by Cleve Moler (of all people!), I got it down to 0.197 and won.
I have been using MATLAB for 19 years now, but I am still learning a lot from these contests. Thanks to the Mathwork's team (and Klaas, Cleve and Paulo) for a great contest. Although my specialty is the optimization of continuous function, these discrete problems are a lot of fun.
-- MR Keenan
We last heard from Christian during the Trucking Contest in May last year, when he won the Midnight Madness Prize. Since then, he's started working on his Master's thesis where he evaluates the performance of a paper machine control system, a task which not surprisingly, MATLAB comes in handy.
Read on to learn about how Christian created his Ozzy solver, named for the Prince of Darkness.
My Sunday push involved many small tweaks and one slightly larger modification where I included my own solver Ozzy. I had seen that Ozzy could improve the result on the public testsuite and was planning on saving it for the final showdown. However, I didn't have the patience to wait and submitted it on Sunday already. It made quite a good improvement on the result but was far to slow to run on all testcases, this led to the biggest and most questionable tweaking effort in my contest history. In the end Ozzy was only used when he could make an improvement on the score, this enabled the program to run fast enough to take the lead.
The basic algorithm in Ozzy chooses the n biggest squares as starting districts then continuously expands the smallest district by adding its biggest adjacent square. The name Ozzy came from my first submission "Prince of darkness" aka Ozzy Osborne. Inside Ozzy the word liberties is used, this is because I reused parts from a simple Go playing program I wrote during a MATLAB course.
I would like to thank the MATLAB contest team and all the other contestants for making this contest one of the best so far. Hopefully I will see you all next time.
-- Christian Ylämäki
Vincent Zhili Wu is our First Past Five winner.