Thread Subject:

MATLAB Programming Contest: November 2-9, 2005

The next MATLAB Programming Contest will start tomorrow at 9 a.m. EST
and run through Wednesday, November 9 at 5 p.m. EST. Topics and rules
will be posted on the morning of the contest:
  
 <http://www.mathworks.com/contest/>
  
As in recent contests, there will be three stages, darkness,
twilight, and daylight. During darkness, both the code and scores for
all entries will be hidden. In twilight, the scores will be visible
but the code will still be hidden. When daylight arrives, all scores
and code are visible. We'll also be holding several mid-contest prize
giveaways of MATLAB bags, caps, and other good stuff, so don't wait
until the last minute to participate.
  
Please use this thread to talk about the contest, strategies, or to
ask related questions. If you have an "administrative" type of
question that you don't feel applies to anyone else, e-mail us at
contest@mathworks.com.
  
We look forward to seeing your entry. Good luck!
  
- The MATLAB Contest Team -

I am a little bit confused by part of the rule

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
The sudoku solving routine is sodoku.m.

 a = sudoku(x,aInit)

where x is the complete vector of n^4 numbers to be placed in the
grid, aInit is the partially filled n^2-by-n^2 solution matrix, and a
is the completed solution. Note that all nonzero elements in aInit
must appear in x.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

the solving routine name is solver.m, moreover, the order of
arguments seems not matching.

Please help

Min Poh wrote:
>
>
> The next MATLAB Programming Contest will start tomorrow at 9 a.m.
> EST
> and run through Wednesday, November 9 at 5 p.m. EST. Topics and
> rules
> will be posted on the morning of the contest:
>
> <http://www.mathworks.com/contest/>
>
> As in recent contests, there will be three stages, darkness,
> twilight, and daylight. During darkness, both the code and scores
> for
> all entries will be hidden. In twilight, the scores will be visible
> but the code will still be hidden. When daylight arrives, all
> scores
> and code are visible. We'll also be holding several mid-contest
> prize
> giveaways of MATLAB bags, caps, and other good stuff, so don't wait
> until the last minute to participate.
>
> Please use this thread to talk about the contest, strategies, or to
> ask related questions. If you have an "administrative" type of
> question that you don't feel applies to anyone else, e-mail us at
> contest@mathworks.com.
>
> We look forward to seeing your entry. Good luck!
>
> - The MATLAB Contest Team -

wuzhili wrote:
>
> I am a little bit confused by part of the rule
> the solving routine name is solver.m, moreover,
> the order of arguments seems not matching.

You are correct. We've updated the rules to match the supplied code.

-Ned Gulley.
MATLAB Contest Team

Hi,

I think I found a typo in the Example.
 <http://www.mathworks.com/contest/sudoku/rules.html>
 
Possibly WRONG
>> target = sum(a)/4
 
CORRECT
>> target = sum(a(:))/4
 
... I should use this thread. Sorry about that.

Regards,
Tetsuya

Min Poh wrote:

> Please use this thread to talk about the contest, strategies, or to

Glancing at the example testsuite, it looks like all the numbers in
the "list" are positive and sorted into ascending order. Can we
assume that all the input lists will be like this?

Thanks, Mike

Regarding the test suite, I noticed that none of the list vectors
contain numbers that are present in the puzzle arrays, so the problem
of repeating numbers within a row, column, or region is not an issue.
 Will this be true of all test inputs?

-Kelly

I'm just wondering if the testsuite you use is "same as" or "similar
to" or "quite differnet from" the testsuite we get from the zip file.
This could largely affect my programming strategy.

All, you said "Your entry will time out and be disqualified if it takes
more than 180 seconds (three minutes). " Does this all mean for 100
samples?

I've been peeking at the entries and we're off to a great start!

Tetsuya, we've fixed that typo in the rules. Thanks.

Mike and Kelly, we don't like to reveal too much about the test
suite. Elements in list do happen to be positive, sorted, and
unique.

viterbi, the sample test suite is similar to the actual one. You can
use it to get a rough idea of how fast your entry runs. Know,
however, that the machine we run it on is older, and that the time
penalty becomes quite severe significantly before the timeout. It is
impossible to know exactly how the timing will influence your final
score during darkness.

In answer to your other question, yes your entry must make it through
the entire testsuite before the timeout.

How long does it take to get scores back? I haven't gotten official
scores back yet on a few entries that I submitted (seemingly) quite a

while ago. I had hoped to have faster response in receiving my
scores because it would be useful to calculate the scoring
coefficients. Knowing whether time or performance is the greater
factor could affect everyone's approach to programming.

Anyway, what's the typical turn-around time expected to be
through-out the contest?

Thanks!

During Darkness, this first phase, you won't be able to see any of
the scores. At noon EST tomorrow, we will show the scores for all
the entries, but the code remains hidden until Friday.

