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 dij, 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.
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.
function xy = solver(kd,bx)A few points to keep in mind about this function and your contest entries:
function xy = solver(kd,bx)
To test this function using the testsuite we've included in the zipfile, at the MATLAB prompt you can call the "runcontest" function:
>> [results] = runcontestThe 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.
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.
The following are prohibited:
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: