MATLAB Programming Contest Blog

November 6th, 2008

The queue was off to a slow start this morning, but results are now in for the Darkness phase. Jan Langer is our winner! A contest veteran, you can read about his previous contest experiences in the Hall of Fame. He’s followed in the rankings by Nick Howe, SY, Mila Naudé, and Benja&Litos.

Jan’s entry, “ebi v1″, now becomes the opponent that all entries will be tested against until Twilight ends at noon tomorrow. His code will remain hidden, making Twilight especially tricky.

23:04 UTC | Posted in Army Ants | Permalink |

You can follow any responses to this entry through the RSS 2.0 feed. You can skip to the end and leave a response. Pinging is currently not allowed.

One Response to “Jan Langer Wins Darkness”

1. Alan Chalker replied on November 7th, 2008 at 18:26 UTC :
   

   While we’re all waiting for the queue to clear and get into daylight, I thought it’d be a good time to post my traditional analysis of the scoring formula. As in past contests, the formula is:

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

   The coefficients were only slightly tweaked compared to the spring contest, as the contest team typically does:

   k1 = 1
   k2 = 0.1
   k3 = 2/30 (0.06666666…)
   k4 = 1
   k5 = 0.001

   The current leading entry has a time of 161s, result of 22940, cyc of 54, and nodes of 1583. Here’s a breakdown of the current tradeoffs:

   -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 1:295 ratio
   -result and score are a 1:1 ratio
   -node and score are a 1:0.001 ratio

   Note that the time component is at a very steep slope in the exponential curve. Adding just 5 seconds changes the ratio to 1:412, whereas saving 5 seconds changes the ratio to 1:226. It’s not until we drop the time to about 75s that the ratio gets down to 1:1.

   So what does this all mean?

   1. Well given that we already know the shortest amount of time is never going to drop below about 70s due to the ‘overhead’ caused by the contest machinery, it will always be better to work on faster code than to work on a better result, unless there is some major algorithmic breakthrough.

   2. Since it appears that all the codes have quite a bit of randomness in them as part of the ’searching phases’, submitting the same code multiple times will likely yield very different scores. We already know from past contests that the contest system can have quite a variable workload, which results in small, but significant time differences. Just a small amount of change in the time can majorly alter the score one way or the other.

Leave a Reply

<pre class="code">
a = magic(3);
sum(a)
</pre>

These postings are the author's and don't necessarily represent the opinions of The MathWorks.