Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
MATLAB Contest: 7-14 Nov 2007

Subject: MATLAB Contest: 7-14 Nov 2007

From: Helen Chen

Date: 7 Nov, 2007 16:55:23

Message: 1 of 57

The 2007 Fall MATLAB Contest officially begins at noon
today. Find out what this challenge is all about at
http://www.mathworks.com/contest/. See a description of the
challenge, the full contest rules, and a FAQ that explains
how to participate.

The contest will run through noon next Wednesday, November
14th. Many of you had asked for a darkness period late in
the contest, so we've added a new twist this time: late
stage twilight. In addition to hiding all code for a full
day, we will change the test suite next Monday. As always,
winners of our various challenges will receive a small prize
for their efforts.

If you have questions about the contest, or encounter
problems along the way, please post your questions as a
reply to this thread.

Good luck to everyone!

Helen Chen and the MATLAB Central Team

PS: After the contest ends on Wednesday, November 14th, some
of us are getting together near Harvard Square (Cambridge,
Mass.) for a drink to celebrate another great contest. Email
me if you’d like to join us.

Subject: MATLAB Contest: 7-14 Nov 2007

From: Alan Chalker

Date: 7 Nov, 2007 18:48:13

Message: 2 of 57

Good luck everyone! This looks to be yet another
interesting and fun contest.

Subject: MATLAB Contest: 7-14 Nov 2007

From: Jeffrey Daniels

Date: 7 Nov, 2007 21:43:54

Message: 3 of 57

Anyone:
Can we assume that although the target is not always
monotonic it is generally increasing. Put another way, can
the target be a random sequence of integers?

Algorithms could be very different to reach the following
targets:
[ 1 2 3 4 5 6 6 7 8]
[ 1 2 3 1 2 3 1 2 3]
[14 12 1 9 16 2 5 1 9]

~JD

Subject: MATLAB Contest: 7-14 Nov 2007

From: Ned Gulley

Date: 7 Nov, 2007 22:10:46

Message: 4 of 57

"Jeffrey Daniels" wrote:
> can the target be a random sequence of integers?

Yes, the target can be essentially random. You shouldn't
assume that it follows any particular pattern.

-Ned.
gulley@mathworks.com
Contest Team

Subject: MATLAB Contest: 7-14 Nov 2007

From: Lucas

Date: 8 Nov, 2007 02:32:28

Message: 5 of 57

How do I submit my code?

Subject: MATLAB Contest: 7-14 Nov 2007

From: Aaron Callard

Date: 8 Nov, 2007 02:47:26

Message: 6 of 57

Is there any bound on the size of the sequences?

can we assume they're less than 2^31-1, less than 100 etc.

Subject: MATLAB Contest: 7-14 Nov 2007

From: Helen Chen

Date: 8 Nov, 2007 03:23:59

Message: 7 of 57

"Lucas " <lucasbang03@yahoo.com> wrote in message
<fgtsfs$4gu$1@fred.mathworks.com>...
> How do I submit my code?

If you go to the contest home page at
http://www.mathworks.com/contest/splicing/home.html, there
is a link on the right nav bar "Submit your entry".

Good luck!
Helen

Subject: MATLAB Contest: 7-14 Nov 2007

From: xyz xyz

Date: 8 Nov, 2007 03:51:40

Message: 8 of 57

Please tell me how to run in Matlab 6.5?


"Helen Chen" <helen.chen@mathworks.com> wrote in message
<fgsqlr$hsv$1@fred.mathworks.com>...
> The 2007 Fall MATLAB Contest officially begins at noon
> today. Find out what this challenge is all about at
> http://www.mathworks.com/contest/. See a description of the
> challenge, the full contest rules, and a FAQ that explains
> how to participate.
>
> The contest will run through noon next Wednesday, November
> 14th. Many of you had asked for a darkness period late in
> the contest, so we've added a new twist this time: late
> stage twilight. In addition to hiding all code for a full
> day, we will change the test suite next Monday. As always,
> winners of our various challenges will receive a small prize
> for their efforts.
>
> If you have questions about the contest, or encounter
> problems along the way, please post your questions as a
> reply to this thread.
>
> Good luck to everyone!
>
> Helen Chen and the MATLAB Central Team
>
> PS: After the contest ends on Wednesday, November 14th, some
> of us are getting together near Harvard Square (Cambridge,
> Mass.) for a drink to celebrate another great contest. Email
> me if you’d like to join us.
>

Subject: MATLAB Contest: 7-14 Nov 2007

From: Jeffrey Daniels

Date: 8 Nov, 2007 04:38:36

Message: 9 of 57

Ned-

Can we assume the splice function given in the contest
rules is a valid function to call, or must we supply that
as a subfunction if we chose to use it?

~JD

Subject: MATLAB Contest: 7-14 Nov 2007

From: Ned Gulley

Date: 8 Nov, 2007 05:47:51

Message: 10 of 57

Jeffrey Daniels wrote:
> Can we assume the splice function given in the contest
> rules is a valid function to call, or must we supply that
> as a subfunction if we chose to use it?

You have to supply it. The function is shown to illustrate
one way to do splicing as we define it. The advantage of
supplying such a function yourself is that you can write a
version that is much faster.

-Ned.
gulley@mathworks.com
Contest Team

Subject: MATLAB Contest: 7-14 Nov 2007

From: Abhisek Ukil

Date: 8 Nov, 2007 10:54:01

Message: 11 of 57

the function doMoves will be automatically available or
we've to include it (cut &paste) additionally with the
solver function?

