Thread Subject:

MATLAB Contest report: Tuesday, June 15, 1999

The contest has been going on for over a week now. We are very pleased
to see that more people have involved. In the last few days the top
score has progressed from 263.96 to 233.59.

This drop of 30 points is good. However, the contest ends this Friday
afternoon at 5:00pm EDT. At the current rate of improvement, the top
score will not reach the next prize target level of 200.

Most of the point reduction in the past few days has come from the
savings in CPU time. This is good, but as Peter Acklam has pointed
out in one of his posts, improvements in CPU time alone will not get
the score down to 200 (at current level of coverage, you need a
negative CPU time to reach 200!). Something must be done about
improving the the covering percentage.

Before kicking off the contest on our web site, we ran the same
contest problem internally within the MathWorks. To give you a
sense of the possibilities, here are some facts about the
internal contest for this same problem.

1. We came up with three COMPLETELY DIFFERENT algorithms which
   reduce the unexplored percentage below 10%.

2. The winning score in the internal contest was below 100, with
   3.76% unexplored. The best coverage achieved in the internal
   contest was 3.02% unexplored.

3. Most importantly, all the above mentioned three algorithms have no
   random number generation in them (i.e. they never called 'RAND').

Like you, none of the internal contestants (except for one) had
any access to the test suite. :)

In the last MATALB contest, the CD Packing contest,
( http://www.mathworks.com/contest/binpack.cgi/home.html )
the final winning score beat our internal winning score by a
wide margin. We hope to see that happen in this contest as well.

Come on and give it a try at http://www.mathworks.com/contest

------
Zhiping You
The MathWorks Inc.
zyou@mathworks.com

Its great that Mathworks employees have found such good solutions. As
you said, "Like you, none of the internal contestants (except for one)
had any access to the test suite. :)". However, unlike you, our daily
jobs involve doing things completely unrelated to Martian Rovers. Since
Matlab is so expensive, we can't afford to have it at home and work on
these interesting problems at home. So ANY progress made in improving
the solution is truly exceptional because we've snuck it in during our
normal business duties. I personally looked at the problem statement,
thought about it for awhile, and decided that to pursue it would require
many hours of my employers time doing things I shouldn't be doing -- so
I didn't. So don't wave your great success in our face! We WORK for a
living!

-Mark Brown-

Zhiping You wrote:
>
> The contest has been going on for over a week now. We are very pleased
> to see that more people have involved. In the last few days the top
> score has progressed from 263.96 to 233.59.
>
> This drop of 30 points is good. However, the contest ends this Friday
> afternoon at 5:00pm EDT. At the current rate of improvement, the top
> score will not reach the next prize target level of 200.
>
> Most of the point reduction in the past few days has come from the
> savings in CPU time. This is good, but as Peter Acklam has pointed
> out in one of his posts, improvements in CPU time alone will not get
> the score down to 200 (at current level of coverage, you need a
> negative CPU time to reach 200!). Something must be done about
> improving the the covering percentage.
>
> Before kicking off the contest on our web site, we ran the same
> contest problem internally within the MathWorks. To give you a
> sense of the possibilities, here are some facts about the
> internal contest for this same problem.
>
> 1. We came up with three COMPLETELY DIFFERENT algorithms which
> reduce the unexplored percentage below 10%.
>
> 2. The winning score in the internal contest was below 100, with
> 3.76% unexplored. The best coverage achieved in the internal
> contest was 3.02% unexplored.
>
> 3. Most importantly, all the above mentioned three algorithms have no
> random number generation in them (i.e. they never called 'RAND').
>
> Like you, none of the internal contestants (except for one) had
> any access to the test suite. :)
>
> In the last MATALB contest, the CD Packing contest,
> ( http://www.mathworks.com/contest/binpack.cgi/home.html )
> the final winning score beat our internal winning score by a
> wide margin. We hope to see that happen in this contest as well.
>
> Come on and give it a try at http://www.mathworks.com/contest
>
> ------
> Zhiping You
> The MathWorks Inc.
> zyou@mathworks.com

"Mark W. Brown" wrote:
>
> Since Matlab is so expensive, we can't afford to have it at home
> and work on these interesting problems at home. So ANY progress
> made in improving the solution is truly exceptional because we've
> snuck it in during our normal business duties.

Can't you stay at work after you have done what you are expected to
do and work on it then? Although, unless you are single... :-)

