The Knots MATLAB® Contest has come to an end.
Congratulations to all of our prize winners!
Thanks to all the participants and spectators who have helped make our final contest in this event series so much fun over the years!
Raphaël Candelier is a researcher in Physics and Biophysics at the University Paris VI (France). He currently works on zebrafish neuroimagery and routinely uses Matlab.
As one can see on the "Contest history" stair graph (see statistics), the darkness and twilight phases have been very active but the daylight phase clearly looked like a moribund escalation of tweaks. At the core of mostly all submissions were the very nice solvers by Alfonso Nieto-Castanon and Hannes Naudé ; these solvers are so efficient that they killed any attempt to search for a deeper well in the energy landscapes ; this would have taken ages.
The winning leap was based on the combination of two simple statements. First, the solutions generated by these solvers were essentially meshes with long crossing edges here and then. One could gain a few knots on every puzzle (and minimise the weighted distance as a side effect) simply by moving some nodes, either inside their Vornonoi cell or somewhere far outside the mesh. This was an appealing idea since a few knots per puzzle make hundreds of points on the global score at the end of the day !
The challenge was then to implement these node moves, and for this I choosed brute force. It was possible because - and it is the second crucial statement - the nodes had to be on discrete position so there was just a limited number of locations to check. I therefore defined a grid that envelops the whole mesh, with a tunable binning, and computed the gain one could earn by moving each node to any position on the grid, one at a time. Performance was then an issue, but I managed to make this run reasonnably fast with reasonnably fine binnings. The winning code is certainly not completely optimized, and fine tuning on the grid binning and/or algorithmic tweaks could certainly generate yet much better solutions.
This was my first Matlab contest. I have to admit that at first I have been very impressed by the leaps during the darkness and twilight phases. Then, I learned a lot simply by looking at the work of others in terms of optimization, strategy and Matlab code optimization. This contest has been a very stimulating experience, and I would like to warmly thank the whole Matlab team for their work.
Some say this contest is the last of this kind: good. Evolving makes it alive. Collaborative contests is a great concept, but for the sake of self-consistency one should not be able to reach the highest rewards by tweaking, but only by leaping. This is of course a personnal point of view, but who knows, perhaps some people among the Matlab contest organizers will read these lines and design the new Matlab contest with this idea in mind.
Hannes Naudé lives in Pretoria, South Africa. I run a small consulting firm, Innoventix Consulting, together with my coding partner from previous contests, Cobus Potgieter. We do algorithm & software development for our clients who are mostly from the defence industry. Our specialization is in signal and image processing and artificial intelligence, and we use Matlab regularly in the algorithm development side of our business. I first participated in the Matlab Contest in the trucking contest of April 2003.
Programming for me started in the 70's with my High School math teacher offering a new thing called Assembly where the code was in octal and entry was using penciled bubble cards. This led to taking a Fortan IV course where bonus points could be acquired by solving the prior years ACM questions. In 1981 I was hired by Hughes Aircraft Co. to program in Fortan IV. Since then I have dabbled in programming and algorithm development. Two years ago I was creating some algorithms when my Team expressed a desire to use Matlab. I was amazed at the rapidity of development, visualization of performance, and efficiency of code.
Since this revelation all new algorithms are developed in Matlab.
My Team mentioned the Matlab contests; I was intrigued. I enjoyed the Crossword and Vines contests while learning quite a bit about programming schemes and optimization. In the Tiles contest I was ecstatic to see my board_perfect_snake routine make it into the Tiles winning solution.
In the final contest my goal was to contribute to the winning solution. The Early Bird win was a pure Lark as I was playing Matlab Golf (code size tweaking) not knowing there was an early leader prize. The Sunday Push was captured by implementing two innovations. By profiling, I realized that "alfonso" could create a second output at virtually no time cost by placing singles on their connecting nodes. Secondly, I implemented a jiggle routine on the best solution to significantly unknot tangles. The jiggle was wonderfully and instantly evolved by Thomas Meier with an outer jiggle loop. I watched helplessly as Yi Cao improved Thomas’ new low knot solution with optimizations of the gradeit routine to come very close to passing my Sunday Push.
My end-game plan boosted me into the lead during the final submissions, however; fantastic new algorithms were created by Raphael, Per, and Alfonso. I achieved my contest goal as my Sunday Push innovations made it into the solutions of the top three - in one form or another. I particularly enjoyed Alfonso's multi-output using varargout in solver_alf.
Not awarded are my Most Submissions and Longest Time without timing out.
On Cody I have hosted Knots for both best Score and Result.
The Cheeeese is virtually unbeatable, even knowing the data sets.
I look forward to the future Matlab Community Activities.
I thank everyone who played and the Mathworks staff.
When not participating in our contests, Yi is also a university lecturer in