Shouldn't I receive an email from Matlab with the score for my
current submissions? With an eye towards iterative improvement, I'm
thinking it would be valuable to know which of my submissions are
doing the best. With the time factor being an unknown, I'm keen to
figure out the scoring coefficients so that I have some sense of
where the most effort should go. Is fast but sloppy much, much
better than slow but careful?

As of yet, I haven't received an email from Mathworks with a score.
Is it the case that ALL scores are in the dark -- that you really
have no idea even of how well your own submissions are performing
against one another?

Darkness is "rather dark". e-mails are not sent (for normal things).
 The only thing is that you see which entries are submitted (and
therfore it is not "really dark")...

Ed Limbaugh wrote:
>
>
> Shouldn't I receive an email from Matlab with the score for my
> current submissions? With an eye towards iterative improvement,
> I'm
> thinking it would be valuable to know which of my submissions are
> doing the best. With the time factor being an unknown, I'm keen to
> figure out the scoring coefficients so that I have some sense of
> where the most effort should go. Is fast but sloppy much, much
> better than slow but careful?
>
> As of yet, I haven't received an email from Mathworks with a score.
>
> Is it the case that ALL scores are in the dark -- that you really
> have no idea even of how well your own submissions are performing
> against one another?

It's quite dark. But... judging from previous contests, results are
rather more important than time at least up to tens of seconds. I
have a vague memory of about 50 seconds becoming a noticable
contribution to the score of one of the best final entries at the end
of a previous contest. In the same contest 40 seconds was
essentially negligible.

Mike

Mike Bindschadler wrote:
> It's quite dark. But... judging from previous contests, results
> are
> rather more important than time at least up to tens of seconds. I
> have a vague memory of about 50 seconds becoming a noticable
> contribution to the score of one of the best final entries at the
> end
> of a previous contest. In the same contest 40 seconds was
> essentially negligible.
>
> Mike

This matches my own recollection (assuming they haven't fiddled with
the constants). But the other unknown is the translation from time
on the sample testsuite on your machine to time on the real testsuite
on the test machine. It makes everything rather uncertain. Good
luck!

I'm confused by an apparent discrepancy about the order of the puzzle
grid. The rules first say under the "Example" section that:

% Begin rules quote %
"The actual context will use the order=3 grid"
% End rules quote %

but later under "Developing Your Entry", it says that:

% Begin rules quote %
"...where puzzle is the partially filled n^2-by-n^2 solution matrix..."
% End rules quote %

So will the puzzle matrix in the actual contest be a 3^2-by-3^2 matrix
or a n^2-by-n^2 matrix?

Akbar

Is the "search entries" button removed on purpose? or will it be
added in "brighter periods"? or does I just don't see it??

Akbar Hi:

The testsuite only contains order=3 puzzles, you may find parts of
code which are generalized because initially we were considering to
make the contest for any order between 2 and 6.

Lucio Cetto
The Contest Team

A Ladak wrote:
>
>
> I'm confused by an apparent discrepancy about the order of the
> puzzle
> grid. The rules first say under the "Example" section that:
>
> % Begin rules quote %
> "The actual context will use the order=3 grid"
> % End rules quote %
>
> but later under "Developing Your Entry", it says that:
>
> % Begin rules quote %
> "...where puzzle is the partially filled n^2-by-n^2 solution
> matrix..."
> % End rules quote %
>
> So will the puzzle matrix in the actual contest be a 3^2-by-3^2
> matrix
> or a n^2-by-n^2 matrix?
>
> Akbar
>
>

Hi guys,

I'm really curious about what the balance between runtime and results
are. It must make a huge difference.

I'm really wondering about the time-limit. Does the three minute
cutoff indicate the algorithm runtime, or the testsuite runtime?

I hadn't realized how addictive the matlab contests are. :)

Mike and Nick: thanks for giving me a rough idea of what to expect. I
took a brief look at results from a previous contest, but

Is anyone else in the contest running matlab for mac?

Francis

Nick Howe wrote:
>> Mike Bindschadler wrote:
>> It's quite dark. But... judging from previous contests,
results are rather more important than time at least up to tens of
seconds. I have a vague memory of about 50 seconds becoming a
noticeable contribution to the score of one of the best final entries
at the end of a previous contest. In the same contest 40 seconds was
essentially negligible.
>>
>> Mike
> This matches my own recollection (assuming they haven't fiddled
with the constants). But the other unknown is the translation from
time on the sample testsuite on your machine to time on the real
testsuite on the test machine. It makes everything rather uncertain.
 Good luck!

