Thread Subject:

MATLAB Programming Contest: April 2 - 9, 2003

The next MATLAB Programming Contest starts tomorrow at 9 a.m. EST and will
run until 5 p.m. EST on Wednesday, April 9. Topics and rules will be posted
to the MATLAB Contest site tomorrow.

http://www.mathworks.com/contest

These contests are a great way to learn new programming tricks, as well as
show off the ones you have. If you are curious to find out more about past
MATLAB contests, visit the link above. Past contest pages are listed under
the title "Previous Contests" on the main page.

Please use this thread to talk about the contest, strategies, or to ask
related questions. If you have an "administrative" type of question that you
don't feel applies to anyone else, e-mail us at contest@mathworks.com.

The contest will start tomorrow so be sure to set aside some time during the
week to watch the contestants at work or to submit an entry. We'll be
holding several mid-contest prize giveaways of MATLAB t-shirts, key chains,
and mugs so don't wait until the last minute to participate. Good luck!

Min Poh
The MATLAB Central Team
The MathWorks, Inc.

with "all the short straight-line distances are equal to one unit", I
presume it is safe to assume that all x,y will be integers (data on a
uniform rectilinear grid)?


/Ghassan

That only applies to the simple example given in the Rules. Take a
look at the testsuite.mat file provided in the download zip file, to
see a sample of the x and y coordinates. There is no constraint to
be integers.


Mike


> with "all the short straight-line distances are equal to one unit",
I
> presume it is safe to assume that all x,y will be integers (data on
a
> uniform rectilinear grid)?
>
> /Ghassan
>

Hello,
The example in rules seems has problem. The length from D to home is
sqrt(5)+1 = 3.2. The truck only has 3 units of gas in D. The rule is
"One unit of gas will move your truck exactly one unit of distance."
How can the truck returns to home from D?

Hello Duan
sqrt(5)+1 is the distance from C to Home passing by D


1 for C to D
sqrt( 1^2 + 2^2) for D to home


Duan wrote:
>
>
> Hello,
> The example in rules seems has problem. The length from D to home is
> sqrt(5)+1 = 3.2. The truck only has 3 units of gas in D. The rule is
> "One unit of gas will move your truck exactly one unit of distance."
> How can the truck returns to home from D?
>

The distance from D to home is only sqrt(5) = 2.2, so you do have
enough fuel to get home. The distance of sqrt(5)+1 in the rules is
in reference of the trip from C to D to home.


Mike


> Hello,
> The example in rules seems has problem. The length from D to home is
> sqrt(5)+1 = 3.2. The truck only has 3 units of gas in D. The rule is
> "One unit of gas will move your truck exactly one unit of distance."
> How can the truck returns to home from D?
>

For the general use:


the scoring constants k1,k2,k3 are the same as the last contest:


1,1/7,1/20


(found by using LSQCURVEFIT )


The constant score contours can be viewed with:


% plot scoring constant contours


[result,runtime] = meshgrid(1700:10:3500,0:180);
k = [1 1/7 1/20];
score = k(1).*result+k(2).*exp(k(3)*runtime);
contour(1700:10:3500,0:180,score,20);
xlabel('result');
ylabel('run time');

Min Poh wrote:
>
>
> The next MATLAB Programming Contest starts tomorrow at 9 a.m. EST
and will
> run until 5 p.m. EST on Wednesday, April 9. Topics and rules will
be
> posted
> to the MATLAB Contest site tomorrow.
>
> <http://www.mathworks.com/contest>
>
> These contests are a great way to learn new programming tricks, as
well as
> show off the ones you have.


I disagree that "these contests are a great way to learn new
programming tricks." They are much better at promoting the
development of poor programming practices. Given the lack of
comments, submitted code is next to impossible to understand unless
one takes the time to decipher what each line does and what the
overall strategy of a given solution is. Like most folks, I have a
day job that does not allow me the time to be an active observer of
the contest, let alone be a viable contributor. Are the contests fun?
Yes, but let's not promote them as being something they are not. If
you were managing the development of MATLAB code, would you encourage
your programmers to adopt the programming practices demonstrated by
these MATLAB contests?


The only thing I've learned about this contest so far is that


xy = (x-x(1)) + 1i*(y-y(1));


is better than


xy = (x-x(1)) + i*(y-y(1));


That is, 1i tells the MATLAB interpreter immediately that one wishes
to multiply by sqrt(-1), whereas using i forces MATLAB to first check
to see if i has been redefined as a variable other than sqrt(-1).

Duane,


Thanks for, once again, pointing out your opinion that the MATLAB
Contest is more for fun then learning. I would like to point out,
thou, that you have written several books on MATLAB programming (good
ones I might add) and would thus expect you to be a MATLAB EXPERT!
So I would expect you in particular to learn very little from these
contests (but I am glad you learned a new trick). As for others there
is the opportunity and possibility of learning.


Although I disagree with you on how much YOU will get out of these
contests, I do agree that it is getting harder and harder for less
experienced users to gain any knowledge from the contest. In addition
to the poor commenting of code, the shear volume of entries can be
overwhelming. Because of this and other usability issues (I will get
into this in a second) I have been tossing around the idea of
creating some what I will call "real-time" contest analysis tools.
My interest in doing this peaked at the last contest and then faided
away. But with the announcement of this contest I revisited the
ideas and started some coding one week ago. As I am fairly new to
perl and database programming I have only gotten so far. I do have
someone who has volunteered to host the site for the contest but due
to lack of time I will probably not put up the (very little) parts I
have now.


But to give some insight into what I have been thinking here is the
basic idea. I am creating a set of tools (listed here) to provide
"real-time" analysis. They include ...


