Thread Subject:

MATLAB Programming Contest: April 21-28, 2004

The next MATLAB Programming Contest starts on Wednesday, April 21,
2004 at 9 a.m. EST. This contest runs for a week and ends on
Wednesday, April 28 at 5 p.m. EST.

We've been listening to feedback from our contestants and the
upcoming contest will use a slightly different format. In the early
stages of this contest, you will have the opportunity to work
independently, without your code being visible to others. More detail
will be provided on the day of the contest, so be sure to check back
then and get a head start!

 <http://www.mathworks.com/contest/>

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.

As usual we'll be holding several mid-contest prize giveaways of
MATLAB T-shirts, lunch bags, and other good stuff, so don't wait
until the last minute to participate.

We look forward to seeing your entry. Good luck!

-Min

Min Poh
The MATLAB Central Team
The MathWorks, Inc.

GOOD Rules for this time:)

Can't I know my own score either?

David

That's right, David. In Darkness, you can't see the score of any of
the entries, including your own. I clarified this in the Latest News.

Does appearance of an entry in the list imply that it has passed?

Nathan

PS interesting format

All entries will appear in this list. Thursday after noon, you will
be able to see if the entries passed or failed as well as the
entries' scores.

Mike

nathan wrote:
>
>
> Does appearance of an entry in the list imply that it has passed?
>
> Nathan
>
> PS interesting format

Min Poh wrote

> The next MATLAB Programming Contest starts on Wednesday, April 21,
> 2004 at 9 a.m. EST. This contest runs for a week and ends on
> Wednesday, April 28 at 5 p.m. EST.

Very interesting and challenging (NP-hard ?!)
problem indeed! It will be hard to resist the
temptation to work on it a bit...

sTefan

Great problem and format! But, I miss the nice graphics of the
previous contests. Anybody working on something?

I agree it is challenging and somewhat interesting, but does anyone
else think these contest problems all seem pretty similar? -- very
discrete and combinatorial. Except for help in managing sets and
lists, I don't find that Matlab has much unique to offer as a
programming language for such tasks. It would be great to have a
contest requiring a solution with some eigenvalues, SVDs, or maybe a
convolution or toeplitz matrix... the way Matlab is meant to be used!
(IMO) I'd even settle for some floating point calculations and a few
matrix multiplications. Perhaps it is difficult to come up with such
a problem that would also be fun.

I do enjoy these contests though (mostly observing) -- thanks to The
MathWorks for putting them on.
Ken

Stefan Stoll wrote:
>
>
> Min Poh wrote
>
>> The next MATLAB Programming Contest starts on Wednesday, April
> 21,
>> 2004 at 9 a.m. EST. This contest runs for a week and ends on
>> Wednesday, April 28 at 5 p.m. EST.
>
> Very interesting and challenging (NP-hard ?!)
> problem indeed! It will be hard to resist the
> temptation to work on it a bit...
>
> sTefan
>
>

MR Keenan wrote:
> But, I miss the nice graphics of the
> previous contests. Anybody working on something?

this is the code i've been using to see how my d looks:

cn=testsuite(k).n;
cl='rgbcmykrgbcmykrgbcmykrgbcmykrgbcmyk';
for i=1:cn,
   spy(c==i,cl(rem(i-1,cn)+1)); hold on;
end;
spy(testsuite(k).map,'ko')

