• MATLAB Contest Winners
• Molecule Contest Analysis
• Mid-Contest Analysis

Mid-Contest Analysis

Monday, May 20, 5:00 pm

Below is an analysis of some of the most significant entries submitted to the MATLAB Molecule Contest so far.

Overview

• Test case: Triangles
• Early entries
• Later entries
• The current leader (as of May 20, 5:00 pm)
• Test case: U.S. Map
• Update: The Worst Entry Ever!

Test case: Triangles

To help visualize the submissions and their results, we have created a test case with six points in a triangular arrangement.

% Set up the six points' locations.
x1 = [0 1 0.5];
y1 = [0 0 sqrt(3)/2];
x2 = x1*.5 + .25;
y2 = y1*.5 + sqrt(3)/12;

x = [x1 x2];
y = [y1 y2];

% Create matrix of ones and zeros to indicate linkages.
a = [ones(3) eye(3); eye(3) ones(3)];

% Plot points and number them.
gplot(a,[x' y'],'k')
axis equal
axis off
set(gcf,'Color','white')
for i = 1:length(x)
  text(x(i),y(i),[' ',num2str(i)])
end

% Create bounding box.
bx = [0 1 0 1];

% Create distance matrix for solvers.
[XY1,XY2] = meshgrid(x,y);
kd = sqrt((XY1 - XY1').^2 + (XY2 - XY2').^2);
kd(a==0) = -1;

The plot above is a zero-strain solution to the problem, although rotated and reflected solutions are equally correct.

Note that this test case has a zero-strain solution; not all our test cases have such a solution.

Strain in solutions returned by solvers is indicated in the following way:

• compression: blue, thicker lines
• expansion: red, thin lines

Brighter red or blue lines indicate larger degrees of compression or expansion. Only segments with zero strain are marked in black.

Early entries

One of our early leaders was 'monti-carlo' by author 'abc' (with the mysterious e-mail address def@ghi.jkl).

runcontest('solver6147',0,kd,bx);

This entry's solver was incorporated in many later entries as subfunction SOLVER1.

The entry 'sloppy n-body #2' by author 'pest' was a dramatic improvement in the early going, beating all previous entries by 400 points.

runcontest('solver6174',0,kd,bx);

In some cases 'sloppy n-body #2' performs as well as or better than the current leaders.

MR Keenan's 'Pretty Silly4' was the first entry to break the 8000 point barrier.

runcontest('solver6266',0,kd,bx);

Later entries

Bert Jagers' 'ImprovedGuess 2.0' took the lead in the mid-afternoon on Friday. The format of this entry (a second solver using the output of 'monti-carlo' and refining the result through a MESHGRID) has been copied and used by the majority of entries since then.

runcontest('solver6337',0,kd,bx);

The winner of Friday afternoon's Early Bird prize was Yi Cao, who tweaked 'ImprovedGuess 2.0', increasing its speed. Its results (using the same random seed) are identical to Bert Jagers' entry, earning it a lower score.

Yi Cao later contributed 'ComplexNoFFT', which takes advantage of the ABS command on complex numbers (which returns the same values as the distance formula). This simplification saved 15 seconds. Again, its results using the same random seed are identical to Bert Jagers' entry.

runcontest('solver6515',0,kd,bx);

The current leader (as of May 20, 5:00 pm)

The current leader is the winner of our last MATLAB Contest, Stijn Helsen. His entry is called 'MadMarkSH01' in honor of another author whose submission improved SOLVER1 and the overall performance.

runcontest('solver6669',0,kd,bx);

Note that in this test case Stijn's solver does not perform as well as Bert Jagers' earlier entry. Note also that there is plenty of room for improvement in this contest, even with such a small test case.

Test case: U.S. Map

The algorithms' performance on larger test cases can make or break a score. For this test case, we used the "Traveling Salesman" demo (TRAVEL.m), which contains a map of the United States. Let's use this map to determine how these entries do with larger problems.

% Load the map, display it, and prepare the associated distance matrix.
load usborder
plot(x,y,'.-')
bx2 = [0 1.5 0 1];
line(bx2([1 2 2 1 1]),bx2([3 3 4 4 3]),'Color','black')
axis(bx2)
axis off

