Thread Subject:

Fall 2009 MATLAB Contest, November 4th-11th

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

"Helen Chen" <helen.chen@mathworks.com> wrote in message <hcmvti$4je$1@fred.mathworks.com>...
> 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.

Hello Community Members -

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

It looks like solver function is called not as

colors = solver(A,[targetRow targetColumn])

but as

colors = solver(A,targetIndex)

is it correct?

SY

"Sergey" <ivssnn@yahoo.com> wrote in message <hcshmq$n7a$1@fred.mathworks.com>...
> It looks like solver function is called not as
>
> colors = solver(A,[targetRow targetColumn])
>
> but as
>
> colors = solver(A,targetIndex)
>
> is it correct?
>
> SY

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

"Sergey" <ivssnn@yahoo.com> wrote in message <hcshmq$n7a$1@fred.mathworks.com>...
> It looks like solver function is called not as
>
> colors = solver(A,[targetRow targetColumn])
>
> but as
>
> colors = solver(A,targetIndex)
>
> is it correct?
>
> SY

Yes, definitely called with the linear index to the array, not two subscripts.

the cyclist

"Doug Hull" <hull@mathworks.SPAMPROOFcom> wrote in message <hcsiie$guh$1@fred.mathworks.com>...
> "Sergey" <ivssnn@yahoo.com> wrote in message <hcshmq$n7a$1@fred.mathworks.com>...
> > It looks like solver function is called not as
> >
> > colors = solver(A,[targetRow targetColumn])
> >
> > but as
> >
> > colors = solver(A,targetIndex)
> >
> > is it correct?
> >
> > SY
>
> 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

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

The A matrix is always 4x4 or it may change?

favs

On Nov 4, 11:52 am, "mavs favs" <devroym...@gmail.com> wrote:
> 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

"mavs favs" <devroymato@gmail.com> wrote in message <hcsm13$omg$1@fred.mathworks.com>...
> 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

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.

"mavs favs" <devroymato@gmail.com> wrote in message <hcso4i$8kc$1@fred.mathworks.com>...
> 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.

Can we assume the board to be square? I mean number of rows=number of columns for all cases?

"mavs favs" <devroymato@gmail.com> wrote in message <hcssh8$do1$1@fred.mathworks.com>...
> 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

"the cyclist" <thecyclist@gmail.com> wrote in message <hcst9j$1lm$1@fred.mathworks.com>...
> "mavs favs" <devroymato@gmail.com> wrote in message <hcssh8$do1$1@fred.mathworks.com>...
> > 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

O right, thank you!!:)

Don't have time to actually write an entry here, but in the community spirit I'll share my very first thought, and that is to use a variant of the A* algorithm for this..... Don't know it if it is a good idea, but the challenge looks like a variant of the school-book example for path-finding.

I am excited to see what the community comes up with for algorithm solutions. I quickly scanned the web yesterday after the contest began and found solutions using tree-search algorithms. I expect many folks have already submitted entries with some type of search algorithm, I wouldn't be surprised if someone has already put in a exceptional entry during darkness.

Go Team!

Let there be twilight!

What have you come up with in the dark?

"Helen Chen" <helen.chen@mathworks.com> wrote in message <hcmvti$4je$1@fred.mathworks.com>...
> 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

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.

Does the "validateSolutionVector" function run very slow for others?

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

"Helen Chen" <helen.chen@mathworks.com> wrote in message <hcmvti$4je$1@fred.mathworks.com>...
> 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

Ugh. All my Darkness entries shot down because I forgot that I cannot use a function from the Statistics Toolbox.

> 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?

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

I have also had most of my entries shot down, I think because I must have used a banned function, but I have no idea what it might be, and the error message shown is not too helpful. It just says "Error using ==> filefilt at 125 The functions I...". I promise I'm not up to anything nefarious :)

-Mike Bindschadler


"the cyclist" <thecyclist@gmail.com> wrote in message <hcv38q$r5f$1@fred.mathworks.com>...
> "Helen Chen" <helen.chen@mathworks.com> wrote in message <hcmvti$4je$1@fred.mathworks.com>...
> > 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
>
> Ugh. All my Darkness entries shot down because I forgot that I cannot use a function from the Statistics Toolbox.

Grrr, and mine failed as we may not use clear!

Markus

In article <hcv4no$sl2$1@fred.mathworks.com>,
mb_matlab.REMOVE@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