Subject: MATLAB Contest: 7-14 Nov 2007

From: Scott Seidman

Date: 8 Nov, 2007 13:27:43

Message: 12 of 57

"Helen Chen" <helen.chen@mathworks.com> wrote in news:fgsqlr$hsv$1
@fred.mathworks.com:

> PS: After the contest ends on Wednesday, November 14th, some
> of us are getting together near Harvard Square (Cambridge,
> Mass.) for a drink to celebrate another great contest. Email
> me if you’d like to join us.
>

What a lovely idea. I can't attend, but someone please drink a beer for me



--
Scott
Reverse name to reply

Subject: MATLAB Contest: 7-14 Nov 2007

From: Jeffrey Daniels

Date: 8 Nov, 2007 23:40:14

Message: 13 of 57


I see that more than just I am getting the following
error. Since I can't see the whole error code I am having
trouble debugging. I don't see where I am calling filefilt
in my code. It does not show up in the profiler.

Error using ==> filefilt at 123 The function CL...

Help? Thanks.

Subject: MATLAB Contest: 7-14 Nov 2007

From: Matthew Simoneau

Date: 9 Nov, 2007 05:08:56

Message: 14 of 57

Jeffery, these "filefilt" messages could be more clear.
It's an indication that your using a disallowed function in
your code, in this case probably "clear".

Subject: MATLAB Contest: 7-14 Nov 2007

From: Luigi Sorbara

Date: 9 Nov, 2007 06:41:19

Message: 15 of 57

Why am i getting this error?

Error using ==> builtin Line: 137 Column: 4 Thi...

what does that mean?

Thanks

Subject: MATLAB Contest: 7-14 Nov 2007

From: Jeffrey Daniels

Date: 9 Nov, 2007 06:42:41

Message: 16 of 57

"Matthew Simoneau" <matthew@mathworks.com> wrote in message
<fh0q18$9ld$1@fred.mathworks.com>...
> Jeffery, these "filefilt" messages could be more clear.
> It's an indication that your using a disallowed function
in
> your code, in this case probably "clear".

Argggg! Thank you!

Subject: MATLAB Contest: 7-14 Nov 2007

From: Luigi Sorbara

Date: 9 Nov, 2007 06:43:00

Message: 17 of 57

Anybody know why I get this error?

Error using ==> builtin Line: 137 Column: 4 Thi...

Thanks!

Subject: MATLAB Contest: 7-14 Nov 2007

From: Lucio Andrade-Cetto

Date: 9 Nov, 2007 14:36:55

Message: 18 of 57

"Luigi Sorbara" <baggio1510@hotmail.com> wrote in message
<fh0vhk$485$1@fred.mathworks.com>...
> Anybody know why I get this error?
>
> Error using ==> builtin Line: 137 Column: 4 Thi...
>
> Thanks!

Luigi
You get that error becasue you used a semicolon after
then 'end' statment.
Change 'end;' to 'end'

Lucio

Subject: MATLAB Contest: 7-14 Nov 2007

From: Matthew Simoneau

Date: 9 Nov, 2007 14:42:26

Message: 19 of 57

Luigi, this is a parse error.

Subject: MATLAB Contest: 7-14 Nov 2007

From: Alan Chalker

Date: 10 Nov, 2007 05:03:36

Message: 20 of 57

Here is my traditional analysis of the scoring formula. I
noticed the the rules for this contest don’t explicitly
spell out the scoring formula as in past contests, however
I’ve determined it’s exactly the same is for the Peg
Solitaire contest, which is:

score = k1*result + k2*e(k3*runtime) + k4*max(complexity-10,0)

Where:

k1 = 0.1
k2 = 2
k3 = 0.05
k4 = 1

The current leading entry has a time of 91s, result of
59747, and cyc of 24. Here’s a breakdown of the current
tradoffs:

-cyc and score are a 1:1 ratio (i.e. each point shaved off
cyc is a point shaved off the score)

-time and score are a 0.1:0.95 ratio
-result and score are a 1:0.1 ratio

We are a little past the ‘knee’ of the time exponential
curve, which is rather flat until about ~80s). Therefore
more is to be gained right now by shaving off time than
anything else. Hope this helps everyone!

Subject: MATLAB Contest: 7-14 Nov 2007

From: Markus Buehren

Date: 10 Nov, 2007 15:56:42

Message: 21 of 57

As in all contests, some guys tend to ruin the contest by
obfuscating their code, as DrSeuss does at the moment.

In the contest rules under "Hacking" we read "we ask that
you not abuse the system." I think this should also be valid
for the annoying obfuscation of code.

In the current leading code, I still find large portions of
my twilight winning code. I insist that you at least do not
obfuscate code that others have written!! If you want
introduce a new variable, call it as you like, but leave the
others as they are!

Markus

Subject: MATLAB Contest: 7-14 Nov 2007

From: Sergey

Date: 10 Nov, 2007 17:07:36

Message: 22 of 57

I support Markus 100%.
I want to point out that the last contest was very
civilized in that respect.

Sergey (SY)

"Markus Buehren" <mb_REMOVEmatlab@gmxTHIS.de> wrote in
message <fh4kbq$qj2$1@fred.mathworks.com>...
> As in all contests, some guys tend to ruin the contest by
> obfuscating their code, as DrSeuss does at the moment.
>
> In the contest rules under "Hacking" we read "we ask that
> you not abuse the system." I think this should also be
valid
> for the annoying obfuscation of code.
>
> In the current leading code, I still find large portions
of
> my twilight winning code. I insist that you at least do
not
> obfuscate code that others have written!! If you want
> introduce a new variable, call it as you like, but leave
the
> others as they are!
>
> Markus
>
>