ugly hack, but it shows a nice map of France (#11 in the testdata,
i've also spotted NZ and India i think ;). I've just looked in my
graphics manuals and "spy" isn't even mentioned, weirdly enough.

What i'd like is a colourmap on the dots showing the values and then
coloured circles around the different d groups

MR Keenan wrote:
>
> Great problem and format! But, I miss the nice graphics of the
> previous contests. Anybody working on something?

Here is a modified runcontest function, I
hope not too long for posting here.

Regards,

Heinrich

function runcontest(diag)
% This version of runcontest will test for voting districts

% runcontest with TestsuiteViewer for Matlab Gerrymander Contest
% Loads testsuite and displays test cases with results.
% Click into figure for next case, press any key to terminate.
% Use the menu item File->New Figure to 'keep' the current case
% and continue in a new window.
% - Heinrich Acker

% Load the testsuite.
load testsuite_sample testsuite

% Preallocate for speed.
results = ones(size(testsuite))*Inf;

f1 = 1;
f2 = 2;

% Run the entries.
t1 = clock;
for k = 1:length(testsuite)
   inputs = struct2cell(testsuite(k));
   %[null,c] = evalc('solver(inputs{:})');
   c = solver(inputs{:});
   clear('global');
   results(k) = grade(inputs{:},c);
if diag==1
figure(f1);
       bar3(testsuite(k).map);
       title(['Case #' num2str(k) ': n = '
num2str(testsuite(k).n) ' pop = ' ...
              num2str(sum(testsuite(k).map(:)),'%6g') ' mapsize =
' ...
num2str(size(testsuite(k).map,1)) 'x'
num2str(size(testsuite(k).map,2))]);

figure(f2);
bar3(c);
title(['Score = ' num2str(results(k))]);
       b = waitforbuttonpress;
if b==1, break, end
end
end
t2 = clock;

fprintf('Score: %.8f%% (average part misplaced)\nTime: %.2f
seconds\n\n', ...
   mean(results), ...
   etime(t2,t1));

Ken Crounse wrote

> I agree it is challenging and somewhat interesting, but does anyone
> else think these contest problems all seem pretty similar? -- very
> discrete and combinatorial. Except for help in managing sets and
> lists, I don't find that Matlab has much unique to offer as a
> programming language for such tasks.

Well, you are absolutely right about the fact that
MATLAB doesn't have much unique in its language to
handle such combinatorial problems. I even would say
nothing unique at all. You can use C++, C#, Java,
Perl or any other language to work on these class
of problems.

> It would be great to have a
> contest requiring a solution with some eigenvalues, SVDs, or maybe a
> convolution or toeplitz matrix... the way Matlab is meant to be used!
> (IMO) I'd even settle for some floating point calculations and a few
> matrix multiplications. Perhaps it is difficult to come up with such
> a problem that would also be fun.

Proposing problems with make use of MATLAB's marix
power, though, is more troublesome. First, there will
be much fewer people being able to understand the
problem, not to speak being able to solve it. Second,
combinatorial problems have the advantage that there
is (almost) never an exact solution available. So
programmers are forced to be creative to devise methods
that are very heuristic (another term for this is hacking
as opposed to writing well-structured, maintainable code
implementing a theortically sound and consistent algorithm
to solve the problem or to approximate its solution...).

The beauty of the kind of problems TMW uses for the contests
is that they are extremely relevant to real world. The
current contest is a variation of the set partitioning
or number partitining problem. The special case where tiles
are restricted to be rectangular is occuring in
databasing. If you browse through the relevant literature (by
searching http://citeseer.ist.psu.edu/ ), you will find
that there are mostly heuristic solutions available with
no guarantee as to the quality of the result.

Happy hacking!

sTefan

"Stefan Stoll" <stefan.notthis.stoll@ethz.ch.delete> wrote in message
news:4087b93a@pfaff2.ethz.ch...
> Ken Crounse wrote
>
<SNIP>
>
> The beauty of the kind of problems TMW uses for the contests
> is that they are extremely relevant to real world.

We picked Gerrymandering at the request of our consulting group. They will
be using the winning entry in Massachussetts to ensure that no Republicans
get elected and in Texas to make sure that no Democrats win. We didn't get
the contract for Florida -- I think that they are planning to use RAND.


> The
> current contest is a variation of the set partitioning
> or number partitining problem. The special case where tiles
> are restricted to be rectangular is occuring in
> databasing. If you browse through the relevant literature (by
> searching http://citeseer.ist.psu.edu/ ), you will find
> that there are mostly heuristic solutions available with
> no guarantee as to the quality of the result.
>
> Happy hacking!
>
> sTefan
>

MR Keenan wrote:
>
>
> Great problem and format! But, I miss the nice graphics of the
> previous contests. Anybody working on something?

Here's something to do the job. Hasn't been extensively tested though
;)

Cheers, Roger

----------

function plotmap(map,N,d)
%PLOTMAP Plot the population map of Rectanglia and its districts
% PLOTMAP(map,n,d) plots the map with n districts defined by matrix
d.
% The map is shown as a flat-shaded grayscale surface, scaled
according to
% the population in each square. White represents zero and dark
gray maximum.
% The districts are randomly colored, semi-transparent and
overlayed on top
% of the map, with black borders.

% Roger Stuckey
% $Revision: 1.0 $ $Date: 2004/04/22 $

ncmap = 512; % number of colors in map

[m,n] = size(map); mn = m*n;

maxmap = max(map(:));

map = map([1:m,m],[1:n,n])/maxmap*ncmap*0.8; % scale, add extra row &
column

surf(map,'EdgeColor','none') % plot the pretty surface

hold on

d = d - min(d(:)) + 1; % check that d starts at 1

d = d([1:m,m],[1:n,n]) + ncmap; % add extra row & column, offset

surf(d,'EdgeColor','none','FaceAlpha',0.4) % plot the districts

cmap = [1:-1/(ncmap-1):0]'*[1,1,1]; % grayscale for the map
cmap = [cmap;jet(N)]; % jet colormap for the districts
colormap(cmap);

% adjust the viewpoint & axes
set(gca,'View',[0,90],'XLim',[1,m],'YLim',[1,n],'ZLim',[0,ncmap + N +
1])
axis ij
axis image

% plot the borders (this should be vectorized!)
for i = 1:m
   for j = 1:n
      if (i > 1) & (d(i,j) ~= d(i-1,j))
        
plot3([j,j+1],[i,i],(ncmap+N)*[1,1],'Color',[0,0,0],'LineWidth',2.0)
      end
      if (j > 1) & (d(i,j) ~= d(i,j-1))
        
plot3([j,j],[i,i+1],(ncmap+N)*[1,1],'Color',[0,0,0],'LineWidth',2.0)
      end
   end
end

Just
    imagesc(map)
(with some none default colormap if wanted) does already give some
reasonable result....

I am embarrassed to see that my two entries oth fail on the official
testsuite, although they pass the sample. Sadly, I can't come up with
an input that would cause them to fail, which makes the problem hard
to fix. Are there any special conditions or tests people have been
trying out that I might be overlooking?

"Rob Henson" <rob@mathworks.com> wrote:

> We picked Gerrymandering at the request of our consulting group.
> They will be using the winning entry in Massachussetts to ensure
> that no Republicans get elected and in Texas to make sure that
> no Democrats win. We didn't get the contract for Florida -- I
> think that they are planning to use RAND.

Kerrymandering?

Good joke, anyhow. :-)

Peter

--
If I made a copy of the The Digital Millennium Copyright Act,
would that be a violation of it?

Stijn Helsen wrote:
>
> Just
> imagesc(map)
> (with some none default colormap if wanted) does already give some
> reasonable result....

You're right, Stijn,

I have replaced BAR from the function in
message 11 with IMAGESC and it gives a
better impression, for both the map and
the result. There are at least four maps
of real countries:

1 Spain
11 France
21 India
22 GB
30 Italy

OK, five countries ...

Hello!

 > [...]
> the result. There are at least four maps
> of real countries:
>
> 1 Spain
> 11 France
> 21 India
> 22 GB
> 30 Italy

I also spotted
63 Australia

Ciao
Olli

It seems that the testsuite (the complete and the sample one) don't
test everything. n is always at least the number of non-zero
elements in the map. (So in place of getting problems with "special
inputs", I see that not correct programs can pass the test.)

Thanks, those are helpful, if not entirely satisfactory.

Looks like the following:
k1 = 10
k2 = 2
k3 = 0.02

I am not sure what map 33 is supposed...

> Looks like the following:
> k1 = 10
> k2 = 2
> k3 = 0.02

I think k2 is closer to 5/3.

> I am not sure what map 33 is supposed...

It's not just me then...

> I am not sure what map 33 is supposed...

#33 seems to be something biologically -
not sure

But what about

#56 New Zealand
#63 Australia

It's so difficult to keep abreast of developments in this competition.

Hello!

>>Looks like the following:
>>k1 = 10
>>k2 = 2
>>k3 = 0.02
>
>
> I think k2 is closer to 5/3.
>

My guess is
k1 = 10
k2 = 2
k3 = 1/60
and this value for k3 makes a lot of sense. These values match perfectly
with the values and scores in the list.

By the way, one map is a brain, perhaps one can post the number of it.

Ciao
Olli

I have been enjoying this competition tremendously (although have
probably spent a little too much time on it!) and have a few
questions and suggestions.
 
Firstly during the running of this last segment of the contest it
might be an idea to make the top, say 20, entries not visible. That
way the latest developments remain secret for a little while whilst
sufficient code is visible for other people to build on.
 
Secondly perhaps the practise of scrambling code should be
discouraged. Perhaps make it a reason for disqualification? I don't
mind other people building on my code (I think most entries since
Kristine are in some way based on that entry). However when their new
versions are not readable due to scrambling it is frustrating.
 
Does anyone know when the next deadline is? I haven't seen a list of
deadlines anywhere.
 
If anyone hasn't deciphered the algorithm behind Kristine yet, here
is a quick description.
 
The 2D problem is quite difficult to partition in an optimal manner.
However the 1D problem is somewhat simpler. Many 1D problems can be
extracted from the 2D problem (an answer to any of these is also a
valid anser to the 2D problem). My approach was, therefore, to split
the problem into a whole bunch of 1D problems. See "Two Way
Controversy" which obtains a simple approximation to the solution of
a single 1D problem. It should be noted that some solutions cannot be
obtained by solving a 1D problem.
 
Each of these problems has a different valued optimal solution which
is by necessity lower than that of the 2D problem. By solving many
different 1D versions of the 2D problem we can therefore hope to get
a good solution to the 2D problem.
 
The neat twist that has been added to this is an algorithm for
optimising the best solution that is obtained in the above manner. I
am not quite sure from whom the code for this is due but credit to
them! I had envisioned adding a step such as that but all the schemes
I dreamed up were too complicated.
 
Good luck to everyone!

> Secondly perhaps the practise of scrambling code should be
discouraged. Perhaps make it a reason for disqualification?

I agree that it should be discouraged. Not sure how though. Some of
the "real" code is pretty hard to read as well! Perhaps we just need
to ignore it.

> The neat twist that has been added to this is an algorithm for
optimising the best solution that is obtained in the above manner. I
am not quite sure from whom the code for this is due but credit to
them!

If you are referencing the K-opt at the end, that would be mine.
But, it pales in comparison to your work, of course. And, I am sure
it can be improved on. It is too slow and dumb!

Anyway, thanks for the explanation of your work.

Great work Klaas and thanks for the explanation.

I have had this feeling every competition so far and has been proven
wrong every time, but it feels like this problem is "solved" already
(current leader TLL23). Or does anyone think that there will come a
solution that trashes this one?

/Christian

For the downloadable test suite, the current leader is not definitely
not finding optimal solutions for several cases. It's not perfect,
though it does seem invincible on the competition suite. I bet the
next prize will squeeze out another fraction of a percent. If I
remember right there was a plateau on saturday afternoon in the
trucking competition too!

By the way I agree with Klaas and MRK on obfuscation - it is silly.
Thanks to Bowen for working to weed out the effects. The cleaned-up
entries seem to run a little faster each time - is there a reason for
that, or is it jitter?

Nathan

christian ylämäki wrote:
>
>
> Great work Klaas and thanks for the explanation.
>
> I have had this feeling every competition so far and has been
> proven
> wrong every time, but it feels like this problem is "solved"
> already
> (current leader TLL23). Or does anyone think that there will come a
> solution that trashes this one?
>
> /Christian

nathan wrote:
>
> Thanks to Bowen for working to weed out the effects. The cleaned-up
> entries seem to run a little faster each time - is there a reason
> for
> that, or is it jitter?
>

For the entry 'Cleaning a Monster', I removed
about 15 assignments that were never used, and
changed the operators |,& to ||,&&. This
improved speed a little, but jitter is on the
same level.

Heinrich

Hi there, I'm not up to the level that you guys achieved with this
contest.

But I had an idea about how to do this when I looked at the problem.
Couldn't code it mind you!!!

1) Work out target : target = sum(sum(map))/n;

2) Look for where only 1 element of matrix 'map' is within say 95% to
105% of target, if not look for 2 elements that sum to 95% to 105% of
target and so on, if not look for 3...

3) Then when target is found make assignment in matrix 'd'.

And repeat with whatever elements of 'map' are left for the remaining
districts.

This doesn't take into account the problem about areas having to be
contigous. Just wondering if someone did a short bit of code, based
on my amazing idea.

Dan.

Heinrich Acker wrote:
> For the entry 'Cleaning a Monster'...

Thanks for the explaination, Heinrich. I realised after posting that
you'd done a lot of cleanup work too.
Nathan

Hi --

I don't have anything substantive to contribute to the contest itself.
I've tried to write a couple of programs, but mine aren't any better at
solving NP-hard problems than the contributions that are being made.

But I do have something to contribute to the scoring process. It even
involves a fews bits of numerical linear algebra.

Our "sparse" function can be used to accumulate the populations.

The scoring function is actually the infinity norm of the deviation.

Something called the Dulmage-Mendelsohn decomposition of the connectivity
graph can be used to determine if the precincts are connected. The
D-M decomposition was introduced into MATLAB by John Gilbert. It's handy
for lots of things. It permutes a matrix of 0's and 1's into a block
triangular form. A precinct is connected if and only if its D-M
decomposition consists of only one block. See "help dmperm" for a
few more details.

Here is my grading function. It's about 50% faster than the one that
is distributed in gerrymander.zip.

  -- Cleve Moler
  moler@mathworks.com

%------------------------------------

function score = grade(A,num,B);
% GRADE Grader for the Gerrymander contest.
% grade(A,num,B) for a population map A, a number of precincts num,
% and a precinct numbering B, checks if B is a valid numbering
% and returns its score.

% Check if valid

if any(size(A) ~= size(B))
   warning('Dimensions do not match')
end