List Tool - allow individuals to create entry lists like the full
ranking list but with selected entries. Also give them the ability to
sort on various criteria, etc. And the tools I have wanted for so
long and which got me thinking about all this is a highlighting tool
which will "highlight" certain entries. I have always had the
toughest time finding me entries in the full rankings list although
they are usually at the bottom! I find the Search tool to simplistic
for my liking.


Graph Tool - provide all sorts of graphs as the contest goes along


Email Tool - send email out when, for example, a higher score is made
than a certain entry or if a modification is made.


And the tool which I believe will start to address some of your
issues and the shear volume of entries is


Genealogy Tool - provide analysis on who is just copying who and what
really new ideas are out there.


Along with the last tool and after thinking about your email I will
add the idea of "real-time" commentary. That is providing some
real-time analysis, ie what have people done to improve other entries
and what can the user learn from these entries.


So here are my thoughts and I hope to see your entry soon (if you
find time). You will be able to find mine once again near the bottom
of the lists!


Ed Manlove


About Duane's books that I mentioned above you can check them out here


Mastering MATLAB 6: A Comprehensive Tutorial and Reference
Duane C. Hanselman & Bruce Littlefield
 <http://www.mathworks.com/support/books/book1703.jsp?category=-1&langua>
ge=-1


and


MATLAB Tools for Control System Analysis and Design, 2e
Duane C. Hanselman & Benjamin C. Kuo
 <http://www.mathworks.com/support/books/book1295.jsp?category=-1&langua>
ge=-1


Duane Hanselman wrote:
>
>
> Min Poh wrote:
>>
>>
>> The next MATLAB Programming Contest starts tomorrow at 9 a.m.
EST
> and will
>> run until 5 p.m. EST on Wednesday, April 9. Topics and rules
will
> be
>> posted
>> to the MATLAB Contest site tomorrow.
>>
>> <http://www.mathworks.com/contest>
>>
>> These contests are a great way to learn new programming tricks,
as
> well as
>> show off the ones you have.
>
> I disagree that "these contests are a great way to learn new
> programming tricks." They are much better at promoting the
> development of poor programming practices. Given the lack of
> comments, submitted code is next to impossible to understand unless
> one takes the time to decipher what each line does and what the
> overall strategy of a given solution is. Like most folks, I have a
> day job that does not allow me the time to be an active observer of
> the contest, let alone be a viable contributor. Are the contests
fun?
> Yes, but let's not promote them as being something they are not. If
> you were managing the development of MATLAB code, would you
encourage
> your programmers to adopt the programming practices demonstrated by
> these MATLAB contests?
>
> The only thing I've learned about this contest so far is that
>
> xy = (x-x(1)) + 1i*(y-y(1));
>
> is better than
>
> xy = (x-x(1)) + i*(y-y(1));
>
> That is, 1i tells the MATLAB interpreter immediately that one wishes
> to multiply by sqrt(-1), whereas using i forces MATLAB to first
check
> to see if i has been redefined as a variable other than sqrt(-1).
>

Dear Ed!


I suggest not to quote the full mail
you are replying to, especially in
a blog!


Kind regards, Frank

Everytime I do this remark. There was just someone who took the lead
with a copy of another : Nextnextsafe (a copy of RAUNoster_89 apart
from a blank line). The difference in CPU time is 2.7 s! That is a
big difference.


Stijn

Ed Manlove wrote:
> But to give some insight into what I have been thinking here is the
> basic idea. I am creating a set of tools (listed here) to provide
> "real-time" analysis.


We're thinking about this as well. You've got some great ideas.


> Graph Tool - provide all sorts of graphs as the contest goes along


We're always looking for ways to visualize what is going on with the
contest. We just started generating some of the most useful or
interesting pictures we've found every half hour or so. Check the
bottom of the home page. If you have anything in particular you'd
like to see, drop us a note and explain how it would be useful to you.


> Email Tool - send email out when, for example, a higher score is
made
> than a certain entry or if a modification is made.


Oh, I like this. It's a good way to push the information out to
those who are interested rather than making contestants dig it out.


> And the tool which I believe will start to address some of your
> issues and the shear volume of entries is
>
> Genealogy Tool - provide analysis on who is just copying who and
what
> really new ideas are out there.


The data here is always a little sketchy because it counts on
contestants using the "Edit" and "Submit" rather than just submitting
a new entry, but it does produce some interesting data. See the the
two pictures in the "Tree Diagrams" section of this analysis of the
Molecule Contest.


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


Is this the sort of thing you were thinking of?


> Along with the last tool and after thinking about your email I will
> add the idea of "real-time" commentary. That is providing some
> real-time analysis, ie what have people done to improve other
entries
> and what can the user learn from these entries.


As you know, it is tough to follow and comment on the contest in
real-time. The closest we've come to this is our mid-contest
analysis. Here are two from the last contest.


 <http://www.mathworks.com/contest/protein.cgi/midcontest.html>


 <http://www.mathworks.com/contest/protein.cgi/story.html>


We encourage authors to fill in comments when they submit an entry.
Also, if you see something interesting in someone else's entry,
please post here to share with everyone else.


Thanks for participating!

Stijn Helsen wrote:
> There was just someone who took the lead
> with a copy of another : Nextnextsafe (a copy of RAUNoster_89 apart
> from a blank line). The difference in CPU time is 2.7 s! That is a
> big difference.


The contest has always been sensitive to timing. Disk access time,
memory thrashing, and other system activity can randomly affect the
entry. The lead can even change because of this. We've tried to
reduce the effect as much as possible by taking measures such as
pre-loading the submission before starting the timing.


I am, however, surprised to see such a big difference. I expected it
to be an order of magnitude smaller. We're looking into this to see
what we can improve.


Thanks.

