MATLAB Programming Contest Blog
November 8th, 2011
Vines Mid-Contest Analysis
This season’s mid-contest analysis is from my coworker Lucio Cetto
I ran a small analysis over the solvers that were among the first five positions at the end of Twilight. The leaders at that time were Nick Howe (Revenge of Antichaff), Alfonso Nieto (test05_tweak10), Robert Macrae (The Fragrant Honeysuckle), Kurt Janssens (v 11), and Martin F (Sixth shot).
First, let’s look at the solutions given by the solvers to the original Fifteen puzzle. My initial configuration placed all odd number at the top and even numbers at the bottom. I had to change the original puzzle a little because Kurt’s solver choked if I passed an initial board with a zero. I replaced that piece with a 16. Nick’s solution was able to interleave the even and odd numbers properly. Notice that there was a lot sliding and few pieces were blown out. Alfonso and Kurt seemed to concentrate on creating their vines and cared less about moving pieces. Robert and Martin preferred to move all the high value pieces to a given region before building a simple vine.
Let’s scale the problem a little bit. In my second board, I placed random pieces in a slightly different configuration. Higher value pieces are toward the bottom of the board. Note the excellent job by Alfonso’s solution – it appears to have the right balance between moving pieces and growing the vine. In a board like this, on one side you need to do a lot of sliding in order to bring the monotonically increasing pieces together. On the other side, you want to minimize sliding because “easy” sliding requires blowing pieces out that could eventually be part of your vine. More difficult sliding, like the one that actually occurs in the real fifteen puzzle where you have restricted space, is much harder to program. In this situation, Nick’s solver changed mode and operated more like Robert’s and Martin’s solutions. It moved pieces to the edges to build the vine. Note that Kurt’s solver did not move any piece at all, yet his strategy of focusing on growing a high value vine permitted Kurt to be among the leaders.
Finally, let’s see how the solvers behave with a random board with only ones and twos. Nick’s solver apparently changed strategy again. The new operating mode refuses to move the pieces. The solution is very similar to Kurt’s solver. Again, note that non-mover solvers are doing fine in several of the problems. Alfonso’s solvers seem to have found the right combination between moving and growing the vine, while Robert’s and Martin’s move all the high value pieces to the edges again. Notice the best scoring solvers left most of the twos out of the vine.
In closing, here’s a quick look at results of the current leader, at the time of writing this post.