pops = full(sparse(B(:),1,A(:))');

if ~isequal(find(pops),1:num)
   warning('All precincts must be represented')
end

if ~isconnected(B)
   warning('Precincts must be connected')
end

% Score it

score = 100*norm(pops-mean(pops),1)/(2*sum(pops));

%------------------------------------

function ok = isconnected(B,ks)
% ISCONNECTED Check if precincts are connected.
% ISCONNECTED(B) is true if all precincts are connected.
% ISCONNECTED(B,k) is true if the k-th precinct is connected.

if nargin < 2
   ks = 1:max(B(:));
end

% The precinct is connected if the Dulmage-Mendelsohn decomposition
% of the connectivity graph has a single upper triangular block.

[m,n] = size(B);
m = m+2;
n = n+2;
for k = ks(:)'

   % Put zeros around the edge.
   C = zeros(m,n);
   C(2:m-1,2:n-1) = (B==k);

   % Construct the graph.
   L = find(C);
   C(L) = 1:length(L);
   I = [C(L); C(L); C(L); C(L); C(L)];
   J = [C(L); C(L-1); C(L+1); C(L-m); C(L+m)];
   G = sparse(I(J~=0),J(J~=0),1);

   % Find its D-M decomposition
   [p,q,r,s] = dmperm(G);

   % Check for just one block
   ok = length(r) == 2;
   if ~ok, break, end
end

In article <c6ghi5$4cj$1@madmax.mathworks.com>,
I <moler@mathworks.com> wrote:
> ...
> The scoring function is actually the infinity norm of the deviation.
> ...

That should say "one norm", not "infinity norm". The program is correct.

  -- Cleve

Me too

That seems to be the case! the machine is getting slower? I submitted
Nathan's No. 1 without any changes (TestInconsistentTime)and by
removing an uneeded pair of parentheses (Time Test) and I got 16.23
and 16.13 instead of 15.85. If I am not mistaken, with almost the
same "Result" this is greatly affecting the score!

Nathan wrote:
>
>
> I submitted 5 copies of the same code (Martijn's Tweak 2_ and
> timing
> jitter test 1 to 4). The CPU times were
> 15.85 15.90, 15.97, 16.05 and 16.17 s. Is that variability at the
> level you would expect?
> Nathan
>
> (By the way, it really wasn't a cheap tactic - I was just curious.)

This also was not a cheap tactic. I did this because I sent earlier
a number of tweeks that my profiler says are much faster but they got
a higher CPU time!

KHH wrote:
>
>
> Me too
>
> That seems to be the case! the machine is getting slower? I
> submitted
> Nathan's No. 1 without any changes (TestInconsistentTime)and by
> removing an uneeded pair of parentheses (Time Test) and I got 16.23
> and 16.13 instead of 15.85. If I am not mistaken, with almost the
> same "Result" this is greatly affecting the score!
>
> Nathan wrote:
>>
>>
>> I submitted 5 copies of the same code (Martijn's Tweak 2_ and
>> timing
>> jitter test 1 to 4). The CPU times were
>> 15.85 15.90, 15.97, 16.05 and 16.17 s. Is that variability at
the
>> level you would expect?
>> Nathan
>>
>> (By the way, it really wasn't a cheap tactic - I was just
> curious.)

Min Poh wrote

> The next MATLAB Programming Contest starts on Wednesday, April 21,
> 2004 at 9 a.m. EST. This contest runs for a week and ends on
> Wednesday, April 28 at 5 p.m. EST.

Just a remark from an interested observer. I see a general
tendency as in previous contests that solver function become
an irritatingly long patchwork of different approaches. The currently
leading entry has 29k and >1000 lines of code! Contestants
increasingly concentrate on tweeking performance by shuffling
code between vectorization and JIT acceleration and on tuning
the algorithm mix to the test suite.
The result is 1) unreadable 2) unmaintainable 3) badly structured
4) completely undocumented, 5) maybe worthless for data beyond the
test suite, etc.

In other words, a hack and not a program.

Enough complaints. Here my proposal:

  Include the number of statements in the scoring function!!

sTefan

Stefan Stoll wrote:
>
>
> Min Poh wrote
>
>> The next MATLAB Programming Contest starts on Wednesday, April
> 21,
>> 2004 at 9 a.m. EST. This contest runs for a week and ends on
>> Wednesday, April 28 at 5 p.m. EST.
>
> Just a remark from an interested observer. I see a general
> tendency as in previous contests that solver function become
> an irritatingly long patchwork of different approaches. The
> currently
> leading entry has 29k and >1000 lines of code! Contestants
> increasingly concentrate on tweeking performance by shuffling
> code between vectorization and JIT acceleration and on tuning
> the algorithm mix to the test suite.
> The result is 1) unreadable 2) unmaintainable 3) badly structured
> 4) completely undocumented, 5) maybe worthless for data beyond the
> test suite, etc.
>
> In other words, a hack and not a program.
>
> Enough complaints. Here my proposal:
>
> Include the number of statements in the scoring function!!
>
> sTefan

I agree. It would be great if the contests promoted good programming
practices not the opposite.

> Stefan Stoll wrote:
>> The result is 1) unreadable 2) unmaintainable 3) badly
structured
>> 4) completely undocumented, 5) maybe worthless for data beyond
> the
>> test suite, etc.
>>
>> In other words, a hack and not a program.
>>

Duane Hanselman wrote:
> I agree. It would be great if the contests promoted good
> programming
> practices not the opposite.

I don't think so. The winning competitors consistently produce
creative, elegant innovations. In between these leaps, granted, there
is a lot of tedious tuning, of which I've been guilty. The code that
evolves is good code, by definition - it is near optimal for a very
specific task under particular constraints. Taking part in the
competition has made my programming better - I write and debug more
quickly, and I code with an eye for efficiency. And my coding style
in the contest is not the same as my style at work, where different
constraints apply.
Nathan

Stefan Stoll wrote:
>
> The result is 1) unreadable 2) unmaintainable 3) badly structured
> 4) completely undocumented, 5) maybe worthless for data beyond the
> test suite, etc.
>
> In other words, a hack and not a program.
>
> Enough complaints. Here my proposal:
>
> Include the number of statements in the scoring function!!
>
> sTefan

I agree to the comments on the result, but I don't think that the
proposal will help. Contestants will tweak as much algorithm as
possible into few very complex statements. Some are very good at
this, as you could see in the last contest ('Golf'). The result could
be described by your attributes 1) to 5), but will be shorter.

I have thought about p-code length as a part of the scoring function,
but then I found out that it varies with length of variable names.
Since shorter names give shorter p-code, we will end with unreadable
code again.

Anybody who has a better suggestion on this can do a lot for the
contest.

Heinrich

Heinrich Acker wrote

> Stefan Stoll wrote:
>>
>> Include the number of statements in the scoring function!!
>
> I have thought about p-code length as a part of the scoring function,
> but then I found out that it varies with length of variable names.
> Since shorter names give shorter p-code, we will end with unreadable
> code again.

Interesting, I didn't know that. It could be circumvented
with a preprocessor function replacing all identifiers in a
submitted m-file by unique identifiers with a standard length
before p-coding it.

sTefan

A score based on code length certainly would lead to more readable
code, but in some ways it would make the contest more frustrating. At
the moment we have to trade off speed and functionality in every
modification - code length would be a third dimension in this
optimisation.
Nathan

I wrongly put this in a separate thread so I am reposting and posting
Stefan's replies..

This is new!
 
Entry SQ1 has less CPU time and exactly the same result but Ranks
after K10mod??
 
Khh
K10mods nathan 1 4.8571 13.80 0.234% 2004-04-27 06:47:05 26453
SQ3 KHH 2 4.8579 13.77 0.234% 2004-04-27 06:52:32 26453
Khh wrote

> Entry SQ1 has less CPU time and exactly the same result but Ranks
> after K10mod??
>
> Khh
> K10mods nathan 1 4.8571 13.80 0.234% 2004-04-27 06:47:05 26453
> SQ3 KHH 2 4.8579 13.77 0.234% 2004-04-27 06:52:32 26453

That's indeed strange. It could be that the results of the
two are different after the 3rd decimal place. The constants
of the scoring function seem to be close to k1 = 10, k2 = 2,
and k3 = 1/60, so a difference of 0.0001 in the result changes
the score by 0.001.

sTefan

Stefan Stoll wrote

> Khh wrote
>
>> Entry SQ1 has less CPU time and exactly the same result but
Ranks
>> after K10mod??
>>
>> Khh
>> K10mods nathan 1 4.8571 13.80 0.234% 2004-04-27 06:47:05 26453
>> SQ3 KHH 2 4.8579 13.77 0.234% 2004-04-27 06:52:32 26453
>
> That's indeed strange. It could be that the results of the
> two are different after the 3rd decimal place. The constants
> of the scoring function seem to be close to k1 = 10, k2 = 2,
> and k3 = 1/60, so a difference of 0.0001 in the result changes
> the score by 0.001.

The number of significant digits is inconsistent:
- result: 3 significant digits
- CPU time: 4 significant digits
- score: 5 significant digits
Due to error propagation, the score shouldn't have
more than 3 digits. Or the number of significant digits
of result and CPU time should be raised to 5.

With the current displayed accuracy on the contest web site,
you wouldn't pass any exam in elementary data analysis...

sTefan

The results aren't exactly the same. Only three decimal places are
displayed on the results page.

Mike