I noticed the parameter 1.09 in the code used by some of the best
entries. Can someone tell me what is the significance of that
particular number?

I found empirically that varying the parameter either up or down
results in a worse raw score, so it is clearly optimized, but I don't
understand why this rather arbitrary-looking number is so special.

> I am, however, surprised to see such a big difference. I expected
it
> to be an order of magnitude smaller. We're looking into this to see
> what we can improve.
You can also look to the difference between AddFreight5 and
AddFreight5_0. The last one does less and lasts 8 seconds longer!
When I do it here (with matlab 6.5) I get timing results which are
closer to my expectation : a small difference between the two (and
the second a bit faster), and a variance of some 0.1s (the same as
you expected).


I'm interested in results of your search (not just for this contest).


Regards,
Stijn

 "Stijn" == Stijn Helsen <SHelsen@compuserve.com> writes:
 Stijn> Everytime I do this remark. There was just someone who took
 Stijn> the lead with a copy of another : Nextnextsafe (a copy of
 Stijn> RAUNoster_89 apart from a blank line). The difference in
 Stijn> CPU time is 2.7 s! That is a big difference.

Oops, Nextnextsafe was supposed to be different from RAUNoster_89,
but apparently I fumbled the submission...

Ave

Matthew Simoneau wrote:


> I am, however, surprised to see such a big difference. I expected
it
> to be an order of magnitude smaller. We're looking into this to see
> what we can improve.
>
> Thanks.


Another example: The same change was made for


Home sweet home -> Home sweet home+
AddGasFreight -> AddGasFreight+


So does this change cost 7.74s or save 0.18?


Heinrich

In fact, I made a few variations myself, and the best value is
dependant of the test suite.


1.089, as I found out empirically seems to work best with the unknown
test suite used for the contest while the optimum for the test suite
in trucking.zip is different.


Klaus "Md" Quiet


cyclist wrote:
>
>
> I noticed the parameter 1.09 in the code used by some of the best
> entries. Can someone tell me what is the significance of that
> particular number?
>
> I found empirically that varying the parameter either up or down
> results in a worse raw score, so it is clearly optimized, but I
don't
> understand why this rather arbitrary-looking number is so special.
>

Interesting...

Removing abs reduced time in my machine (AMD Athlon 1GHz, Linux, Matlab
6.5.0.180913a) from 34s to 28s, but increased time in Mathowrks contest
machine from 90 to 97s, It's not easy to optimise speed...

With abs:
 xy = x + 1i*y;
 [X,Y]=meshgrid(xy);
 dist = abs(X-Y);

Without abs:
 dist=zeros(n);
 for i1=1:n
  dist(:,i1)=sqrt((x-x(i1)).^2+(y-y(i1)).^2);
 end

Ave

Garron wrote:
>
>
> Here's an idea for a global strategy:
>
> .....
I'm not sure, I haven't really looked to the code. But rather in the
beginning there were some submissions "building lego blocks"(??).
When I saw that title I thought it could be something described here.
 I think all those submissions failed because of time.
But I suppose people were allready thinking about this....
Stijn

Heinrich Acker wrote:
> it seems that there is something wrong with at least one diagram on
> the contest homepage.


Hello Heinrich:


The "normalized log plots" you're referring to are meant to be purely
qualitative. We're doing something fairly simple-minded to emphasize
recent progress.


In each case we subtract the lowest score from all the scores, and
then we add an offset to keep the log plot happy. In one plot we add
100, and in the other we add 1. We'll fix it up so they use the same
offset, but in the meantime, keep in mind that it's a qualitative
plot that is intentionally skewed to make recent progress obvious.
The "percent improvement" plot is more usefully quantitative, as you
point out.


-Ned Gulley.
The MATLAB Contest Team

Not to complain, but I noticed that the likely early bird winner
MadMax2 performs significantly worse on the downloadable test suite
than my own entry (1855.643K vs. 1837.522K), but then MadMax2 does
better with the official on-line test suite (2058.166K vs. 2060.954K).


I agree that the official test suite is the true contest measure, but
what could account for such a disparity? Maybe just one or two
special cases?


Brian

E. Brian Welch wrote:
> Not to complain, but I noticed that the likely early bird winner
> MadMax2 performs significantly worse on the downloadable test suite
> than my own entry (1855.643K vs. 1837.522K), but then MadMax2 does
> better with the official on-line test suite (2058.166K vs.
2060.954K).


As the contest continues, the entries tend to become specifically
tuned to the test suite. We try to limit this by having a large
number of test cases in the suite, but it is inevitable.


> I agree that the official test suite is the true contest measure,
but
> what could account for such a disparity? Maybe just one or two
> special cases?


This time around we didn't put any strange special cases in the test
suite. We wrote some code to randomly generate a test suite. We ran
it once to create the actual test suite, and then again to create the
sample test suite.

Matthew Simoneau wrote:
>
> As the contest continues, the entries tend to become specifically
> tuned to the test suite. We try to limit this by having a large
> number of test cases in the suite, but it is inevitable.
>


Thanks Matthew for the explanation. The difference between the test
suites does make it more difficult to steal good entries from the
queue like I was. I had my own small score improvement to add, but I
was sitting there watching the queue and testing entries that popped
up. I only had a chance of beating 'MadMax2' because I stole
'SwapRoute' (sorry Claus). Maybe it would be a good idea for new
entries to not be viewable until they have a score.


But hey, I was just trying to finally be a legitimate winner. This
contest seems to be insulated well against cheating. I surrender.


Brian

Concerning those differences of scoring results. If you compare the
scores (testcase/testcase) of two submissions. You can see the big
individual differences, positive and negative. That means that the
total (or mean) of those individual scores can vary a lot.


So I think that those differences of scoring results for the
testsuite and final suite are normal.