> I personally looked at the problem statement, thought about it for
> awhile, and decided that to pursue it would require many hours of
> my employers time doing things I shouldn't be doing -- so I didn't.

I admire your strength. :-)

Seriously, I have thought the same. I have several ideas for
algorithms that would I would like to try, I just don't have the
time to implement them.

I have thought about making a recursive "lookahead"-algorithm that
goes to extrordinary length to find unsurveyed locations (_before_
moving), where the recursion stops when an unsurveyed location is
found or when the rover runs out of steam (t>500). I realize now
that there is no way I will be able to implement this before the
deadline on Friday.

> So don't wave your great success in our face! We WORK for
> a living!

I think it was interesting to see how well the people at TMW were
able to do. It just makes me want to beat their percentage. :-)

Peter

--
Peter J. Acklam - jacklam@math.uio.no - http://www.math.uio.no/~jacklam

"Mark W. Brown" <mark_w_brown@mail.northgrum.com> writes:

> Its great that Mathworks employees have found such good solutions. As
> you said, "Like you, none of the internal contestants (except for one)
> had any access to the test suite. :)". However, unlike you, our daily
> jobs involve doing things completely unrelated to Martian Rovers. Since
> Matlab is so expensive, we can't afford to have it at home and work on
> these interesting problems at home. So ANY progress made in improving
> the solution is truly exceptional because we've snuck it in during our
> normal business duties. I personally looked at the problem statement,
> thought about it for awhile, and decided that to pursue it would require
> many hours of my employers time doing things I shouldn't be doing -- so
> I didn't. So don't wave your great success in our face! We WORK for a
> living!
>
> -Mark Brown-

My original post was not intended as a snub to our users. If it makes
you feel that way, I am sorry.

With all those smart minds out there working in concert, we are sure
that the contest will move past its current plateau. In fact, we
expect that the ultimate winner of the MATLAB contest will do better
than we were able to do here at the MathWorks. That's exactly what
happened during the last MATLAB contest.

The reason that we gave out some facts about our internal contest was
that we have observed that the external contest had plateaued at a
local optimum for the past several days. We simply hope to encourage
the contestants to look for a significantly better algorithm, by
offering some proof of its existence.

Here's a message that we received from a contestant after he read our
post:

> Perhaps this contest has served to demonstrate the dangers of
> blindly trying to optimize a poor initial algorithm. Don't count us
> out just yet though. Now that people are aware of the possibilities
> for optimizing the code with a non-random approach, I'm sure that it
> will be done.

You're right that the MATLAB programming contest is a diversion from
"real" work. It is intended to be fun. It is also intended to offer
an opportunity for MATLAB users to learn about MATLAB programming from
other expert users and to share their expertise with others.

By the way, our jobs are not related to Martian Rovers either. I'm
sorry that you haven't been able to participate in the contest.
Perhaps next time you'll be able to.

Have fun.

------
Zhiping You
The MathWorks Inc.
zyou@mathworks.com

Mark W. Brown <mark_w_brown@mail.northgrum.com> wrote:
> Since
> Matlab is so expensive, we can't afford to have it at home and work on
> these interesting problems at home.

I'm not in Sales, but it is my understanding that if your employer has
bought you a copy for the office, you can get an additional copy to use at
home for free.

Of course, that isn't your point.

--
Matthew J. Simoneau
Development, Mathematics Group
The MathWorks, Inc.