Subject: MATLAB Contest: 7-14 Nov 2007

From: Alan Chalker

Date: 10 Nov, 2007 17:41:35

Message: 23 of 57

As I’ve done in the past, I’ve also now submitted a heavily
commented version of the Friday night leading code to help
casual players better understand how the algorithms work.
It’s titled “Read Me 1st” and is submission # 43338
http://www.mathworks.com/contest/splicing.cgi/view_submission.html?id=43338

Other obligations are preventing me from commenting it quite
to the extent I’ve done in the past, but I think this should
still be quite helpful. If you make changes, please don’t
remove the comments.

As several other people have requested, let’s keep this
contest ‘in the daylight’ as much as possible instead of
obscufating everything.

Subject: MATLAB Contest: 7-14 Nov 2007

From: Nathan

Date: 10 Nov, 2007 18:29:37

Message: 24 of 57

Hello all

LostInTranslation2 is a cleaned-up version of the current
leader.

Nathan


"Sergey " <ivssnn@yahoo.com> wrote in message
<fh4ogo$9md$1@fred.mathworks.com>...
> I support Markus 100%.
> I want to point out that the last contest was very
> civilized in that respect.
>
> Sergey (SY)
>
> "Markus Buehren" <mb_REMOVEmatlab@gmxTHIS.de> wrote in
> message <fh4kbq$qj2$1@fred.mathworks.com>...
> > As in all contests, some guys tend to ruin the contest by
> > obfuscating their code, as DrSeuss does at the moment.
> >
> > In the contest rules under "Hacking" we read "we ask that
> > you not abuse the system." I think this should also be
> valid
> > for the annoying obfuscation of code.
> >
> > In the current leading code, I still find large portions
> of
> > my twilight winning code. I insist that you at least do
> not
> > obfuscate code that others have written!! If you want
> > introduce a new variable, call it as you like, but leave
> the
> > others as they are!
> >
> > Markus
> >
> >
>

Subject: MATLAB Contest: 7-14 Nov 2007

From: Stijn Helsen

Date: 11 Nov, 2007 18:09:21

Message: 25 of 57

I have the opinion that the "cyclic complexity" check is not the right one
for "nice code". Long code with lots of pieces of code with almost the
same comments, except some are, I think, "better" than code where only
the differences are coded separately, looking the the "complexity check".
For me such long code is much more complex to read than code with
"nice if-then-else" clauses to show the differences.
Looking to efficiency is something else, of course. But therefore the
timing is already included in the scoring.
Am I the only one who is thinking like that? (or am I wrong in
interpreting the "complexity-results").

Stijn

Subject: MATLAB Contest: 7-14 Nov 2007

From: Helen Chen

Date: 12 Nov, 2007 01:52:33

Message: 26 of 57

"Alan Chalker" <alancNOSPAM@osc.edu> wrote in message
<fh4qgf$5f$1@fred.mathworks.com>...
> As I’ve done in the past, I’ve also now submitted a heavily
> commented version of the Friday night leading code to help
> casual players better understand how the algorithms work.
> It’s titled “Read Me 1st” and is submission # 43338
>
http://www.mathworks.com/contest/splicing.cgi/view_submission.html?id=43338
>

Many thanks for the great job, Alan! I'm sure that this
will help many people in the second half of our Fall contest.

Best wishes,
Helen

Subject: MATLAB Contest: 7-14 Nov 2007

From: Stijn Helsen

Date: 12 Nov, 2007 18:03:48

Message: 27 of 57

A disadvantage of this second twilight is that if you want to look what
has been done in earlier daylight, you can't see anything. So people that
can spend time shortly before the start of twilight, and get the code they
want have advantages. It seems better (but more difficult to implement)
that all earlier code can be viewed during this time.
I don't have any real problem as it is now, but I want to write this "to
think about".

Subject: MATLAB Contest: 7-14 Nov 2007

From: Markus Buehren

Date: 12 Nov, 2007 18:47:40

Message: 28 of 57

> A disadvantage of this second twilight is that if you want
to look what
> has been done in earlier daylight, you can't see anything.


Hi all!

This is not only a "think about" but a huge disadvantage for
contestants who want to get back into the game now, compared
to those who were online short before twilight started!!
Without seeing the last leading submissions before twilight
it will be very hard to get in again!

To the contest team: Please, please make the code submitted
before twilight visible again as soon as possible!

Markus

Subject: MATLAB Contest: 7-14 Nov 2007

From: Nicholas Howe

Date: 12 Nov, 2007 20:02:42

Message: 29 of 57

"Stijn Helsen" <SHelsen@compuserve.com> wrote:
> I have the opinion that the "cyclic complexity" check is
not the right one
> for "nice code". Long code with lots of pieces of code
with almost the
> same comments, except some are, I think, "better" than
code where only
> the differences are coded separately, looking the the
"complexity check".
> For me such long code is much more complex to read than
code with
> "nice if-then-else" clauses to show the differences.
> Looking to efficiency is something else, of course. But
therefore the
> timing is already included in the scoring.
> Am I the only one who is thinking like that? (or am I
wrong in
> interpreting the "complexity-results").
>
> Stijn


I tend to agree with Stijn. Low complexity scores seem to
encourage coding practices that actually decrease
readability. For example, compare

if (a < 0)
  b = c+d;