Stijn

I had another query which might be relevant to this discussion. I was
looking at the code for runcontest when I noticed a peculiarity in
the scoring system.


It seems that a solution that runs out of fuel is not disqualified
(as I assumed) but the score generated is simply that for no freight
returned and no fuel returned. This is actually better than the score
that [1 1] generates since it returns fuel but no freight.


I made the obvious changes to the entry which was leading at the time
to improve the performance and saw significant improvement on the
sample suite but a poorer result on the test suite.


I can think of only two reasonable explanations for this
1. A bug in my code (likely)
2. The online scoring system has been updated to score out-of-gas
entries more fairly.


Another thing I noticed (and tried to exploit) is the fact that the
gas penalty is based on remaining gas at the end rather than total
collected gas as everyone seems to have assumed. This can have
drastic impact on code along the lines of swaproute, since if the
route is made shorter but no extra stops can be added the score
actually becomes worse since more fuel is left at the end.


I hope someone else can make better use of this knowledge than I have
been able to.


Hannes Naudé / RAU team

Stijn Helsen wrote:
> g = cumsum(a(c(1:end-1),4));
> .... g(end)
> So that means sum(a(c(1:end-1),4))). I think that that the total
gas
> is and not the remaining.
>
> Agree?
> Stijn


Yes I agree. Stupid mistake on my part.


As to running out of fuel. I just did a little experiment. I modified
the sample entry to look as follows


function c = solver(a)
n=size(a,1)
c = [1:n 1];


and the raw score went from 4913K to 4922K (ie. got worse). On my
system the score went from 4906K to 4887K (ie. got better). To me
this looks like conclusive proof that the scoring works different on
the online and local versions of runcontest. But I might be wrong
(again).


While I'm rambling I might as well ask wether any of the old hands at
this contest know of a nice program to quickly compare two files
under windows (to see what mods were made) as searching for the
tweaks becomes prohibitively time consuming and if you just mod a mod
you haven't learnt anything.


Thanks
Hannes Naudé / RAU Team

Hannes Naudé wrote:
> Another thing I noticed (and tried to exploit) is the fact that the
> gas penalty is based on remaining gas at the end rather than total
> collected gas as everyone seems to have assumed. This can have
> drastic impact on code along the lines of swaproute, since if the
> route is made shorter but no extra stops can be added the score
> actually becomes worse since more fuel is left at the end.
>
Is it? I read :
g = cumsum(a(c(1:end-1),4));
.... g(end)
So that means sum(a(c(1:end-1),4))). I think that that the total gas
is and not the remaining.


Agree?
Stijn

> While I'm rambling I might as well ask wether any of the old hands
at
> this contest know of a nice program to quickly compare two files
> under windows (to see what mods were made) as searching for the
> tweaks becomes prohibitively time consuming and if you just mod a
mod
> you haven't learnt anything.