KHH wrote:
> I wrongly put this in a separate thread so I am reposting and posting
> Stefan's replies..
>
> This is new!
>
> Entry SQ1 has less CPU time and exactly the same result but Ranks
> after K10mod??
>
> Khh
> K10mods nathan 1 4.8571 13.80 0.234% 2004-04-27 06:47:05 26453
> SQ3 KHH 2 4.8579 13.77 0.234% 2004-04-27 06:52:32 26453
> Khh wrote
>
>
>>Entry SQ1 has less CPU time and exactly the same result but Ranks
>>after K10mod??
>>
>>Khh
>>K10mods nathan 1 4.8571 13.80 0.234% 2004-04-27 06:47:05 26453
>>SQ3 KHH 2 4.8579 13.77 0.234% 2004-04-27 06:52:32 26453
>
>
> That's indeed strange. It could be that the results of the
> two are different after the 3rd decimal place. The constants
> of the scoring function seem to be close to k1 = 10, k2 = 2,
> and k3 = 1/60, so a difference of 0.0001 in the result changes
> the score by 0.001.
>
> sTefan
>
> Stefan Stoll wrote
>
>
>>Khh wrote
>>
>>
>>>Entry SQ1 has less CPU time and exactly the same result but
>
> Ranks
>
>>>after K10mod??
>>>
>>>Khh
>>>K10mods nathan 1 4.8571 13.80 0.234% 2004-04-27 06:47:05 26453
>>>SQ3 KHH 2 4.8579 13.77 0.234% 2004-04-27 06:52:32 26453
>>
>>That's indeed strange. It could be that the results of the
>>two are different after the 3rd decimal place. The constants
>>of the scoring function seem to be close to k1 = 10, k2 = 2,
>>and k3 = 1/60, so a difference of 0.0001 in the result changes
>>the score by 0.001.
>
>
> The number of significant digits is inconsistent:
> - result: 3 significant digits
> - CPU time: 4 significant digits
> - score: 5 significant digits
> Due to error propagation, the score shouldn't have
> more than 3 digits. Or the number of significant digits
> of result and CPU time should be raised to 5.
>
> With the current displayed accuracy on the contest web site,
> you wouldn't pass any exam in elementary data analysis...
>
> sTefan

KHH wrote:
>
>
> I wrongly put this in a separate thread so I am reposting and
> posting
> Stefan's replies..
>
> This is new!
>
> Entry SQ1 has less CPU time and exactly the same result but Ranks
> after K10mod??
>
> Khh
> K10mods nathan 1 4.8571 13.80 0.234% 2004-04-27 06:47:05 26453
> SQ3 KHH 2 4.8579 13.77 0.234% 2004-04-27 06:52:32 26453
> Khh wrote
>
>> Entry SQ1 has less CPU time and exactly the same result but
Ranks
>> after K10mod??

There are 4 decimal places shown in results on the chronological
results page, but even there the scores are identical, at 0.2340%. I
think that uncertainty of 1e-5% is just enough to result in a worse
overall score for SQ1 despite its better time. A little bit of luck
on the clock could have sent it either way...
Nathan

Joe Ercolino wrote:
>
>
> Where is the mat3d function that appears in the mid-contest
> analysis?
> I couldn't find anything in the matlab documentation.
>
> Joe

This the mat3d file we are using in the mid contest analysis, it is
not warranted it will work for all possible partitions but if there
are not rare cases it may help you to visualize your maps.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function mat3d(X,D,f)
% X is the matrix with indices (integers)
% M is the population density matrix
% f used to magnify the error showed by the height of the blocks

h=figure('color',[1 1 1],'renderer','opengl');
uih=uicontrol('Style','text','Position',[350 5 200
20],'BackgroundColor',[1 1 1]);
set(h,'Userdata',uih,'toolbar','figure')

u=unique(X(:));

for i = 1:numel(u)
   if u(i)~=0
    M = X==u(i);
    popo(i) = sum(D(M));
   end
end

popr=max(0,popo-min(popo)*f);

for i = 1:numel(u)
   if u(i)~=0
   h=[];
   M = X==u(i);
   pop = popr(i);
   [vx,vy] = mtx2vec(M);
   h(1)=patch(vx,vy,zeros(numel(vx),1)+pop,i);
   h(2)=patch(vx,vy,zeros(numel(vx),1),i);
   for j = 1:numel(vx)-1
       h(2+j)=patch(vx([j j+1 j+1 j]),vy([j j+1 j+1 j]),[0 0 pop
pop],i);
   end
   set(h,'Tag',sprintf('Pop: %5.2f, Reg: %d',popo(i),i))
  
set(h,'ButtonDownFcn','set(get(gcbf,''UserData''),''string'',get(gcbo,
''Tag''))')
   end
end

axis([0 size(X,2) 0 size(X,1) 0 max(pop)*1.5])
view([60 45]);
camlight headlight
lightangle(0,30)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%
function [vx,vy] = mtx2vec(M)

x=[];

T=diff([zeros(1,size(M,2));M;zeros(1,size(M,2))],[],1);
for i = 1:size(M,2)
    h=find(T(:,i))-1;
    x = [x ; [[h zeros(size(h))+i-1] [h zeros(size(h))+i]
T(h+1,i)>0]];
end

T=diff([zeros(size(M,1),1),M,zeros(size(M,1),1)],[],2);
for i = 1:size(M,1)
    h=find(T(i,:))-1;
    x = [x ; [[zeros(size(h(:)))+i-1 h(:)] [zeros(size(h(:)))+i h(:)]
T(i,h+1)'<0]];
end

h=find(x(:,5));temp = x(h,[1 2]);x(h,[1 2])=x(h,[3 4]);x(h,[3
4])=temp;x(h,5)=0;

y=[];
y(1,:) = x(1,[3 4]);
h(1)=false;
n=0;
while n~=1
  n=find(sum(abs(repmat(y(end,:),size(x,1),1)-x(:,[1 2])),2)==0);
  y(end+1,:)=x(n,[3 4]);
  h(n)=false;
end

h = zeros(size(y,1),1);
for i = 2:numel(h)-1
    if all((diff(y([i-1 i],:))-diff(y([i i+1],:)))==0)
        h(i)=1;
    end
end

vx=y(~h,2);
vy=y(~h,1);

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%

nathan wrote:
>
> A score based on code length certainly would lead to more readable
> code, but in some ways it would make the contest more frustrating.
> At
> the moment we have to trade off speed and functionality in every
> modification - code length would be a third dimension in this
> optimisation.
> Nathan

Why not drop the speed from the scoring function then, since it is
not reproduceable, causes so much headache, and makes us submit the
same function 100 times? All that unproductive replacement of

n*ones(size(x)), length(a)==0, etc

with

0*x+n, isempty(a), etc (or vice-versa!!!)

would be gone. The number of entries would be less than 30% of what
we have now, the contest would be easier to follow.

If you think this is too radical, since speed matters - what do you
think about this:

T_limits = logspace(0,2,10);
time_class = sum(T_limits<elapsed_time);
score_new = score_result + k4*time_class + k5*pcode_length;
% pcode_length with Stefans suggestion from message 42

Heinrich

Why Yi Cao's 'RepeatTest1' can not pass the testsuite released by
Contest Team?
Some earlier entries were involved with this similar phenomena.
Maybe offical suite is not robust:)

There was a bug in the display of the "results" field on some of the
web pages. The results are recorded as strings in the database, like
"4.179%". The code that constructs the table was recasting this
string to a number and then displaying it with an additional bogus
decimal place, like "4.1790". This could lead to some confusing
scores, like KHH and others pointed out. I corrected the this
problem.

Unfortunately, because the "results" field is stored as a string, I
can't easily increase the number of digits displayed. The "score",
however, is computed by MATLAB using the original double values of
"result" and "cpu time", so no accuracy is lost.

I also increased the number of digits displayed in the "cpu time"
field, since it is stored in the database as a number. I hesitated a
little because, as nathan and others have pointed out, these extra
digits far exceed the timing accuracy of the machine. Nevertheless,
these somewhat arbitrary digits affect your final score, so it makes
sense to display them.

We've tried to improve the accuracy of the timing in this contest by
running each entry twice and taking the timing from the second run.
This reduces the disk access, which adds a lot of noise. We're also
now running on a stripped-down Linux with only vital processes
running. Modern operating systems have so much caching and other
effects, however, there is still a good deal of variability. This is
probably exacerbated by the relatively short run times in this
contest. I'm hoping there's more we can do to improve this in the
future.

We're enjoying following your discussion here. Keep your feedback
coming.

Sincerely,
Matthew Simoneau
The MathWorks, Inc.

Hi,
could someone please explain how these
 if s>80 && s<185
statements are supposed to work. I assume it enables certain
algorithms only for certain test cases.

But I tried some things (I mean real algorithmic changes) on the test
suite and there was improvement. Then I enabled the change only for a
specific score range and it was much faster. But on the server I cant
see any change. I mean I understand that the test suite is different
from the one on the server, but how do you guys know these magic
scores, for which to enable algorithms. Please don't tell me you're
just guessing by submitting dozens of entries.
regards,
Jan

I sugguest to reduce or even vanish the factor of the runtime, when
score down to
a threshold(10s or 15s).Afterall,we want the best result,not the
shortest runtime.

Hi,Jan Langer:
    I'm sure guessing have existed in the course of contest.Afterall,
no perfect solution in those NP-problems.But this condition is not
useful for inspired algorithm,I think.

         Jin Mingjian

Jin Mingjian wrote:
>
>
> Why Yi Cao's 'RepeatTest1' can not pass the testsuite released by
> Contest Team?
> Some earlier entries were involved with this similar phenomena.
> Maybe offical suite is not robust:)