else
  b = e+f;
end

with the following:

b = (a < 0)*(c+d) + (a >=0 )*(e+f);

Which is most clear to you?

Subject: MATLAB Contest: 7-14 Nov 2007

From: Nicholas Howe

Date: 12 Nov, 2007 20:20:56

Message: 30 of 57

"Stijn Helsen" <SHelsen@compuserve.com> wrote:
> I have the opinion that the "cyclic complexity" check is
not the right one
> for "nice code". Long code with lots of pieces of code
with almost the
> same comments, except some are, I think, "better" than
code where only
> the differences are coded separately, looking the the
"complexity check".
> For me such long code is much more complex to read than
code with
> "nice if-then-else" clauses to show the differences.
> Looking to efficiency is something else, of course. But
therefore the
> timing is already included in the scoring.
> Am I the only one who is thinking like that? (or am I
wrong in
> interpreting the "complexity-results").
>
> Stijn


I tend to agree with Stijn. Low complexity scores seem to
encourage coding practices that actually decrease
readability. For example, compare

if (a < 0)
  b = c+d;
else
  b = e+f;
end

with the following:

b = (a < 0)*(c+d) + (a >=0 )*(e+f);

Which is most clear to you?

Subject: MATLAB Contest: 7-14 Nov 2007

From: Ned Gulley

Date: 12 Nov, 2007 21:34:34

Message: 31 of 57

Stijn Helsen wrote:
>> I have the opinion that the "cyclic complexity"
>> check is not the right one for "nice code".

Nicholas Howe wrote:
> I tend to agree with Stijn. Low complexity scores
> seem to encourage coding practices that actually decrease
> readability.

It's true that trying to make the complexity as low as
possible can result in hard-to-read code. That's why we only
apply a penalty to code with a complexity greater than 10.
Below that, there is no penalty at all. Above that, the
notion is that you'd be better served by moving
functionality into a subfunction.

This is a subtle topic, and I invite you all to help us out
here. What we want to do is find quantitative metrics (i.e.
no human judgment involved) that indicate whether code, in
addition to solving the problem at hand, is "good". Good can
be interpreted in a lot of ways: readable, elegant, clean,
easy to adapt and maintain. We know this is not easy...
almost any metric can be gamed and abused. Complexity isn't
a perfect metric, but it's a reasonable candidate. We can
argue about the right penalty threshold, but generally
speaking code with high complexity (greater than 50, say)
truly is hard to read.

Help us pick good metrics for the next contest. Ultimately
we'd like to make a contest that can focus your collective
brainpower to produce code that has value beyond the
contest. Is that possible, or is it just a dream?

-Ned.
gulley@mathworks.com
Contest Team

Subject: MATLAB Contest: 7-14 Nov 2007

From: Ned Gulley

Date: 12 Nov, 2007 21:39:42

Message: 32 of 57

Stijn Helsen wrote:
>> A disadvantage of this second twilight is that if you
>> want to look what has been done in earlier daylight,
>> you can't see anything.

Markus Buehren wrote:
> This is not only a "think about" but a huge disadvantage
> for contestants who want to get back into the game now.

Over on the contest blog
(http://blogs.mathworks.com/contest/), we've posted a link
to the last leading entry before the late twilight began,
Steve's "Slow Deutsch".

Here's the direct link to that file:

http://www.mathworks.com/contest/splicing.cgi/view_submission.html?id=43987

-Ned.
gulley@mathworks.com
Contest Team

Subject: MATLAB Contest: 7-14 Nov 2007

From: Heinrich Acker

Date: 13 Nov, 2007 16:47:14

Message: 33 of 57

"Ned Gulley" <gulley@mathworks.com> wrote in message
<fhagta$o43$1@fred.mathworks.com>...

> Help us pick good metrics for the next contest. Ultimately
> we'd like to make a contest that can focus your collective
> brainpower to produce code that has value beyond the
> contest. Is that possible, or is it just a dream?
>
> -Ned.
> gulley@mathworks.com
> Contest Team

What is a *useful* metric of complexity? I believe it is
the time a programmer needs to read the code until
understanding what it does.

According to Guido van Rossum, the inventor of Python, one
of the most productive languages is Python, because it
usually lets you create the shortest program of all
languages for a given problem - while having a clean
syntax. His explanation is that a programmer spends much
more time in reading than actually writing code. His claim
is hardly ever rejected, and several language studies
(which do not include proprietary systems like Matlab) show
that Python delivers high productivity and usually the
shortest code. My personal experience is that Matlab code
is as short and readable as Python, which explains its
success in markets where time-to-working-prototype counts.

So we can conclude that an algorithm is needed that
measures a formalized human reading effort. Nicholas'
example for the problem pointed out by Stijn shows that the
current complexity metric is not suitable to indicate the
human effort. Another point is that the cyclomatic
complexity can deliver completely different results,
depending on how an algorithm is split across functions. If
the functions do not belong to a library one is familiar
with, but have to be studied and understand together with
the main part, splitting does not help to reduce the time
to understand the whole. McCabe does not address this
issue, as his metric deals with software modules, not
complete solutions. Note that cyclomatic complexity is
described as related to 'difficulty', I'm talking about
time and productivity.

Since each entry for the contest is parsed anyway, my
suggestion is counting source-code 'items' for a complexity
metric. There are several possibilities for the definition
of these items. Tokens are candidates, but combinations of
them are also possible. Giving different weights can be
used to adjust to a specific taste. As a first approach, I
propose equally-weighted counting of the occurrences of:

- identifiers (functions, variables, ...)
- operators
- scalar constants
- string literals
- keywords

and not counting:

- comments (obviously ...)
- the special
characters ':', '...', '[', ']', '{', '}', ',', ';'
- parenthesis around indices and function arguments

Reason for the exclusions is the state of being delimiter
to an item or items already counted (i.e. an indexing
operation costs the count of the index, an argument list
the count of the list, a matrix definition the count of its
elements - but not more). Parenthesis to prioritize
operators should be counted, because an expression with
many of them takes longer to read, as we all know.

This choice of items and weighing fits to the human
perception in the sense that reading a keyword or a
descriptive identifier is 'cheap', even if it has, say, 15
characters (compared to an expression of equal length). It
is also a good choice with regard to possible abuse,
because short names do not pay off.

It should be moderately easy to implement this method for
somebody who already has a Matlab parser.

Heinrich

Subject: MATLAB Contest: 7-14 Nov 2007

From: roberson@ibd.nrc-cnrc.gc.ca (Walter Roberson)

Date: 13 Nov, 2007 17:00:50

Message: 34 of 57

In article <fhckei$j6u$1@fred.mathworks.com>,
Heinrich Acker <firstname.lastname@web.de> wrote:
>Parenthesis to prioritize
>operators should be counted, because an expression with
>many of them takes longer to read, as we all know.

Expressions *without* parentheses can take much longer to read,
if the precedence table is sufficiently complex that people would
often have to refer to reference material to parse a complex expression.

For example, "if A | ~(B|C)" is fairly straight-forward to read;
can you immediately say whether applying DeMorgan's law gives
equivilent code? "if A | ~B & ~C" In some languages it does,
in other languages it doesn't (and that's not even taking into
account considerations of whether & and | are bitwise or logical
operators.)
--
   "Any sufficiently advanced bug is indistinguishable from a feature."
   -- Rich Kulawiec