If I'm working on Windows (that is at work ("illegally playing")),
I'm using a program which was included in the MS-VisualC++ package.
(Here at home on my Mac I'm using BBEdit.)
I haven't look for it, but I would think that such a program can be
found on the internet. (And I think it is a necessary tool in this
contest, at least very very useful.)
I wish you good luck. (Is it a big team ?)


Stijn

> I wish you good luck. (Is it a big team ?)
>
> Stijn
>
No, when we're at max strength we're 3. We're postgrad engineering
students and this is much more fun than working on our dissertations.


Most of the time its just me, however. My fiance is understandably
getting a bit agitated over my addiction to this "game".


Good luck to you too and thanks for the info.


Hannes Naudé

Dear Contestants and MATLAB Contest Team,


it has been criticized that many of the contest entries are
unreadable and therefore it is difficult to follow the contest, even
more difficult to learn from it. Although everybody knows that it
would be good to add a lot of comments to the code, few contestants
take the time. That's not surprising, one has to be quick in this
competition.


I would like to suggest a way to improve this in the next contest,
with the current contest as the example.


Imagine the function call of the solver would be


function path = solver(x, y, freight, gas, n)


with the obvious meanings of the parameters; instead of the current


function c = solver(a)


In that way, there would be a common basis for all submissions, one
that will even not be dropped when tweaking for milliseconds.


The work will essentially be the same, as nobody of us is challenged
e.g. by the line
n=size(a,1).


Of course, this will not make it much easier to follow, just a bit,
but this improvement is easy to implement.


Regards,


Heinrich

Hi Nathan
> I don't really understand how the random number generator works. If
a
> code depending on some random influence is submitted more than once,
> is it guaranteed to produce the same results? This seems to be the
> case.
That is done on purpose. The random generator is reset, so that
every submission has the same (random) luck (or unluckiness) when
using random numbers.


> Well, this is my first matlab contest and it is giving me far too
> much enjoyment. It's one of the most addicitve and compulsive things
> I have tried. The exercise is improving my programming skill - true
-
> but in return I have neckache, backache, a terrible diet, no social
> life, and not much of a work life either. Also, I have experienced
> physical trembling while making the final preparations to send a
code
> into the pit. Is that normal?
I recognise the things you describe (and I think my wife and children
too, and I'm lucky my boss isn't looking over my shoulder whole the
time...).


> There seems to be a lull in activity at the moment. Are you all
> brewing up something special? Or enjoying your saturdays like
normal people?
Or a combination of the two....


Stijn (Alken - Belgium)

Regarding my comment about removing the ability to use
rand('state',J).


 <http://www.mathworks.com/contest/trucking.cgi/view_submission.html?id=>
11093


I don't think that it is nessesary because eventually better programs
will come that is less dependent on random numbers.

Hi,
The discussion has been done a couple of times, but I want to start
again. 8 days of a contest of this type (not very important, but
"addictive") is long. I had the same last contest. I can't stop, but
I'm also not so interested in "working" for three days on this (so
that I can't do real work).
If it is necessary to have a weekend during the contest I propose to
do it from Thursday to Monday or from Friday to Tuesday.


Stijn

I agree.


Stijn Helsen wrote:
>
>
> Hi,
> The discussion has been done a couple of times, but I want to start
> again. 8 days of a contest of this type (not very important, but
> "addictive") is long. I had the same last contest. I can't stop,
but
> I'm also not so interested in "working" for three days on this (so
> that I can't do real work).
> If it is necessary to have a weekend during the contest I propose to
> do it from Thursday to Monday or from Friday to Tuesday.
>
> Stijn
>

Another query:


I notice that the two depth first searches
turbodiesel and enumerate by Stijn were both implemented using an
explicit stack. Is this due to experience in previous contests, that
indicate that this is faster than using recursion??


I'm considering implementing a recursive version but seeing as this
is probably the easier option anyway, I figure there must be a reason
why no-one has done it??


Thanks
Hannes Naudé / RAU Team

Hi,


I've implemented that enumeration first recursive. That had bad
timing results. It is especially because a lot of memory is used.
If it is about variables which are not changed (constants) it is ok,
they are (implicitely) used "by reference". But a lot of arrays are
changed (for example an "avail"-variable). Probably it could be done
better than as I've done that (for example using global variable),
but still I don't think it will be better then the "flat" way.
Another reason why I did it, is that it is easier for a "fast-exit".
Still another (unused) reason was that other things could be done
during "backtracking".


But, if you think it could be done better..., good luck with it.


Stijn

In the comment of Td lazy, it is written "is fgbest ever better than
fgsbest???". Now it is true. In earlier versions findenum gave the
two sets of outputs. They were optimized separately. That gave
better results, but worse CPU-time. It is still possible that better
things can be done with the "long but not-yet-so-good" result then
with the "short and currently-best" result.


Stijn

Here are some thoughts (this post is long) about the contest.


The MATLAB programming contest is designed to be a balance between
cooperation and competition, but our foremost goal is to make it fun.
The tension between cooperation and competition is evident in the
feedback we hear. For instance, some people point out that the code
is very difficult to read, and is even sometimes purposely obscured
by contestants. Why don't we take some steps to coerce people into
commenting their code or naming their variables more clearly? On the
other hand, we also hear from people who are disappointed by the need
to expose their code once it is in the queue. Couldn't we hide the
code until it gets a score, or why not hide it for an hour, or hide
only the entry with the best score?


It is ultimately the emphasis we place on fun that makes us keep the
balance where it is. We're not trying to determine the most clever
MATLAB programmer in the world, because we know that it's crazy to
give one person full credit for what is certainly the combined work
of many people. We also know that our contest machinery is not
strictly deterministic. Sometimes funny things happen with the CPU
timing that we can't explain. That's why our prizes our
inexpensive... imagine the trouble it would cause if we gave the
winner a new car or a fancy computer. If your name has ever appeared
at the top of the list with the big red number one next to it, you
know it is due to a funny combination of cleverness, the ability to
sift through other people's code, hard work, and luck.


Now suppose you really want to know how well your particular
wholly-original algorithm works, and suppose also that you didn't
want anybody else to peek at your code. There is a straightforward
strategy to achieve your goal: work on it by yourself, don't look at
any other entries (so as not to steal their ideas), and submit it one
minute before the contest closes. It's possible, but very unlikely,
that you will win the contest and bring unshared glory to your name.
Of course, you can improve your chances by entering the contest with
a test entry somewhat earlier. But this test entry comes with a cost:
you have to reveal your code. There is a hidden benefit, though: if
your algorithm is useful, it's very likely that someone else will
improve for you while you watch (or even while you sleep). And once
it's been improved in some unexpected way by some unseen friend,
you'd be foolish not to include the improvement in your own private
experiments.


This is how the contest draws people in. It's very much an open
source model. Cleverness is sprinkled across the globe, and the
contest is a way to concentrate it in one small bundle. You deserve
credit for making the code better, but you are also wise to
acknowledge the efforts of others. The winning entry for each contest
we've run has included code from many, sometimes dozens, of
contributors. The person who's name ends up at the top of the list
gets a prize and a moment of glory, but as for who made the most
significant contribution, who can say?


Having said all that, we're interested in suggestions for how to
improve the contest. It does get hard to understand the code as time
passes. One of the trends I'm happy to see is more cooperative
discussion on the newsgroup thread. Duane Hanselman has suggested
that we simply do an old-style contest where you mail in one entry
and run them all once. Would you like to see that? Suppose we run the
contest for a much shorter time, say 24 hours? That might prevent
some of the test suite overfitting, but of course you'd only get one
day's worth of contest twice a year. Finally, I'm curious to hear
some of the strategies that people use as they play the contest. Do
you try out ideas one at a time, saving your best for the last day?
Or do you simply make the best play you can right now? Send us your
thoughts, or post them here.


Thanks for reading, watching the contest, and playing.


-Ned Gulley.
The MATLAB Contest Team

nathan <nathoq@yahoo.com> writes:

> Still on the topic of tweaking, do you all think it would be a good
> idea to declare a "second winner" based on some formula involving
> percentage step improvements? Tweaking is a fine art and should
> rightly be rewarded, but it would be nice to give recognition to
> developers of major new code too.

On this topic I thought it would be a neat idea to run the contest in
two phases. The first phase would allow original submissions only.
No viewing of others' code at all. A winner would be chosen at the
end of phase 1. Then all submissions would be opened for viewing and
resubmission, so the best possible entry could evolve.


--
Peter Boettcher <boettcher@ll.mit.edu>
MIT Lincoln Laboratory
MATLAB FAQ: http://www.mit.edu/~pwb/cssm/

Ned Gulley wrote:
>
>
> Here are some thoughts (this post is long) about the contest.
>
 Duane Hanselman has suggested
> that we simply do an old-style contest where you mail in one entry
> and run them all once. Would you like to see that?


Not true. That would be just as bad as the current approach. Please
reread my post.


The best contest finds a balance between the current instant
availability of code submissions and a totally closed contest as you
incorrectly attributed to me above. Both extremes lead to a less than
ideal contest.


How about holding individual entries for 24 hours and keep the
contests going as long as they are now. That way an individual can
submit multiple refined entries over a 24 hour time period before
anyone else sees even their first submission. That way a person can
tune their code quite a bit before having others borrow from it. The
first day of contests would be private, but privacy would disappear
as more and more submissions become public in later days. Early
privacy would encourage more people to submit. As it is now, the pool
of potential submitters rapidly decreases as submissions are minded
for their strengths and the code becomes too complicated for those
who cannot spend the time to bury themselves in it.


I'm glad that you are willing to say that the purpose of the contests
is "fun" as opposed to them being "a great way to learn new
programming tricks, as well as show off the ones you have" as stated
by Min Poh in the first posting in this thread. Your statement more
accurately reflects reality. No one beyond the small number of active
submitters can decipher the winning submission without spending undue
time figuring out what is going on.


Duane Hanselman
Mastering MATLAB 6

Matthew Simoneau wrote:
>
> I am, however, surprised to see such a big difference. I expected
it
> to be an order of magnitude smaller. We're looking into this to see
> what we can improve.
>


Even worse, my submission, "BugFix" has been failed due to timed out
(over 180 seconds). However, the same code resubmitted with name
"Unbelievable CPU time" has got CPU time only 96.598 seconds.

It may help to determine the "winner" more accurately if you hide the
entries in the queue in the last 1 hour of the contest.


But, on the whole, the contest structure is good. I think the
quality of the contest is very dependent on the quality of the
problem. The current problem is a little dull, but that is a matter
of taste. It is certainly more difficult for me to understand the
algorithms that have been posted so far than previous contest
algorithms, but maybe it's just me (and a very busy work schedule,
unfortunately!).