Yes, this is very annoying. I think the first rule change should be
that an entry must be able to run the test suite correctly. The
timing and result of the test suite can be ignored when computing the
score, but it must be successful on the test suite. It really does
seem to make a mockery of the whole thing.

MR Keenan:
   I agree with you absolutely!
   I think:
1> A bad timing is worse than no timing;
2> The offical testsuite should be more natural rather than
man-made.

Jin Mingjian wrote:
>
>
> MR Keenan:
> I agree with you absolutely!
> I think:
> 1> A bad timing is worse than no timing;
> 2> The offical testsuite should be more natural rather than
> man-made.

I think the timing of the contest is pretty good, although I wish it
were biased for more CPU-intensive algorithms.

As for man-made vs natural test suites. I am not sure what you mean.
 The test suite seems to be pretty good, IMO.

I support that most of them are very nice.(Thanks to contest team:))
But sometimes I'm too confused...such as the repeated code have some
different scores,and so on above.Of course,it is difficult to get rid
of all bugs.However,we hope more perfect contest!:)

Jan Langer wrote:
>
>
> Hi,
> could someone please explain how these
> if s>80 && s<185
> statements are supposed to work. I assume it enables certain
> algorithms only for certain test cases.
>
> But I tried some things (I mean real algorithmic changes) on the
> test
> suite and there was improvement. Then I enabled the change only for
> a
> specific score range and it was much faster. But on the server I
> cant
> see any change. I mean I understand that the test suite is
> different
> from the one on the server, but how do you guys know these magic
> scores, for which to enable algorithms. Please don't tell me you're
> just guessing by submitting dozens of entries.
> regards,
> Jan

I have the same doubt on the magic numbers during the contest. But
finally I know it is searched by guys through multiple submissions.

It looks like cheating or overfitting, because the algorithm by such
tunning will be less generic for testsuites other than the specific
one adopted by Mathwork team. But for the exact task, driven by
scoring measure based on the specific testsuite, you can do this.

If the generalization capacity of algorithm is called for concern, I
think the Mathwork contest team can either increase the testsuite
size such that more cases are incuded, or hide a seperate testsuite,
while scores on the genuine test set will only published after the
contest.

Anyway, the current criteria is fairly good already, it indeed drives
the evolution of coding.

Jin Mingjian wrote:
>
>
> Why Yi Cao's 'RepeatTest1' can not pass the testsuite released by
> Contest Team?
> Some earlier entries were involved with this similar phenomena.
> Maybe offical suite is not robust:)

Uh-oh... does this mean our entries are *not* checked for contiguity?
Anyone?

The solution (using "Spotless scan 20") to the first test case that
fails in runcontest (k=13) is clearly not.

Roger

nathan wrote:
>
> How about this?
> A scoring tolerance could be established which is significantly
> greater than any effect of the known timing variability (say 5
> standard deviations). To take the lead, a new entry would have to
> have a better raw result or improve the overall score by a margin
> greater than this tolerance. This would at least partly remove the
> incentive for tiny speed tweaks.

How do you sort an entry into the list, if it produces the same
result, has a shorter runtime (within the tolerance), and must not
take the lead?

Heinrich Acker wrote:
>
> How do you sort an entry into the list, if it produces the same
> result, has a shorter runtime (within the tolerance), and must not
> take the lead?

An entry moves up the list until it encounters an entry that is equal
within tolerance. If the new entry has a better raw score, it moves
ahead. If not, it's considered equal but later, and it stops there.

But never mind that. I have a better idea. Why not use the collective
problem-solving might of matlab contest fans? For the next contest,
the challenge is to write a scoring algorithm that detects tweaking,
scrambling, inelegant code, funny names for entries, helpful
commenting, sensible names for entries, overtuning, nicely structured
code, meaningful variable names, code that's short and code that's
too short. The winning algorithm will be the one that most justly
punishes the guilty and reward the virtuous!

Nathan
Nathan

Jan Langer wrote:
> Hi,
> could someone please explain how these
> if s>80 && s<185
> statements are supposed to work.Please don't tell me you're
> just guessing by submitting dozens of entries.
> regards,
> Jan

I'm just guessing by submitting dozens of entries. Datamining and
overfitting have a long history in this contest. I don't really like
it but as long as it is allowed I'm prepared to do it. Several
suggestions have been made to avoid this. One way would be to name an
overall winner based on a hidden testsuit.

That said I have to say that the current format is pretty good. One
just have to realize that we are not finding the best generic solver
we are just trying to beat the testsuit.

Im really glad that my global variable OZZY got cleaned out, but who
knows it might appear again :)

/Christian

nathan wrote:
>
>
> Heinrich Acker wrote:
>>
>> How do you sort an entry into the list, if it produces the same
>> result, has a shorter runtime (within the tolerance), and must
> not
>> take the lead?
>
> An entry moves up the list until it encounters an entry that is
> equal
> within tolerance. If the new entry has a better raw score, it moves
> ahead. If not, it's considered equal but later, and it stops there.

The idea is flawed - I suppose that's what you were getting at,
Heinrich. An entry that beat the leader by 1.5*tolerance could get
stuck behind one that beat it by 0.8*tolerance. But maybe that is ok.
Maybe there could be a regular ranking table with a leader (not
necessarily #1 in the table), defined as the last entry to make a
significant break from the pack?

nathan wrote:
>
> An entry moves up the list until it encounters an entry that is
> equal
> within tolerance. If the new entry has a better raw score, it moves
> ahead. If not, it's considered equal but later, and it stops there.

Sorry, but I think you missed a point here. The problem with your
proposal is that you do not sort the entries by their performance any
more. An example:

Entry Rank Time Result
ABC 1 9.1 1%
DEF 2 9.3 1%
GHI 3 9.5 1%

With a tolerance of 0.1 s, for instance, the new entry XYZ (9.05, 1%)
now reaches rank 2. OK. Next entry XYZ2 (8.95, 1%) is succesively
compared to existing entries from below and reaches rank 3, although
it is better than ABC for more than the tolerance.

Min Poh wrote

> The next MATLAB Programming Contest starts on Wednesday, April 21,
> 2004 at 9 a.m. EST. This contest runs for a week and ends on
> Wednesday, April 28 at 5 p.m. EST.

Just an additional suggestion for improving the
web interface

  Supply buttons for
  download and upload of m-files.

Currently, one has to copy/past from and to edit
fields on the "Edit an Entry" and the "Submit a
New Entry" pages. This is very impractical.

Ideally, there could be a button "Edit in MATLAB
editor"...

sTefan

vincent wrote:
>
>
> Jan Langer wrote:
>>
>>
>> Hi,
>> could someone please explain how these
>> if s>80 && s<185
>> statements are supposed to work. I assume it enables certain
>> algorithms only for certain test cases.
>>
>> But I tried some things (I mean real algorithmic changes) on
the
>> test
>> suite and there was improvement. Then I enabled the change only
> for
>> a
>> specific score range and it was much faster. But on the server
I
>> cant
>> see any change. I mean I understand that the test suite is
>> different
>> from the one on the server, but how do you guys know these
magic
>> scores, for which to enable algorithms. Please don't tell me
> you're
>> just guessing by submitting dozens of entries.
>> regards,
>> Jan
>
> I have the same doubt on the magic numbers during the contest. But
> finally I know it is searched by guys through multiple submissions.
>
> It looks like cheating or overfitting, because the algorithm by
> such
> tunning will be less generic for testsuites other than the specific
> one adopted by Mathwork team. But for the exact task, driven by
> scoring measure based on the specific testsuite, you can do this.
>
> If the generalization capacity of algorithm is called for concern,
> I
> think the Mathwork contest team can either increase the testsuite
> size such that more cases are incuded, or hide a seperate
> testsuite,
> while scores on the genuine test set will only published after the
> contest.
>

The problem is that you are never able to generate a really general
code. We always have resource limited. We have to trade off many
things, speed, memory, accuracy and so on. For example, without guess
and try, how do you determine what is the maximum size of problem you
are going to solve? Different size of problem, you have to take
different strategies to program. Particularly for NP hard problem, no
algorithms can suit for all problems.
> Anyway, the current criteria is fairly good already, it indeed
> drives
> the evolution of coding.

This is the first Matlab programming contest I have followed closely,
and I have been enjoying it immensely even though I haven't had time
to contribute anything since Thursday. I have a few comments on
issues that have come up in the thread:

Klaas Hartmann wrote:
 
> Firstly during the running of this last segment of the contest it
> might be an idea to make the top, say 20, entries not visible. That
> way the latest developments remain secret for a little while whilst
> sufficient code is visible for other people to build on.

Perhaps it would suffice to hide the entries still in the queue.
Most of the time the queue is mostly empty, and entries would show up
right away. But just before deadlines, when the queue tends to fill
up, entries would have a bit more time before they became public.

Second, I have some comments about the timing issue. One approach
would be to run each entry n times (n = 5, say) and take the median
time. This would reduce the jitter somewhat, more the larger n is.

I think the "significant improvement" method also has merit, although
it is more complicated to explain. You would have to run it as
follows: entries with similarities within the significance threshold
would be grouped together and ranked according to submission time.
To move above a group, you would only have to beat the lead
(original) submission in the group.

We have one more mid-contest prize with a new twist. Between 12 and
3 PM EDT, we will have a Sixty Second Best Results Showdown. If your
code gets the lowest results percentage, you win a MATLAB T-shirt.
There is no time penalty as long as your code finishes in less than
60 seconds of CPU time. I posted it here because the deadline is
approaching fast. Good luck.

Matthew Simoneau wrote:
>
>
> We have one more mid-contest prize with a new twist. Between 12
> and
> 3 PM EDT, we will have a Sixty Second Best Results Showdown. If
> your
> code gets the lowest results percentage, you win a MATLAB T-shirt.
> There is no time penalty as long as your code finishes in less than
> 60 seconds of CPU time. I posted it here because the deadline is
> approaching fast. Good luck.

How do you decide the winner if there is a tie?

christian ylämäki wrote:
>
>
> Matthew Simoneau wrote:
>>
>>
>> We have one more mid-contest prize with a new twist. Between
12
>> and
>> 3 PM EDT, we will have a Sixty Second Best Results Showdown.
If
>> your
>> code gets the lowest results percentage, you win a MATLAB
> T-shirt.
>> There is no time penalty as long as your code finishes in less
> than
>> 60 seconds of CPU time. I posted it here because the deadline
is
>> approaching fast. Good luck.
>
> How do you decide the winner if there is a tie?

:) tricky question, simple 'first achieved,first T-shirt served '?
if a tie comes, people will start tuning parameters.

