Molecule - Rules

You are trying to model the structure of a molecule (which for the sake of simplicity will be limited to two dimensions). You have been given a collection of plastic connecting rods that represent the distance between pairs of atoms in the molecule. Your job is to fit the connecting rods together as well as possible into a consistent two dimensional shape.

This isn't always possible, so some of the lengths you specify will be slightly longer or shorter than their preferred length. Stretching or compressing the connecting rods is legal, but it causes strain, and you want to minimize strain as much as possible.

The strain on the rod between any two atoms is defined as the absolute value of the difference between the preferred distance and the actual distance between atoms i and j.

The preferred lengths between points will be given to you in a distance matrix like so

        [  0   4  -1   3 ]
   d =  [  4   0   2  -1 ]
        [ -1   2   0   7 ]
        [  3  -1   7   0 ]

The preferred distance between atom i and atom j is d_ij, so the matrix is symmetric and the main diagonal is zero. A -1 in the ij location signifies that there is no connection specified between the two atoms in question, and no strain will result, whatever the final orientation of atom i and atom j. In the matrix above, atoms 1 and 3 are free to move relative to one another without penalty.

Finally, you need to put your completed model inside a box for shipping, so none of the points can fall outside the box limits provided.

Inputs and outputs

Your function, which should always be named solver.m, should have the following syntax:

  xy = solver(d, bx) 

where d is the corresponding preferred distance matrix, and bx is the four-element bounding box in [xLow xHigh yLow yHigh] form. xy should take the form of an n-by-2 matrix where each row contains first the x and then the y position of the center of a circle. There should be as many rows in xy as there are rows in d.

Remember: the preferred distance matrix d is not necessarily a "proper" distance matrix. It may be inconsistent. For instance, the preferred distance between all pairs of atoms may be identical, which becomes impossible to manage for more than three atoms. So zero strain is often not possible.

Each entry must complete the entire test suite in less than three minutes, or it will fail. The faster it completes the suite, the lower (better) the score.

Developing your entry

Let's take a closer look at the example included on the MATLAB Central File Exchange. If you download and uncompress the zipfile, you will have the files used below.  The first line in the solver.m file is

function xy = solver(kd,bx)

A few points to keep in mind about this function and your contest entries:

• The function has the proper signature

function xy = solver(kd,bx)

• The function returns a properly formatted Nx2 matrix of points

To test this function using the testsuite we've included in the zipfile, at the MATLAB prompt you can call the "runcontest" function:

 >> [results] = runcontest

The first column of results will contain your "score", that's the total strain, and the second column will give you an estimate of the runtime. 

It's also useful to visualize what your entry is doing; you can do this by passing runsuite an input of 1:

 >> [results, message] = runcontest(1)

After your entry has completed each test in the testsuite, a graphical display of the result is shown. After your entry has completed each test in the testsuite, a graphical display of the gameboard is shown. Press any key to continue viewing displays of the subsequent tests.

Scoring

Here are the factors, in order of importance, that affect your score:

1. Total Strain
2. Runtime of your code

This list indicates relative weighting; it's possible that very strong performance in a less important area can make up for slightly weaker performance in a more important area. Your code will time out and fail after 180 seconds, so beware of combinatoric explosions in your algorithm.

Good luck!

Collaboration and editing existing entries

Once an entry has been submitted, it cannot be changed. However, any entry can be viewed, edited, and resubmitted as a new entry. You are free to view and modify any entries in the queue. The contest server maintains a history for each modified entry. If your modification of an existing entry improves its score, then you are the "author" for the purpose of determining the winners of this contest. We encourage you to examine and optimize existing entries.

We also encourage you to discuss your solutions and strategies with others. We have provided a link to an online chat room so that you can chat about the contest and see who else is watching. You can also post to a comp.soft-sys.matlab thread that we've started from our newsreader.

Fine Print

The allowable functions are those contained in the basic MATLAB package available in $MATLAB/toolbox/matlab, where $MATLAB is the root MATLAB directory. Functions from other toolboxes will not be available. Entries will be tested against MATLAB version 6.1 (R12.1).

The following are prohibited:

MEX-files
Java commands or object creation
eval, feval, etc.
Shell escape such as !, dos, unix
Handle Graphics commands
ActiveX commands
File I/O commands
Debugging commands
Printing commands
Simulink commands
Benchmark commands such as tic, toc, and flops

FAQ

Check our FAQ for answers to frequently asked questions about the contest.

About named visibility periods

Contests are divided into segments where some or all of the scores and code may be hidden for some users. Here are the segments for this contest:

• Darkness - You can't see the code or scores for any of the entries.
• Twilight - You can see scores but no code.
• Daylight - You can see scores and code for all entries.
• Finish - Contest end time.


Download Sample Code