Subject: MATLAB Contest: 7-14 Nov 2007

From: Markus Buehren

Date: 15 Nov, 2007 06:52:55

Message: 35 of 57

Hi all!

Sorry for stealing the grand prize! In the last days, I did
not find the time to do any effort for enhancing the
algorithm. I justed came back from work half an hour before
deadline, randomly opened about 40 entries in the queue and
the top 10 and applied the time-saving repmat-tweak. Luckily
I hit the entry M07 that would end up at the very top
(sorry, MikeR). Thanks to the one who introduced the repmat
function and thanks to all the contestants who did not
realize that possible improvement ;-)

I just remembered the blockbuster contest, where the cyclist
snatched the victory with an nearly unnoticeable tweak also
applied to an entry in the queue. Here ist a comparison of
the entries in first and second place:

http://www.mathworks.com/contest/blockbuster.cgi/diff.html?id1=31864&id2=31920

Thanks to all of you - contestants and contest team - and
see you in the next contest!

Markus

Subject: MATLAB Contest: 7-14 Nov 2007

From: srach Rach

Date: 15 Nov, 2007 07:47:45

Message: 36 of 57

Congratulations to Markus and all sub-contest winners!

Once again, the contest was both interesting and
entertaining for me; it was really fun to learn from you.

A big "Thank You!" goes to the people at Mathworks who
organized the contest - Great Work! (As usual...)

Hope to see you all in Spring,
srach

Subject: MATLAB Contest: 7-14 Nov 2007

From: Mike Russell

Date: 15 Nov, 2007 11:55:03

Message: 37 of 57

Hello Community,

Again another very succesful competition! I like many
others was overly busy with school/work so I couldn't spend
the time required to develop my own solver :(

Similar to Peg Solitaire this contest appeared to go the
way of some random seeding through weighted variables like
rFac. I really stared down that new2solver and markussolver
which were almost alike in an attempt to unwrap or combine
some of the functionality but was never succesful.

I was actually saving the modification of the
movelengthThresh variables until the final push but I
believe Fernando jumped the gun with an entry that would
put this idea out there for everyone. The pure reduction in
score and not computation time seemed easily obtainable
through some small changes to these variables. I probed
appropriatly and hit the "sweet spot" with "M07".

I immediatly noticed YC's entry of a much shorter solver
which appeared to be a tree implementation (ala Peg
Solitaire where I spent considerable time on my own tree
algorithm). I jumped on this quickly and tried to very the
depth/breadth sufficiently since I had little to no
information from the test-suite. In the end it didn't work
as well as I had thought.

No hard feelings on the two entries that jumped ahead of me
in the very end, I made a small mistake on my last ~15
entries that probably cost me more score reductions. Just
another reason to eagerly wait for the next Matlab
Programming Contest!

Thanks again to the developers of the contest and all the
participants!

Now back to work!

- MikeR

Subject: MATLAB Contest: 7-14 Nov 2007

From: Sergey

Date: 15 Nov, 2007 13:55:53

Message: 38 of 57

Congratulations to Markus!
It is only fair that he won the contest because all winning
entries were descendants of his twilight submission.

A lot of thanks to contest organizers.

Some random suggestions:
1. Can we make information about “Timed out” available
during darkness? I understand that it will go against
purity of darkness. I see it mainly as “hardware
calibration” issue. Many of my darkness entries were timed
out because I underestimated the speed of my laptop. May be
it is possible to provide some calibration code with known
running time on the test computer.
2. Late twilight was interesting idea. However I would
prefer the last day of contest to be twilight. Do we
consider the rush of last second submissions and applying
of small tweaks on top of somebody else random tweaks to be
essential part of competition?
3. Better advertisement? At least some information on
main MathWorks page. I would be nice to know dates of the
contest 2-3 month in advance. It looks like participation
is shrinking. What about giving lifetime Matlab license to
the winner?

Sergey (SY)

Subject: MATLAB Contest: 7-14 Nov 2007

From: Yi Cao

Date: 15 Nov, 2007 14:19:27

Message: 39 of 57

"Mike Russell" <russelms@gmail.com> wrote in message
<fhhc2n$n0e$1@fred.mathworks.com>...
>
> I immediatly noticed YC's entry of a much shorter solver
> which appeared to be a tree implementation (ala Peg
> Solitaire where I spent considerable time on my own tree
> algorithm). I jumped on this quickly and tried to very
the
> depth/breadth sufficiently since I had little to no
> information from the test-suite. In the end it didn't
work
> as well as I had thought.
>
Thank you, Mike to pick up my code. I even didn't know that
there are someone used my code. Unfortunately, that was my
partially finished algorithm. I did not have time to
complete it hence just submitted it before the end to see
how it perform, :)-. To complete, it should have more
parttern branches and improvement in speed. But currently,
it cannot compete with the winning code. That is the life.