if (score1 == score2) && (t1_submitted < t2_submitted)
    if t1_span > t2_span
       disp('try to tuning contestant1's code(parameter) for a little
bit more running-time except it is 3PM or his code exactly lives
60.000 sec');
    elseif t1_span <= t2_span
       disp('what's a real killer!');
    end;
end;

Maybe, the Mathwork team are telling us that some secrets are hiding
in the parameters, or the current results are not as they expect:)

In event of a tie to the three decimal places displayed in the result
field, the winner will be the first one submitted. I added a table
to the statistics to help:

 <http://www.mathworks.com/contest/gerrymander/statistics.html>

"Roger Stuckey" <Roger.Stuckey@dsto.defence.gov.au> wrote in message
news:eed9c6e.58@webx.raydaftYaTP...
> Jin Mingjian wrote:
> >
> >
> > Why Yi Cao's 'RepeatTest1' can not pass the testsuite released by
> > Contest Team?
> > Some earlier entries were involved with this similar phenomena.
> > Maybe offical suite is not robust:)
>
> Uh-oh... does this mean our entries are *not* checked for contiguity?
> Anyone?

There was a bug in the "pattern" function that has been in since very early
on. "pattern" was not robust to maps with less than three regions. Yi Cao's
clever idea of looking for repeated sub-regions trips over this in the
sample suite but not in the actual suite (where it seems that the repeated
regions are more complex than in the sample suite). This problem was first
reported on Saturday but didn't become an issue until Yi Cao's submission.
Both Yi Cao and Mr. Bond provided fixes for this fairly quickly after it was
reported for the second time.

Rob Henson
The MathWorks, Inc.

> The solution (using "Spotless scan 20") to the first test case that
> fails in runcontest (k=13) is clearly not.
>
> Roger

Look at the sample solver function provided by the mathworks, it
still take more than 60 seconds. I suspect that even if the solver
function takes no time, the runcontest function will take more than
60 seconds to check the result (grade function is very slow), thus,
this task may not be possible, unless there's some way to cheat.

Min Poh wrote:
>
>
> The next MATLAB Programming Contest starts on Wednesday, April 21,
> 2004 at 9 a.m. EST. This contest runs for a week and ends on
> Wednesday, April 28 at 5 p.m. EST.
>
> We've been listening to feedback from our contestants and the
> upcoming contest will use a slightly different format. In the early
> stages of this contest, you will have the opportunity to work
> independently, without your code being visible to others. More
> detail
> will be provided on the day of the contest, so be sure to check
> back
> then and get a head start!
>
> <http://www.mathworks.com/contest/>
>
> 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.
>
> As usual we'll be holding several mid-contest prize giveaways of
> MATLAB T-shirts, lunch bags, and other good stuff, so don't wait
> until the last minute to participate.
>
> We look forward to seeing your entry. Good luck!
>
> -Min
>
> Min Poh
> The MATLAB Central Team
> The MathWorks, Inc.

Congratulations to Paulo Uribe, and great thanks to the Matlab
Central Team.

Well, that was some fun, and went very smoothly. Congratulations to
Paulo Uribe, and to all the other winners, and well done The MathWorks
for keeping it all under control.

The contest task was interesting enough, and simple enough to define.
This was good.

Darkness seemed to me of less value than twilight. Perhaps if I could
at least know if my entries have passed or failed during darkness, that
would be helpful. Still, I imagine darkness was useful for the contest
organisers as they could check and tune the scoring parameters without
public scrutiny.

Twilight was a good phase. I could see where I was at, and what to aim
for.

I like the idea that you can't see other peoples code straight away.
Perhaps that could be extended throughout the contest. Have code
visible for all but the top ten entries. When the code moves down the
ranks a bit, we can find out what made it work. Until then, it remains
a secret.

Mid contest prizes are fun too. Tuesday leap, and sixty second best
results seemed like the best ones to me.

As for keeping the length of code manageable and readable, I think that
is up to us, the contestants, rather than something to be enforced or
rewarded by the contest rules. Keep the scoring system simple, and
easily measured. (Bring back the flops command!)

The score system used this time seems good to me. Exponential penalty
on time is appropriate.

 
--
Dr Tristram J. Scott
Energy Consultant

Hi,
it was my first contest and i basically liked it a lot. i considered
the twilight phase a good thing, although i wondered the whole day
why some guys had results and runtime ten or twenty times faster than
mine ;-).

the task was very interested and well described.

the best prize was in my opinion the big sunday push. it was very
motivating to see all of your own improvements count for you. the
other prizes seem to encourage the holding back of entries until the
last minute without testing them.

maybe an overall score improvement prize (perhaps scaled according to
the phase of the contest) should be considered.

an current table of the leaders in the small prizes should be
published too, because i didnt knew on sunday who is the leader and
what are the differences.

what i didnt like was this "beating the testcase" method which
dominated the end of the contest.

i also tried to do this by using random starting points for the ozzy
function and searching for certain rand seeds which gave improvement.
i actually found a few and tried to cut runtime by enabling them only
for certain map sizes. the problem is that you need to make your
whole program slower or more ineffective to keep your approach
hidden. furthermore you really need to send a couple of dozens of
entries to get results. this also made me the "most active"
participant.

unfortunately i managed to send the entry a few minutes too late
after 11pm, b/c i didnt get home in time.

though in conclusion i think this "approach" should be discouraged,
and the whole contest should be converted into a big sunday push.

but i learned a lot about matlab and algorithms in general and im
looking forward to the next contest in fall.
regards
jan

Great contest! Thanks to the organising team, congrats to the
winners, and thanks to all the competitors for making it such fun.
There were some really awesome feats of programming combined with
strategic competitive genius. It was interesting that some of the
winners and most influential entries were well written and commented
- competitive success is compatible with "good" programming. But I am
glad it's over.

All the innovations in the competition were very welcome. Darkness
was a good chance to really think about the problem and the code
without pressure. So was twilight, with more competitive pressure but
some measure of success, but without the wearying need to keep up to
date with the latest code. Both should be retained. I particularly
enjoyed the 24 hour push because it wasn't necessary to strategise
about timing the release of new code. The 60 second contest was a
revelation - it was so sweet not to have to agonise about every loop,
assignment and parameter. The fact that it was run over a relatively
period meant it didn't degenerate into tuning around the timeout
barrier. Maybe the limited precision of the score was significant
too. Timing jitter obviously has been an issue but maybe there is the
beginning of a solution among the suggestions floated here. I don't
think we need to worry too much about sorting the ranking list - is
the number 2 spot important?

I think various new features of this contest addressed all of the
problems inherent in the format in different ways. Thanks again, and
see you all next time.

Nathan

I love this game very much, and appreciate the open and fair platform
provided by the Mathwork team. It is exciting to learn new algorithms
and new tricks, eventually contributing my own.

I agree that a darkness phase isn't comfortable because we are always
afraid of getting no response after a submission.

For the contest setup, I may have following proposal:

1) testsuites are divided into three groups:

1.1) testsuite in daylight: it is the test suite you can download for
evaluating your algorithm in your local machine.

1.2) testsuite in twilight: scores on the suite are used by Mathworks
for ranking contests during the game, as well as for encouraging us
attacking some subtasks like 'largest leap', 'first break', and
'rushing 60s'. Also scores on this suite weighs a significant portion
in final judgement.

1.3) testsuite in darkness: you will not see the score for this
testsuit unless the end of game, but the score will be counted in
final overall judgement.

2) For code visibility, 4 or more stages can be adopted:

2.1) a twilight stage at beginning to force people to design their
own algorithm.

2.2) then a daylight stage to allow all kinds of tuning,new
implementation and new algorithms.

2.3) from time to time, a dark-cloud appears for hiding some
contests' informaton (may be the best submission in Top 10 / or his
recent attempts/ or his evolution history). Certainly it is hard to
specify it, maybe just let the Mathwork play dice.

2.4) a darkness stage in the last several (e.g. 5~10) minutes,
because it is usually true that we cannot see the quene in the last
(2~3) minutes.

Vincent, Zhili Wu

