Thread Subject:

MATLAB Programming Contest May 16-23

Hi,

I'd like to announce the next MATLAB Programming Contest. The contest
will start at 9AM EDT on May 16, and will run until 5 PM EDT on May 23.
You can access it by visiting:

  http://www.mathworks.com/contest

Tomorrow morning, we'll post the rules and open the contest queue for
entries.

These contests are open to anyone who's interested, and have always been
a lot of fun. They're a great way to learn new programming tricks, meet
other MATLAB programmers, and earn MATLAB-related prizes.

If you have any questions about the contest, feel free to post your
response on this newsgroup, or e-mail contest@mathworks.com.

We're looking forward to seeing your entry; good luck!

-- Nabeel Azar and The MATLAB Contest Team

Hi,


I am not clear if the optimization toolbox put the funfun in that direction or it comes with default. Please clear.


Kai

It seems that the problem is a special kind of "multidimensional scaling"..
Any expert in that field can suggest an effective algorithm to
solve MDS with the criteria function

sum |r(i,j) - d(i,j)|

where r(i,j)'s are the real distance matrices, d(i,j)'s are the
calcualted distance, and the summation is only over "valid" (i,j) pairs
only?

Hi,

> I am not clear if the optimization toolbox put the funfun in that direction or it comes
> with default. Please clear.

