MATLAB Programming Contest Blog

May 10th, 2007

Darkness Ends and Twilight Begins

At the end of Darkness, we’re happy to welcome Nick Howe to the MATLAB Contest Hall of Fame. Nick has been an active participant in past contests, but this is his first contest win. The trickiest part of Darkness is that contestants have no way to know how fast their entries will run on the contest machine and hidden test suite, and no way to calculate the time penalty. Nick solved this problem by submitting a several different variants of the same code with different balances between run time and results. Using this technique, he edged out strong entries from Yi Cao, Steve Hoelzer, Hannes Naudé, and Ouri, who took the next four spots.

We’re now in the Twilight phase of the contest, where you can see the scores of all the entries but not any of the code. Our next award is for the best entry at noon EDT on Friday, when Daylight begins and everyone’s code becomes visible. The queue will likely back up as we approach the deadline, limiting and eventually blocking feedback from the contest machine, so submit your entries early.

By Matthew Simoneau

13:43 UTC | Posted in Peg Solitaire | 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 “Darkness Ends and Twilight Begins”

  1. Nick Howe replied on May 16th, 2007 at 20:54 UTC :

    Just for the record, here are my comments on the winning Darkness entry. I actually didn’t expect it to come out on top — unlike previous contests, I didn’t feel like I had any special tricks up my sleeve. The entry that won was one of a series of implementations of a simple beam search algorithm. (The first entry in the series was named BMW as a nod to the algorithm used, and successive refinements got named using a sports car theme.) The first version used a fixed beam size and was fairly slow. By the time I got to the winning entry, I was adjusting the beam size according to the size of the puzzle and the number of relatively good solutions, and I had improved the speed of the code to allow searching many more possible moves. Because the beam size directly controlled the running time of the code, it was easy to select any time/performance tradeoff that I desired. I tried to limit the number of different variants to a reasonable number, so it was partially luck that one of the entries turned out to be fairly well tuned for the test set.

Leave a Reply

Wrap code fragments inside <pre> tags, like this:

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

If you have a "<" character in your code, either follow it with a space or replace it with "&lt;" (including the semicolon).

About

The MATLAB Programming Contest is a semi-annual competition where contestants submit MATLAB code to try to solve a challenge. For more information, see the overview.

Subscribe

Recent Comments

  • gopal: This is a try
  • Amtu: Well done Alfonso ! Congratulations ! Thanks MATLAB team, I’m already looking forward to the next time.
  • Alan Chalker: Just wanted to post here as well that I think Alfonso should be declared the grand winner since the top...
  • Alan Chalker: Just noticed something curious on the statistics page. While some of the charts are updating correctly,...
  • Ned: To Oliver: There will not be a late stage twilight in this contest. So it’s full daylight right to the end.
  • Oliver Woodford: Much obliged, Mike. For anyone looking for a speed boost to that approach I recommend “Basic...
  • MikeR: I agree with Oliver that if possible making the final few hours of the contest conceal the entries will be...
  • Oliver Woodford: When does late stage twilight begin, and will it then run on until the end of the contest?
  • Alan Chalker: As I traditionally do about this time in the contest, I’ve submitted a heavily commented version...
  • the cyclist: Looks like there might be a problem with the statistics page. For one thing, Alan Chalker holds all 20...

Blog Admin

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