vincent wrote:
>
>
> I love this game very much, and appreciate the open and fair
> platform
> provided by the Mathwork team. It is exciting to learn new
> algorithms
> and new tricks, eventually contributing my own.
>
> I agree that a darkness phase isn't comfortable because we are
> always
> afraid of getting no response after a submission.
>
> For the contest setup, I may have following proposal:
>
> 1) testsuites are divided into three groups:
>
> 1.1) testsuite in daylight: it is the test suite you can download
> for
> evaluating your algorithm in your local machine.
>
> 1.2) testsuite in twilight: scores on the suite are used by
> Mathworks
> for ranking contests during the game, as well as for encouraging us
> attacking some subtasks like 'largest leap', 'first break', and
> 'rushing 60s'. Also scores on this suite weighs a significant
> portion
> in final judgement.
>
> 1.3) testsuite in darkness: you will not see the score for this
> testsuit unless the end of game, but the score will be counted in
> final overall judgement.
>
> 2) For code visibility, 4 or more stages can be adopted:
>
> 2.1) a twilight stage at beginning to force people to design their
> own algorithm.
>
> 2.2) then a daylight stage to allow all kinds of tuning,new
> implementation and new algorithms.
>
> 2.3) from time to time, a dark-cloud appears for hiding some
> contests' informaton (may be the best submission in Top 10 / or his
> recent attempts/ or his evolution history). Certainly it is hard
> to
> specify it, maybe just let the Mathwork play dice.
>
> 2.4) a darkness stage in the last several (e.g. 5~10) minutes,
> because it is usually true that we cannot see the quene in the last
> (2~3) minutes.
>
> Vincent, Zhili Wu
I like the idea about darkness stage at the end of contest because it
will prevent someone to resubmit otherone's code waiting in the
queue. Therefore, it will encourage people to submit final code
earlier.

Three testsuites may make contest too complicated. But using the open
testsuite for validation of any entry may encourge people to test
their code before submission.

Big sunday push is a good format. It does encourage people to submit
their code in time. The Tuesday Leap also makes contestants to think
overall performance of their code.

Yi Cao

I also think Darkness and Twilight are both good ideas. Only change
I would make is to add an extra day of Darkness (but that is probably
not a general preference).

I liked the Sunday push and the 60 seconds showdown the best. The
Tuesday leap the least. I wonder if the Tueday leap had been on
Wednesday if there would have been any takers. That might be more
interesting!

It may be interesting to make the last few hours be in twilight.

A rule change I would make is that an entry must succeed on the test
suite.

I would bias CPU less so that more CPU-intensive algorithms have a
chance. I think we could have done better on this problem but the
CPU time seemed to keep getting in the way. GA approaches for
example didn't seem to have a chance.

Another great contest. Thanks to the Mathworks team and
congratulations to Paulo -- the Tiger Woods of Matlabbing!!!

Congratulations to the Contest Team for designing such a great
contest. It was my 5th, and the one that I liked most. It was nice to
see several suggestions from contestants implemented this time. The
way they were implemented deserves a big applause: While most
suggestions are written to convince others that the suggestion is the
one and only way to improve the contest, the Contest Team has shown
that it is possible to satisfy different tastes in one contest.

Two things stand out in my opinion:

1) Darkness and Twilight: These phases encourage the contestants to
develop a complete solution themselves. I did so for the first time,
and take much pride from beeing able to get a result of 0.616% (much
more than the winning entry) without using other contestants
intellectual property. For me, darkness could be shorter, twilight
longer.

2) The different prizes during the contest: There have always been
critics who pointed out that there is no reward for people who
develop smart solutions during the contest, now there is. I like that
new metrics have been introduced for this. Whether you like the hunt
for speed or for the best result, you find the contest designed for
you.
This applies also for the daddies among the contestants, who always
wanted a shorter duration of the contest - taking part only until
daylight is a solution.

I think the biggest challenge that the Contest Team faces for the
next contest is finding a problem that differs from the last ones.

Improving the rules is a difficult task. Some suggestions that have
been made simply won't work, I hope nobody is offended by this
statement. A few examples how unsportsmanlike individuals (we have
seen this) can spoil the contest if the rules are not designed well:

1) Hiding the code of entries on Rank 1:n => submit n copies of
the leading entry to see this code soon.
2) Getting rid of jitter problem by putting new entries with CPU time
t in the list as if they had t+tol => if successive tweaks with
t-t2 (t2<tol) are submitted, the top entry gets 'protected' by
these entries. A later entry with t-tol-eps might not get through on
top of the list, which wasn't the intention of this rule.
3) Adding a darkness at the end of the contest would simply stretch
the last minute of the contest to that of this period - submitting in
the end-darkness is the same as submitting right at the end.
4) Using the old FLOPS for scoring would shift the whole contest to
integer or logical types.

But what else can be done?

I still would like to see the p-code length introduced into the
score, sTefan had a good idea how to make this feasible. Also, I
would like to see the influence of CPU time reduced, or the jitter
problem solved. Why not round the CPU times to one second to make the
hunt for milliseconds unattractive? Not only for the contest, but
also for Matlab in general, a modern version of FLOPS would be
extremely useful: One that counts exclusively the CPU time of the
target commands - something that tic, toc, or the profiler obviously
do not.

Very embarrassing was the new habit of scrambling entries. While it
is impossible to prevent this automatically, a new step of
preprocessing entries might help: The editor has this nice
smart-indent feature. This and a script that takes out excessive
white spaces could help to keep the entries more readable. Also, I
would like to see the variable name l on the black list.

Thank you for providing such a wonderful opportunity to learn.

Regards,

Heinrich

Thanks for all the congratulatory messages and to the Matlab contest
team for running one of the best contests so far in my opinion. And
special thanks to Lucio for providing the mid-contest analysis that
inspired the changes to Vincent's 'chkIntMap'.

I certainly didn't plan on that photo finish. I wanted to wait for
the last second but not literally. With about 2.5 minutes to go I
submitted 'timetest' to verify the server time stamp. It gave me a
false sense of security. My plan was to submit three entries with 30
seconds to go. So I started with dm1 and then was surprised to see
dm2 rejected because the queue was closed. I was very lucky that dm1
made it on time!

As far as the contest format goes I really liked the darkness and
twilight phases. Hopefully we will see them back in future contests.
 It also seems the Matlab team fixed the long queue problem that has
plagued other contests. Could this be the reason for the time
jitter? Are you guys running entries in several computers?

Paulo

For the issue of the "jitters" of CPU time....

How about running the entry 10 times, and take the average? The
running time estimated should show less fluctuation.

If an algorithm gives different results on different runs (because of
the use of random number), perhaps we can take the average of the
scores over different runs. This may also discourage repeated
submission of the same entry to get a better score because of
different random seeds...

And... for the idea of evaluating an algorithm by an independent,
hidden test suites.... This is actually a standard practice in the
pattern recognition community..... So I did not see any problem with
this... Of course, the matlab contest teams need more effort to
design additional test cases.

Great contest. I enjoyed it very much. Particularly better than
previous contests was the smoother queue processing.

I had what I thought was going to be a huge improvement in the code:

I replace the "myscore" function:

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function Score = myscore(ma,in,n)
Total = zeros(1,n);
for i = 1:numel(ma),
    Total(in(i)) = Total(in(i)) + ma(i);
end
Score = abs(Total(1)-1);
for k=2:n
    Score = Score + abs(Total(k)-1);
end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

with my "improvment":

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function Score = myscore(ma,in,n)

Total = zeros(1,n);
for i = 1:n
    Total(i) = Total(i) + sum(ma(in==i));
end
Score = sum(abs(Total-1));
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

This led to a 15% speedup in the test suite on my machine (using
v6.1), but was slower on the contest suite!

Frustrating, to say the least.

cyclist, I'm doing some investigation into timing jitter and I wanted
to see how your new version of myscore performed. I just tested the
two versions of "myscore. You say you're running R12.1, so I also
compared R12.1 against R13sp1, which is what we used in the contest.
Here are my results:

n = 40, run 500 times
       orig yours
R12p1 6.81 1.61
R13sp1 0.13 1.41

n = 500, run 1 time
       orig yours
R12p1 2.14 15.40
R13sp1 0.04 7.36

Your version is the fastest on small problems in R12p1. R13sp1 runs
both versions of myscore faster, but to differing degrees. You can
see also that the results vary dramatically depending on the size of
the problem. I suspect the dramatic differences are due to the large
temporary variables that your version allocates, like "in==i", which
the original avoids at the expense of more looping. Looping used to
be something to be avoided at all other costs in MATLAB, but that is
no longer true.

