The Spring 2011 MATLAB® Programming Contest has come to an end. We hope you had as much as we did!
Thanks to all the participants and spectators who have helped make the Crossword Puzzle Contest such a great success. Congratulations to all our winners! It was great to have seasoned veterans back, and really great to see some new faces.
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 contest I didn't get much done during Darkness, but I had some time during Twilight to develop an entry. For the most part I adopted the same strategy that everyone used of trying to fit as many words in as possible, but I was also able to write a solver that could handle the boards that had full grids of intersecting words. This didn't improve the overall score all that much, but it was enough to put me on top for the phase.
After this early win, I wasn't planning to compete much during the remainder of the contest, but I did follow developments. I was interested in the No Bogus Word challenge proposed by Alan, and decided to try my hand at it. I came up with a method of fitting words into a lattice grid that did pretty well, although it was not as successful as Albert's NBW work. Like Albert, I missed the deadline for NBW, so I never actually posted this code until later. What's more, I realized that I could combine my own approach with Albert's to get an NBW solver that was actually competitive with the leader on about a dozen boards. So my basic strategy was to throw this new solver into the mix along with the existing ones, and let it improve the score where it could. I was worried about the time penalty, though: if the improvements were modest they could be swamped in the score by the increased time required for my solver to run. So I was looking for other options.
I realized that Albert's code had a lot of applications. If you look at the solutions his programs produce, they are very densely populated on the left-hand side where he exploits the two letter words. The density falls off a lot on the right-hand side as the words get longer. My strategy for combining Albert's code with others was to use it to fill the left-hand side densely, and then switch to another method for the remainder of the board. That's what I did with my Lattice code. But I realized that the same trick could be applied to James' solver, replacing the grid of 2x2 squares with the more-dense stairsteps from Albert. That leaves slightly more room for the remaining words, and also runs a bit faster because the press2 routine in James' original is somewhat slow and is not used by Albert's. So my most mature solution computes a partial fill using Albert's method, and them tries several alternatives for filling the right-hand size, including my own lattice code and James' routine. Because I was worried about computation time, I took out the parts that computed the original grid of squares, hoping that it wouldn't hurt me. I didn't have time to test the effects of this slimmed-down code in advance -- thus the title of the winning entry.
I am currently working at Marine Biological Lab in Woods Hole, MA after completing my M.S. in Biomedical Engineering at Drexel University in 2009. At MBL, I work on developing state-of-the-art imaging systems, microscopy applications and techniques. MATLAB has been an integral part throughout my graduate studies and at my current work place. I primarily use MATLAB for algorithm development, image processing, instrumentation and signal processing. I also enjoy using MATLAB for its versatility and interacting with Java and C# to develop quick customizable solutions.
This was my 3rd MATLAB contest and my past participation experiences definitely contributed substantially. Leap to me is a phase when competing theories merge to provide the best solution and the Statistics page in this respect is a great tool. Since I was short on time and Saturday Leap phase had already begun for my first attempt, I decided to merge Alfonso’s top entry and Nicholas’s leading entry. The submission returned expected results with an improvement of 0.44%. However, shortly Fel submitted his entry which jumped to the top spot with an improvement of 0.63%. Fel’s submission went a step further by including solvers by Victoria and his own, along with Nick and Alfonso’s. In my last effort to gain the lead I went through the Stats page again and incidentally found the entry by James White which had been overlooked till now. After tweaking a few parameters and discarding words with null weight I submitted Crazy Ivan on Kangaroo Jack and clocked an improvement of 1.11% which eventually won the Saturday Leap. Crazy Ivan is actually a crazy tactic rather than a name over here and Kangaroo Jack was a metaphor for Leap.
I always to get to learn a great deal of new things from the MATLAB contests and would like to thank the contest team and all the participants, for another enjoyable contest.
My actual name is David Felguera, I live in Madrid, Spain, and I work for the Airborne Radar Department at Indra. I'm also pursuing the Ph.D. degree at the Microwave and Radar Group of Polytechnic University of Madrid researching in Interferometric Radar Imaging techniques. I use MATLAB every day since 2004 for Radar Signal Simulation and Radar Algorithm Design.
In this contest I tried to develop my own solver during darkness and twilight. It was a very poor approach that only tried to fill the board row-wise making bogus words if it was worth to. Once daylight arrived I started to test other solvers and found that many of them followed similar approaches but performance was very dependent on the test case.
I really enjoy Saturday Leap, so I tried to win that price again sending the code I used to test the different solvers. That code selected the algorithm which gave a better result for each board. I think this started the multiple-solver nightmare, and i apologize for it :P. However, Amitabh was faster than me sending a significant contribution on Saturday which made the improvement of my first submission decrease. Later, he also added some other good solvers to the mix and made a huge improvement so i decided to wait till Sunday to summit the rest of my improvements.
In Sunday I tried to reduce the score filling areas that some of the solvers left empty and decreasing the cyclomatic complexity to the optimum one. My Sunday submissions were titled “Dead End Strategies” because I though that no significant improvement could be done following those same strategies and a mayor algorithm change were needed. As has been discussed, the scoring formula didn't promote making real crosswords so those new algorithms didn't show up in the leading entries.
I couldn't follow the rest of the contest with the same dedication. Nevertheless, I tried to take part in the mini-contests and in the final stage. The hidden queue feature has reduced the excitement in the final (tweaking) sprint which I loved. However, I think it gives more value to the contest grand price that, as in this contest, should always be won by people making significant result improvements.
Alfonso Nieto-Castañón is a returning player to the MATLAB Programming Contest. He was the Grand Prize Winner of the Color Bridge Contest .
This was a very interesting contest, in that there was no clearly optimal approach for a general solver and submissions tended to very sparsely fill the solution space focusing on narrow cases (fill-in as many words as possible, consider full-board cases, consider the two-word cases, etc.) The relatively low penalty term for incorrect crossings played an important role in facilitating that a simple solver that would attempt to fill-in as many words as possible, such as the one that won the Darkness phase, would perform comparatively well. This particular solver recursively partitioned the board into smaller segments, based on the actual score gain from either fully or sparsely filling a particular segment with same-length words compared to the score gain that could be expected from the remaining of the board. Since I felt a bit guilty about winning a “crosswords” prize without actually crossing a single word, I then devoted many coffee breaks to pondering how to tackle different word-crossing scenarios, and although I had a great time doing this and learning from the very interesting approaches everybody brought to the contest, by the end of the contest my latest try fell short from the stronger entries of Nick and others. As it is always the case this just left me craving for more, so I guess I will just have to wait a few more months for yet another great matlab contest!
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.
I have been taking part in Matlab Contest since 2006 very often being one of the most active players. Unfortunately I did not have much time to compete in Crossword Matlab Contest. I was just following it without making many submissions. However Ned provoked me to pay more attention to 1000 Node challenge daring everybody to beat me in this challenge. (It so happens that I was lucky to win several “short code” challenges before). Obviously, I was practically forced to participate.
Initially I started with the long code I liked, trying to shortened it. However I was not able to cut it below 1200 nodes. Then I switched to the best already short code. I checked “crosswords” created by it and found that it can be improved by inserting additional words into empty spaces. As a second step I decided to use known tactics of repeating code with random variations of words order. After those modifications my code became little bit too long. I needed to shorten it by approximately 80 nodes which I managed to do. Both modifications were successful, providing 160 and 20 point score improvement. Apparently it was enough to win the challenge with Fel and Amitabh Verma submitting their versions of significantly improved code.
Alan has been using MATLAB for about 15 years, originally learning at The Ohio State University where he was working on his degree in electrical engineering. He also has a Ph.D. in biomedical engineering from the University of North Carolina at Chapel Hill. Alan works as a Program Director for the Ohio Supercomputer Center in Columbus, Ohio and has regularly been an instructor at training classes on MATLAB for a variety of audiences.
Early in the Daylight phase of the contest, many people noticed that there wasn’t much incentive in the way the rules were setup for creating ‘traditional’ crossword type boards – the way the penalties were calculated were rather insignificant to the weights of the words. There was some discussion about this on the newsgroup thread, and I made the suggestion that the contest team hold a subcontest for the best solver that didn’t generate any boards with bogus words. They liked that idea and announced the minicontest a few days later. My approach to the contest was to generate a MATLAB script that sequentially grabbed each entry from the submissions webpage, executed it locally on my machine, and recorded the results of those that didn’t generate any bogus words. Via this technique, I was able to identify the best scoring ‘no bogus words’ solver up till that point was one submitted by Albert in the Twilight phase. I grabbed it and made a few tweaks in the hope of improving upon the time and node score in case anyone else discovered it as well. I submitted several variations a few minutes before the mini-contest deadline, and luckily for me (unlucky for him) Albert didn’t notice the deadline until it was too late and thus submitted an even further improved entry 5 minutes past the deadline. Likewise, Nick Howe had an even better entry, but he missed the deadline too (but that enabled him to win the Grand Prize). As Ned pointed out in the blog entry, I might have been destined to win since I originally came up with the mini-contest idea, and this does make it official (contrary to what some other players might think), that I’m not “Bogus”;)