Fall 2009 MATLAB Contest, November 4th-11th
Helen Chen
Helen and the MATLAB Central Contest team
the cyclist
> I hope you are all getting ready for the Fall MATLAB Contest which starts on Wednesday around noon (Boston time). Because of your requests, we are returning to the traditional contest format. It should be fun so we hope to see you then!
>
> Helen and the MATLAB Central Contest team
Thanks in advance to the contest team, and good luck to everyone.
Helen Chen
The Fall MATLAB Contest is now officially underway.
Color Bridge is a color-flooding contest based on the
game Flood-it. As usual, we are starting out in Darkness
moving into Twilight, then Daylight. The contest will
run until next Wednesday, November 11, 2009, high noon
(Boston time).
Links to get started:
- The rules are posted at
http://www.mathworks.com/contest/flooding/rules.html
- The initial download is at http://www.mathworks.com/matlabcentral/fileexchange/25740-matlab-contest-flooding
- The newsgroup thread is http://www.mathworks.com/matlabcentral/newsreader/view_thread/264764
Best of luck to everyone! We look forward to
seeing you all online!
Helen and the MATLAB Central Contest Team
Sergey
colors = solver(A,[targetRow targetColumn])
but as
colors = solver(A,targetIndex)
is it correct?
SY
Doug Hull
Everyone,
Sorry about that. I wrote the contest code in absolute indexing, and then changed it to match the rules. I pushed the absolute indexing version accidentally. My bad.
We just modified the rules to match the contest suite as it is on the File Exchange. Looks like some of the early entries figured it out and are doing well. Use ind2sub to convert to row column if you happen to need it.
sorry,
Doug
the cyclist
Yes, definitely called with the linear index to the array, not two subscripts.
the cyclist
mavs favs
I changed , the opening line of solver as:
function colors = solver(A,[targetRow targetColumn])
Is this fine or do we need to use: function colors = solver(A,targetRowAndColumn) and then use 'ind2sub'?
mavs
mavs favs
favs
Nathan
> The A matrix is always 4x4 or it may change?
>
> favs
Have you taken a look at the supplied testsuite_sample.mat?
That .mat file has samples of different matrices (of different sizes)
as well as different locations for the target location.
I would assume that they wouldn't want you to change the solver
function. It's not hard to convert targetRowAndColumn into targetRow
and targetColumn, given the size of A.
-Nathan
the cyclist
> The A matrix is always 4x4 or it may change?
>
> favs
No, it will vary. You can type
>> load testsuite.mat
to see a list of the boards and goals in the test suite. They are stored as fields in the struct array "testsuite".
the cyclist
mavs favs
the cyclist
> How can the goals be more than 900 as is testsuite(3).goal = 2500, when the total number of elements are 900, assuming this goal value is that single targetRowAndColumn index value.
Note that testsuite(3).board is [50x50], so 2500 is the bottom right.
mavs favs
the cyclist
> Can we assume the board to be square? I mean number of rows=number of columns for all cases?
Again, you might want to look at the test suite
testsuite(8).board is 100x10
mavs favs
O right, thank you!!:)
Daniel Armyr
Mike Russell
Go Team!
Anders Skj?l
What have you come up with in the dark?
the cyclist
>
> Helen and the MATLAB Central Contest team
Looks like most of the usual suspects are here in Darkness, and a lot of unfamiliar names as well, which is great. Good luck to all.
Mike Russell
When I execute "runContest" against the example testsuite it the grader occupies 99% of the time it takes to return the result. My solver is very basic and the returned time by runcontest is ~.02 seconds.
Just wondered if others are experiencing a similar issue? Also I don't see any of the scores on the entry listing page yet?
Thanks,
MikeR
the cyclist
>
> Helen and the MATLAB Central Contest team
Ugh. All my Darkness entries shot down because I forgot that I cannot use a function from the Statistics Toolbox.
Markus Buehren
>
> Just wondered if others are experiencing a similar issue? Also I don't see any of the scores on the entry listing page yet?
The subfunction flood of function runSolutionVector.m is very slow indeed. I have uploaded a faster version on Matlab Central. I hope it will be online soon! To find it, search for the tag "flooding".
Markus
Michael Bindschadler
-Mike Bindschadler
"the cyclist" <thecy...@gmail.com> wrote in message <hcv38q$r5f$1...@fred.mathworks.com>...
Markus Buehren
Markus
Loren Shure
mb_matla...@gmxTHIS.de says...
> Grrr, and mine failed as we may not use clear!
>
> Markus
>
Reset the variable in question to [] if you are trying to reclaim
memory.
--
Loren
http://blogs.mathworks.com/loren
mavs favs
favs
Michael Bindschadler
-Mike
"Michael Bindschadler" <mikeREMOV...@gmail.com> wrote in message <hcv4hi$h08$1...@fred.mathworks.com>...
Nicholas Howe
Maybe I am confused, but I thought I had submitted an entry and saw it waiting for evaluation in the queue. But now having reloaded the full and chronological listings, I don't see it anywhere. Not even as generating an error.
I guess I'll submit it again, and hope it all works out. Could be my error somehow...
Michael Bindschadler
"Nicholas Howe" <Nik...@hotmail.com> wrote in message <hcvftb$cqo$1...@fred.mathworks.com>...
diyet
thank you..
chethan C U
> Isn't str2num allowed?
>
> favs
Use which functionName to check its root directory
Steven Lord
"chethan C U" <cheth...@gmail.com> wrote in message
news:hd1bk0$rqg$1...@fred.mathworks.com...
STR2NUM is part of MATLAB; the reason I believe it's disallowed is because,
as its documentation indicates, it calls EVAL and EVAL is on the list of
prohibited functions given at the bottom of the rules page.
http://www.mathworks.com/access/helpdesk/help/techdoc/ref/str2num.html
For example, this works and returns the handle of the line the PLOT command
created:
str2num('plot(1:10)')
I'm not certain as I haven't checked but I believe the contest machinery
should allow STR2DOUBLE, which you can use as a replacement for STR2NUM
(unless you were counting on using STR2NUM's EVAL-ing behavior, in which
case I point you to the section titled "Hacking" in the rules :)
--
Steve Lord
sl...@mathworks.com
comp.soft-sys.matlab (CSSM) FAQ: http://matlabwiki.mathworks.com/MATLAB_FAQ
the cyclist
> I hope you are all getting ready for the Fall MATLAB Contest which starts on Wednesday around noon (Boston time). Because of your requests, we are returning to the traditional contest format. It should be fun so we hope to see you then!
>
> Helen and the MATLAB Central Contest team
Glad to see the statistics page up early this contest, as I like to see it evolve.
I think it would be cool if the "results vs cpu time" were data-transformed so that the "isoscore" lines were circular arcs. I think that might give a better indication of whether results or time are driving the improvements. (Every contest I tell myself I am going to program that myself, but never have.)
Anders Skj?l
Nicholas Howe
"Markus Buehren" <mb_matla...@gmxTHIS.de> wrote in message <hcv4ec$an4$1...@fred.mathworks.com>...
Helen Chen
> Is there going to be an "Early Bird" as indicated by the submissions histogram in Statistics?
Matt just posted to the blog. Early Bird runs now to 8pm tomorrow.
Helen
Helen Chen
> Glad to see the statistics page up early this contest, as I like to see it evolve.
>
> I think it would be cool if the "results vs cpu time" were data-transformed so that the "isoscore" lines were circular arcs. I think that might give a better indication of whether results or time are driving the improvements. (Every contest I tell myself I am going to program that myself, but never have.)
Cool suggestion, we'll take a look it as a possibility for future reports.
Helen
Sergey
Look like it is 8PM today (Friday, Nov.6 ) not tomorrow
Please clarify.
SY
Helen Chen
> Please clarify.
Clarification - You are correct, sorry!
Helen
Jim
Jim
Seth Popinchalk
> How many boards must be solved in the 3 minutes? Just 1? 100? Thanks.
All entries must solve the same number of boards in the shortest amount of time possible. The number of boards is more than 1, and of sufficient size to exercise many dimensions of this challenge. (I don't know the exact number.)
Do you think knowing the number will help your entry?
Markus Buehren
Hi Nicholas,
I wanted to submit the function as a p-coded version, but this is not accepted on Matlab Central. I have resubmitted it now as an m-file. Drop me an E-mail to floo...@gmx.de and I will send the files directly to you.
Markus
Alan Chalker
score = k1*result + k2*e(k3*runtime) + k4*max(complexity-10,0) + k5*nodes
Where:
k1 = 0.01
k2 = 0.001
k3 = 1/12 (0.08333…)
k4 = 1
k5 = 0.001
The current leading entry has a time of 89s, result of 663581, cyc of 9, and nodes of 1961. Here’s a breakdown of the current tradoffs:
-cyc and score are a 1:1 ratio (i.e. each point shaved off cyc is a point shaved off the score)
-time and score are a 1:0.2 ratio
-result and score are a 1:0.01 ratio
-node and score are a 1:0.001 ratio
As is common at this point in the contest, Nick Howe's entries have already settled in just below the ‘knee’ of the time exponential curve, which is rather flat until about ~110s. However, because of results are so high right now and change quite a bit with small tweaks, I think we are going to find more payoff in trying to reduce the results by searching the boards for a bit longer, at least until the times get up around the 120s range. Unfortunately that during the various contest end times the queue is going to get very backlogged, since each entry will take several minutes to execute.
Alan Chalker
'ComplicatedMess3', submission 53910
http://www.mathworks.com/contest/flooding.cgi/view_submission.html?id=53910
Unfortunately, unlike in any of the contests since I've been doing this, the leading code is so complicated I wasn't able to fully understand or document it, even after spending several hours on it today.
Perhaps I'm just being dense lately, but I think part of the reason is there are some VERY sophisticated graph theory type calculations going on in the code, which I was having difficulty following. As a result, only about 80% of the code is documented, but that should be enough to give people a general idea of what's going on.
Interestingly enough the cyc complexity and node counts of the code are equal to or less than what we've seen in other contests, so those aren't really good measures this time around regarding the 'readability' of the code.
Hopefully this won't discourage people from participating during the rest of the contest. If anyone with a better grasp of the various code sections or graph theory is willing to pick up on commenting the code where I left off, I encourage you to!
Alan Chalker
Even though the results were the same for each running of the code, the interesting part is that the time it took to run each submission varied a lot more widely than would be expected. Here are the stats:
min 87.9155
avg 88.74906
max 89.5264
stddev 0.486613084
There wasn't any obvious correlation between the time and the order of the submission (i.e. the last code wasn't the fastest), but the fact there was a 1.6109 second difference in time between the fastest and the shortest is a bit troubling.
Put another way, the timing variation was ~2%. As mentioned in my score formula analysis message, time and score at this point are in about a 1:0.2 ratio. Thus the impact on score is about 0.322 points. As of me writing this message, the current top 10 entries on the leaderboard are separated by this value, meaning any of them could be the 'actual' best entry, it just depends on the 'luck of the draw'.
Sergey
Oliver Woodford
> Unfortunately, unlike in any of the contests since I've been doing this, the leading code is so complicated I wasn't able to fully understand or document it, even after spending several hours on it today.
>
> Perhaps I'm just being dense lately, but I think part of the reason is there are some VERY sophisticated graph theory type calculations going on in the code, which I was having difficulty following. As a result, only about 80% of the code is documented, but that should be enough to give people a general idea of what's going on.
I'm going to assume you're referring (at least in part) to my "dijkstra" function, and take that as a compliment. It's actually not that complicated, but the way I've coded (for speed and efficiency) makes it look so. It's based on the Bellman-Ford algorithm (not Dijkstra's, as I'd thought when I implemented it), so read up on that to understand what's going.
I believe that lots of further algorithmic (as opposed to parametric) improvements can be made, but I'm keeping them under my hat for the time being. Lets see if anyone can beat it with a different approach though.
Oliver
Alan Chalker
>
> I'm going to assume you're referring (at least in part) to my "dijkstra" function, and take that as a compliment. It's actually not that complicated, but the way I've coded (for speed and efficiency) makes it look so. It's based on the Bellman-Ford algorithm (not Dijkstra's, as I'd thought when I implemented it), so read up on that to understand what's going.
>
> I believe that lots of further algorithmic (as opposed to parametric) improvements can be made, but I'm keeping them under my hat for the time being. Lets see if anyone can beat it with a different approach though.
>
That function was indeed the 'straw that broke the camel's back' on my commenting attempts. And yes, I was intending to complement you and everyone else who contributed the various subfunctions that currently make up the main code base.
Thanks for the reference... the wikipedia page on Bellman-Ford indeed helps me understand a bit better what's going on, although it would still be very difficult to translate that into line-by-line comments in the code.
I look forward to whatever additional algorithmic improvements you can introduce to the competition, and hopefully they'll be easier to follow what's going on in the code;)
Markus Buehren
A little late, but here it is now:
http://www.mathworks.com/matlabcentral/fileexchange/25765
Markus
the cyclist
> I hope you are all getting ready for the Fall MATLAB Contest which starts on Wednesday around noon (Boston time). Because of your requests, we are returning to the traditional contest format. It should be fun so we hope to see you then!
>
> Helen and the MATLAB Central Contest team
So, the flood of entries (pun intended) is in for the 1000 Node Challenge. I'm interested to know if any real improvements are there, or just random hopefulness.
I have two tweaks in the queue that I believe are improvements. One is changing the class of one more variable, changing this line
>> D = uint16(A(p(r(1:ng))));
into
>> D = uint8(A(p(r(1:ng))));
I know it works on the test suite, and gives a time improvement that is well over the typical timing variability.
The second tweak is quite annoying to me. As many of you probably already know, starting with 2009b MATLAB allows a new output method, as exhibited by the line:
>> [p , ~, r] = dmperm(Q);
This is a way of ignoring the second argument of a function. Unfortunately, this new method actually seems slower, so I changed it to
>> [p , q, r] = dmperm(Q);
which gives a tiny speedup, probably NOT bigger than the variability.
Oliver Woodford
> So, the flood of entries (pun intended) is in for the 1000 Node Challenge. I'm interested to know if any real improvements are there, or just random hopefulness.
>
> I have two tweaks in the queue that I believe are improvements. One is changing the class of one more variable, changing this line
>
> >> D = uint16(A(p(r(1:ng))));
>
> into
>
> >> D = uint8(A(p(r(1:ng))));
>
> I know it works on the test suite, and gives a time improvement that is well over the typical timing variability.
Yes, that tweak will work (and speed things up), which is extremely annoying. The reason (for the benefit of everyone else) is that I have been working on some proper algorithmic improvements, and, wanting to avoid my submissions being tweaked and beaten, I submitted them, literally, at the last minute. Then the cyclist has seen my submissions and picked one that arrived at 17:59:17, applied his tweak, and resubmitted at 17:59:45. My only hope is that that particular attempt now times out (I submitted several, each one slower than the last). If it happens to be the winning entry I will be extremely cheesed off.
I think that entries should only be viewable once they've been scored, or perhaps after a 5 minute delay, to avoid this chicanery in future.
Oliver
mavs favs
Oleg Komarov
> Just wondering if anybody knows when will the Late-Stage Twilight begin?
example:
lets assume the goal is in 9.
1 4 7
2 5 8
3 6 9
then all the possible paths here are
2 3 6 9
2 5 6 9
2 5 8 9
4 5 6 9
4 5 8 9
4 7 8 9
i didnt find any way to iterate this path-research but i do believe this could be a nice algorithm.
once all possible paths are found, those which contains a 0 are to be eliminated. Then minimizing the cost of the path should do the trick (at least the first part of the total cost formula).
Oliver Woodford
> I have been working on some proper algorithmic improvements...
Ha! I failed miserably. Gotten by the `knee point'.
Oliver Woodford
> I was wondering if it could be possible to calculate all the possible paths constraining the movements to right and down.
> example:
> lets assume the goal is in 9.
> 1 4 7
> 2 5 8
> 3 6 9
> then all the possible paths here are
> 2 3 6 9
> 2 5 6 9
> 2 5 8 9
> 4 5 6 9
> 4 5 8 9
> 4 7 8 9
> i didnt find any way to iterate this path-research but i do believe this could be a nice algorithm.
> once all possible paths are found, those which contains a 0 are to be eliminated. Then minimizing the cost of the path should do the trick (at least the first part of the total cost formula).
It's similar in spirit to trying every possible sequence of colours. Optimal: yes. Efficient: no. Consider you'd be following about 2^(h + w - 1) paths.
mavs favs
To Oleg, Yes, that could be done and its very inefficient and would easily run for more than 3 minutes for a 10x10 block with target at end. I made such code that way, would upload maybe soon.
Oleg Komarov
To mavs:
> To Oleg, Yes, that could be done and its very inefficient and would easily run for more than > 3 minutes for a 10x10 block with target at end. I made such code that way, would upload
> maybe soon.
A similar approach is used by nchoosek and it really runs slow also for small matrices.
But constraining the moves should yield a faster (greatly faster) solution.
nchoosek(1:9,4) lists more than 100 paths while those acceptable (according to the constraint) is just 6.
Oleg
Oliver Woodford
> To Oliver:
> > It's similar in spirit to trying every possible sequence of colours. Optimal: yes. Efficient: no. > Consider you'd be following about 2^(h + w - 1) paths.
> if h and w stand for matrix dimensions in a 3x3 matrix i listed just 6 paths (because the number of moves is limited to right or down)
Exactly. So on a 30x30 problem you'll need to try about 7.8722e+261 paths. In 180s? Not possible.
Oleg Komarov
Oliver Woodford
> > Exactly. So on a 30x30 problem you'll need to try about 7.8722e+261 paths. In 180s? Not possible.
> but if u constrain the moves the paths reduce significantly and i liked to verify if the 180s barrier is sufficient
I am constraining the moves to right and down, my friend. The equation I gave takes those constraints into account. What are the other constraints?
Oleg Komarov
but in my example there are just 6 paths.
i start from position 1 and end in position 9.
Oliver Woodford
> > I am constraining the moves to right and down, my friend. The equation I gave takes those constraints into account. What are the other constraints?
> 3x3 matrix = 32 paths
> but in my example there are just 6 paths.
> i start from position 1 and end in position 9.
Sorry. You're right - my equation is incorrect. It should be 2^min(h,w). So with a 30x30 block you'll only need to search 1 billion paths.
Alan Chalker
This is an interesting mental exercise. Oliver, I don't think your latest equation is correct either. Let's step through some simple examples:
Constraints are:
Always start in 1,1
always end in h,w
only go 'down' or 'right'
Thus:
2x2 block = 2 paths
2x3 block = 3 paths
2x4 block = 4 paths
3x3 block = 6 paths
3x4 block = 10 paths
I'm not sure what the formula is, but it's not 2^min(h,w). Somebody could probably derive it easily.
Of course I'd also like to point out that this general approach wouldn't work as a solver because of the presence of walls on the board. If you look at the test suite (board 18 for example I think), some of the walls force the resulting path into a zig-zag pattern, meaning you must sometimes go up or left (which returns us to the original very large calculations a couple postings up).
Oleg Komarov
> 2x2 block = 2 paths
> 2x3 block = 3 paths
> 2x4 block = 4 paths
> 3x3 block = 6 paths
> 3x4 block = 10 paths
>
> I'm not sure what the formula is, but it's not 2^min(h,w). Somebody could probably derive it easily.
>
> Of course I'd also like to point out that this general approach wouldn't work as a solver because of the presence of walls on the board. If you look at the test suite (board 18 for example I think), some of the walls force the resulting path into a zig-zag pattern, meaning you must sometimes go up or left (which returns us to the original very large calculations a couple postings up).
I tried to derive this formula but couldn't figure it out.
For the zig-zag pattern it could have been solved with the same approach by segmenting the original board into suboard and reversing the constraints on the moves!
But these are all thoughts that don't have a practical application right now...since the contest is at the end.
oleg
Oleg Komarov
http://mathforum.org/library/drmath/view/66728.html
Also in this thread i was discussing the same subject.
Apparently, bruno's function does search all the possible paths...
http://www.mathworks.com/matlabcentral/newsreader/view_thread/265544#693883
but it runs slow...
the cyclist
> I hope you are all getting ready for the Fall MATLAB Contest which starts on Wednesday around noon (Boston time). Because of your requests, we are returning to the traditional contest format. It should be fun so we hope to see you then!
>
> Helen and the MATLAB Central Contest team
Well, it's always fun to have the top entry when the queue closes, but I know that approximately 100 entries will pass it. Good luck to everyone.
the cyclist
> I hope you are all getting ready for the Fall MATLAB Contest which starts on Wednesday around noon (Boston time). Because of your requests, we are returning to the traditional contest format. It should be fun so we hope to see you then!
>
> Helen and the MATLAB Central Contest team
Well, if Alan doesn't win, at least he made an impressive surge for most entries.
Speaking of copious entries, where is David Jones?
Alan Chalker
1. Thanks again to the contest team for an exciting event! I always look forward to this time of the year and have lots of fun.
2. Before we begin the inevitable conversation about 'queue spamming' at the end of the contest, I'd like to point everyone to the newsgroup thread from last year, where we hashed out many of the same issues: http://www.mathworks.com/matlabcentral/newsreader/view_thread/238684
3. For those of you in the US, be sure to thank a veteran today!
Oliver Woodford
> I'm not sure what the formula is, but it's not 2^min(h,w). Somebody could probably derive it easily.
"Oleg Komarov" wrote:
> Here's the formula (thank to Steven Lord):
> http://mathforum.org/library/drmath/view/66728.html
Ah, yes. Always happy to be corrected :)
Alan Chalker
So the result for a 30x30 board is approximately 3.0067e+016. The exact formula I used was: nchoosek((row+col-2),(row-1)).
Oliver Woodford
This has been my first contest and it's been fun - thanks to the contest team for putting it on.
Mike Russell
> Wow, that was a flood and a half! Best of luck to everyone.
>
> This has been my first contest and it's been fun - thanks to the contest team for putting it on.
Oliver I just quickly examined your Bellman-Ford entries, very impressive. Without a single rand function call you appear to have locked in some winning entry's. If you do not take away the main prize I believe Matlab should honor you with an award for putting the foundation in place for almost every entry.
Also I really wish the Mathworks crew had implemented the feedback from last years contest regarding blackout periods, entry captcha's, etc. This contest did not appear to be any different than those in the past, possibly less involvement of the mathwork team than ever in the past. Regardless I still enjoy the contest offering and am very pleased with this year's problem.
Cheer!
MikeR
Anders Skj?l
http://hmatime.files.wordpress.com/2009/07/trump-youre-fired1.jpg
(Oliver stays.)
Amitabh Verma
I still don't get it why >79 works better than ==80 :P
mavs favs
Alan Chalker
> Since early twilight we (well, you mostly) improved the result by merely 2%. Two percent in a week!
This observation made me curious, so I went and checked previous contests. Here's the total % improvement in score during both twilight and daylight for some past contests:
Flooding: 4.02% / 2.03% (as of right now.. queue still being processed)
Wiring: 1.56% / 6.42%
Splicing: 5.93% / 22.11%
Solitaire: 1.96% / 6.02%
Blackbox: 9.20% / 10.00%
Blockbuster: 5.08% / 13.22%
This contest isn't really that far off from the wiring or solitaire ones. The major difference is here there were major improvements during twilight, whereas there the improvements came during daylight. We can all thank Oliver for his wonderful (and difficult to decipher;) path finding algorithm for that!
Alfonso Nieto-Castanon
Could you please let me know how your entry A27 differs from lasttry01? Just curious what your contribution was.
I also enjoyed the contest and the problem and would like to thank the matlab team for making it happen!
Alfonso
Darren Rowland
http://matlabcentral.uservoice.com/pages/6137-matlab-contest
for ideas on how to improve the next contest.
The current most widely supported suggestions in order are
1 - Prohibit the use of rand functions
2 - Require a CAPTCHA to be entered when submitting an entry
3 - Process one queue entry per contestant at a time
4 - Re-evaluate the scores for the leading entries at the end of the contest and re-rank them using an average result
5 - Show pass/fail indicator for code during darkness
6 - Leave the queue always in darkness
I think 5 and 6 are essential modifications. Further to 5, I think the time taken by passing entries should be shown, in order to establish a time comparison between the contest machine and the contestants. Code which ran through the testsuite in ~60 secs on my machine timed out on the contest machine.
WRT 4, I think this is a reasonable idea but the problem set should be different to the normal set used during the contest. This will help to eliminate the 'lucky tweaking' effect.
2 and 3 attempt to tackle the issue of queue bombardment, but at different stages. 3 is a good idea, so long as a unique identifier can be attributed to each contestant. I would not be opposed to trialling a CAPTCHA on the next contest, just to see the difference it makes.
With point 1, sometimes random numbers are required, given the nature of the contest. The Army Ants contest without random numbers would be impossible, therefore I don't think this should be instituted.
Darren
Alfonso Nieto-Castanon
> Hi MikeR
> Could you please let me know how your entry A27 differs from lasttry01? Just curious what your contribution was.
After examining some of you other entries I see that you appear to have made valuable contributions in the rest of your entries, and (please correct me if I am wrong) that this is the only case where you appear to have simply copied without any modification an entry from the queue and submitted it as your own, so I imagine this was likely an honest mistake. In any way this is just fine and perfectly within the contest rules (and let me be the first to congratulate you on your good eye/luck!). If anything I guess I would really like to see point (6) being implemented in future contests to recover some of the best thrills of participating.
Cheers!
(see http://matlabcentral.uservoice.com/pages/6137-matlab-contest for this an other suggestions to improve future contests)
Alfonso
Darren Rowland
Also well done to the contest team for hosting another enjoyable contest.
mavs favs
With no intentions of offending anyone, I actually thought there would be some Late-Stage Twilight thing when the scores &/or code would not be shown. Maybe something like that can be made in future contests.
Mavs
Alan Chalker
> "Alfonso Nieto-Castanon" <alf...@gmail.com> wrote in message <hdft14$89a$1...@fred.mathworks.com>...
> > Hi MikeR
> > Could you please let me know how your entry A27 differs from lasttry01? Just curious what your contribution was.
>
>
There isn't any difference between the 2 codes. As many people do, MikeR just randomly resubmitted your code and lucked out with a timing variation. I believe there is some precedence from previous contests that you should be declared the grand winner since your version was submitted first.
Alan Chalker
> I think 5 and 6 are essential modifications. Further to 5, I think the time taken by passing entries should be shown, in order to establish a time comparison between the contest machine and the contestants. Code which ran through the testsuite in ~60 secs on my machine timed out on the contest machine.
>
Showing the time would defeat the whole purpose of darkness. Twilight is the period when you are supposed to be getting a little bit of feedback. If we show anything other than pass/fail it opens the door for people to try to 'extract' information about what's going on. The whole purpose of me proposing item 5 was because a lot of people get caught by the file filter before their entries even get a chance to run, and those are simple, honest mistakes that shouldn't be penalized at that stage.
Sergey
I believe he has to be declared the winner of the contest.
SY (Sergey)
Mike Russell
I am sorry for the late response I've been quite busy with work this morning. I did in fact just resubmit Alfonso's code, I first checked it and determined there was a rand function call and figured that a re-run of the same code may result in a different result. I was quite surprised this morning when I checked the contest page and saw the final results, and at the same time felt sore that I had taken #1 by simple code resubmission.
I had no part in implementing his changes and as such I agree that Alfonso should be declared the overall winner of this year's contest. His late entry that ran multiple solvers choosing the lowest scoring result per board was a fantastic addition.
I have added my votes on the UserVoice forum for things like removal of the rand functions, and a blackout during the final stage of the contest. I very much enjoy reading and running entries from some of the very bright entrants in the contest (SY, Nick Howe, Yi Cao, Alfonso, Gwendolyn Fish, Oliver Woodford, the list goes on and on). I play by the rules during the contest but I believe the rules need to be updated to really allow some of these entrants to gain the recognition they deserve.
Again thanks to all for making this another great contest period, and I hope all will come back to play again next time this is offered.
Cheer!
MikeR
Nicholas Howe
Thank you to the people at Mathworks, as always, for taking the time to run the contest. Without you none of us would be able to have this fun.
A final note to the person who complained about the small decrease in the overall score over the course of the contest: the score includes a built-in "floor" which it is easy to prove no algorithm can beat. (At solution, every matrix element can be no lower than the lesser of its value or the goal value.) On the test suite the floor is well over 480,000. So as a percentage of the achievable score, the improvement is actually larger than it appears.
Markus Buehren
> the rand functions, and a blackout during the final stage of the contest.
Hehe, I had a blackout while programming during twilight, but no one wants to make it a contest rule to have one :o) I guess you refer to a second darkness phase!
Markus
Sergey
It is even more interesting:
“35 red balloons?” by the cyclist was submitted at 11:14 and was at the top for little while.
Your “Balloon Tilt 3” was based on it and was submitted at 11:56:24
My “LastCatStadning 99” was based on your code and was submitted at 11:58:41
After that the cyclist picked up my code and resubmited it with some tweaks (“LCS99”) at 11:59:24.
(Any way, my other submissions, based directly on “35 red balloons?” are close to the top too.)
"Nicholas Howe" <Nik...@hotmail.com> wrote in message <hdh950$gt7$1...@fred.mathworks.com>...
Oliver Woodford
Ned Gulley
We all know that low complexity, by itself, does not guarantee readability. But on balance do you think it's a useful addition to the score? Do you ever pay attention (or did you in previous contests) the complexity number when you're looking to modify someone else's entry?
Ned.
Oliver Woodford
> Bravo, Alfonso! That was a very impressive score.
Two things impress me a great deal:
1) That Alfonso's winning entry has a board score only 50 points higher than the lowest score (also his own).
2) That the next best board score from another conestant (ignoring MikeR's resubmission) was 2758 points higher (if I found the next lowest correctly).
In the context of the incremental improvements that had been made over the last day or two of the competition that is a huge margin of victory. This graph sums it up rather well:
http://www.mathworks.com/contest/flooding/scoreStair.png
Sergey
It, actually, reduces score by ~ 5000 points, (next best submission improves score by ~900 only).
However you do not want to read too much by comparing with last two days of competition, because during that time participants usually tend to keep new ideas for final submissions.
"Oliver Woodford" <o.j.woo...@cantab.net> wrote in message <hdhg9n$kk5$1...@fred.mathworks.com>...
Doug Hull
When I was making the testsuite, I had 12 different styles of boards. I am curious if the little "gotchas" I put in there were effective. Please comment on them:
1.) 50 x 50
[0:6 80] are the elements of the board
Random distribution
Goal is high value (6) in far corner
The high value 80's significantly change the motivation to gobble them up.
2.) 40 x 40
[1 1 1 1 1 1 1 1 1 2 2 3 4 5 6 6 6 6 6] are the elements of the board
Random distribution
Goal is low value (1) in bottom middle
Because there are so many of the goal value, it will be a challenge to NOT hit the goal before all the high value pixels are eaten.
3.) 100 x 10
[1: 30] are the elements of the board
random distribution
Goal is mid value (15) in lower left corner
Because there are so many different values, there will rarely be clumps of the same value connected.
4.) 30 x 30
[1 1 1 1 2 2 2 3 3 3 4 5 6] are the elements of the board
random distribution
Goal is mid value (3) in lower edge 2/3 over from left
Lots of islands of low values to avoid
5.) 20 x 100 - Bisected board made of
Left: [1 1 1 1 3 3 3 3 5 5 5 5 7]
Right: [2 2 2 2 4 4 4 4 6 6 6 6 8]
Random distrobution
Goal is mid value (3) in lower right of board.
The two boards are really independent.
6.) 30 x 30
[1 1 2 3 4 5 6] are the elements of the board
random distribution
Goal is mid value (4) in lower right of board.
The goal is surrounded by 1's. You must use a 1 at the end of the solution, so there is no reason to try and leave ones for a better score.
7.) Same as above except the start is also surrounded by 2's. This becomes irrelevant after first move, but was hoping to catch people that looked for a path that avoided a given number!
8.) The big deal on this board was that there was a forced sequence at the end of the board. If the solution exposed the same sequence that lead to a huge pool of 1's, the score would suffer. Made it too easy to avoid this trap. Should have made it more tempting by leaving a 100 point block in there or something...
9.) Serpentine board. Big long path
10.) Made a short path (three steps) to get to goal. The second step touched off a huge pool of the same number. Sometimes this number was hig value, sometimes low value. This defeats pure brushfire algorithms that would take the short path without noting the cost. (My test solver had been brushfire- slow, but sure. Good to make sure all these were solvable.)
11.) Four quadrant board. Upper right held many high value pixels and walls. Lower left held only two low value colors. It was faster to go through the lower left, but more high value pixels were in upper right.
12.) random board with blurring. Goal value could be high or low. Because of edge effects, for high value goals, solutions often hugged the walls.
Please comment on how these features changed the solver, which caused the most problems, or were even noticed!
Thanks,
Doug
Nicholas Howe
Ned: I don't find cyclomatic complexity useful at all. If anything it is a detriment; in previous contests where the complexity was above 10, tweakers could reduce it by various tricks that only made the code more complicated.
Now, a suggestion of my own for future contests, if the kind folks at Mathworks are willing to listen. In thinking back over the contests I have enjoyed the most, they all involved solving a puzzle with limited information. In all contests the official test suite remains unknown to the programmers, but in some contests (like this one) the solver routine has access to all the information about the problem. In other previous contests (Ants, BlackBox, etc.) the solver does not have complete information, and has to decide what to do anyway. Looking back, I have found this makes the problem especially interesting. So, to the extent that you have a choice, I vote in favor of more partial-information problems. (I don't even know how you keep coming up with great problems year after year, but kudos to the people who do it!)
Steve Eddins
> [snip]
> Ned: I don't find cyclomatic complexity useful at all. If anything
> it is a detriment; in previous contests where the complexity was
> above 10, tweakers could reduce it by various tricks that only made
> the code more complicated.
I personally rely on the complexity metric in my code and find it very
useful as a tool that helps me produce more readable and maintainable
code. Most of the other members of my team use it that way as well. I
should note that I rarely have to measure it explicitly anymore, because
I'm now in the habit of writing many short, mostly straight-line
functions. I can see at a glance if the metric for a function is over 10.
However, I think the metric only helps to produce more readable code IF
that's the coder's purpose.
If the coder's goal is simply to reduce the metric below 10, as may be
the case in the contest, then I imagine it's quite possible to get a
result that's less readable, not more.
To put it another way ... I believe that a high complexity metric
correlates quite well with code that is a maintenance nightmare.
Therefore it's a "bad code smell." But it's quite possible to have
low-complexity-metric code that is a maintenance nightmare as well.
---
Steve Eddins
http://blogs.mathworks.com/steve/
Sergey
I would consider “last second code modification” as a sign of respect
(the cyclist always picks up one or two of my submissions ;) )
I absolutely agree with you about preferred type of the puzzle. For puzzle with known score one can, practically, predict how contest will develop:
Phase one – after twilight best code will be optimized time-vise.
Phase two – fast and very random solution will be added to the mix.
Phase three- massive “optimization” of random parameters will take significant amount of attention, overfitting test set. That will make it very difficult to introduce small but meaningful improvements.
Phase three and half – more solvers or weighting parameters will be added (or not) to deal with specific cases
Phase four – contest winner will smartly incorporate one more solver into the mix
Significant part of phases two-four will be based on score calculating and choosing best solution.
About complexity: I am paying attention to it during contest (not in real life). One on my submissions (leading for just 30 min) was deliberate “simplification” of my previous submission (from complexity 15 to 10). However, I do not think it improves “readability” of the code.
"Nicholas Howe" <Nik...@hotmail.com> wrote in message <hdhqc8$lfa$1...@fred.mathworks.com>...
Darren Rowland
> Showing the time would defeat the whole purpose of darkness. Twilight is the period when you are supposed to be getting a little bit of feedback. If we show anything other than pass/fail it opens the door for people to try to 'extract' information about what's going on. The whole purpose of me proposing item 5 was because a lot of people get caught by the file filter before their entries even get a chance to run, and those are simple, honest mistakes that shouldn't be penalized at that stage.
I agree with your position now Alan! The times should be hidden.
What could be provided instead is a benchmarking routine, nothing too complicated, with reported timings for the contest machine. If the time to execute on the contest machine is 30 secs and my computer completes the benchmark in 10 secs then I know -roughly- how long a particular entry should take.
I recall that the specifications of the contest machine used to be provided (I didn't notice if they were this time), so this would not be against the spirit of the competition. But what do others think?
With regards to the cyc. complexity I don't think it has much influence on making the code more understandable. Without Alan's midcontest analysis most of us would not have known what the leading entries were doing. And if Oliver had deliberately obfuscated his code there would be an even smaller number of people who could build upon its success.
Finally to Doug, I noticed most of the different board types. The large snaking wall boards were a particularly devious choice.
Magnus Sch?fer
> I hope you are all getting ready for the Fall MATLAB Contest which starts on Wednesday around noon (Boston time). Because of your requests, we are returning to the traditional contest format. It should be fun so we hope to see you then!
>
> Helen and the MATLAB Central Contest team
A big thanks to the MATLAB Contest team for this entertaining contest.
Would it be big problem to keep the contest running (with a seperate top20 maybe) until the next contest starts? No prizes, no glory, just to play around with the task a little more. :)
Bye,
Magnus
Doug Hull
Why were the snakey ones devious? Simply because they were so long? Would an equivalent length long skinny board been the same, or was it the fact that paths were running parallel to one another?
Just curious so Lucio and I can remain ever devious in future contests. Glad to hear about the "hidden knowledge" aspect. We have a few ways of classifying problems (poll and response, head to head, etc) I am not sure hidden knowledge qwas one we specifically called out.
Doug