I still enjoy the contest although I didn't have time to
make more contributions. The most amazing thing to me in
this contest is the largest improvement achieved by
Gwendolyn Fisch and nathan q on Monday. Normally, as the
contest evolves, it becomes harder and harder to make a bif
improvement. But these two contesters pushed the score down
more than 100 points for several times in the middle of the
contest!!! I suggest they should deserve a special award
for they great contribution to the contest.

Yi

Subject: MATLAB Contest: 7-14 Nov 2007

From: Markus Buehren

Date: 15 Nov, 2007 14:48:33

Message: 40 of 57

> Congratulations to Markus!
> It is only fair that he won the contest because all winning
> entries were descendants of his twilight submission.

Thanks very much, Sergey!
 
> May be it is possible to provide some calibration
> code with known running time on the test computer.

Thats a good idea. Adapting my scoring function is the first
thing I do when the timings are visible. The contest team
could just let one of the submissions of this contest run
through their machine once and put the timing result to the
website. Every contestant can then use the old runcontest.m
and check their own speed.

I have blown up the runcontest.m quite much in order to be
able to let several solvers in parallel, compute the scoring
including time, provide parameters to the solver functions
and to stop execution early if a solver is likely to run out
of time. If someone is interested in that code, just let me
know.

> Late twilight was interesting idea. However I would
> prefer the last day of contest to be twilight. Do we
> consider the rush of last second submissions and applying
> of small tweaks on top of somebody else random tweaks to be
> essential part of competition?

That's also my opinion, even if the current rules allowed me
to get the grand prize by only a small tweak.

> Better advertisement? At least some information on
> main MathWorks page.

Definitely!

> I would be nice to know dates of the
> contest 2-3 month in advance. It looks like participation
> is shrinking.

Not necessarily 2-3 month, but at least more than three days
in advance :-) Maybe the contest team could let us know why
the contest was announced so shortly before start. Of course
they have their daily work to do, but...

> What about giving lifetime Matlab license to
> the winner?

Yes, also to the current winner please :-))

Markus

Subject: MATLAB Contest: 7-14 Nov 2007

From: Yi Cao

Date: 15 Nov, 2007 15:03:27

Message: 41 of 57

"Sergey " <ivssnn@yahoo.com> wrote in message <fhhj59
$jfc$1@fred.mathworks.com>...
> 2. Late twilight was interesting idea. However I would
> prefer the last day of contest to be twilight. Do we
> consider the rush of last second submissions and applying
> of small tweaks on top of somebody else random tweaks to
be
> essential part of competition?

I like this idea, we have dark, twilight, and daylight. Why
cannot we have a dusk phase just before end.

Schedule is an issue. If it can be annouced more earlier,
more people may get more time to attend. MATLAB license may
be another point to attract attendence.

Subject: MATLAB Contest: 7-14 Nov 2007

From: Yi Cao

Date: 15 Nov, 2007 15:03:47

Message: 42 of 57

"Sergey " <ivssnn@yahoo.com> wrote in message <fhhj59
$jfc$1@fred.mathworks.com>...
> 2. Late twilight was interesting idea. However I would
> prefer the last day of contest to be twilight. Do we
> consider the rush of last second submissions and applying
> of small tweaks on top of somebody else random tweaks to
be
> essential part of competition?

I like this idea, we have dark, twilight, and daylight. Why
cannot we have a dusk phase just before end.

Schedule is an issue. If it can be annouced more earlier,
more people may get more time to attend. MATLAB license may
be another point to attract attendence.

Subject: MATLAB Contest: 7-14 Nov 2007

From: Yi Cao

Date: 15 Nov, 2007 15:03:48

Message: 43 of 57

"Sergey " <ivssnn@yahoo.com> wrote in message <fhhj59
$jfc$1@fred.mathworks.com>...
> 2. Late twilight was interesting idea. However I would
> prefer the last day of contest to be twilight. Do we
> consider the rush of last second submissions and applying
> of small tweaks on top of somebody else random tweaks to
be
> essential part of competition?

I like this idea, we have dark, twilight, and daylight. Why
cannot we have a dusk phase just before end.

Schedule is an issue. If it can be annouced more earlier,
more people may get more time to attend. MATLAB license may
be another point to attract attendence.