Isn't str2num allowed?

favs

I found my problem. I had just copied over some of the grading functions supplied with the contest, and they contained graphics commands. These commands would never have been executed, but their presence was enough to disqualify my entries...

-Mike

"Michael Bindschadler" <mikeREMOVETHISbind@gmail.com> wrote in message <hcv4hi$h08$1@fred.mathworks.com>...
> I have also had most of my entries shot down, I think because I must have used a banned function, but I have no idea what it might be, and the error message shown is not too helpful. It just says "Error using ==> filefilt at 125 The functions I...". I promise I'm not up to anything nefarious :)
>
> -Mike Bindschadler
>
>
> "the cyclist" <thecyclist@gmail.com> wrote in message <hcv38q$r5f$1@fred.mathworks.com>...
> > "Helen Chen" <helen.chen@mathworks.com> wrote in message <hcmvti$4je$1@fred.mathworks.com>...
> > > 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
> >
> > Ugh. All my Darkness entries shot down because I forgot that I cannot use a function from the Statistics Toolbox.

Is there a problem with the queue?

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

I think what's going on is that they're updating the queue and rankings only every 20 min. I had one of mine disappear for a while before it appeared in the rankings, but it did show up.

"Nicholas Howe" <NikHow@hotmail.com> wrote in message <hcvftb$cqo$1@fred.mathworks.com>...
> Is there a problem with the queue?
>
> 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" <mikeREMOVETHISbind@gmail.com> wrote in message <hcvo3q$7nm$1@fred.mathworks.com>...
> I think what's going on is that they're updating the queue and rankings only every 20 min. I had one of mine disappear for a while before it appeared in the rankings, but it did show up.
>
> "Nicholas Howe" <NikHow@hotmail.com> wrote in message <hcvftb$cqo$1@fred.mathworks.com>...
> > Is there a problem with the queue?
> >
> > 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...

thank you..

"mavs favs" <devroymato@gmail.com> wrote in message <hcvbru$rkc$1@fred.mathworks.com>...
> Isn't str2num allowed?
>
> favs


Use which functionName to check its root directory

"chethan C U" <chethan.cu@gmail.com> wrote in message
news:hd1bk0$rqg$1@fred.mathworks.com...
> "mavs favs" <devroymato@gmail.com> wrote in message
> <hcvbru$rkc$1@fred.mathworks.com>...
>> Isn't str2num allowed?
>>
>> favs
>
>
> Use which functionName to check its root directory

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
slord@mathworks.com
comp.soft-sys.matlab (CSSM) FAQ: http://matlabwiki.mathworks.com/MATLAB_FAQ

"Helen Chen" <helen.chen@mathworks.com> wrote in message <hcmvti$4je$1@fred.mathworks.com>...
> 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.)

Is there going to be an "Early Bird" as indicated by the submissions histogram in Statistics?

I don't see Markus's file on the file exchange. Has it not been approved yet? I know I could write my own, but I am too lazy to do it right. :-)

"Markus Buehren" <mb_matlab.REMOVE@gmxTHIS.de> wrote in message <hcv4ec$an4$1@fred.mathworks.com>...
> 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

"Anders Skj?l" <askjal.no.spam.no@homail.com> wrote in message <hd1rq6$3d4$1@fred.mathworks.com>...
> 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

"the cyclist" <thecyclist@gmail.com> wrote in message <hd1pef$6f9$1@fred.mathworks.com>...
> 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

"Helen Chen" <hhchenma@hotmail.com> wrote in message <hd1tuq$gec$1@fred.mathworks.com>...
> "Anders Skj?l" <askjal.no.spam.no@homail.com> wrote in message <hd1rq6$3d4$1@fred.mathworks.com>...
> > 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

Look like it is 8PM today (Friday, Nov.6 ) not tomorrow
Please clarify.

SY

"Sergey" <ivssnn@yahoo.com> wrote in message
> Look like it is 8PM today (Friday, Nov.6 ) not tomorrow
> Please clarify.

Clarification - You are correct, sorry!

Helen

How many boards must be solved in the 3 minute period. Just one board? 100? Thanks.

How many boards must be solved in the 3 minutes? Just 1? 100? Thanks.

"Jim" <jah104@pitt.com> wrote in message <hd2bpc$pjg$1@fred.mathworks.com>...
> 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?