Francis Esmonde-White wrote:
> Is anyone else in the contest running matlab for mac?
>
> Francis
Yes, there is....(most of the time). And this time even only ("the
good old") Matlab 5.2, and it workst fine.
For timing estimation it is not so easy, but in the first days, don't
look to not too complex code, which also runs without too much
JIT....
Stijn

Min Poh wrote:
>
>
> The next MATLAB Programming Contest will start tomorrow at 9 a.m.

In addition to the top 20 entry list and the complete entry list, it
might be nice to show an entry list that has only the top-scoring
entry of each author (or the top 20 authors, say).

Francis Esmonde-White wrote:

> I'm really curious about what the balance between runtime and
> results
> are. It must make a huge difference.

The scoring coefficients are

k1 = 0.1
k2 = 0.01
k3 = 0.1

Loophole found?
Just check out the chronological listing...

Niilo Sirola wrote:
>
>
> Loophole found?
> Just check out the chronological listing...

Brian Welch strikes again:

 <http://www.mathworks.com/contest/mastermind.cgi/cheating.html>

>> Niilo Sirola wrote:
>> Loophole found?
>> Just check out the chronological listing...

> the cyclist wrote:
> Brian Welch strikes again:
>http://www.mathworks.com/contest/mastermind.cgi/cheating.html <http://www.mathworks.com/contest/mastermind.cgi/cheating.html>

Yes, we've been successfully hacked: Brian's entries exposed our test
suite. Our plan is to continue scoring with the current test suite
until the noon prize is awarded, at which point we will change the
tests. The new test suite will be similar in character to the old
one, but there will be a discontinuity in the results.

-Ned Gulley.
MATLAB Programming Contest Team

>>> Niilo Sirola wrote:
>>> Loophole found?
>>> Just check out the chronological listing...
I missed it(?). What was shown - the whole suite? I'm curious.
Will we be able to find out how he did it?

Stijn Helsen wrote:
>
>
>>>> Niilo Sirola wrote:
>>>> Loophole found?
>>>> Just check out the chronological listing...
> I missed it(?). What was shown - the whole suite? I'm curious.
> Will we be able to find out how he did it?

It looked like the whole suite, and nicely formatted too!
Ken

Min Poh wrote:
>
>
> The next MATLAB Programming Contest will start tomorrow at 9 a.m.
> EST
> and run through Wednesday, November 9 at 5 p.m. EST.

Is "Daylight" being delayed for some reason?

Brian's hack caused us some amount of scrambling today. He figured
out a way to pass information out of the test suite using RETHROW.
We've added RETHROW to the forbidden list and deleted his entries.
We ask that anyone who used this information to take the lead
disqualify himself from winning the Twilight phase.

After we finish processing entries that were submitted before noon
and announce our Twilight winner, we will swap in a new test suite.
It will be similar to the original (and the sample) test suite, but
any specific tuning of entries will be lost. It will be
interesting to see how changing test suites affects the generality of
the submissions.

In the meantime, we've entered the Daylight phase, so you're now able
to see everyone's code. Look for the announcement of another
mid-contest challenge soon.

It is a pitty that the more free version of this game was choosen
(with flexible dimensions). In that way, the full coding wasn't
done, which gave "realer" codes.

Min Poh wrote:
>
>
> The next MATLAB Programming Contest will start tomorrow at 9 a.m.
> EST
> and run through Wednesday, November 9 at 5 p.m. EST.

Is anyone else taken to a non-Mathworks web site when they click on
"Chronological Listing"?

the cyclist wrote:

> Is anyone else taken to a non-Mathworks web site when they click on
> "Chronological Listing"?

Yep, had to turn my java off to stop that. Apparently the rethrow-bug
isn't completely fixed yet. :)

Niilo Sirola wrote:
>
> Yep, had to turn my java off to stop that. Apparently the
> rethrow-bug
> isn't completely fixed yet. :)
But this time it wasn't something from Brian. It is a submission of
someone who called himself "sudokuist"....??

And the last improvement of half a second (by Timothy) was done
without any change in the code!!

We should be back in business now. This second hack was courtesy of
a new way to call function handles. Here is how you define a
function handle:

>> f = @sin;

You used to have to evaluate it like this:

>> y = feval(x,3);

Now you can also evaluate it like this directly:

>> y = f(3);

Our machinery wasn't smart enough to be able to catch this case and
block if the function was disallowed. We've improved this and it
seems to be working now. Hopefully won't get any false positives.

For more information on function handles, see the MATLAB
documentation:

<http://www.mathworks.com/access/helpdesk/help/techdoc/matlab_prog/ch05_m20.html>

Knowing that you can be lucky (or unlucky) with tolerances in timing,
is one thing, but successively just resubmitting entries is not
really a nice way of gaming, is it?
Now was Timothy less "lucky", by gaining only 3/100 s with TLL024,
but that was enough...

Stijn, you've been participating in this contest long enough to know
how fickle first place can be. (In fact, you've even won a couple of
times and contributed analyses.)

We definitely want to reward contestants who make entries run faster.
 This can be as challenging as improving the answer. It is very
difficult to reproduce timing measurements on modern PCs with all the
layers of caching and optimization. Even if our timing were very
accurate, resubmitting the same entry would have a 50% chance of
beating the original, right?

We're always looking for ideas to better measure contributions. I'm
a big fan of the Big Sunday Push mid-contest prize which we just
announced:

 <http://blogs.mathworks.com/contest/>

Cumulative improvement is one of the more accurate metrics we use.
One of its problems, though, is the scale possible improvement
diminishes rapidly. It's harder to make the same size decrease at
the end of the day.

I encourage everyone to look at the Contributions by Day to see who
the big movers are in the contest. For example, Johan Svahn made the
biggest in score so far today in one leap. Stijn has made many
improvements in score and is our second biggest contributor.

Should we make this metric more prominent? Is there another way we
can better detect the best entries? Please keep the feedback coming.

Matthew Simoneau wrote:
>
>
> Stijn, you've been participating in this contest long enough to
> know
> how fickle first place can be. (In fact, you've even won a couple
> of
> times and contributed analyses.)
>
> We definitely want to reward contestants who make entries run
> faster.
> This can be as challenging as improving the answer. It is very
> difficult to reproduce timing measurements on modern PCs with all
> the
> layers of caching and optimization. Even if our timing were very
> accurate, resubmitting the same entry would have a 50% chance of
> beating the original, right?
>
> We're always looking for ideas to better measure contributions.
> I'm
> a big fan of the Big Sunday Push mid-contest prize which we just
> announced:
>
> <http://blogs.mathworks.com/contest/>
>
> Cumulative improvement is one of the more accurate metrics we use.
> One of its problems, though, is the scale possible improvement
> diminishes rapidly. It's harder to make the same size decrease at
> the end of the day.
>
> I encourage everyone to look at the Contributions by Day to see who
> the big movers are in the contest. For example, Johan Svahn made
> the
> biggest in score so far today in one leap. Stijn has made many
> improvements in score and is our second biggest contributor.
>
> Should we make this metric more prominent? Is there another way we
> can better detect the best entries? Please keep the feedback
> coming.

I can think of two possibilities, both of which have pros and cons.
First would be to round the execution time of the code to the nearest
half-second before entering it into the scoring algorithm. In the
event of a tie scoring (which would become far more common), the
higher place is awarded to the earlier entry, naturally. The
downside is that even a tiny random variation could push an entry
down into the next lower time increment, but I think it would reduce
the incidence substantially.

A second idea is to "fail" entries that result in identical p-code.
The downside is that it is presumably easy to change the M-file
trivially to get around this requirement, while still actually having
an identical algorithm. (I have no idea!) It would at least
eliminate the "casual duplicater".

the cyclist wrote:
>
> I can think of two possibilities, both of which have pros and cons.
>
> First would be to round the execution time of the code to the
> nearest
> half-second before entering it into the scoring algorithm. In the
> event of a tie scoring (which would become far more common), the
> higher place is awarded to the earlier entry, naturally. The
> downside is that even a tiny random variation could push an entry
> down into the next lower time increment, but I think it would
> reduce
> the incidence substantially.
>
> A second idea is to "fail" entries that result in identical p-code.
>
> The downside is that it is presumably easy to change the M-file
> trivially to get around this requirement, while still actually
> having
> an identical algorithm. (I have no idea!) It would at least
> eliminate the "casual duplicater".

That's a great idea. I think there should also be some minimal code
preprocessing (automatic variable renaming, whitespace formatting and
so on) to compare the code. If no code changes are present between
different entries, a time penalty should be added (as they already do
for identical entries).

Francis Esmonde-White wrote:

> If no code changes are present between
> different entries, a time penalty should be added (as they already
> do
> for identical entries).

Identical entries are assessed a time penalty now? I had no idea.
When did that begin?

the cyclist wrote:
>
>
> Francis Esmonde-White wrote:
>
>> If no code changes are present between
>> different entries, a time penalty should be added (as they
> already
>> do
>> for identical entries).
>
> Identical entries are assessed a time penalty now? I had no idea.
> When did that begin?

Try submitting *exactly* the same code twice. I realized this while
testing performance of the server vs my G5, and trying to see if the
random number generator made a big difference. Unfortunately, it's
only flagged if you submit the code twice yourself. I think they add
+1 second for each subsequent resubmission. It would be wonderful if
that was done between submitters as well.

We don't have any timing penalties for resubmitted entries. It would
be too easy to fake out such a system by making insignificant changes.

Matthew Simoneau wrote:
>
>
> We don't have any timing penalties for resubmitted entries. It
> would
> be too easy to fake out such a system by making insignificant
> changes.

Thanks for the clarification Matt!

Matthew Simoneau wrote:
>
>
> Stijn, you've been participating in this contest long enough to...
I didn't want to complain, really. Just thinking loud enough, and
writing it gives enough relief......

the cyclist wrote:
>
>
> First would be to round the execution time ...
>
> A second idea is to "fail" entries that result in identical
p-code.....
I don't think that these proposals would work. The first one can
give strange results, I think. Then submissions would be optimised
for having a round time (or +0.5).
The second idea has the main disadvantage that many people are often
trying the same things. If you are the second one who is trying it,
without knowing it from the other, wouldn't give any result!

One problem, I think it the high increase of the timing-influence
above a certain time (because of the exponential). I think a flatter
one (quadratic) could be better. (Now the time is around a minute,
and an entry with result 0 must be faster than 94 seconds to be on
top now!)
And, I think that's just part of the game, (((as long as we can
complain here, now and then...))).