Certainly, those CPU issues should be looked into.

Ned Gulley wrote:
> Suppose we run the contest for a much > shorter time, say 24
hours? That might > prevent some of the test suite
> overfitting, but of course you'd only get > one day's worth
of contest twice a year.


Another idea to battle overfitting would be to use a third (huge)
validation suite that is never revealed or tested on until the end of
the contest. The top ten entries (based on test suite performance)
are then run on the validation suite to determine the final winner.
This eliminates the motivation for excessive tuning of parameters.


Sometimes small errors slip into the top entries but correcting these
actually lead to slight deterioration in performance due to some
chance characteristic of the test suite. Using a validation set would
ensure that CORRECT code is valued higher than code that happens to
perform well.


Lastly, I find that I have to step back from time to time and read
through all the code of the top entry slowly to make sure that I
retain my grip on what it is doing. Seeing as I have to do this
anyway I will be perfectly willing to comment it as I go along and
resubmit (and I'm sure there will be others who will do the same) .
If this entry happens to land on top many future submissions will be
based on it and contain comments for most of its content.


Unfortunately the chances of an entry like that landing on top are
slim since it will take a while to comment after which significant
improvements hav probably been made. Secondly the person who now
moves down to two might not take kindly to this. (Yes its not
rational but we all know how important it becomes to get that big red
one and keep it)


Maybe a separate queue for entries like that would be a good idea??
Competititors could then base their entries on the top submission in
this queue (if the performance difference is not too big) and the
comments diffuse through to the main queue.


If the people at Mathworks would be willing to make the info that is
available on the contest home page available on some other port in
some open protocol, clients for this protocol would very quickly
become available (I know I would write one) opening the way for
features like alerts when given barriers are broken or significant
improvements are made and even semi-automatic commenting.


P.S. I'm still wondering about the reason for the out-of-gas scoring
phenomenon that I described earlier. If this is obvious to anyone
please mail me.


Hannes Naudé / RAU team

It's hard to pick out which entries are introducing significant new
code. To help with this, I just added a new "Difference from
Leader". It naively diffs the last 100 entries against the current
leader and color codes each by its percent-difference. Mousing over,
on most browsers, will show you a tooltip with the entry's author and
title. Clicking on it will take you to that entry.

Ned Gulley wrote:

> that we simply do an old-style contest where you mail in one entry
> and run them all once. Would you like to see that?


Where would the fun be?


>Suppose we run the
> contest for a much shorter time, say 24 hours?


More like three days - a friday to a sunday? The current timing must
be difficult for people who are at "work" when the contest closes.


>That might prevent
> some of the test suite overfitting, but of course you'd only get one
> day's worth of contest twice a year.


Hannes' suggestion of a large problem suite applied after the contest
makes sense.


How about blocking read access to submissions that are waiting in the
queue? This would block some desperate, blind last-minute tweaking of
new algorithms that have been saved until the end.


As a newcomer I was sceptical about the role of "competitive
collaboration". However I'm now convinved that it's what makes the
contest work (as you at Mathworks are always saying). And anyway the
really consistent competitors keep returning to the top of the table
and staying there with innovations that are more than tweaks. And the
fact that it's so popular must mean the basic formula is right. I
think there is a self-regulating aspect to it - nobody comments their
code overhelpfully, but nobody has gone out of their way to obscure
code either and variable names etc are not too cryptic. As long as
nobody wants to start a trend which will result in more illegible
code. I don't think any attempt on your part to police commenting etc
would work.


I would like to see some award based on performance leaps. It would
have to limited to a later period of the competition. I liked the
idea of a prize for first passed a defined score.


> Finally, I'm curious to hear
> some of the strategies that people use as they play the contest. Do
> you try out ideas one at a time, saving your best for the last day?


My ingenious strategy was to develop a set of invincible algorithms
and release them in phases over the last hour. Unfortunately this
strategy required the ability to think up invicible algorthms and an
attention span to read programs of more than 100 lines. When this
problem became clear, I switched to a strategy of thinking up witty
names for non-existent winning codes, while marvelling at the stamina
of Stijn, Heinrich, RAU, Ave et al as they whanged out 2 and 3
submissions a minute. Falling asleep in a meeting was also a key
element of my strategy.


thanks
Nathan

I agree with Nathans suggestion to block read access to the queue.
Perhaps also blocking read access to the top five submissions (or
some other number) would prevent people from posting nearly identical
submissions. This would make sense also because of the troubles with
CPU timing.


How about running the best X algorithms on a new set of test problems
after the submission deadline and adding the score from that test set
to the already obtained score? The sum of the score from the first
and second round would thus determine the winner. The first test set
acts as a qualifying round and the second as the actual competition.
You would be rewarded for a good score in the first round and
punished for small errors in the code or an overfitted algorithm in
the second round. Running the qualified entries online in reversed
order with respect to the obtained score from the first round would
make the second round quite interesting as well!


Anyway, thanks for another interesting competition! I certainly
learned some new programming tricks (and a few things what not to
do).


Claus

Hello Ned,


now that the contest is over, I'd like to respond to your invitation
and propose a few things. First of all, I agree to the view that the
contest is for fun. We shouldn't take it too serious. On the other
hand the contest is worth thinking about, because it is already so
good. I like the concept and would keep it. Regarding changes for the
next contest, I would distinguish the improvements from the
variations.


Variations are changes in the contest duration, for instance. A three
day contest is neither better nor worse, but different. Some people,
like Stijn, have said they would like to protect their families from
a contest weekend. Others prefer the weekend because they don't have
the time to participate Mon-Fri. The natural reaction to these
conflicting interests would be to let the contest duration vary for
the next contests. I think 24 hours is too short for this kind of
contest, because the uncoordinated cooperation takes time to develop,
but anything between 3 and 8 days, starting at any day of the week,
why not? There's no reason to have a standard for that.


Now the suggestions for improvement:


1. Message 36 of this thread.


2. Block any random command, because the contest is about developing
an algorithm, not about gambling. This would also kill some
difficult-to-follow tweaking and test-suite-fitting.


3. Make sure that all extreme cases are part of the test suite. This
prevents people from tweaking away a reasonable, problem-oriented
special case test in order to get a few milliseconds, but essentially
downgrading the entry according to the specified problem.


4. Use a faster machine to be able to run a larger test suite within
the reasonable 3 min limit. My 1000$ PC runs the test suite twice as
fast as the contest computer. A larger test suite makes
test-suite-fitting more difficult again. During the preparation of
the contest, try to find a balanced test suite by checking several
for sensitivity to score variations.


5. Change the scoring function. a) The raw score reflects a
reasonable cost function that has to be minimized. The cost of
computation is proportional to CPU time, so why not have a linear
model? I don't see why +10s are more costly at 100s compared to 90s.
b) The 'raw score' could also be used, rewarding the most tricky
algorithm that finds a solution in three minutes. That would indeed
make the contest easier to follow, because tweaking would concentrate
on improving raw score. The timing problems would also disappear. c)
Make the length of the entry a part of the scoring function, that
could be funny. If you manage to find a way to count something like
'language elements', such that comments, indenting etc. cost nothing,
tweaking away complex function calls for for-loops would not make
sense any more, which results in entries easier to read. d) Finally,
making memory usage expensive could also be interesting.