Subject: MATLAB Contest: 7-14 Nov 2007

From: srach

Date: 15 Nov, 2007 19:45:24

Message: 44 of 57

"Markus Buehren" <mb_matlab.REMOVE@gmxTHIS.de> wrote in
message <fhhm81$6pu$1@fred.mathworks.com>...

> I have blown up the runcontest.m quite much in order to be
> able to let several solvers in parallel, compute the scoring
> including time, provide parameters to the solver functions
> and to stop execution early if a solver is likely to run out
> of time. If someone is interested in that code, just let me
> know.

Indeed I am interested in your modified runcontest. Do you
use it on a multicore CPU or how can you run multiple solver
in parallel?

Best,
srach

Subject: MATLAB Contest: 7-14 Nov 2007

From: Ned Gulley

Date: 15 Nov, 2007 23:14:12

Message: 45 of 57

Sergey wrote:
> 2. Late twilight was interesting idea. However I would
> prefer the last day of contest to be twilight.

What did other people think of late twilight? It was an
experiment. Do you think it made the solutions any better?
Should we do it again?

As always, we invite any other suggestions on how to make
the contest more fun.

Several people mentioned that we didn't leave enough time
between the announcement and the beginning of the contest.
Sorry about that! We'll try to give you a few weeks' warning
next time.

Thanks for playing. Look for us again in the Spring.

-Ned.
gulley@mathworks.com
Contest Team

Subject: MATLAB Contest: 7-14 Nov 2007

From: Nicholas Howe

Date: 16 Nov, 2007 01:23:16

Message: 46 of 57

Thanks to all who helped organize this contest. I'm sorry
that my schedule didn't permit me to be involved after the
first two days!

Not that I'd turn my nose up at a lifetime Matlab license,
but I actually think the contest is more fun if it is just
for bragging rights and Mathworks gear. If the prizes were
worth more I'm afraid (sorry to say) that it might
discourage good sportsmanship. It only takes a few
win-at-all-costs types to make the contest less pleasant for
everyone. Add to that the healthy dose of luck needed some
years to come out on top in the final submission scramble
and I don't see a compelling reason to up the prize.

Subject: MATLAB Contest: 7-14 Nov 2007

From: Nicholas Howe

Date: 16 Nov, 2007 01:27:15

Message: 47 of 57

One other thought -- I always found the 1000 character
challenge appealing. Did that get cut in favor of the late
twilight, and if so what do others think of that?

Subject: MATLAB Contest: 7-14 Nov 2007

From: Nathan

Date: 16 Nov, 2007 12:58:33

Message: 48 of 57

Hi everybody,

thanks again, Mathworks people, for a great contest.
Congratulations to all the winners. I love how every contest
has a distinctive feel, thanks to the varying personalities
of the problems and the contestants.

The race on monday that resulted in big score improvements
was highly entertaining for me. The breakthrough was
Gwendolyn Fisch's - the discovery that "we can do better"
with a swap-based solver to try out alternatives for the
last few moves offered by the main solver. I don't really
know why this works - I suppose sometimes the solver needs
to be nudged away from the best next move in order to find a
better move later, and swapping provides moves that are
sufficiently different from the base solution, and not too
much worse. Any thoughts? I had developed a swapper in
twilight which wasn't remotely competitive against Markus's
all-conquering search. I'm sure several people had similar
ideas. When Gwendolyn found a use for swapping, it was very
easy to insert my twilight solver. A three-way chase
followed - I managed to steal and repackage at least one
more idea from Gwendolyn, while srach found some other
improvements. With hindsight, I wish I'd tried to hold
something back for twilight, but after the initial jump the
developments were pretty obvious, and I'm sure you all would
have been jumping on it before very long.

I for one didn't enjoy the second twilight. I like early
twilight because you get to work on whole algorithms in
relative peace and quiet. In late twilight I found it hard
to excited about looking for small improvements without
seeing what others were doing. However, I do think that a
twilight period at the end of the contest could be a good
thing. It would offer some advantage for late algorithmic
improvements by protecting them from subsequent parameter
tweaks and near-identical resubmissions. It would also give
a chance to contestants who can't be online at the very end.

Thank you all, and see you in 2008.

Nathan

Subject: MATLAB Contest: 7-14 Nov 2007

From: Markus Buehren

Date: 16 Nov, 2007 14:35:03

Message: 49 of 57

> Indeed I am interested in your modified runcontest. Do you
> use it on a multicore CPU or how can you run multiple solver
> in parallel?

Not exactly parallel. But each board (or puzzle or how you
want to call it) is given to all solver after each other,
then the next board and so on. The cpu processing times are
counted separately.

Markus

Subject: MATLAB Contest: 7-14 Nov 2007

From: Markus Buehren

Date: 16 Nov, 2007 14:51:00

Message: 50 of 57

> with a swap-based solver to try out alternatives for the
> last few moves offered by the main solver. I don't really
> know why this works - I suppose sometimes the solver needs
> to be nudged away from the best next move in order to find a
> better move later, and swapping provides moves that are
> sufficiently different from the base solution, and not too
> much worse. Any thoughts?

I had the same idea of swapping (as many of you did) but my
solution was not competitive. The reason that swapping works
is that larger parts of the gene sequence stay unchanged. If
a part in the beginning of the gene sequence in the
currently modified sequence is found at the end of the
target, a single move to fit those parts over each other
would shift all values between the two parts and kill all
matches in that area.

Markus

Subject: MATLAB Contest: 7-14 Nov 2007

From: Sergey