what about this: if your code makes it to the top your score is given
a -.1 bonus (or whatever quantity considered fair). In that way only
changes that would improve your "real" score by at least that amount
could beat it.

Stijn Helsen wrote:
>
>
> the cyclist wrote:
>>
>>
>> First would be to round the execution time ...
>>
>> A second idea is to "fail" entries that result in identical
> p-code.....
> I don't think that these proposals would work. The first one can
> give strange results, I think. Then submissions would be optimised
> for having a round time (or +0.5).
> The second idea has the main disadvantage that many people are
> often
> trying the same things. If you are the second one who is trying
> it,
> without knowing it from the other, wouldn't give any result!
>
> One problem, I think it the high increase of the timing-influence
> above a certain time (because of the exponential). I think a
> flatter
> one (quadratic) could be better. (Now the time is around a
> minute,
> and an entry with result 0 must be faster than 94 seconds to be on
> top now!)
> And, I think that's just part of the game, (((as long as we can
> complain here, now and then...))).

Some one please explain to me how the timing of the leading entry
almost doubles by replacing:

    target = sum(sum(solution))/9;

with:

    target = sum(solution(:))/9;

The CPU time went from 54.05 to 99.25. Does it really take the same
amount of time to calculate the sum using the second technique as it
does to find the whole solution?