Only basic MATLAB is used, so you can't use functions in the
Optimization Toolbox. On a related note, all function-functions are
disallowed (we prohibit the use of EVAL and FEVAL; it's part of the
contest machinery's security)

-- Nabeel

Hi,

Sounds like you have an idea for an algorithm. Go ahead and submit it
and see how you do!

-- Nabeel


Hiu Chung Law wrote:
>
> It seems that the problem is a special kind of "multidimensional scaling"..
> Any expert in that field can suggest an effective algorithm to
> solve MDS with the criteria function
>
> sum |r(i,j) - d(i,j)|
>
> where r(i,j)'s are the real distance matrices, d(i,j)'s are the
> calcualted distance, and the summation is only over "valid" (i,j) pairs
> only?

Is the CPU time (on the website) measured in seconds?

Yes, it is measured in seconds using the cputime function. There is a
180 second limit on submissions.

Mike

Ghassan Hamarneh wrote:

> Is the CPU time (on the website) measured in seconds?

All of the contest results are stored in a MySQL database. I've written an m-file that uses the Database Toolbox to pull the information out of the database and into MATLAB. The m-file plots each passing submission as a blue dot and draws a red line representing the best-to-date score. When an entry makes a large enough percent-decrease in score, it circles the entry and adds the author's name. You can view this plot on the Contest Home page.


 <http://www.mathworks.com/contest/molecule.cgi/home.html>


We set up a cron job to fire up MATLAB and run this m-file every 15 minutes.


What insights can you gain by looking at this plot? How can it be improved? What other plots or numbers would be the most interesting to track as the contest continues? For some ideas, look at the Analysis sections from previous contests. Post your thoughts here.

So the early bird deadline is passed, and maybe let me write something
on the algorithms used.

I may have missed some, but there are at least four algorithms for
solving the problem.

1. One is nbody ode-like solver, where each iteration the positions
of the molecules is updated iteratively. This seems to get stuck in
some local minimum.

2. One simple method that does pretty well is to randomly pick a point,
generate a random location, and accept that if the strain is reduced.

3. One is to first sort the points in descending order of maximum
distance, and then search a grid of points exhaustively to find the optimal
location of the molecules. One may then choose to refine the results
by some means.

4. One is to put every points at the center and then each molecule
"move" away gradually to satisfy the length requirement.

The site (or parts because the Contest home is running well) is very slow. Posting an entry lasts minutes.
Is there a problem ? (Or does my computer have a problem ?)

Hi Stijn,


> The site (or parts because the Contest home is running well) is very slow.
> Posting an entry lasts minutes.
> Is there a problem ? (Or does my computer have a problem ?)


It is slow right now. I'm not sure why (it may just be a lot of web traffic), but we'll take a look at this and try to get it fixed as soon as possible.


-- Nabeel

The problem of the slow reaction is solved, ..., luckily.


Stijn

I must be missing something here. The cputime is machine dependent, right? I downloaded the number 1 "solver.m", and it takes "runcontest.m" less than 3 seconds to run on my machine.


Lingji


Michael Thomas wrote:
>
>
> Yes, it is measured in seconds using the cputime function. There is a
> 180 second limit on submissions.
>
> Mike
>
> Ghassan Hamarneh wrote:
>
>> Is the CPU time (on the website) measured in seconds?
>
>

I believe the discrepency you are experiencing is due to the fact that the download only has a small fraction of the puzzles in the master testsuite, so when you run on your machine, the
time will be much less than your submission to the contest.

Also, cputime is independant of the machine, but the amount of time it takes for a given code to run will vary from machine to machine.

Mike

Lingji Chen wrote:

> I must be missing something here. The cputime is machine dependent, right? I downloaded the number 1 "solver.m", and it takes "runcontest.m" less than 3 seconds to run on my machine.
>
> Lingji
>
> Michael Thomas wrote:
> >
> >
> > Yes, it is measured in seconds using the cputime function. There is a
> > 180 second limit on submissions.
> >
> > Mike
> >
> > Ghassan Hamarneh wrote:
> >
> >> Is the CPU time (on the website) measured in seconds?
> >
> >

Hello,


I want to react on what is written in the mid-contest analysis. A problem coming to a good algorithm is that it seems there are a lot of problems where the solution is bounded very much by the boundary. Therefore a "nice algorithm" which works well for "nice problems" is easily disturbed by problems which don't fit at all inside the boundary.
I think that is one of the reasons there are not much good algorithms with "nice results" for "nice problems" as shown in the analysis. It is also stated that it is surprising that there are no "black lines" (which are green in the latest 'runcontest'-routine). A reason is that it is more worth working on the "big strains" than getting a almost zero to zero.


Besides trying to improve other algorithms (which I do much more now than last year), I'm still working on an own (for which I also did some submissions). So this "message" don't say that I'm disappointed. I just wanted to react.
It is much "nicer" to "be" in the contest, then just working on your own on a good algorithm if there are not much 'stimuli' to believe that you are working in the right way. So I can't hold myself of doing those small improvements, although it can mean that I don't get my algorithm reay.


And a last statement. The current algorithm seems to be so lucky with the random set generated by Matlab. Even adding a dummy random, gives a much worser result. This makes it also more difficult to do "direct improvements".


Regards,
Stijn

I also have a similar feeling. A simple arithmetic average of the
strains put strong weights on those "large" problems. That does not
look a very good performance metric IMHO. Maybe a weighted average
works better, although it will be controversial on
how the weights should be selected.

Stijn Helsen <SHelsen@compuserve.com> wrote:

> I want to react on what is written in the mid-contest analysis.

[ snip ]

A comment to the US border map of the mid-contest:
There must be infinitely many solutions with zero
strain to this problem. It is like laying a chain on
a floor. That can be made in very many ways without
causing strain to the links. One of many ways is to
lay it so it resembles the border-line of the US. I
don't think it is a good test problem.


Regards.

TA wrote:
>
>
> A comment to the US border map of the mid-contest:
> There must be infinitely many solutions with zero
> strain to this problem. It is like laying a chain on
> a floor. That can be made in very many ways without
> causing strain to the links. One of many ways is to
> lay it so it resembles the border-line of the US. I
> don't think it is a good test problem.
You are right when you take only the distances between successive border points. But what is tested here is a full matrix of all the distances between the points. (Otherwise it would be rather (I mean veryvery) strange that a couple of algorighms had solutions with some resemblences, or has the US a "logical shape"?)
Stijn

I must admit the mid-contest analysis was a little unfair because we picked "pretty" examples that aren't representative of the test suite at large. We were looking for ways to show the differences between various entries, and pretty examples are much easier to visualize, even if they aren't representative of the test suite (although there are some zero strain examples in the test suite). Anyway, please consider the analysis light entertainment more than anything else.


It's true that our arithmetic average of the strains means that large problems dominate the score. Believe me, we argued a lot about what the scoring metric should be. We discussed using a more "proper" engineering definition of strain, that is a percentage change in the natural length of the connecting rod


  (measured length - preferred length)/(preferred length)


What we call "strain" in the problem definition is really more like what an engineer would call stress (where the force is caused by Hooke's Law: F = -kx), since we use absolute distance rather than percent change. But in the end you have to optimize on something, and whatever you choose will dominate your approach. If we used percent change instead, then the solution would be dominated by the shorter segments. And the competition is so fierce in this contest, that even finding one small improvement in one small part of the test suite would make a big difference.


The biggest problem we face every time we run a contest is coming up with a good problem (and test suite). If you think you have a good idea for the next contest, please send it to us. We're always on the lookout for something new. Thanks for joining in the fun. We love seeing all the activity on the site.


-Ned Gulley
The MATLAB Contest Team


TA wrote:
> A comment to the US border map of the mid-contest:
> There must be infinitely many solutions with zero
> strain to this problem.

Actually, the queue was fine...it was just bogged down. There were close to 70
entries between 4 and 6 this evening, and the server only runs one at a time. If an
entry times out, then there is a few more minutes to reboot the machine in addition
to the 3 minutes to run most entries.

We realize this can be frustrating, but there is no way around it. Thanks for
keeping on me about the queue, and if it looks like it is hung, don't hesitate to
throw another message my way. Oh, and thanks for playing.

Mike

Yi Cao wrote:

> The queue has been held again for more than a hour. Please check and sort it out.

about the contest, what does this mean:


Error using ==> filefilt Unable to find "C:\home\contest\submission.m".


i see this in alot of entries, and don't know why.

i am reposting this question. can someone TMW answer this:


> about the contest, what does this mean:
>
> Error using ==> filefilt Unable to find "C:\home\contest\submission.m".
>
> i see this in alot of entries, and don't know why.

It is weird that a solution I posted yesterday had a very nice solution to the usborder problem and yet the current best solution looks terrible on that problem. I think there are some characteristics of the test data set that we haven't discovered yet. Probably something simple. Or maybe it is just a waste of time to get too close to the optimum.

Sorry for the slow reply. This error occurs when your code fails to parse
which indicates invalid syntax somewhere in the code. Trying to run the
entry (in solver.m) on your local machine against the sample testsuite should
give you a better indication of what the exact problem is.

me wrote:

> i am reposting this question. can someone TMW answer this:
>
> > about the contest, what does this mean:
> >
> > Error using ==> filefilt Unable to find "C:\home\contest\submission.m".
> >
> > i see this in alot of entries, and don't know why.

me wrote:
> about the contest, what does this mean:
>
> Error using ==> filefilt Unable to find
 "C:\home\contest\submission.m".


This means that MATLAB cannot parse the entry, i.e. , the entry is not valid MATLAB code. For example, there might be an "if" with no "end". That means the entry was never tested before being submitted. You can see a more detailed error by trying it out for yourself.


Making this error message more descriptive is on our list of improvements to make for the next contest.


Thanks for playing.

How about posting the entire test suite so we can check our queued entries?

I also think it is a good idea to post the test suite after the contest...
Actually, it would be nice if the server can keep running for a while
despite the contest is over, since some contestants may still be interested
in cracking the 7800 barrier.....

Mike Keenan <jxkeenan@aol.com> wrote:
> How about posting the entire test suite so we can check our queued entries?

Hello,
I have a proposal for getting faster response.
I think it is a (very) good idea to do the tests on one computer. But is it not possible to do the filefilter by another computer. That computer takes the list and filters out the routines with errors. I see the following advantages without much disadvantages (apart from the additional hardware and programming efforts..)
- When you make an error you can see it faster. (testing with the testsuite does not guarantee that there are no errors)
- the waiting list is shorter
- the "working-computer" has less work


Isn't this possible ?


But, ...., testing our nerves could be a reason for not doing it ?


Regards,
Stijn

I also have a question.
During the contest I use the "Edit-option" of submissions for copying the program to get a nicer layout. (Others just copy from the web-page, but then you get the long and ugly layouts.)
Could it be possible for getting a possibility to get the codes (after the contest, but maybe also an option that could be used during the contest).
(After the earlier contest I've made a (matlab-)program to parse html-files to get the code out of it, but this is not the easiest way.)


One possibility that I see is that you an option (for example next to the submission name) a "direct-text"-option (could be a small "file-icon"). That option is then a link to a text-file containing only the program. It could be read in the web-browser, or you could do a "save link to...".


Could this be a possibility ?


Stijn

Watching the queue and already processed submissions I come to another question. Is it possible to see the sumissions sorted in time? The submisions with errors (filefilt or runtime) are sorted, but the others not (and sorting it by "ranking" is of course the most important).


(?maybe you could sell a CD with the submissions in the last five contests? as a "fifth-contest-celbration-CD" ?)


Stijn

Many errors detected by the server were produced by direct editing with the web editor without checking in MATLAB. Would it be possible to run the small public test suit in a MATLAB web server. It will only take a few secend to get the result to rule out most editing errors. This will also provide an example to demonstrate the usefulness of the product.

The problem we were trying to solve here is an inverse one: find the positions given the distances (the corresponding direct problem is to find the distances given the positions, which is -as usual- far more easier to solve...) It is well known that inverse problems have a tendency to be ill-posed: the solution may not exist at all, or -if it exists- it may not be unique, or it may depend on the data (distances in this case) in a non-continuous way.


The code i wrote uses a conjugate-gradient algorithm to minimize a (nonlinear) cost functional on the total strain. It converges just fine for zero-strain problems (as those presented in the mid-contest analysis, namely the triangles and the US map) as well as for some non-zero-strain problems (like those with kd=ones(N)-eye(N), with N atoms in the molecule). However, it does not perform very well with the test suite (average strain 2157).


It seems that the test suite contains some carefully chosen difficult situations with local minima that trap the optimization. There are also the too-small-box problems, where all the atoms move right away to the borders -or corners- as the available space is too confining. Maybe the all-corners cases should be treated with some different approach (e.g., formulating it as a discrete problem, with possible positions only at the corners -had no time to try it) and the borders with a mixed approach: one-dimensional displacement, plus a discretized problem to choose the right side.


I know that it is frustrating to develop an algorithm that works well on "normal" cases (even better that the winning entries) but fails on the average. On the other hand, this is the nature of inverse problems: there are always unpleasant surprises. I think that the test suite was designed with this in mind. Although i feel that an algorithm's capability of solving "normal" cases was not given enough bonus (correspondingly, an algorithm's failure on those cases was not given enough penalty), i am probably wrong. It would be very interesting and helpful to get the full testing suite now that the contest is over, together with some comments from the contest team on how they chose the problems in it.


This contest gave me the idea for a hands-on tutorial on applied inverse problems; i thank the contest team for that!


MR Keenan wrote:
>
>
> It is weird that a solution I posted yesterday had a very nice solution to
> the usborder problem and yet the current best solution looks terrible on
> that problem. I think there are some characteristics of the test data set
> that we haven't discovered yet. Probably something simple. Or maybe it
> is just a waste of time to get too close to the optimum.
>

> But, ...., testing our nerves could be a reason for not doing it ?
If the processing stops a (long) while, it starts being a really big test..... ;-)


Stijn

I have put the full contest test suite into the zip file on the File Exchange
(fulltestsuite.mat). Enjoy... and thanks again to everyone who participated in
the contest.

Mike

Mike Keenan wrote:

> How about posting the entire test suite so we can check our queued entries?

Hi Stjin and Yi Cao,

Thanks for the feedback regarding improving the contest experience. It's
always beneficial for us to be aware of the features that users like or
dislike. We will keep these suggestions in mind when developing future
versions of the contest.

Min


"Yi Cao" <y.cao@cranfield.ac.uk> wrote in message
news:eeadd04.30@WebX.raydaftYaTP...
> Many errors detected by the server were produced by direct editing with
the web editor without checking in MATLAB. Would it be possible to run the
small public test suit in a MATLAB web server. It will only take a few
secend to get the result to rule out most editing errors. This will also
provide an example to demonstrate the usefulness of the product.

Just a question :
What are possible reasons for differences in average strain calculated by
myself (with the full testsuite) and by the Mathworks ? The differences are
small (for example Really hopeless gives 2030.508 here and 2030.317 at your
side) ? Is it the Matlab version ?
(I'm using the newest available for Mac : 5.2.0)


Just curious...
Stijn

Hello Stijn:


Here's a trick that will let you see all the entries sorted by time. Click on
the "Search for an entry" link, and then instead of entering a search term,
simply press the button labeled "Search for an entry". This returns a long list
with all the entries, with the most recent entries at the top of the list


-Ned Gulley.


Stijn Helsen wrote:
> Watching the queue and already processed submissions I come to another
> question. Is it possible to see the sumissions sorted in time? The
> submisions with errors (filefilt or runtime) are sorted, but the others
> not (and sorting it by "ranking" is of course the most important).
>
> Stijn