6. Change the way to determine a winner without changing the contest
itself. The last contests were sometimes too hard for the leader,
especially for an inventing leader. Five minutes, another tweak, and
the lead is gone. How about a second list, one for the participants,
which lists the total time of lead or the total points (or
percentage) to previous leader for any contestant. There could be an
additional price for the leader of this list in the end. That would
improve cooperative development, because it does not make sense any
more to hide something. Instead, it would be best to submit any
improvement as soon as possible. Also, hiding your identity with a
second alias in some submissions would be uninteresting.


All this I believe can work without changing the idea and concept of
the contest, or the way it fascinates. I would be pleased if you
consider some of these suggestions.


'See you' in the next contest,


Heinrich

Randomized algorithm is one important type of algorithms for solving
hard problem, and banning its use may not be a good idea.

Heinrich Acker <Heinrich.Acker@web.de> wrote:

> 2. Block any random command, because the contest is about developing
> an algorithm, not about gambling. This would also kill some
> difficult-to-follow tweaking and test-suite-fitting.

Matthew Simoneau wrote:
>
>
> Don't miss Roger Stuckey's comments. They're on a new thread:
>
> <a href="/WebX?50@@.eebc40b">Roger Stuckey "More thoughts"
4/10/03
> 12:49am</a>
>


Sorry, I hit the wrong button... Doh!


Here's the link if anyone's interested:
Roger Stuckey "More thoughts" 4/10/03
12:49am


Roger

If the decision is made to shorten the contest, how about posting the whole
problem statement, sample code, and testsuite a week before the queue opens
up? Then folks have a chance to get their minds wrapped around the problem
by testing their own algorithms at home, form up a private team, etc. When
the queue opens, the serious players can hit the ground running with well
thought out algorithms. There would still be time for widespread
collaboration via the open source viewing we have in the current rules. The
idea of not allowing the top few entries to be viewed is kind of
interesting, but has the potential to seriously change the dynamics of the
contest.

