MATLAB Programming Contest Blog
November 10th, 2004
Contest Analysis ‘Furniture’
Contest Analysis ‘Furniture’
By Lucio Cetto
In this analysis we take the winning solver (‘asdf1′) and test it with some interesting cases. Some of these have similar characteristics to those in the test suite. Others are taken from real life examples.
Here we have three columns. The middle one has heavy blocks (red) while the other two have light blocks (blue). We need to swap the two outer columns. In the middle column there is only one lightweight block. A good solution will break the middle wall at this point and pass the swapping blocks through it. We observe that ‘asdf1′ opens the gate at the correct location, but it actually moves two blocks in the wall. The outer column blocks manage to get to their targeted positions, even though there is not much space. The solver deals with this by moving some blocks to the edges to make some space.
Your car is blocked in the parking lot and you need to get it out, preferably by moving only a few cars. Around this lot there is a brick wall which would be very expensive to remove and rebuild (but always possible). The lot is packed with cars. It is interesting to note that the solver is able to move blocks which are already in their targeted (final) position in order to make space for others that need to move out. The last is achieved even with several levels of blocking cars, and most of the times without needing to destroy the walls. We didn’t even include this kind of problem in the test suite because we though it was too difficult, given the high density of the lot. To our pleasant surprise it did not take long for the submitted entries to solve problems like this.
Even so, the winning entry does not always makes the correct decision. Sometimes it prefers to pass the car through the wall rather than move the blocking cars.
Several of the problems in the test suite followed the house layout pattern. We put one or two walls (columns or rows) of heavy blocks in the middle of the box, and we left few light blocks within these walls which represent doors. The challenge was to move one or more pieces of furniture from one room to another. Most of the time the solver had no problems figuring out the doors and moving the furniture through them. We found few cases in which the solver would need to open more than two doors, and in these cases it preferred to walk through the wall.
Most of the time ‘asdf1′ finds the correct path in a maze, even when there is more than one block moving through the maze. Again, this type of problem was not in the contest test suite, but it presented no difficulty for ‘asdf1′. This problem is interesting because in order to find the optimal solution, the moving block must sometimes travel away from its targeted position. There are few cases in which the solver moves the walls of the maze, even if it was not necessary. In the second example, there is sufficient space for the blocks to cross-over in the small area (4:5,4:5), but the solver decided to move some walls.
Finally when we tried to increase the density of blocks in the problems, we found that the solver generally finds a solution when the proportion of occupied area is below 90%. Beyond this limit, the solver tends to break at the ‘matrixxolver’ sub function. To create this type of problems we randomly placed the blocks over the available space. Weights were also drawn randomly from one or more distributions with different characteristics (usually uniform or normal distributions). Finally we randomly selected which ones will move. Sometimes all were required to move, and other times only the light blocks were required to move. Most of the problems in the test suite were very similar to this pattern, but in the contest we imposed a density threshold of around 50%, since otherwise some participants may have been discouraged by not being able to create a passing entry.
The performance of the winning algorithm is truly impressive. Our page shows only one grand prize winner, but clearly many people contributed to the winning entry. We hope all of you who participated in the contest enjoyed it, even if you didn’t win a prize. Happy MATLAB programming, and we hope to see you all in the next contest.
Published with MATLAB® 7.0.2