Date: 16 Nov, 2007 15:27:54

Message: 51 of 57


I believe, the swapping algorithm works because it looks
for two-step optimization (for some specific cases of
course). As such, it sometimes finds better solution than
Marcus’s solver which is looking for one-step function
minimum. I am really surprised that we have not found
better optimization matrix than direct sequence difference
(see discussion for Peg Solitaire contest). I tried to do
it, but was not successful.

Sergey

"Markus Buehren" <mb_matlab.REMOVE@gmxTHIS.de> wrote in
message <fhkaok$igm$1@fred.mathworks.com>...
> > with a swap-based solver to try out alternatives for the
> > last few moves offered by the main solver. I don't
really
> > know why this works - I suppose sometimes the solver
needs
> > to be nudged away from the best next move in order to
find a
> > better move later, and swapping provides moves that are
> > sufficiently different from the base solution, and not
too
> > much worse. Any thoughts?
>
> I had the same idea of swapping (as many of you did) but
my
> solution was not competitive. The reason that swapping
works
> is that larger parts of the gene sequence stay unchanged.
If
> a part in the beginning of the gene sequence in the
> currently modified sequence is found at the end of the
> target, a single move to fit those parts over each other
> would shift all values between the two parts and kill all
> matches in that area.
>
> Markus

Subject: MATLAB Contest: 7-14 Nov 2007

From: Mike Russell

Date: 17 Nov, 2007 23:30:20

Message: 52 of 57

Will the final testsuite be posted along with the modified
one used during the late twilight? I would be interested in
playing with this further.

Thanks!

MikeR

Subject: MATLAB Contest: 7-14 Nov 2007

From: Mike Russell

Date: 18 Nov, 2007 02:03:52

Message: 53 of 57

Will the final testsuite be posted along with the modified
one used during the late twilight? I would be interested in
playing with this further.

Thanks!

MikeR

Subject: MATLAB Contest: 7-14 Nov 2007

From: Yi Cao

Date: 18 Nov, 2007 14:13:28

Message: 54 of 57

"Sergey " <ivssnn@yahoo.com> wrote in message
<fhkctq$nbt$1@fred.mathworks.com>...
>
> I believe, the swapping algorithm works because it looks
> for two-step optimization (for some specific cases of
> course). As such, it sometimes finds better solution than
> Marcus’s solver which is looking for one-step function
> minimum. I am really surprised that we have not found
> better optimization matrix than direct sequence
difference
> (see discussion for Peg Solitaire contest). I tried to do
> it, but was not successful.
>
> Sergey
>
Yes, swapping is a two step approach, but it is not two-
step optimization. I think the main reason for swapping to
make a significant contribution is its different pattern
affecting the sequence:

All single step approaches affect the sequence in a
continuous zone in the middle, for example for moves = [len
ai bi 0] the resulted sequence is
[1:ai-1 ai+len:bi+len-1 ai:ai+len-1 bi+len:end], therefore,
the head 1:ai-1 and the tail, bi+len:end are untouched.

However, for a swapping: moves=[len ai bi-len 0;len bi ai
0], the resulted sequence is
[1:ai-1 bi:bi+len-1 ai+len:bi-1 ai:ai+len-1 bi+len:m].
There are three sections, head, tail and center, ai+len:bi-
1 untouched.

Therefore, swapping offers a new pattern to find the best
move sequence, which may not be able to be identified by
single step moves.

I have completed my depth-branch solver by looking multiple
step ahead with multiple branches (all vectorized). It now
can beat both the the winning code and the best result
(ignoring time). If anyone wish to play with it, please let
me know.

Subject: MATLAB Contest: 7-14 Nov 2007

From: Matthew Simoneau

Date: 18 Nov, 2007 19:36:03

Message: 55 of 57

MikeR, the download now contains testsuite_actual and
testsuite_swap.

Subject: MATLAB Contest: 7-14 Nov 2007

From: Gwendolyn Fischer

Date: 19 Nov, 2007 07:41:38

Message: 56 of 57

Hello everyone,

unfortunatly I had to leave my computer before the end of
the contest, I just returned. So I was not involved in the
really last part of the contest.

But first I would thank you all for the fun. My last
submissions where using YC's algorithm which on my machine
bet the that time leading code on the testsuit so I hoped I
could benefit from his experience.

Concerning the swapping approach: One other advantage of
the swapping is its possibility to know the score-outcome
of the moves with "no" costs so swapping is fast making it
possible to just add it to other solvers without to much
speed considerations.

Concerning the late twilight, I'm unsure about that, on the
one hand side I like the idea of the really last phase of
the contest not being lot's of resubmissions of tigny
tweaks, on the other hand I learned also from them for my
daily work where sometimes even this tigny tweaks help...
And from my experience over the last three contest this
tweaking is also part of the contest.
In contrast to the idea of extending the late twilight till
the end of the contest, I would vote for moving it maybe
half a day earlier, in order to still encourage some
algorithm developement.

This said, thanks again for the great time,

see you in may

Gwendolyn

Subject: MATLAB Contest: 7-14 Nov 2007

From: Yi Cao

Date: 19 Nov, 2007 13:49:05

Message: 57 of 57

I have post my solver in File Exchange:
http://www.mathworks.com/matlabcentral/fileexchange/loadFile
.do?objectId=17586&objectType=file

After downloading the actual and swap testsuites, I realize
that the main deficiency of my code is the weakness in flip
then swap moves. I may implement such moves if I find time
in the near future.

See you all next time.
Yi Cao

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us