Pat

We all know how much fun a completely open contest is. On the other
hand some argue that this format does not give enough acknowledgement
to the algorithm architects since crafting a new algorithm requires
hours and (if it works out) probably only lands the author on top for
a few minutes since tweaking can be done quite quickly.


In my opinion however, the biggest drawback of the open format is the
fact that it induces a significant amount of "groupthink". Since we
all read the same (leading) entries we all start to think in the same
way and a lot of the diversity inherent in having hundreds of people
with different backgrounds from all over the world work on the same
problem is lost.


In this context I quote Pat


> If the decision is made to shorten the contest, how about posting
the whole
> problem statement, sample code, and testsuite a week before the
queue opens
> up?


Great idea! (One could even have the queue open but private ie. you
can test run your code to make sure all is well but the results are
not visible to everyone).


I suspect many a great algorithm has gone unimplemented because the
person who came up with it was too busy following the queue and
tweaking. On the other hand tweaking is a big part of the contest
experience and if it is lost (by not making the code of leading
entries available for instance) the contest will a lot of its
popularity.


This kind of split approach could force contestants to take a long
hard think about the problem before getting sucked into the game and
tweaking for milliseconds. Ideally one would then award the early
bird prize immediately before actually opening up the queue for
public viewing. This would amount to a prize for the best individual
contribution.


Once the queue opens for public viewing, the great diversity of
different approaches present, (since all contributions were made
independently) would provide the most hardened tweaker with hours of
good "entertainment" and the final result would probably be better
than that obtained with a week long entirely open contest.


Hannes

Ned,
I have just discovered the contest. I would love to take part and
have registered to be informed of the next one.
However, whilst the concept appeals, I expect that I will not have
time to get heavily involved due to other commitments. I think that
it would be a good idea to alternate between open contests like this
one and 'covert' contests with a longer timescale, where everyone
submits at the same time. This allows people with less spare time to
get involved.
The iterative development of the winning solutions is clearly fun,
and if you are involved from the start of the contest, your are
likely to be able to follow the code. However, if you are dipping in
when you can, you are unlikely to be able to keep up!
I hope to have a go at the next one, but I think that it would be
easier for me to get involved in a more conventional contest.
My recommendation: run both!
Regards,
Paul Eveleigh
Time-strapped Consultant.


Ned Gulley wrote:
>
>
> Here are some thoughts (this post is long) about the contest.
>
> The MATLAB programming contest is designed to be a balance between
> cooperation and competition, but our foremost goal is to make it
fun.
> The tension between cooperation and competition is evident in the
> feedback we hear. For instance, some people point out that the code
> is very difficult to read, and is even sometimes purposely obscured
> by contestants. Why don't we take some steps to coerce people into
> commenting their code or naming their variables more clearly? On the
> other hand, we also hear from people who are disappointed by the
need
> to expose their code once it is in the queue. Couldn't we hide the
> code until it gets a score, or why not hide it for an hour, or hide
> only the entry with the best score?
>
> It is ultimately the emphasis we place on fun that makes us keep the
> balance where it is. We're not trying to determine the most clever
> MATLAB programmer in the world, because we know that it's crazy to
> give one person full credit for what is certainly the combined work
> of many people. We also know that our contest machinery is not
> strictly deterministic. Sometimes funny things happen with the CPU
> timing that we can't explain. That's why our prizes our
> inexpensive... imagine the trouble it would cause if we gave the
> winner a new car or a fancy computer. If your name has ever appeared
> at the top of the list with the big red number one next to it, you
> know it is due to a funny combination of cleverness, the ability to
> sift through other people's code, hard work, and luck.
>
> Now suppose you really want to know how well your particular
> wholly-original algorithm works, and suppose also that you didn't
> want anybody else to peek at your code. There is a straightforward
> strategy to achieve your goal: work on it by yourself, don't look at
> any other entries (so as not to steal their ideas), and submit it
one
> minute before the contest closes. It's possible, but very unlikely,
> that you will win the contest and bring unshared glory to your name.
> Of course, you can improve your chances by entering the contest with
> a test entry somewhat earlier. But this test entry comes with a
cost:
> you have to reveal your code. There is a hidden benefit, though: if
> your algorithm is useful, it's very likely that someone else will
> improve for you while you watch (or even while you sleep). And once
> it's been improved in some unexpected way by some unseen friend,
> you'd be foolish not to include the improvement in your own private
> experiments.
>
> This is how the contest draws people in. It's very much an open
> source model. Cleverness is sprinkled across the globe, and the
> contest is a way to concentrate it in one small bundle. You deserve
> credit for making the code better, but you are also wise to
> acknowledge the efforts of others. The winning entry for each
contest
> we've run has included code from many, sometimes dozens, of
> contributors. The person who's name ends up at the top of the list
> gets a prize and a moment of glory, but as for who made the most
> significant contribution, who can say?
>
> Having said all that, we're interested in suggestions for how to
> improve the contest. It does get hard to understand the code as time
> passes. One of the trends I'm happy to see is more cooperative
> discussion on the newsgroup thread. Duane Hanselman has suggested
> that we simply do an old-style contest where you mail in one entry
> and run them all once. Would you like to see that? Suppose we run
the
> contest for a much shorter time, say 24 hours? That might prevent
> some of the test suite overfitting, but of course you'd only get one
> day's worth of contest twice a year. Finally, I'm curious to hear
> some of the strategies that people use as they play the contest. Do
> you try out ideas one at a time, saving your best for the last day?
> Or do you simply make the best play you can right now? Send us your
> thoughts, or post them here.
>
> Thanks for reading, watching the contest, and playing.
>
> -Ned Gulley.
> The MATLAB Contest Team
>