[XY1,XY2] = meshgrid(x,y);
kd2 = sqrt((XY1 - XY1').^2 + (XY2 - XY2').^2); 

Let's try 'monti-carlo':

xy = solver6147(kd2, bx2);
plot(xy(:,1),xy(:,2),'.-');
line(bx2([1 2 2 1 1]),bx2([3 3 4 4 3]),'Color','black')
axis(bx2)
axis off

Ouch! This demonstrates that while a method like 'monti-carlo' may work adequately and quickly for small sets, it doesn't do so well with large ones.

Here's 'sloppy n-body #2':

xy = solver6174(kd2, bx2);
plot(xy(:,1),xy(:,2),'.-');
line(bx2([1 2 2 1 1]),bx2([3 3 4 4 3]),'Color','black')
axis(bx2)
axis off

Not much better. Again, the nature of this method makes it very useful for small sets, but not so good for large ones.

Take a look at 'Pretty Silly4':

xy = solver6266(kd2, bx2);
plot(xy(:,1),xy(:,2),'.-');
line(bx2([1 2 2 1 1]),bx2([3 3 4 4 3]),'Color','black')
axis(bx2)
axis off

Things are getting better; it is now possible to vaguely see the borders coming into focus.

What about 'ImprovedGuess 2.0'?

xy = solver6337(kd2, bx2);
plot(xy(:,1),xy(:,2),'.-');
line(bx2([1 2 2 1 1]),bx2([3 3 4 4 3]),'Color','black')
axis(bx2)
axis off

Wow!! This entry really does an amazing job! (Check out Michigan, Maine, Washington, and Florida.)

Let's try our current leader, 'MadMarkSH01':

xy = solver6669(kd2, bx2);
plot(xy(:,1),xy(:,2),'.-');
line(bx2([1 2 2 1 1]),bx2([3 3 4 4 3]),'Color','black')
axis(bx2)
axis off

This entry does a decent job, but is not quite able to work with the West Coast. Its strain score is over five times larger than the score of 'ImprovedGuess 2.0'. Still, it is the current leader, so it must be doing a lot of things right!

One thing we found surprising in this Mid-Contest Analysis is that in no entry we investigated were there any "black" lines -- there were no places where strain became zero. In these two examples, it is theoretically possible to get exactly zero strain for all connections, but no entry can yet do it. Perhaps yours will be the first...?

Update: The Worst Entry Ever!

On Monday between 3 and 6 pm, we issued a Mini-Contest challenge to come up with the entry yielding the highest possible score. The worst (passing) entry submitted within that time would receive a prize. The winner was Bert Jagers, whose 'ImprovedGuess 2.0' has been a key innovator. Few changes were made to produce 'ImprovedGuess 2.0 in reverse II'. Let's see how it does with the triangle data:

runcontest('solver6690',0,kd,bx);

If you're wondering where all the points went, points 1, 2, and 3 (the outer triangle) are placed at the identical location to maximize the strain between them. Point 5 is placed in the upper left corner of the box, while points 4 and 6 are placed in the lower right corner of the box. This maximizes the strain between 4 and 5 and between 5 and 6, and even causes a strain between 4 and 6.

Let's see how this entry handles the U.S. map:

xy = solver6690(kd2, bx2);
plot(xy(:,1),xy(:,2),'.-');
line(bx2([1 2 2 1 1]),bx2([3 3 4 4 3]),'Color','black')
axis(bx2)
axis off

Where is the map, you wonder? Every point in the original map has been pushed into either the lower left or upper right corner of the box. To visualize this entry better, here is a picture of the original map. The points moved to the lower left corner will be marked red, and the points moved to the upper right corner will be marked green.

whichCorner = any(xy>0,2) + 1;
plot(x,y,'-','Color',[.7 .7 1])
hold on
plot(x(whichCorner==1),y(whichCorner==1),'ro','MarkerFaceColor','r');
plot(x(whichCorner==2),y(whichCorner==2),'go','MarkerFaceColor','g');

Although not universally true, in most areas of the map consecutive points are mapped to opposite corners to maximize strain. While we're not sure if this is the worst possible placement for these points, it is certainly extremely far away from being a map of the United States. For this, we salute you, Bert.

Good luck to everyone, and see you in the queue...

The MATLAB Contest Team