MATLAB Programming Contest Blog

May 1st, 2008

We’re still deep in Twilight here at Contest Headquarters, but I was able to get Lucio to release a few pictures of how the lead entries are doing. David Jones is all over the lead so far. Here are three entries of his at various points of development.

By the way, this puzzle is NOT from the actual test suite.

This solver is from last night at around 10 PM. Total score for this board: 858.

Next is a solver from around 2 AM, presumably before David went to sleep. Or maybe he just stepped away from the computer, grabbed a coffee, and started working off line for a while. Notice this entry is starting to make use of bridges, whereas the example above did not. Total score: 612.

He was up again the next morning before noon and submitted this winning entry in time to secure the coveted “Prince of Darkness” prize. Fewer bridges, more connectivity, and a better score (487). Nice work David!

Can you see any way to improve this score by hand?

18:30 UTC | Posted in Wiring | 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.

5 Responses to “Sneak peek: leading solvers at work”

1. DrSeuss replied on May 1st, 2008 at 19:59 UTC :
   

   Yes,

   Remove the connectors for (49) from [6,4] to [11,7] and reconnect the [11,7] (49) straight down until it T’s into the existing 49-connectors. Reuses the one bridge across the (35,35) pair to (23,23) pair but via few connectors.

   How practical is this challenge problem? Wouldn’t there be a previous step that asks are the parts on the circuit layed out in such a manner that the minimum cost wiring is a consideration?

   :-)
   Sam I Am

2. Yi Cao replied on May 2nd, 2008 at 03:40 UTC :
   

   Based on DrSeuss’ improvement, rewire the connection between two 35’s, then two 21’s can be connected.

3. Alan Chalker replied on May 2nd, 2008 at 03:59 UTC :
   

   Sorry all, but it appears I have the dubious honor of being the first to crash the queue this time around. I was trying to determine the scoring coefficients and submitted a program with what should be a very high node count. However, after testing it on my version of R2008a, it appears that mtree ‘wraps around’ the node count as a fault and it’s returning a value of 1 for the node count.

4. Alan Chalker replied on May 2nd, 2008 at 04:21 UTC :
   

   Even though I accidentally crashed the queue, I think I have been able to figure out the scoring formula and am posting it here as I traditionally do. I’ve determined it’s very similar to the recent contests:

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

   Where:

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

   The current leading entry has a time of 56s, result of 141891, cyc of 25, and nodes of 4196. 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 1:5.7 ratio
   -result and score are a 1:0.1 ratio
   -node and score are a 1:0.001 ratio

   David Jones entries have already settled in just at the ‘knee’ of the time exponential curve, which is rather flat until about ~50s. However, because of the new time exponent constant, we are going to see much more payoff in this content in focusing on reducing the execution time versus other scoring elements, probably down to the ~10 second range.

   Unfortunately that probably also means that people are going to end up taking the lead due to ‘luck of the draw’ in the minor variations we always see in execution times, since they will be amplified more in the total score compared to in the past.

   Hope this helps everyone!

5. Matthew replied on May 2nd, 2008 at 14:38 UTC :
   

   From Lucio, here’s his test board:

   [ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
   0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
   0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
   0 0 0 0 0 0 0 0 0 0 23 9 21 35 0 0 0 0 0
   0 0 0 0 0 9 0 0 0 0 9 0 23 27 76 0 0 0 0
   0 0 0 0 0 0 27 0 0 0 44 0 0 23 0 49 49 58 0
   0 0 0 0 23 0 0 23 0 0 27 23 35 23 0 0 0 0 0
   0 0 0 0 0 0 0 76 0 0 0 0 58 49 0 0 0 0 0
   0 0 0 0 0 0 0 0 0 35 0 0 9 0 0 0 0 0 0
   0 0 0 0 0 0 0 35 0 0 0 21 0 0 0 0 0 0 0
   0 0 0 0 0 0 0 0 0 0 49 0 23 58 0 0 0 0 0
   0 0 0 0 0 49 35 21 0 23 0 0 23 0 0 0 0 0 0
   0 0 0 0 0 49 0 23 0 0 0 0 0 0 0 0 0 0 0
   0 0 0 0 0 49 21 18 0 0 0 0 0 0 0 0 0 0 0
   0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
   0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]

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.