# Thread Subject: MATLAB Programming Contest: November 2-9, 2005

 Subject: MATLAB Programming Contest: November 2-9, 2005 From: Min Poh Date: 1 Nov, 2005 13:02:20 Message: 1 of 72 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:         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 -
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: wuzhili Date: 2 Nov, 2005 09:40:43 Message: 2 of 72 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: > > > > 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 -
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: Ned Gulley Date: 2 Nov, 2005 09:54:03 Message: 3 of 72 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
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: Tetsuya Kajita Date: 2 Nov, 2005 10:08:08 Message: 4 of 72 Hi, I think I found a typo in the Example.     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
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: Mike Bindschadler Date: 2 Nov, 2005 10:39:07 Message: 5 of 72 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
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: Kelly Date: 2 Nov, 2005 11:56:37 Message: 6 of 72 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
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: viterbi Date: 2 Nov, 2005 10:44:21 Message: 7 of 72 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?
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: Matthew Simoneau Date: 2 Nov, 2005 16:37:18 Message: 8 of 72 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.
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: Ed Limbaugh Date: 2 Nov, 2005 17:16:51 Message: 9 of 72 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!
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: Matthew Simoneau Date: 2 Nov, 2005 17:23:02 Message: 10 of 72 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.
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: Ed Limbaugh Date: 2 Nov, 2005 17:36:52 Message: 11 of 72 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?
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: Stijn Helsen Date: 2 Nov, 2005 18:33:34 Message: 12 of 72 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")...
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: Mike Bindschadler Date: 2 Nov, 2005 20:57:37 Message: 13 of 72 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
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: Nick Howe Date: 2 Nov, 2005 23:19:57 Message: 14 of 72 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!
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: A Ladak Date: 2 Nov, 2005 23:25:55 Message: 15 of 72 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
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: Stijn Helsen Date: 3 Nov, 2005 02:55:22 Message: 16 of 72 Is the "search entries" button removed on purpose? or will it be added in "brighter periods"? or does I just don't see it??
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: Lucio Cetto Date: 3 Nov, 2005 04:04:23 Message: 17 of 72 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 > >
 Subject: MATLAB Programming Contest: November 2-9, 2005 Date: 3 Nov, 2005 04:46:14 Message: 18 of 72 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!
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: Stijn Helsen Date: 3 Nov, 2005 07:29:22 Message: 19 of 72 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
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: the cyclist Date: 3 Nov, 2005 16:03:07 Message: 20 of 72 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).
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: the cyclist Date: 3 Nov, 2005 23:43:16 Message: 21 of 72 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
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: Niilo Sirola Date: 4 Nov, 2005 07:26:30 Message: 22 of 72 Loophole found? Just check out the chronological listing...
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: the cyclist Date: 4 Nov, 2005 09:26:17 Message: 23 of 72 Niilo Sirola wrote: > > > Loophole found? > Just check out the chronological listing... Brian Welch strikes again:
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: Ned Gulley Date: 4 Nov, 2005 10:58:33 Message: 24 of 72 >> 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 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
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: Stijn Helsen Date: 4 Nov, 2005 11:10:32 Message: 25 of 72 >>> 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?
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: Great Rumpuscat Date: 4 Nov, 2005 11:18:07 Message: 26 of 72 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
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: the cyclist Date: 4 Nov, 2005 12:48:50 Message: 27 of 72 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?
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: Matthew Simoneau Date: 4 Nov, 2005 13:13:29 Message: 28 of 72 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.
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: Stijn Helsen Date: 4 Nov, 2005 16:38:32 Message: 29 of 72 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.
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: the cyclist Date: 5 Nov, 2005 09:11:59 Message: 30 of 72 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"?
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: Niilo Sirola Date: 5 Nov, 2005 09:34:15 Message: 31 of 72 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. :)
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: Stijn Helsen Date: 5 Nov, 2005 10:48:52 Message: 32 of 72 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"....??
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: Stijn Helsen Date: 5 Nov, 2005 11:05:04 Message: 33 of 72 And the last improvement of half a second (by Timothy) was done without any change in the code!!
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: Matthew Simoneau Date: 5 Nov, 2005 13:39:42 Message: 34 of 72 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:
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: Stijn Helsen Date: 5 Nov, 2005 14:22:11 Message: 35 of 72 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...
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: Matthew Simoneau Date: 5 Nov, 2005 17:59:26 Message: 36 of 72 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:   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.
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: the cyclist Date: 5 Nov, 2005 22:39:52 Message: 37 of 72 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: > > > > 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".
 Subject: MATLAB Programming Contest: November 2-9, 2005 Date: 5 Nov, 2005 22:44:45 Message: 38 of 72 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).
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: the cyclist Date: 6 Nov, 2005 00:02:15 Message: 39 of 72 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?
 Subject: MATLAB Programming Contest: November 2-9, 2005 Date: 6 Nov, 2005 00:55:48 Message: 40 of 72 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.
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: Matthew Simoneau Date: 6 Nov, 2005 01:04:24 Message: 41 of 72 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.
 Subject: MATLAB Programming Contest: November 2-9, 2005 Date: 6 Nov, 2005 01:34:41 Message: 42 of 72 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!
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: Stijn Helsen Date: 6 Nov, 2005 08:26:12 Message: 43 of 72 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......
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: Stijn Helsen Date: 6 Nov, 2005 08:38:21 Message: 44 of 72 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...))).
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: A. Nieto-Castanon Date: 6 Nov, 2005 11:52:49 Message: 45 of 72 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...))).
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: Paulo Date: 7 Nov, 2005 09:59:14 Message: 46 of 72 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.
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: the cyclist Date: 7 Nov, 2005 14:43:33 Message: 47 of 72 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.
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: Stijn Helsen Date: 7 Nov, 2005 16:45:44 Message: 48 of 72 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.
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: Loren Shure Date: 7 Nov, 2005 16:50:35 Message: 49 of 72 In article , 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
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: Matthew Simoneau Date: 7 Nov, 2005 17:47:17 Message: 50 of 72 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.
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: Tom Lemke Date: 8 Nov, 2005 02:05:41 Message: 51 of 72 Is the Midnight Madness cutoff 2005-11-08 00:00:00? -Guy Incognito
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: Stijn Helsen Date: 8 Nov, 2005 03:23:10 Message: 52 of 72 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")....
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: Tom Lemke Date: 8 Nov, 2005 03:55:35 Message: 53 of 72 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?
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: Stijn Helsen Date: 8 Nov, 2005 05:36:40 Message: 54 of 72 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").
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: gok Date: 8 Nov, 2005 15:22:52 Message: 55 of 72 I think it will be a good idea to get algorithms description authors used in their code.
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: PB Date: 8 Nov, 2005 15:58:43 Message: 56 of 72 Is is just me or is the queue stuck (or just extremely slow)? Haven´t seen any TMW-announced errors with the queue... /PB
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: Niilo Sirola Date: 9 Nov, 2005 04:33:23 Message: 57 of 72 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 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...)
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: wuzhili Date: 9 Nov, 2005 10:32:14 Message: 58 of 72 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.   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 > 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...)
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: Volkan Date: 9 Nov, 2005 11:14:53 Message: 59 of 72 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.
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: Stijn Helsen Date: 9 Nov, 2005 12:57:08 Message: 60 of 72 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...
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: Niilo Sirola Date: 9 Nov, 2005 14:18:38 Message: 62 of 72 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...
 Subject: MATLAB Programming Contest: November 2-9, 2005 Date: 9 Nov, 2005 14:29:27 Message: 63 of 72 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...
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: Stijn Helsen Date: 10 Nov, 2005 02:08:20 Message: 64 of 72 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".
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: Hannes Naude Date: 10 Nov, 2005 06:22:36 Message: 65 of 72 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é
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: Hannes Naude Date: 10 Nov, 2005 06:25:37 Message: 66 of 72 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
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: Mihi Date: 11 Nov, 2005 18:20:55 Message: 67 of 72 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
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: Tom Lemke Date: 12 Nov, 2005 17:03:26 Message: 68 of 72 > 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...
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: Matthew Simoneau Date: 16 Nov, 2005 17:20:22 Message: 69 of 72 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:   These early stages of the contest attract the greatest number of players.
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: Tom Lemke Date: 22 Nov, 2005 08:03:22 Message: 70 of 72 Is there going to be further activity on this contest page?
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: Tom Lemke Date: 28 Nov, 2005 08:05:47 Message: 71 of 72 Tom Lemke wrote: > > > Is there going to be further activity on this contest page? I see.
 Subject: MATLAB Programming Contest: November 2-9, 2005 From: Min Poh Date: 11 Jan, 2006 17:17:12 Message: 72 of 72 To wrap up the last contest, The Sudoku Final Analysis is now available online:   Min Tom Lemke wrote: > > > Tom Lemke wrote: >> >> >> Is there going to be further activity on this contest page? > > I see.

### Everyone's Tags:

Separated by commas
Ex.: root locus, bode

### 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.