These benchmarking issues are tricky. We have developers at the
MathWorks who spend a lot of time thinking about what to benchmark
and how to benchmark it, to measure our progress from release to
release. (I'm not one of them.)

Matthew Simoneau wrote:
>
>
> cyclist, I'm doing some investigation into timing jitter and I
> wanted
> to see how your new version of myscore performed. I just tested
> the
> two versions of "myscore. You say you're running R12.1, so I also
> compared R12.1 against R13sp1, which is what we used in the
> contest.
> Here are my results:
>
> n = 40, run 500 times
> orig yours
> R12p1 6.81 1.61
> R13sp1 0.13 1.41
>
> n = 500, run 1 time
> orig yours
> R12p1 2.14 15.40
> R13sp1 0.04 7.36
>
> Your version is the fastest on small problems in R12p1. R13sp1
> runs
> both versions of myscore faster, but to differing degrees. You can
> see also that the results vary dramatically depending on the size
> of
> the problem. I suspect the dramatic differences are due to the
> large
> temporary variables that your version allocates, like "in==i",
> which
> the original avoids at the expense of more looping. Looping used
> to
> be something to be avoided at all other costs in MATLAB, but that
> is
> no longer true.
>
> These benchmarking issues are tricky. We have developers at the
> MathWorks who spend a lot of time thinking about what to benchmark
> and how to benchmark it, to measure our progress from release to
> release. (I'm not one of them.)

But on my machine (R13), the new myscore is much slow than original
one. Running over the testsuit using the orignal one, the time is
about 6.25 second, but using the "improvement", the time is 8.75
seconds.

In terms of room for improvement, I think further partition will
help. That is in addition to identify repeated submatrices, we can
also identify submatrices which have population exactly (or may use
nearly) equal to an integer times of goal population. In this way, a
large problem can be divided into several small problems, which is
easier to be solved. Anyone wishes to try, here is the code, you can
put it after the code of repeated submatrices.

Yi Cao

-------------------
smap=sum(map);
cMap=cumsum(smap);
cIdx=setdiff(find(rem(cMap,1)/n<1e-12),[find(~smap)
find(abs(cMap-n)<1e-12) s2]);
ndiv=length(cIdx)+1;
if ndiv>1,
    d=map;
    nn=diff([0 round(cMap(cIdx)) n]);
    bDiv=[1 cIdx+1];
    eDiv=[cIdx s2];
    offset=cumsum([0 nn(1:ndiv-1)]);
    for i=1:ndiv
        k1=bDiv(i);
        k2=eDiv(i);
        mm = map(:,k1:k2);
        d(:,k1:k2)=solver1(mm,nn(i),s1,k2-k1+1,goal)+offset(i);
    end
    return;
end
smap=sum(map,2);
rMap=cumsum(smap);
rIdx=setdiff(find(rem(rMap,1)/n<1e-12),[find(~smap);find(abs(rMap-n
)<1e-12);s1]);
ndiv=length(rIdx)+1;
if ndiv>1,
    d=map;
    nn=diff([0;round(rMap(rIdx));n]);
    bDiv=[1;rIdx+1];
    eDiv=[rIdx;s1];
    offset=cumsum([0;nn(1:ndiv-1)]);
    for i=1:ndiv
        k1=bDiv(i);
        k2=eDiv(i);
        mm = map(k1:k2,:);
        d(k1:k2,:)=solver1(mm,nn(i),k2-k1+1,s2,goal)+offset(i);
    end
    return;
end

My ideal contest:

- Darkness, twilight, and daylight are equal length.

- Time counts for less in the overall score and/or a larger test
suite.

- Three test suites:
  1) examples you can download to test code.
  2) a set with performance, time, overall score, and ranking
published on the web during twilight and daylight.
  3) a set with only rank published on the web. All data will be
published once the contest is over.

- Two catagories for ranking based on test suites two and three:
  1) Suite 2 is identical to this contest except that scores are
rounded to the nearest tenth of a second to help the jitter problem.
  2) Suite 3 is ranked with time rounded to the nearest whole second
and only rank is published. Time and results can be published once
the contest is finished.

I like this setup because I favor algorithm developement and
refinement as opposed to trial and error tweaking. I think the third
test suite will allow someone like me to focus on a more general
algorithm because there is very little feedback about the data set.
However, I realize that mine isn't the only opinion so the second
test suite results remain visible.

I guess this really makes two individual contests with different
goals and methods of optimization. I'm okay with that.

Steve

P.S. I like the mini-contest live results (stats page) but they
didn't always show up until near the mini-contest end. It would be
great to have those available as soon as a mini contest starts. Also,
these results should be on individual pages (not with stat plots) so
they load and reload quickly.

(Note, I mis-posted this in the wrong thread, so here it is again.)

This was my first Matlab contest, and I probably enjoyed it too much
(you know, losing sleep and annoying others in my personal life :) ).
Thanks to the MathWorks team for setting up such an interesting
problem and running the contest so well.
 
IMO, darkness and twilight could each be 1/3 of the contest length,
with daylight at the end.
 
The many sub-contests were definately fun and good incentive to keep
coding/ tweaking/ thinking along the way.
 
Also, props to those who figured out the strategy of trying out new
ideas on the contest suite "under the radar" by intentionally slowing
down some other part of the code. I think the reason this was
happening is that toward the end of the contest, it was basically
useless to test suite on local computers for comparing performance.
 
I'm not sure if there is a way to make the contest suite and test
suite more comparable, but I'd be for it if so.
 
Is there any chance the contest suite will be published now that its
over? (I see that it is now .. thanks!)
 
Congrats to all the winners! I look forward to the next contest.
 
- Alan

I just downloaded the actual test suite that was used for the
contest. I got the following error tring to load
testsuite_largemaps.mat:

??? Error using ==> load
Unable to read MAT file testsuite_largemaps.mat

File may be corrupt.

Can anyone tell me if they reproduced that or if it worked? I am
running R13. I was able to load testsuite_actual without any
problem. I was a little disappointed that the actual test suite is
smaller than the sample, but it still looks fairly representative.

MR Keenan wrote:
> I got the following error tring to load
> testsuite_largemaps.mat:
>
> ??? Error using ==> load
> Unable to read MAT file testsuite_largemaps.mat

I got the same thing. MATLAB Version 6.5.1.199709 (R13) Service Pack 1

MR, I saved the MAT-file using R14, which compresses the MAT-files by
default. This makes them unreadable in older versions. I'll resave
the MAT-file using the "-v6" switch so you'll be able to load them.
Sorry about the confusion.

Hi All and congrats to Paulo for taking the crown... yet again...
even if it was
just in the nick of time :)

Here are my thoughts on the contest:

Firstly, the different phases, Darkness and Twilight, were fun, and
obviously
encouraged algorithm development. But I dare say that once daylight
had
occurred, many of the algorithms that didn't make it to the top (like
mine,
which was way off at the time :)) probably never made it back into
the fray. I'd
say that's why the snaking algorithm became so ubiquitous, as opposed
to a
growing algorithm which would have performed better in certain cases,
as Lucio
pointed out in his analysis.

I don't think the issue of time-jitter is a big one - it could be
rectified by
simply increasing the resolution at which entries are stored, as
suggested by
Heinrich. For example, rounding the time to the nearest 0.1 second
and duplicate
timed (and equal resulting) entries placed below the first. I seem to
recall
from a previous contest that the latter aspect has already been
incorporated
into the scoring/ranking procedure.

I still feel that the biggest problem is the lack of comments (which
I admit,
I am also guilty of) and general obfuscation of the code, through
poorly named
variables, too much/little whitespacing, irregular indentation and so
on. I was
horrified when I saw that the top entry had been scrambled at one
stage and
almost gave up, but I guess most others felt similarly and the
problem was
rectified. Thanks to those that made an effort into putting an
unscrambled
version back at the top, as well as those that cleaned and commented
their
entries before resubmitting.

Unfortunately (or perhaps fortunately), I think the only practical
way to people
to put comments into their entries is to encourage it. And the only
way to do
that, I believe, is by encouraging collaboration. Penalising
uncommented code is
a nice idea, but difficult to implement, since manual scrutiny is too
labour-
intensive and automatic grading can be easily side-stepped by the
competitor
simply executing a script to insert garbage comments at the end of
some/every
line in their entry prior to submission.

I really liked the Golf contest, and as far as commenting went, it
could be
considered an exception, since the code was generally very short, so
it wasn't
too difficult to figure out how each entry worked. A viable
alternative is to
get people working in teams, thereby encouraging commenting since it
is crucial
for team members to understand what each has done. I guess this could
be avoided
by sharing a commented version of the code via other means
(email/file-server),
but this would be less efficient and an uncommented entry would be
quite
obvious.

Another idea is to hide the code for each entry, but show the results
when
tested against one/several sample testsuites. That way, people can
get an idea
of the algorithms behind each entry, without knowing the explicit
details. Even
better if this could be done graphically as well, like showing a map
with the
resulting partitioning scheme in this latest contest.

I also like the idea of a "King of the Hill" style contest, where
individuals or
teams would compete *against* each other using a single entry, rather
than being
ranked against a pre-determined testsuite. A couple of examples of
this are
Robocode and JROBOTS.

JROBOTS:
 <http://www.cfxweb.net/~jrobots/>

Robocode:
 <http://robocode.alphaworks.ibm.com/home/home.html>
 <http://www-106.ibm.com/developerworks/java/library/j-robocode/index.html>

The (Java) code for individual entries in these is not visible to all
competitors, but there is no reason why some visibility wouldn't work
either.
Perhaps the code for the top entry could be hidden and the others
visible, or
the top entry only hidden for some time (one hour/one day) and the
others hidden
indefinitely. As alluded to above, having some code hidden clearly
encourages
algorithm development.

Having said all that, for me, the aspect which makes the contest so
fun is the
diversity of the problems posed, and the variation in the format of
the contest,
which includes the many mid-contest deadlines that are set. Thanks to
the people
at MATLAB Central... it was good to see they had implemented many of
our
previous suggestions :) I hope to see you all again in the next one,
time
permitting!

Roger