> I don't see Markus's file on the file exchange. Has it not been approved yet? I know I could write my own, but I am too lazy to do it right. :-)

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 flooding@gmx.de and I will send the files directly to you.

Markus

I have been able to figure out the scoring formula and am posting it here as I traditionally do. As usual, it’s very similar to the recent contests:

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

Where:

k1 = 0.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.

As I traditionally do about this time in the contest, I've submitted a heavily commented version of the code, which happens to currently be at the top of the leaderboard:
'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!

Early Sat. morning EST I accidentally submitted the same code (RandSeed) 15 times in a row, but got some interesting data out of it. The queue was completely empty at the time I submitted the code, and it filled up over a period of about 3 minutes with the submissions. It took about 40 mins for the system to run through all the submission. I assume the machine load was rather constant during the time, since nobody else was submitting code or likely viewing the queue.

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

Is Sunday Push running right now?

"Alan Chalker" wrote:
> 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

"Oliver Woodford" <o.j.woodford.98@cantab.net> wrote in message <hd7f4r$gi4$1@fred.mathworks.com>...
>
> 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;)

> I don't see Markus's file on the file exchange. Has it not been approved yet? I know I could write my own, but I am too lazy to do it right. :-)

A little late, but here it is now:

http://www.mathworks.com/matlabcentral/fileexchange/25765

Markus

"Helen Chen" <helen.chen@mathworks.com> wrote in message <hcmvti$4je$1@fred.mathworks.com>...
> 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.

"the cyclist" wrote:
> 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

Just wondering if anybody knows when will the Late-Stage Twilight begin?

"mavs favs" <devroymato@gmail.com> wrote in message <hddpp7$e42$1@fred.mathworks.com>...
> Just wondering if anybody knows when will the Late-Stage Twilight begin?
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).

"Oliver Woodford" wrote:
> I have been working on some proper algorithmic improvements...