What gives?

Matthew Simoneau wrote:
>
>
> We don't have any timing penalties for resubmitted entries. It
> would
> be too easy to fake out such a system by making insignificant
> changes.

Paulo wrote:
>
>
> Some one please explain to me how the timing of the leading entry
> almost doubles by replacing:
>
> target = sum(sum(solution))/9;
>
> with:
>
> target = sum(solution(:))/9;
>
> The CPU time went from 54.05 to 99.25. Does it really take the
> same
> amount of time to calculate the sum using the second technique as
> it
> does to find the whole solution?

I tried this "optimization", too, which I also do in my "real-life"
code. I am equally baffled.

Paulo wrote:
> Some one please explain to me how the timing of the leading entry
> almost doubles by replacing:
> target = sum(sum(solution))/9;
> with:
> target = sum(solution(:))/9;
> The CPU time went from 54.05 to 99.25.....
I can be completely wrong, but I suppose it has to do with making a
mess in memory management. 'solution(:)' has to make a new array,
with the same space, but with another shape. New memory is reserved,
the sum is made, and the memory is made free again. The next time
(probably depending on what's done before), the same memory space is
not found (always) to put the array. New memory is reserved. After
some time the memory is full of small used memory space, which has to
be "cleaned" after some time. (That's the main reason why the cpu
times of the same codes can differ a lot, I think (except of course
every other thing that computers do on its own, these days).
When doing sum(sum(xx)), the new array is smaller, and therefore it
can last longer before the memory become "total mess", and maybe it
is easier to find the smaller memory space in already used memory.
I repeat, my idea can be completely wrong, but that's how I've
explained to myself, after being surprised too.

In article <ef1a059.46@webx.raydaftYaTP>, sss@ccc.com says...
> Paulo wrote:
> > Some one please explain to me how the timing of the leading entry
> > almost doubles by replacing:
> > target = sum(sum(solution))/9;
> > with:
> > target = sum(solution(:))/9;
> > The CPU time went from 54.05 to 99.25.....
> I can be completely wrong, but I suppose it has to do with making a
> mess in memory management. 'solution(:)' has to make a new array,
> with the same space, but with another shape. New memory is reserved,
> the sum is made, and the memory is made free again. The next time
> (probably depending on what's done before), the same memory space is
> not found (always) to put the array. New memory is reserved. After
> some time the memory is full of small used memory space, which has to
> be "cleaned" after some time. (That's the main reason why the cpu
> times of the same codes can differ a lot, I think (except of course
> every other thing that computers do on its own, these days).
> When doing sum(sum(xx)), the new array is smaller, and therefore it
> can last longer before the memory become "total mess", and maybe it
> is easier to find the smaller memory space in already used memory.
> I repeat, my idea can be completely wrong, but that's how I've
> explained to myself, after being surprised too.
>

Good theory, but MATLAB is smart enough to just create a new header for
the array solution(:) and change the size vector in the header only. So
it's not obvious at all what is going on here - normally sum(a(:)) is
faster than sum(sum(a))!

--Loren

It also depends on the size of the matrix. "sum(solution(:))" is
slightly faster with small matrices, while "sum(sum(solution))" is
faster with big ones. On my desktop, the crossover is around 16x16.

In any case, the difference wouldn't account for a huge difference in
performance in the overall entry. Another possibility is that the
roundoff error of these two approaches causes the entry to run
through two totally different code paths in the actual test suite. I
haven't verified this, though.

Is the Midnight Madness cutoff 2005-11-08 00:00:00?

-Guy Incognito

Tom Lemke wrote:
>
>
> Is the Midnight Madness cutoff 2005-11-08 00:00:00?
>
> -Guy Incognito
I suppose so. So, you are the winner..... (00:00 means 6:00 in the
morning in Belgium, not the easiest time during a "working week")....

Stijn Helsen wrote:
> (00:00 means 6:00 in the
> morning in Belgium, not the easiest time during a "working
> week")....

True, but I'm not sure what time makes for a better deadline during a
working week.
:)

Since the shared code forces us all to be synchronized, I wonder if
it might make sense to have one of the markers like "Midnight
Madness" change timezone from contest to contest.
Perhaps next year it can be Midnight Madness in Belgium or
Bangladesh.

Is it tuesday(today) that they usually have a 17:00 midcontest prize?

Tom Lemke wrote:
> Is it tuesday(today) that they usually have a 17:00 midcontest
> prize?
When I look to the "hall of fame" (because I never remember what was
when), the midcontest prize is not one of the "usuals").

I think it will be a good idea to get algorithms description authors
used in their code.

<SNiP Contest announcement>

Is is just me or is the queue stuck (or just extremely slow)? Haven´t
seen any TMW-announced errors with the queue...

/PB

Initially, I was happy to see that finally we have a contest problem
that can be nicely put into linear algebra framework, and thought
that clever use of MATLAB's matrix routines would play a part in
winning this contest... Alas, JIT is getting just too good :) and it
seems that specific element-wise manipulation and hard-coding of the
indices is indeed faster than vectorizing your code properly. Here's
another way of looking at the problem, nevertheless. You can look up
some of my early entries <http://www.mathworks.com/contest/sudoku.cgi/view_submission.html?id=24351>
o see these ideas implemented.

Say the solution is reshaped into a 81*1 vector sol. Then it is easy
to devise the 27*81 matrix A such that A*sol gives a vector
consisting of the row sums, column sums and region sums. (Each row of
A would consist of ones at elements to be added in the
row/column/region sum in question and zeros elsewhere).

The goal is to make all the sums equal (or close to) to sum(sol)/9,
so the problem is to solve A*sol = ones(27,81)*sol/9, or B*x = 0,
where B = (A-1/9).

The "given" elements of sol are pre-fixed, and this can be taken into
account by splitting sol into "free" and "locked" parts x and y, and
the columns of B similarily to get: B*sol = [M L]*[x; y] = M*x + L*y.
Note that b = -L*y is constant, so the problem is just to solve M*x =
b. The system is underdetermined and there are dozens of degrees of
freedom in choosing x that solves this equation accurately.

The final restriction on x is that it's elements must come from the
given list, and here is of course where the heuristics come in...

One approach is to first solve the relaxed problem M*x = b without
restriction to x and then choosing the values from the list that are
closest to the accurate solution. "Closest" in the sense that the
norm(b-M*x, 1) = sum(abs(b-M*x) is minimized.

I've tried different things, using Gauss-Newton iterations to try to
refine the "quantized" solution, and exploiting the null-space of M
(which MATLAB also computes in a flash) to find accurate solutions
that would also be close to the list elements, but can't seem to
match the speed nor the performance of the current strain anymore.

Well, at least to me it seemed easier to deal with the problem of
minimizing the 1-norm of (b-M*x) instead of juggling in terms of rows
and columns and sectors. Alas, if the optimality criteria of the
solution would been 2-norm instead of 1-norm, maybe some
eigen-thingies could have been of use... Also, I have to agree with
Stijn's earlier post about free dimensions being much more
interesting than fixed one. (although then there soon would have been
specialized solvers for different n values...)

It is a great idea to use systematic linear algebra.

The Darkness Winner Per Rutquist also used very nice (but still hard
to understand) linear algebra.

 <http://www.mathworks.com/contest/sudoku.cgi/view_submission.html?id=23213>

But later, all leading solvers do not follow a linear algebra setup.


Niilo Sirola wrote:
>
>
> Initially, I was happy to see that finally we have a contest
> problem
> that can be nicely put into linear algebra framework, and thought
> that clever use of MATLAB's matrix routines would play a part in
> winning this contest... Alas, JIT is getting just too good :) and
> it
> seems that specific element-wise manipulation and hard-coding of
> the
> indices is indeed faster than vectorizing your code properly.
> Here's
> another way of looking at the problem, nevertheless. You can look
> up
> some of my early entries <http://www.mathworks.com/contest/sudoku.cgi/view_submission.html?id=24351>
> o see these ideas implemented.
>
> Say the solution is reshaped into a 81*1 vector sol. Then it is
> easy
> to devise the 27*81 matrix A such that A*sol gives a vector
> consisting of the row sums, column sums and region sums. (Each row
> of
> A would consist of ones at elements to be added in the
> row/column/region sum in question and zeros elsewhere).
>
> The goal is to make all the sums equal (or close to) to sum(sol)/9,
> so the problem is to solve A*sol = ones(27,81)*sol/9, or B*x = 0,
> where B = (A-1/9).
>
> The "given" elements of sol are pre-fixed, and this can be taken
> into
> account by splitting sol into "free" and "locked" parts x and y,
> and
> the columns of B similarily to get: B*sol = [M L]*[x; y] = M*x +
> L*y.
> Note that b = -L*y is constant, so the problem is just to solve M*x
> =
> b. The system is underdetermined and there are dozens of degrees of
> freedom in choosing x that solves this equation accurately.
>
> The final restriction on x is that it's elements must come from the
> given list, and here is of course where the heuristics come in...
>
> One approach is to first solve the relaxed problem M*x = b without
> restriction to x and then choosing the values from the list that
> are
> closest to the accurate solution. "Closest" in the sense that the
> norm(b-M*x, 1) = sum(abs(b-M*x) is minimized.
>
> I've tried different things, using Gauss-Newton iterations to try
> to
> refine the "quantized" solution, and exploiting the null-space of M
> (which MATLAB also computes in a flash) to find accurate solutions
> that would also be close to the list elements, but can't seem to
> match the speed nor the performance of the current strain anymore.
>
> Well, at least to me it seemed easier to deal with the problem of
> minimizing the 1-norm of (b-M*x) instead of juggling in terms of
> rows
> and columns and sectors. Alas, if the optimality criteria of the
> solution would been 2-norm instead of 1-norm, maybe some
> eigen-thingies could have been of use... Also, I have to agree with
> Stijn's earlier post about free dimensions being much more
> interesting than fixed one. (although then there soon would have
> been
> specialized solvers for different n values...)

Great work Amr Tawfik,

Just go ahead and resubmit people's codes even before they are
scored.
And yes we won't notice that they are the exact same code if you
delete a line of comment or two.
I hope it feels good enough to see your name on the top of the list,
because that looks like the only thing you will get out of this
contest.

Volkan wrote:
> Great work Amr Tawfik,
>
> ...because that looks like the only thing you will get
> out of this contest.
Do I see some angryness? That's the game (rather than contest)...
Of course, it is nicer to see other people come on top after doing
real improvements, but yes, it's part of the game that other people
can be quick in copying code...

Can anyone explain why of the following 3 snippets of code, the first
generates a more optimal solution?

After all, the first yields approximately 1.7% (~1/lq) duplicates,
which should just waste a significant portion of the swapping
subroutine runtime. Also, the modulo operation on all of the elements
takes a significant slice of time (12.5 ms for 30000 elements). Only
performing it on a small subset of elements should reduce the total
time by a small but significant slice.

% popular in the main codebase
index1v = ceil(rand(1,NUMREPS)*lq);
index1v = q(index1v);
index2v = mod((index1v+floor(rand(1,NUMREPS)*(lq-1))),lq)+1;
index2v = uint8(q(index2v));
index1v = uint8(index1v);

% first alternate approach
index1v = ceil(rand(1,NUMREPS)*lq);
index2v = ceil(rand(1,NUMREPS)*lq);
[y,bad]=find(index1v==index2v);
% find duplicates... this swap is useless
if mod(lq,2) nudge=1; else nudge=2; end
% make the elements unequal
index2v(bad)=mod(index2v(bad)+nudge,lq)+1;
index1v = uint8(q(index1v));
index2v = uint8(q(index2v));

% second alternate approach
index1v = ceil(rand(1,NUMREPS)*lq);
index2v =index1v+floor(rand(1,NUMREPS)*(lq-1));
% use something closer to the original approach
[xyz,bad]=find(index2v>lq);
% don't use mod
% we know that the value will never be more than 2*lq
index2v(bad) = index2v(bad)-lq;
% adjust the range of the bad members
[xyz,bad]=find(index1v==index2v);
% take care of duplicates
index1v(bad)=ceil(rand(1,numel(bad))*lq);
% replace duplicates
% (this is a poor method, because some duplicates remain)
index2v = uint8(q(index2v));
index1v = uint8(q(index1v));

Thanks,
Francis

Francis Esmonde-White wrote:

> Can anyone explain why of the following 3 snippets of code, the
> first generates a more optimal solution?

Simple. The variant from the leading entry has "magical" random
number sequence, changing any of those will take the solution out of
the deep local minimum it's been driven into.

At this stage, you'll have to do all optimizations such that the same
random numbers are used in same places, or go through the trouble of
seeking the optimal rand seed, numbers of repetitios, threshold
values etc...

Hence, we're optimizing the algorithm to take advantage of the exact
sequence in the random number generator. That's pretty much what I
thought, but I'd hoped there was a more interesting answer that I was
somehow missing.

Perhaps it would make the contest more interesting if the seed wasn't
disclosed, and was altered occasionally throughout the contest (or
run-sequence) so that silly things like this weren't possible.

I do enjoy the contest, and I'd like to applaud the great
organization by the mathworks people in charge. Overall, the contest
is very well thought out.

I think that the best solution is still probably quite far from the
optimum value, considering the mid-contest hints.

Francis

Niilo Sirola wrote:
>
>
> Francis Esmonde-White wrote:
>
>> Can anyone explain why of the following 3 snippets of code, the
>> first generates a more optimal solution?
>
> Simple. The variant from the leading entry has "magical" random
> number sequence, changing any of those will take the solution out
> of
> the deep local minimum it's been driven into.
>
> At this stage, you'll have to do all optimizations such that the
> same
> random numbers are used in same places, or go through the trouble
> of
> seeking the optimal rand seed, numbers of repetitios, threshold
> values etc...

Matthew Simoneau wrote:
>
>
> It also depends on the size of the matrix. "sum(solution(:))" is
> slightly faster with small matrices, while "sum(sum(solution))" is
> faster with big ones. On my desktop, the crossover is around
> 16x16.
I did a test, and there was a constant difference in time for
matrices of nxn sizes between 2 and 50, always giving a higher time
for "A(:) calculation".

Hi all.

Someone, please explain this to me?!

I'm running Matlab 7.0.4, same as the contest PC. When we take one of
the leading entries and replace all the abs(x)
in the inner loop with

if (x<0) x=-x; end;

the code executes in 40% less time and returns the exact same result.
However, when we submit the code it still returns the same result but
takes LONGER than the original.

To explain better, compare the following 2 entries
            SHsudo10cor2 & cleanagain (which differ as Local t
   47.39 s 28.64 s described)
Local res 936.42 936.42
Contest t 55.23 s 57.8717 s
Contest res 948.02 948.02

The only explanation I can come up with is that the significant
timing difference may be due to differences between the Windows and
Unix JVMs. Is the contest server running on a *nix box? Or could it
be due to differences in hardware?

Anyway, thanks for a great contest, congrats to the cyclist, and
we'll be back for the next one.

Hannes Naudé

Sorry, formating on previous post went haywire, the table should look
like :(this is probably still not right but at least better)
            SHsudo10cor2 & cleanagain (which differ as described)

Local t 47.39 s 28.64 s
Local res 936.42 936.42
Contest t 55.23 s 57.8717 s
Contest res 948.02 948.02

H

now that was a very interesting Matlab contest. I really enjoyed this
one :).

But there are still some things which could improve the contest
further IMHO.

1. extend the twilight phase (by 2 or 3 days), to encourage the
independent development of algorithmic ideas

2. set a predefined secret random seed and disable the rand(x,'seed')
function (the hunt for "magic" random number is IMHO not the goal of
this contest and is just no fun at all)

3. define a "leaders time" which gets only updated if a submission
improves the run time by a certain amount tdif (lets say 0.5 sec) or
if the result is changed. Submission which don't improve the result
and fall into tdif get the same score as if they have the "leaders
time". This should disencourage the constant resubmission with
unchanged code

Mihi

> 1. extend the twilight phase (by 2 or 3 days), to encourage the
> independent development of algorithmic ideas
>
> 2. set a predefined secret random seed and disable the
> rand(x,'seed')
> function (the hunt for "magic" random number is IMHO not the goal
> of
> this contest and is just no fun at all)
>
> 3. define a "leaders time" which gets only updated if a submission
> improves the run time by a certain amount tdif (lets say 0.5 sec)
> or
> if the result is changed. Submission which don't improve the result
> and fall into tdif get the same score as if they have the "leaders
> time". This should disencourage the constant resubmission with
> unchanged code

I really like the first idea, but I don't think anything can be done
about #2, you could effectively move to another seed by calliing rand
a few times at the beginning of the code.

I agree with the point of #3, but I don't know if a static tdif is a
fair way to do it...

Mihi and Tom, we have been thinking about extending the twilight
phase of the contest, especially after looking at the "Participants
per Day" section of the Contest Evolution:

 <http://www.mathworks.com/contest/sudoku/evolution.html>

These early stages of the contest attract the greatest number of
players.

Is there going to be further activity on this contest page?

Tom Lemke wrote:
>
>
> Is there going to be further activity on this contest page?

I see.

To wrap up the last contest, The Sudoku Final Analysis is now
available online:

 <http://www.mathworks.com/contest/sudoku/analysis.html>

Min

Tom Lemke wrote:
>
>
> Tom Lemke wrote:
>>
>>
>> Is there going to be further activity on this contest page?
>
> I see.