Molecule Contest 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

function xy = solver(kd,bx)

• 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

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)

Scoring

1. Total Strain
2. Runtime of your code

Good luck!

Collaboration and editing 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 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