Ha! I failed miserably. Gotten by the `knee point'.

"Oleg Komarov" wrote:
> 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.

"Oliver Woodford" <o.j.woodford.98@cantab.net> wrote in message <hde3hl$fpd$1@fred.mathworks.com>...
> "Oleg Komarov" wrote:
> > 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.

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.

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)

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

"Oleg Komarov" wrote:
> 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.

"Oliver Woodford" <o.j.woodford.98@cantab.net> wrote in message <hdeaq7$jpa$1@fred.mathworks.com>...
> "Oleg Komarov" wrote:
> > 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.
but if u constrain the moves the paths reduce significantly and i liked to verify if the 180s barrier is sufficient

"Oleg Komarov" wrote:
> > 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?

"Oliver Woodford" <o.j.woodford.98@cantab.net> wrote in message <hdedpr$muo$1@fred.mathworks.com>...
> "Oleg Komarov" wrote:
> > > 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?
3x3 matrix = 32 paths
but in my example there are just 6 paths.
i start from position 1 and end in position 9.

"Oleg Komarov" wrote:
> > 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.

"Oliver Woodford" <o.j.woodford.98@cantab.net> wrote in message <hdeml1$cmv$1@fred.mathworks.com>...
> "Oleg Komarov" wrote:
> > > 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.

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

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

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

> I tried to derive this formula but couldn't figure it out.
Here's the formula (thank to Steven Lord):
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...

"Helen Chen" <helen.chen@mathworks.com> wrote in message <hcmvti$4je$1@fred.mathworks.com>...
> 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.

"Helen Chen" <helen.chen@mathworks.com> wrote in message <hcmvti$4je$1@fred.mathworks.com>...
> 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?

A couple quick comments for everyone:

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!

"Alan Chalker" wrote:
> 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 :)

"Oliver Woodford" <o.j.woodford.98@cantab.net> wrote in message <hderka$pac$1@fred.mathworks.com>...
> "Alan Chalker" wrote:
> > 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 :)

So the result for a 30x30 board is approximately 3.0067e+016. The exact formula I used was: nchoosek((row+col-2),(row-1)).

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 Woodford" <o.j.woodford.98@cantab.net> wrote in message <hdesgf$jqd$1@fred.mathworks.com>...
> 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

Since early twilight we (well, you mostly) improved the result by merely 2%. Two percent in a week!
http://hmatime.files.wordpress.com/2009/07/trump-youre-fired1.jpg
(Oliver stays.)

Thanks MATLAB ! This was my first and really fun.

 I still don't get it why >79 works better than ==80 :P

My first MATLAB contest it was and was great to see people really helping out each others even though it's a contest, really applaudable and thanks to MATLAB too to provide one more interesting board game thing (no sarcasm, mean it really). Hungry now, take care all :).

"Anders Skj?l" <askjal.no.spam.no@homail.com> wrote in message <hdf7ko$pau$1@fred.mathworks.com>...
> 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!

Hi MikeR
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

For those who may not be aware, there is a suggestion page at
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" <alfnie@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.

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

Congratulations to Mike and Alfonso for finishing at the pointy end of the contest.

Also well done to the contest team for hosting another enjoyable contest.

"Alfonso Nieto-Castanon" <alfnie@gmail.com> wrote in message <hdgbq2$6ea$1@fred.mathworks.com>...
> "Alfonso Nieto-Castanon" <alfnie@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.
>
> 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

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

"Alfonso Nieto-Castanon" <alfnie@gmail.com> wrote in message <hdgbq2$6ea$1@fred.mathworks.com>...
> "Alfonso Nieto-Castanon" <alfnie@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.

"Darren Rowland" <darrenjremovethisrowland@hotmail.com> wrote in message <hdg29s$pvr$1@fred.mathworks.com>...

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

Congratulations to Alfonso for developing winning code.
I believe he has to be declared the winner of the contest.

SY (Sergey)

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

All,

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

I also want to congratulate Alfonso, who appears to have stepped in at the last minute with brand-new code to win the grand prize. Well done! I'm pleased to see that some of my last-minute entries scored well, even if they weren't enough to take the top score (and SY even added his own improvements to mine in the last few minutes!) I wish I had had more time available on the last days to try some more in-depth improvements.

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.

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

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

Nick,
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" <NikHow@hotmail.com> wrote in message <hdh950$gt7$1@fred.mathworks.com>...
> I'm pleased to see that some of my last-minute entries scored well, even if they weren't enough to take the top score (and SY even added his own improvements to mine in the last few minutes!) >

Bravo, Alfonso! That was a very impressive score.

I have question about cyclomatic complexity and scoring. Some time ago, we introduced a small penalty for cyclomatic complexity greater than ten. In this contest almost all the entries (the competitive ones, anyway) managed to stay below that threshold.

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" wrote:
> 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

You are absolutely correct; score improvement by Alfonso code is huge.

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.woodford.98@cantab.net> wrote in message <hdhg9n$kk5$1@fred.mathworks.com>...
> "Oliver Woodford" wrote:
> > 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

I enjoyed watching the contest, though I do not understand the solvers!

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

Sergey: You're right, there was a lot of speculative code swapping in the final minutes. I'm flattered that you thought enough of me to use one of my entries as a base (although I notice that you did the same with a number of the other leaders).

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!)

Nicholas Howe wrote:
 > [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.
> [snip]

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/

Nick,
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" <NikHow@hotmail.com> wrote in message <hdhqc8$lfa$1@fred.mathworks.com>...
> Sergey: You're right, there was a lot of speculative code swapping in the final minutes. I'm flattered that you thought enough of me to use one of my entries as a base (although I notice that you did the same with a number of the other leaders).
>
> 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!)

"Alan Chalker" <alancNOSPAM@osc.edu> wrote in message <hdgsc6$77q$1@fred.mathworks.com>...

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

"Helen Chen" <helen.chen@mathworks.com> wrote in message <hcmvti$4je$1@fred.mathworks.com>...
> 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

"Darren Rowland" <darrenjremovethisrowland@hotmail.com> wrote in message
> Finally to Doug, I noticed most of the different board types. The large snaking wall boards were a particularly devious choice.

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

"Magnus Sch?fer" <magnus.schaefer@rwth-aachen.de> wrote in message
<snip>
> 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. :)
</snip>

I myself would love to have a running contest (maybe even till the next Spring contest), the only hurdle to this I see is once the test suite is released we would start seeing customized solutions rather than a general one which would really spoil the fun.

Rgds,
- Amitabh

"Doug Hull" <hull@mathworks.SPAMPROOFcom> wrote in message <hdhq2t$3ok$1@fred.mathworks.com>...
> I enjoyed watching the contest, though I do not understand the solvers!
>
> 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.

The high-80 boards were the only ones I noticed significantly changing the strategy. Oliver's code was quite good at all the others, but not so strong on these, which is why most solutions ended up using a different solver on them. In order to get all the 80 tiles you pretty much had to flood the whole board, which is why a random solver worked fairly well. I ad hoped to write something which would go after the 80s in a more directed (and hopefully more efficient) manner, but I never had the time.

I'm curious what strategies other people thought of and tried out or didn't try out? Some of these may even have been in the final code, or been obviated by it; I never had time to fully follow what was going on in Oliver's solver. But some unimplemented ideas I had were:

- use cc computation to find areas traversible with a subset of colors, and restrict yourself to those colors in those areas. From the start, you want areas where low numbers will suffice (to keep the path cost low). Working back from the finish, you want areas where high numbers will suffice (to avoid flooding low areas unnecessarily at the end.)

- in similar vein, do postprocessing on a successful solution and try to move the final appearance of a particular low-number color flood earlier in the string, to limit incidental flooding.

- identify large high-value areas and connect to them as a preliminary task before reaching the final goal. Unfortunately, there didn't seem to be any boards where this was a clear win (e.g. treasure trove of high values behind a wall of lows, with an easy path to the goal as distraction.) Maybe I just missed them.

Some explanations/comments:

Oliver’s code finds best path from start to finish from the point
of view of cost of the part itself. It does not take into account
“expansion” of the path due to flooding of connected
clusters. Algorithm was improved later by addition of
“flood” function which adds some colors just before last
step to flood high-value areas.

Case “80” was specific because it has multiple pixels with
value significantly higher thanthe rest of the board (if one wants to
create universal solver one, probably, needs to create histogram of
board values (or cluster base values) and check for peak at high
values.) Then suggested solution was to flood whole board without using
“80” then add “color 80” before last step. Board
flooding was done in random manner, with choosing best path using
calculated score. I am sure here we have room for improvement. In
several final submissions I was trying to make floodin less random,
thinking that we can shorten path trying to flood largest areas first.
(it was implemented crudely and generated ~60 points
“result” gain but was slower).

On my opinion, improvement of Oliver’s code lays on the way of
figuring out how to take “path expansion” into account. I
was trying to do it “stupid men” way: by adding value of
connected clusters with some weighing coefficient. Obviously, the longer
path, the more important “expanson”. And, obviously,
because expansion is cumulative, it is larger closer to starting point.

SY

"Nicholas Howe" <NikHow@hotmail.com> wrote in message
<hdk0b0$1jt$1@fred.mathworks.com>...
> "Doug Hull" <hull@mathworks.SPAMPROOFcom> wrote in message
<hdhq2t$3ok$1@fred.mathworks.com>...
> > I enjoyed watching the contest, though I do not understand the
solvers!
> >
> > When I was making the testsuite, I had 12 different styles of
boards. I am curious if the little "gotchas" I put n 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.
>
> The high-80 boards were the only ones I noticed significantly changing
the strategy. Oliver's code was quite good at all the others, but not
so strong on these, which is why most solutions ended up using a
different solver on them In order to get all the 80 tiles you pretty
much had to flood the whole board, which is why a random solver worked
fairly well. I ad hoped to write something which would go after the 80s
in a more directed (and hopefully more efficient) manner, but I never
had the time.
>
> I'm curious what strategies other people thought of and tried out or
didn't try out? Some of these may even have been in the final code, or
been obviated by it; I never had time to fully follow what was going on
in Oliver' solver. But some unimplemented ideas I had were:
>
> - use cc computation to find areas traversible with a subset of
colors, and restrict yourself to those colors in those areas. From the
start, you want areas where low numbers will suffice (to keep the path
cost low). Working back from the finish, you want areas where high
numbers will suffice (to avoid flooding low areas unnecessarily at the
end.)
>
> - in similar vein, do postprocessing on a successful solution and try
to move the final apearance of a particular low-number color flood
earlier in the string, to limit incidental flooding.
>
> - identify large high-value areas and connect to them as a preliminary
task before reaching the final goal. Unfortunately, there didn't seem
to be any boards where this was a clear win (e.g. treasure trove of high
values behind a wall of lows, with an easy path to the goal as
distraction.) Maybe I just missed them.

A review of the contest test suite and comparison of the 1000 node winner and final winner has been posted:

http://blogs.mathworks.com/videos/2009/11/13/contest-flood-wrap-up/

Doug

Thanks, Doug, for your video. I always enjoy reading (or viewing) the mid- and post-contest analyses.

Your point about liberating extra high nodes by using the goal color just before it becomes blocked is a good one, and not all that hard to code. I wonder how much this would have added on the test suite? We also could have done a more thorough search through all possible orderings of the gleaning (that's what I called the inserted high-value colors just before the goal) to figure out which was most efficient. Unfortunately, the advantage from these sorts of small optimizations can easily be swamped by the effects of randomness, so I'm usually wary about investing much time on them.

I'll add one more strategy, which my 'Tilt' series explored, but not fully: it seems that you can get a small but consistent score improvement if you bias the random choices according to the color value.

Alfonso, would you perhaps be interested in talking us through your winning strategy? As Doug observed, you do well on the high-80 boards, which Oliver's original code had trouble with and the random solver is at best a half-hearted solution.

Is this a valid theory...
I felt like if the value of the board were temporarily enhanced for the solver it might be able to find a clearer path without losing much on time.

So for demonstration I take Nieto's winning code (lasttry01) and ran it on the example test suite and got the following:
results: 642680.0000
time: 45.91

and Nick Howe's (CerealTilt) #10
results: 649008.0000
time: 41.05

Then I made a minor modification on (lasttry01) by adding A=A*2 at the top and colors=colors/2 at the end and replacing all "> 40" by "> 80"
results: 641952.0000 (728 lower)
time: 46.14

and and Nick Howe's (CerealTilt) #10
results: 647822.0000 (1186 lower)
time: 53.94

For the online test suite a factor of 3 seemed to work better. However, I didn't get a chance to try this out much.

Any thoughts on this ?

PS: Tried on SY's LastCatStanding_99 and got a worse result. Didnt go deeper in the code to find the reason.

"Sergey" <ivssnn@yahoo.com> wrote in message <hdk733$394$1@fred.mathworks.com>...
> On my opinion, improvement of Oliver’s code lays on the way of
> figuring out how to take “path expansion” into account.

I totally agree on this. "Path expansion" is what limits the optimality of the Bellman-Ford search on the tree formed by clusters of same color pixels. My approach implemented a standard greedy depth-first search over the solution space, using a heuristic measure to determine the "optimal" move at each step. In the case of the "80"'s boards, a relatively succesfull approach was trying to flood the board by choosing at each step the path that maximizes the distance-to-target (minimal number of moves neccessary to reach the target), while trying to leave high-valued clusters until the end. Interestingly the minimal-distance measure can be effectively computed using a single initial Bellman-Ford run computing the path of minimal distance from every cluster (sets of pixels with the same color) to the goal cluster.

Overall lasttry01 tries out five different heuristics (and each of them it is tried out on up to three variations, using all the colors available, or avoiding all together the first or second of the most "costly" colors) in addition to trying out qcost3 (a great and very fast solver, thanks to Nicholas Howe), and simpy selects the best one for each board. The fifth heuristic implemented implements the approach described above which was particularly succesfull for many of the "80"'s boards. Another heuristic that was useful for these cases was taking into account the "delayed satistfaction" cost of a move (the maximal differential gain that could be achieved, if one is flooding the board and if instead of choosing a color right now, one was able to delay picking this color until the end moves, approximated by the number of pixels reamining for each color times the value of these pixels).
An heuristic that simply selected the color at each step that had the minimal sum of true cost and "delayed satisfaction" cost seemed to also performed quite well for some of these cases.

Of course a depth-first search was quite not satisfactory and I would have liked to implement some A* approaches and compute some more sophisticated cluster-level measures of interest for some of these heuristics by using additional Bellman-Ford runs but there is never enough time...

"Alfonso Nieto-Castanon" <alfnie@gmail.com> wrote in message
> In the case of the "80"'s boards, a relatively successfull approach was trying to flood the board by choosing at each step the path that maximizes the distance-to-target (minimal number of moves neccessary to reach the target), while trying to leave high-valued clusters until the end. Interestingly the minimal-distance measure can be effectively computed using a single initial Bellman-Ford run computing the path of minimal distance from every cluster (sets of pixels with the same color) to the goal cluster.

Of course! It seems so simple now that you say it. In most cases (where on average flooding increases costs) minimizing distance-to-target makes sense, but if you're trying to flood the entire board to collect all the 80's then the opposite is better. I actually experimented with solvers that computed the initial minimal-distance measure, but never found an effective way to use them. Well done. Thanks for explaining.