Thread Subject:

MATLAB Programming Contest: May 9 - May 16, 2007

Hello Community!

This is just a quick message to let everyone know that the MATLAB
Contest Masters have been hard at work! They have been crafting a
really exciting new challenge for our Spring event with some very
cool prizes waiting for our champions.

It's time to clear your calendars so that you can come join the fun!
The contest will start at noon Eastern time on May 9, ending at noon
on Mary 16th.

We will be announcing more details about the contest as we get
closer, so if you want a refresher about MATLAB Central contests,
check out the contest overview page at <http://www.mathworks.com/contest/overview.html>.
ou can checkout past contests using links on that page.

Stay tuned for more information...

Best wishes,
Helen Chen
MATLAB Central Team

Our contest will indeed begin today at noon EDT. I posted a welcome
message to the contest blog with some new information:

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

We have a few channels for contest conversation. This newsgroup
thread is the best place for general discussion. If you have a
response to anything we post on the blog, we encourage you to leave a
comment on the blog itself. Finally, if you'd like to communicate
with the contest team privately, e-mail us at contest@mathworks.com.

Good luck to everyone!

Thanks for organizing another contest. I'm looking forward to
participating as I'm sure a lot of people are.

Maybe this is in the code package, which I haven't looked at yet, but
what is the formula for the final result? In the past you've always
outlined it as something like

result = a*score + b*e^(c*time)

However with the new cyclomatic complexity variable it'd be helpful
to understand how that factors into the result.

The contest problem looks pretty interesting, thanks for setting it
up!

I tried to run the solitaireGUI.m function which came with zipped
contest files, and got an error message as follows:
 
Warning: Divide by zero.
> In solitaireGUI at 63
??? Undefined command/function 'bsxfun'.

Error in ==> solitaireGUI>drawGUI at 200
  c = c(:,~(sum(bsxfun(mf,1:size(c,2),(1:size(c,2))'))>1))';

Error in ==> solitaireGUI at 69
[hf,ha,sh,ht,hl] = drawGUI; printStats

I'm running MATLAB 7.1 student edition.

Mike Bindschadler wrote:
>
>
> The contest problem looks pretty interesting, thanks for setting it
> up!
>
> I tried to run the solitaireGUI.m function which came with zipped
> contest files, and got an error message as follows:
>
> Warning: Divide by zero.
>> In solitaireGUI at 63
> ??? Undefined command/function 'bsxfun'.
>
> Error in ==> solitaireGUI>drawGUI at 200
> c = c(:,~(sum(bsxfun(mf,1:size(c,2),(1:size(c,2))'))>1))';
>
> Error in ==> solitaireGUI at 69
> [hf,ha,sh,ht,hl] = drawGUI; printStats
>
> I'm running MATLAB 7.1 student edition.
  
bsxfun only came out in the most recent release.

John

Hi Alan,

I added the scoring formula to the rules. It is the same as it was
before with k*complexity added on the end.

Thanks,
Matthew

I'm just trying to run "runcontest", to see what the basic unmodified
solver does to the testsuite. I have a choice of error messages...

>> runcontest
??? Too many inputs.

Error in ==> runcontest at 18
    solutions = cellfun(@solver,boards,'UniformOutput',false);

>> runcontest(true)
??? Function name must be a string.

Error in ==> solitaireGUI>drawGUI at 184
  ht = cellfun(@(f,p) uicontrol('Sty','Tex','Fore',f,'Back',[1 1
.83],...

Error in ==> solitaireGUI at 69
[hf,ha,sh,ht,hl] = drawGUI; printStats

Error in ==> runcontest at 27
       
solitaireGUI(testsuite(i).board,solution,min(1,5/size(solution,1)))

>>

(MATLAB version 7.0.1)

Any ideas?

This may also be due to the fact that we used 7.4.0 to create the
GUI, we will provide a backwards compatible version soon. Please bare
with us.

Lucio

 Windy Miller wrote:
>
>
> I'm just trying to run "runcontest", to see what the basic
> unmodified
> solver does to the testsuite. I have a choice of error messages...
>
>>> runcontest
> ??? Too many inputs.
>
> Error in ==> runcontest at 18
> solutions = cellfun(@solver,boards,'UniformOutput',false);
>
>>> runcontest(true)
> ??? Function name must be a string.
>
> Error in ==> solitaireGUI>drawGUI at 184
> ht = cellfun(@(f,p) uicontrol('Sty','Tex','Fore',f,'Back',[1 1
> .83],...
>
> Error in ==> solitaireGUI at 69
> [hf,ha,sh,ht,hl] = drawGUI; printStats
>
> Error in ==> runcontest at 27
>
> solitaireGUI(testsuite(i).board,solution,min(1,5/size(solution,1)))
>
>>>
>
> (MATLAB version 7.0.1)
>
> Any ideas?

Hi!

I am having the same problem with the bsxfun error message, as I am
running R2006a. The contest team did a good job in obfuscation, or
what do you think about these lines?

% mf = @(g,h) arrayfun(@(h)
all(inpolygon(c{1,g},c{2,g},c{1,h},c{2,h})),h);
% c = c(:,~(sum(bsxfun(mf,1:size(c,2),(1:size(c,2))'))>1))';

This source couldn't be easier to read I guess :-)

A good contest to all of you!

Markus

Markus wrote:
>
>
> Hi!
>
> I am having the same problem with the bsxfun error message, as I am
> running R2006a. The contest team did a good job in obfuscation, or
> what do you think about these lines?
>
> % mf = @(g,h) arrayfun(@(h)
> all(inpolygon(c{1,g},c{2,g},c{1,h},c{2,h})),h);
> % c = c(:,~(sum(bsxfun(mf,1:size(c,2),(1:size(c,2))'))>1))';
>
> This source couldn't be easier to read I guess :-)
>
> A good contest to all of you!
>
> Markus
  

It's not deliberate obscufation that I can tell. The first line is
setting up an nested anonymous function handle (search for anonymous
functions in the MATLAB help for info). bsxfun is a new one to me,
but it applies element by element binary operations to 2 arrays.

The bottom line is they have used some of the more advanced
functionality to setup a demo solver and runcontest program that is
vectorized versus containing a lot of loops. This also factors into
the new Complexity rating.

Kudos to them for setting the bar high on this contest by trying to
start us off on a vectorized path instead of the 'easier to follow'
looping path many people would prefer to take.

OK to run in 7.1 change the following lines, sorry for the wrapping,
we will update the zip file and investigate further the other Windy's
problem (Windy, what release are you using?)

% c = c(:,~(sum(bsxfun(mf,1:size(c,2),(1:size(c,2))'))>1))';
  
CHANGE TO:

  MF = zeros(size(c,2));
  for i1 = 1:size(c,2)
      for i2 = 1:size(c,2)
          MF(i1,i2) = mf(i1,i2);
      end
  end
  c = c(:,~sum(MF)>1)';

% patch(bsxfun(@plus,j(:)',.1*sin(-2*pi:pi/4:2*pi)'),...
% bsxfun(@plus,i(:)',.1*cos(-2*pi:pi/4:2*pi)'),...
% zeros(17,numel(i)),'faceC',[0 .5 0],'FaceL','none');

CHANGE TO:

patch(repmat(j(:)',17,1)+repmat(.1*sin(-2*pi:pi/4:2*pi)',1,numel(j)),.
..
       
repmat(i(:)',17,1)+repmat(.1*cos(-2*pi:pi/4:2*pi)',1,numel(i)),...
        zeros(17,numel(i)),'faceC',[0 .5 0],'FaceL','none');

Lucio

 Alan Chalker wrote:
>
>
> Markus wrote:
>>
>>
>> Hi!
>>
>> I am having the same problem with the bsxfun error message, as
I
> am
>> running R2006a. The contest team did a good job in obfuscation,
> or
>> what do you think about these lines?
>>
>> % mf = @(g,h) arrayfun(@(h)
>> all(inpolygon(c{1,g},c{2,g},c{1,h},c{2,h})),h);
>> % c =
c(:,~(sum(bsxfun(mf,1:size(c,2),(1:size(c,2))'))>1))';
>>
>> This source couldn't be easier to read I guess :-)
>>
>> A good contest to all of you!
>>
>> Markus
>
>
> It's not deliberate obscufation that I can tell. The first line is
> setting up an nested anonymous function handle (search for
> anonymous
> functions in the MATLAB help for info). bsxfun is a new one to me,
> but it applies element by element binary operations to 2 arrays.
>
> The bottom line is they have used some of the more advanced
> functionality to setup a demo solver and runcontest program that is
> vectorized versus containing a lot of loops. This also factors
> into
> the new Complexity rating.
>
> Kudos to them for setting the bar high on this contest by trying to
> start us off on a vectorized path instead of the 'easier to follow'
> looping path many people would prefer to take.

Marko wrote:
>
>
> Can somebody explain me this line in the grade.m function?
>
> if tb(f) && board(f(2),f(1))>0 % valid pick
>
> why isn't board(f(1),f(2)) checked? Do I have to read the contest
> rules more carefully?

I have the same question. This seems odd:

board = [1 5 0];
score = grade(board,[1 1 1 3])
gives 7 (because the jump is invalid)

but
score = grade(board,[1 1 3 1])
gives 2; the expected score, i thought...

Marko wrote:
> Can somebody explain me this line in the grade.m function?
>
> if tb(f) && board(f(2),f(1))>0 % valid pick
>
> why isn't board(f(1),f(2)) checked? Do I have to read the contest
> rules more carefully?

I have also big problems with the grade function.
Jan

All indices of type x(2),x(1) must be x(1),x(2) i think

Thanks once again to everybody at the Mathworks who works hard to
bring us a fun contest. I have a question concerning a possible
discrepancy in the starter files. The solver provided seems to
generate moves which the grade.m function considers invalid. In
looking into the matter, it appears that the expected order of
indices is swapped. So for example, the first set of commands will
generate a poorer score than the second:

moves = solver(board)
grade(moves)

moves = solver(board)
grade(moves(:,[2 1 4 3]))

Of course, runcontest does the former. So should we write our
solvers accordingly?

Marko wrote:
> All indices of type x(2),x(1) must be x(1),x(2) i think
It looks like doing this at the end of your 'solver' solves the problem:

moves = moves(:,[2 1 4 3]);

Peter Torrione wrote:

> It looks like doing this at the end of your 'solver' solves the
> problem:
>
> moves = moves(:,[2 1 4 3]);

Yes but it's not supposed to work like that and confusing shifting
from row,colum indices to colum,row

Maybe I should stop solving and start evaluating again :-)

Peter is correct, the indexes got messed up when we set the grade.m
function from the GUI. Changing the lines

    f = moves(i,[1 2]);
    t = moves(i,[3 4]);

to

    f = moves(i,[2 1]);
    t = moves(i,[4 3]);

should be enough, albeit I will carefully revise it, when done we'll
update the zip file. Sorry for the inconvenience.

Lucio

Peter Torrione wrote:
>
>
> Marko wrote:
>> All indices of type x(2),x(1) must be x(1),x(2) i think
> It looks like doing this at the end of your 'solver' solves the
> problem:
>
> moves = moves(:,[2 1 4 3]);
>

Marko wrote:
> Peter Torrione wrote:
>
>> It looks like doing this at the end of your 'solver' solves the
>> problem:
>>
>> moves = moves(:,[2 1 4 3]);
>
> Yes but it's not supposed to work like that and confusing shifting
> from row,colum indices to colum,row
>
I agree. Plus the gui becomes useless...

Sorry for repeat. Did not see Lucio’s response.

Hi.

According to the web page, there is a 180 second time limit on our
programs. Is that for each board? How many boards will the programs be
expected to solve in 180 seconds?

-pete

Pete:

As usual, the testsuite sample that we provide has the
same level of complexity as the hidden testsuite. 180 seconds is the
time given to solve the whole testsuite.

Lucio

 Peter Torrione wrote:
>
>
> Hi.
>
> According to the web page, there is a 180 second time limit on our
> programs. Is that for each board? How many boards will the
> programs be
> expected to solve in 180 seconds?
>
> -pete
>

We've updated the File Exchange download to include a version of the
GUI that will run on older versions of MATLAB, solitareGUIb.m. We've
also made the fix to grade.m.

This same code was used on the scoring machine. We've updated
grade.m there as well. One of the reasons that we the administrators
like starting the contest in darkness is that we can patch up any
last-minute discoveries before it affects the game.

Lucio dreams in MATLAB code, so please forgive its terseness. He was
also a contest participant before he was an employee. Have y'all
checked out our list of job openings? We're hiring!

Thanks everyone for your patience.

Matthew Simoneau wrote:
>
>
> We've updated the File Exchange download to include a version of
> the
> GUI that will run on older versions of MATLAB, solitareGUIb.m.
> We've
> also made the fix to grade.m.
>
> This same code was used on the scoring machine. We've updated
> grade.m there as well. One of the reasons that we the
> administrators
> like starting the contest in darkness is that we can patch up any
> last-minute discoveries before it affects the game.
>
> Lucio dreams in MATLAB code, so please forgive its terseness. He
> was
> also a contest participant before he was an employee. Have y'all
> checked out our list of job openings? We're hiring!
>
> Thanks everyone for your patience.
  
I'm not sure you fixed grade.m. I manually did the fix outlined
above and everything was working fine. Then I just downloaded the
new version and it's giving high scores again. Looking at the file
you didn't switch the indexes you just switched the f = moves... and
t=moves... lines positions.

Matthew Simoneau wrote:
>
>
> We've updated the File Exchange download to include a version of
> the

Great, for all those (like me) that are on much older versions
without anonymous functions (the @), they are easy to replace by
ordinary functions. NB, does the complexity of an anonymous functions
add to the cyclomatic complexity of the function they are defined in?


Also I was suprised that the peg values are not integers but all
kinds of floats? Is that correct?

Otherwise a fun puzzle indeed!

Alan, you're right. I didn't read Lucio's instructions carefully
enough. The re-corrected version will be live shortly.

Matthew Simoneau wrote:
>
>
> Alan, you're right. I didn't read Lucio's instructions carefully
> enough. The re-corrected version will be live shortly.
  

Damn...

I've been double checking my code for the last two hours.
Couldn't figure out why on earth every change I make keeps on
increasing my score.

Thanks for pointing out the fix guys.

Leendert Combee wrote:
>
>
> Matthew Simoneau wrote:
>>
>>
>> We've updated the File Exchange download to include a version
of
>> the
>
> Great, for all those (like me) that are on much older versions
> without anonymous functions (the @), they are easy to replace by
> ordinary functions. NB, does the complexity of an anonymous
> functions
> add to the cyclomatic complexity of the function they are defined
> in?
>
>
> Also I was suprised that the peg values are not integers but all
> kinds of floats? Is that correct?
Probably so they can pop the number right into the evaluation
function. I'm not sure but I seem to recall PIV and Core 2 Duo's have
more floating point units than integer, good chance it could improve
performance (at least on compiled code :( )
>
> Otherwise a fun puzzle indeed!

I just downloaded the new score.m - last modified at 5:22 pm, is
something odd about:

>> board = [1 5 0];
>> moves = [1 1 1 3];
>> score = grade(board,moves)

score =

     6

?

I thought score should be 2...

Are we allowed to use try ... catch constructs?

On May 10, 1:29 am, "Matthew Simoneau" <matt...@mathworks.com> wrote:
> Our contest will indeed begin today at noon EDT. I posted a welcome
> message to the contest blog with some new information:

Peter, I seem to be too sleepy for this! I still had it wrong in
grade.m. I'm updating it again. Please copy Lucio's fix above more
carefully than I did!

Richard, there's no problem with try/catch, but you're not allowed to
call ERROR explicitly.

Hi,

I'm using MATLAB Version 7.3.0.267 (R2006b).

Still getting error in GUI :
Undefined function or method 'bsxfun' for input arguments of type
'function_handle'.

How can I use the new GUI: solitaireGUIb.m

Any help?

Rgds,
Abhi

Abhi wrote:
>
>
> Hi,
>
> I'm using MATLAB Version 7.3.0.267 (R2006b).
>
> Still getting error in GUI :
> Undefined function or method 'bsxfun' for input arguments of type
> 'function_handle'.
>
> How can I use the new GUI: solitaireGUIb.m
>
> Any help?
>
> Rgds,
> Abhi
  

Open runcontest.m and change line

       
solitaireGUI(testsuite(i).board,solution,min(1,5/size(solution,1)))

to

       
solitaireGUIb(testsuite(i).board,solution,min(1,5/size(solution,1)))

srach

srach wrote:
>
>
>
> Open runcontest.m and change line
>
>
> solitaireGUI(testsuite(i).board,solution,min(1,5/size(solution,1)))
>
> to
>
>
>
solitaireGUIb(testsuite(i).board,solution,min(1,5/size(solution,1)))
>
>
> srach
 

Thnxx..that works...

Rgds,
Abhi

There seems to be a discrepancy between the timestamp given on the
page you see after you submit an entry, and the timestamp you get
when you follow the "Entry Listing" link from the contest menu. The
latter seems to lag the former by two minutes or so. At least that's
how it looked to me at the end of Darkness. I submitted a (slightly
late) last-minute entry and the page said 12:01, then clicked the
Entry Listing link and got a page that said 11:59. My most recent
entry wasn't there yet, which sort of makes sense. Is the "Entry
Listing" link a time-delayed view, or are there two clocks? Just
curious. :-)

Hi Nick and welcome back. Most of the pages you see on the contest
site are refreshed only every couple of minutes. (We do this to keep
from having to hit the database every time someone views every page.)
 When you see "This page was generated..." on a page, the time
represents when this page was last refreshed, as late as a few
minutes ago, not the current time.

Is there any possibility of getting this to work on say r12.1? I've
been making modifications to try to get this to happen but im getting
the following error i do not understand?

runcontest
??? Error: File: C:\contest\jumping\solver.m Line: 10 Column: 6
"identifier" expected, "(" found.

Error in ==> C:\contest\jumping\runcontest.m
On line 20 ==> solutions{i} = solver(testsuite(i).board);

which pertains to

s = @(i,j) sub2ind([m,n],i,j);

in solver.m

Does anyone know why this errors? Is this due to my old version of
matlab?

Thanks

 

Lucio wrote:
>
>
> This may also be due to the fact that we used 7.4.0 to create the
> GUI, we will provide a backwards compatible version soon. Please
> bare
> with us.
>
> Lucio
>
> Windy Miller wrote:
>>
>>
>> I'm just trying to run "runcontest", to see what the basic
>> unmodified
>> solver does to the testsuite. I have a choice of error
> messages...
>>
>>>> runcontest
>> ??? Too many inputs.
>>
>> Error in ==> runcontest at 18
>> solutions = cellfun(@solver,boards,'UniformOutput',false);
>>
>>>> runcontest(true)
>> ??? Function name must be a string.
>>
>> Error in ==> solitaireGUI>drawGUI at 184
>> ht = cellfun(@(f,p) uicontrol('Sty','Tex','Fore',f,'Back',[1 1
>> .83],...
>>
>> Error in ==> solitaireGUI at 69
>> [hf,ha,sh,ht,hl] = drawGUI; printStats
>>
>> Error in ==> runcontest at 27
>>
>>
> solitaireGUI(testsuite(i).board,solution,min(1,5/size(solution,1)))
>>
>>>>
>>
>> (MATLAB version 7.0.1)
>>
>> Any ideas?

In article <ef55232.39@webcrossing.raydaftYaTP>,
B <Brian.Corwin@hotmail.com> wrote:
>Is there any possibility of getting this to work on say r12.1? I've
>been making modifications to try to get this to happen but im getting
>the following error i do not understand?

>runcontest
>??? Error: File: C:\contest\jumping\solver.m Line: 10 Column: 6
>"identifier" expected, "(" found.

>Error in ==> C:\contest\jumping\runcontest.m
>On line 20 ==> solutions{i} = solver(testsuite(i).board);

>which pertains to

>s = @(i,j) sub2ind([m,n],i,j);

>in solver.m

>Does anyone know why this errors? Is this due to my old version of
>matlab?

Did R12.1 support anonymous functions?
--
  "It is important to remember that when it comes to law, computers
  never make copies, only human beings make copies. Computers are given
  commands, not permission. Only people can be given permission."
                                               -- Brad Templeton

"Walter Roberson" <roberson@ibd.nrc-cnrc.gc.ca> wrote in message
news:f1vo7n$cph$1@canopus.cc.umanitoba.ca...
> In article <ef55232.39@webcrossing.raydaftYaTP>,
> B <Brian.Corwin@hotmail.com> wrote:
>>Is there any possibility of getting this to work on say r12.1? I've
>>been making modifications to try to get this to happen but im getting
>>the following error i do not understand?
>
>>runcontest
>>??? Error: File: C:\contest\jumping\solver.m Line: 10 Column: 6
>>"identifier" expected, "(" found.
>
>>Error in ==> C:\contest\jumping\runcontest.m
>>On line 20 ==> solutions{i} = solver(testsuite(i).board);
>
>>which pertains to
>
>>s = @(i,j) sub2ind([m,n],i,j);
>
>>in solver.m
>
>>Does anyone know why this errors? Is this due to my old version of
>>matlab?
>
> Did R12.1 support anonymous functions?

No. Anonymous functions were introduced in MATLAB 7.0 (R14). Brian, you
could try converting the anonymous functions into a regular function, but
you'd also need to modify the locations where those anonymous functions are
called to pass in the correct parameters in the correct order.

--
Steve Lord
slord@mathworks.com

Perhaps this is a topic for another thread but, im not exactly sure
of what the purpose of using the anonymous function in this case is?

with the statement s=@(i,j) sub2ind([m,n],i,j);
am i just declaring a function S that takes in values i and j and is
simply using the sub2ind function?

when i call the s function in the above case as s(i,j) the value
returned in place of s(i,j) is just the value of sub2ind([m,n],i,j)?

Aside from having multiple script files what is the benefit in this
situation of using the anonymous function?

Thanks,
Brian

>
>
>
> "Walter Roberson" <roberson@ibd.nrc-cnrc.gc.ca> wrote in
message
> news:f1vo7n$cph$1@canopus.cc.umanitoba.ca...
>> In article <ef55232.39@webcrossing.raydaftYaTP>,
>> B <Brian.Corwin@hotmail.com> wrote:
>>>Is there any possibility of getting this to work on say
r12.1?
> I've
>>>been making modifications to try to get this to happen but
im
> getting
>>>the following error i do not understand?
>>
>>>runcontest
>>>??? Error: File: C:\contest\jumping\solver.m Line: 10
Column: 6
>>>"identifier" expected, "(" found.
>>
>>>Error in ==> C:\contest\jumping\runcontest.m
>>>On line 20 ==> solutions{i} = solver(testsuite(i).board);
>>
>>>which pertains to
>>
>>>s = @(i,j) sub2ind([m,n],i,j);
>>
>>>in solver.m
>>
>>>Does anyone know why this errors? Is this due to my old
version
> of
>>>matlab?
>>
>> Did R12.1 support anonymous functions?
>
> No. Anonymous functions were introduced in MATLAB 7.0 (R14).
> Brian, you
> could try converting the anonymous functions into a regular
> function, but
> you'd also need to modify the locations where those anonymous
> functions are
> called to pass in the correct parameters in the correct order.
>
> --
> Steve Lord
> slord@mathworks.com
>
>
>

> with the statement s=@(i,j) sub2ind([m,n],i,j);
> am i just declaring a function S that takes in values i and j and

yes, that's right and all, just a more compact code...

to Walter: just replace s(x,y) in the code by sub2ind([m,n],x,y)
where x and y are the actual arguments used whereever you encounter
s. In grade.m you need to do something similar to t(f)

Thanks all, I believe I am close to having a package that will
atleast let me try to develop contest solutions. I am curious though
if someone can do me a favor so i can validate my results. Can
someone run the testsuite for say the first 3 boards, and tell me
what the results are when running the test suite unchanged? I'd like
to verify that all of my modifications are still kosher.

b

 Leendert Combee wrote:
>
>
>> with the statement s=@(i,j) sub2ind([m,n],i,j);
>> am i just declaring a function S that takes in values i and j
and
>
> yes, that's right and all, just a more compact code...
>
> to Walter: just replace s(x,y) in the code by sub2ind([m,n],x,y)
> where x and y are the actual arguments used whereever you encounter
> s. In grade.m you need to do something similar to t(f)

Hi,
 
I get this error:
 
Error using ==> filefilt at 123 The function ER...
 
What does it mean? I am quite puzzled...
 
Thanks!

> Error using ==> filefilt at 123 The function ER...

The rest of this message is "The function ERROR has been disabled".
ERROR is on our list of blocked functions.

Your are right, thanks!

While we are at it, it turns out that ERROR appeared in the function
grade which you supplied and I used. Maybe you want to consider
removing it from grade... :)

Thanks again!

 Matthew Simoneau wrote:
>
>
>> Error using ==> filefilt at 123 The function ER...
>
> The rest of this message is "The function ERROR has been disabled".
>
> ERROR is on our list of blocked functions.

Hi all,

Does anyone know what the number in paranthesis just below the
Results field is? Does it have anything to do with the submissions
cyclomatic complexity?

Volkan wrote:
>
>
> Hi all,
>
> Does anyone know what the number in paranthesis just below the
> Results field is? Does it have anything to do with the submissions
> cyclomatic complexity?
  
Yes. It IS the cyclomatic complexity.

the cyclist wrote:
> Yes. It IS the cyclomatic complexity.

Cyclistmatic?

I added "cyc: " in front of the number so everyone will have a chance
of guessing what it means. Someday we'll get this thing its own
column.

Alan Chalker wrote:
> For those of you interested, I've submitted a heavily commented
> version of the current leading code

Great idea Alan! That is really in the spirit of the contest!

Hi Markus !

We definitely think think that this is a good idea but unfortunately
do not have the resources to redo the contest site at this time. We
are looking to do something along those lines in the future.

Helen

 Markus wrote:
>
>
> To the contest team:
>
> In the last contests we were already crying for inserting a
> "captcha"
> on the entry submit page. Just as I have to fill "BTQNT" in a Word
> verfication line below the form where I currently am typing this
> text
> in. This would prevent spamming the queue and searching for the
> best
> parameters by multiple entries.
>
> Did you not include it because you don't like the idea or because
> you
> did not have the resources to do the modification to the interface?
>
>
> Markus

> This is just a quick message to let everyone know that the MATLAB
> Contest Masters have been hard at work!

Looks like there might be some small problems with the statistics
page. The Saturday "Contributions in Daylight" seem to be being
counted in Friday as well. Also, I think some or all of the graphs
on that page are not being updated.

Thanks again for putting on the contest.

Thanks for pointing this out! We'll take a look at this, although
maybe not until Monday.

Helen

  the cyclist wrote:
>
>
>> This is just a quick message to let everyone know that the
MATLAB
>> Contest Masters have been hard at work!
>
> Looks like there might be some small problems with the statistics
> page. The Saturday "Contributions in Daylight" seem to be being
> counted in Friday as well. Also, I think some or all of the graphs
> on that page are not being updated.
>
> Thanks again for putting on the contest.

I want to credit Jim Mikola's entry Juno39 for providing the grist
for my EarlyBird winner. A number of entries were doing better on
small problems than the current leader at the time, so I decided to
try combining them. I had intended to use my own Darkness solution in
this role (and submitted a few attempts that did so) but the
combination with Jim's solution worked the best. Thanks Jim!

I fixed the bug in the "Contributions in Daylight" section of the
Statistics page that the cyclist noticed. Thanks for letting us know.

Hi,
I am trying to use Matlab 6.0 R12. I have changed the anonymous
functions s and tb to
%%%% function s
function ret = s(siz,i,j)
ret = sub2ind(siz,i,j);

%%%%% function tb
function p = tb(p,siz)
all([p>0 p<=[siz(2) siz(1)] ~rem(p,1)]);

Is this correct?

Also I received errors on all if statements which use || or && and
that was solved by changing them to | and & respectively.
Have these operators changed in recent versions ?

After this on runcontest I am getting
ans =

results: 130055.0797
time: 0.59

Is this what i am supposed to get?

Matthew Simoneau wrote:
>
>
> I fixed the bug in the "Contributions in Daylight" section of the
> Statistics page that the cyclist noticed. Thanks for letting us
> know.
  
Thanks! The only issue I see right now on the Statistics page is
that the font on the Contest History graph is huge.

I have been following the last two contests. I am amazed at the
programming ability of many of the contestants. For a senior
mechanical engineering student, I am good with MATLAB. Compared to
what is going on here, I am not in the same league. How have all of
you become such guru's? How do I become a matlab guru?

Note: I started a new thread on the MATLAB Newsgroup page that you
can reply to this. I only posted this message so that some of the
contestants would see and reply.

Matthew Simoneau wrote:
>
>
> I fixed the bug in the "Contributions in Daylight" section of the
> Statistics page that the cyclist noticed. Thanks for letting us
> know.
  

Continuing to be the watchdog of the Stats page ...

I think the Most Active Participants graph is not being updated.

For those of you interested, I've posted another heavily commented
version of the leading code as of mid-day today, Monday. The code is
"Guided Tour Part 2" (id: 40979).

Unfortunately, with the number of subfunctions and recursive calls
the code has become much more difficult to understand than in my
previous attempt at this. Hopefully you'll find this of value /
interest.

cyclist, these images seem to be up-to-date on my end. Your browser
may be caching old versions. Try forcing a reload with ctrl-shift-R
or whatever your browser uses.

Alan Chalker wrote:
>
> Unfortunately, with the number of subfunctions and recursive calls
> the code has become much more difficult to understand than in my
> previous attempt at this. Hopefully you'll find this of value /
> interest.
  
I wish I could get the code rewritten without nested functions that
seem to inherit and pass on variables without properly included in
the argument lists. I am on an older Matlab version and just can't
get the first method (based on solveri) to work properly, it's making
wrong moves. I have tried twice, but to no avail. D@mn.

Matthew Simoneau wrote:
>
>
> cyclist, these images seem to be up-to-date on my end. Your
> browser
> may be caching old versions. Try forcing a reload with
> ctrl-shift-R
> or whatever your browser uses.
  
I tried clearing my cache, and I also tried using IE instead of
Firefox, and I still see the same stale graphs.

Since quite a while I haven't been able to reach the contest site (http://www.mathworks.com/contest/jumping/home.html).
t just diplays a "Page not found" message.

Is this problem related to my internet connection or is the site
down, i.e., does anybody experience the same problem?

Best,
srach

srach, the site is back up.

Helen Chen wrote:
>
>
> Hello Community!
>
> This is just a quick message to let everyone know that the MATLAB
> Contest Masters have been hard at work! They have been crafting a
> really exciting new challenge for our Spring event with some very
> cool prizes waiting for our champions.
>
> It's time to clear your calendars so that you can come join the
> fun!
> The contest will start at noon Eastern time on May 9, ending at
> noon
> on Mary 16th.
>
> We will be announcing more details about the contest as we get
> closer, so if you want a refresher about MATLAB Central contests,
> check out the contest overview page at <http://www.mathworks.com/contest/overview.html>.
> ou can checkout past contests using links on that page.
>
> Stay tuned for more information...
>
> Best wishes,
> Helen Chen
> MATLAB Central Team

Shashi Khatri wrote:
>
>
> Has anyone estimated k_1, k_2, k_3 and k_4. It seems like time
> plays
> almost no role in the score!
>
> Isn't the maximum time allowed 180 seconds? How come I'm yet to see
> an entry that takes more than 60 seconds?
>
> Thanks people...
>
> Shashi
  
Alan Chalker posted the following coefficients in the contest blog:

k1 = 0.1
k2 = 2
k3 = 0.05
k4 = 1

To Shashi,
In a contrary, I think that at the moment time plays too important
role. It is very easy just to improve result, but time penalty will
be significant. So, collective wisdom tells us that current sweet
spot is around 50 sec.
It resembles the situation with Blockbuster contest. However during
BlackBox contest times played less important role and participants
spent more time optimizing actual logic of algorithm then trying to
shave extra 0.01 sec from running time.
Saying that, I have to admit that it is practically impossible to set
coefficients in advance and create perfect result/time balance

SY

Shashi Khatri wrote:
>
>
> Has anyone estimated k_1, k_2, k_3 and k_4. It seems like time
> plays
> almost no role in the score!
>
> Isn't the maximum time allowed 180 seconds? How come I'm yet to see
> an entry that takes more than 60 seconds?
>
> Thanks people...
>
> Shashi

Helen Chen wrote:
>
>
> Hello Community!
>
> This is just a quick message to let everyone know that the MATLAB
> Contest Masters have been hard at work!

Bad timing for "planned server maintenance". I hope Brian Welch
wasn't behind this!

Thanks guys.

Another dumb question, the contest is open till Wednesday 12PM EDT,
right?

Sergey Yurgenson wrote:
>
>
> To Shashi,
> In a contrary, I think that at the moment time plays too important
> role. It is very easy just to improve result, but time penalty will
> be significant. So, collective wisdom tells us that current sweet
> spot is around 50 sec.
> It resembles the situation with Blockbuster contest. However during
> BlackBox contest times played less important role and participants
> spent more time optimizing actual logic of algorithm then trying to
> shave extra 0.01 sec from running time.
> Saying that, I have to admit that it is practically impossible to
> set
> coefficients in advance and create perfect result/time balance
>
> SY
>
> Shashi Khatri wrote:
>>
>>
>> Has anyone estimated k_1, k_2, k_3 and k_4. It seems like time
>> plays
>> almost no role in the score!
>>
>> Isn't the maximum time allowed 180 seconds? How come I'm yet to
> see
>> an entry that takes more than 60 seconds?
>>
>> Thanks people...
>>
>> Shashi

I have a concern about the contest score calculation, two entries
which are near or at the top currently appear to be identical with
scores differing solely based on computation time.

My entry 'Lions' : ID - 41452 - 2007-05-15 14:26:18 - Score -
3947.6295
and
nathan q's entry 'Filigree Siberian Hamster 2': ID - 41457 -
2007-05-15 14:29:33 - Score - 3947.3199

Performing a diff on these produced no differences, then examining
submission time shows that nathans was submitted after mine.

Is is it explained anywhere the effect of a high number of entries
waiting in the queue and the actual score. I assumed that each file
was tested in the same environment?

Thanks!

PS. This contest is addictive

MikeR wrote:
>
>
> I have a concern about the contest score calculation, two entries
> which are near or at the top currently appear to be identical with
> scores differing solely based on computation time.
>
> My entry 'Lions' : ID - 41452 - 2007-05-15 14:26:18 - Score -
> 3947.6295
> and
> nathan q's entry 'Filigree Siberian Hamster 2': ID - 41457 -
> 2007-05-15 14:29:33 - Score - 3947.3199
>
> Performing a diff on these produced no differences, then examining
> submission time shows that nathans was submitted after mine.
>
> Is is it explained anywhere the effect of a high number of entries
> waiting in the queue and the actual score. I assumed that each file
> was tested in the same environment?
>
> Thanks!
>
> PS. This contest is addictive
  
It is well known (but perhaps not widely known?) that identical
entries will produce identical result but not identical time. This
is not hard to understand when you consider that all the things going
on with the computer that runs the entries. I know that Mathworks
has stripped it down pretty well, and take a lot of measures to keep
timing as consistent as reasonably possible. But it can't be
perfect. Small time-improvement tweaks are swamped by the
variability in timing.

the cyclist wrote:
>
> It is well known (but perhaps not widely known?) that identical
> entries will produce identical result but not identical time. This
> is not hard to understand when you consider that all the things
> going
> on with the computer that runs the entries. I know that Mathworks
> has stripped it down pretty well, and take a lot of measures to
> keep
> timing as consistent as reasonably possible. But it can't be
> perfect. Small time-improvement tweaks are swamped by the
> variability in timing.
  

Since the contest is drawing to a close, this presents an opportunity
to start making suggestions for improvements. Its been suggested
many times in the past, but I'll again suggest that the number 1
improvement would be to put a roundoff in the time contribution to
overall score. I think rounding off to the nearest tenth or quarter
of a second would still entice people to try to tweak parameters ,
but would eliminate the variability due to system variations.

On both occasions during this contest when I submitted a heavily
commented version of the leading code, my commented version took the
lead for quite a while. I made no algorithmic changes to the code,
yet due to the fact I submitted them when the queue's were empty and
machine basically idle I got a slight speedup in the run-time. While
that was a nice quirk, it clearly illustrates the variability queue
load has on the timing calculations.

Anybody have any other suggestions for way to improve the contest?

MikeR wrote:
>
> I have a concern about the contest score calculation,
> two entries which are near or at the top currently
> appear to be identical with scores differing solely
> based on computation time.

Hi Mike:

The cyclist is right to say that, try as hard as we might (and we do
try) identical files get different running times.

I carefully diff'd the two files you describe, and you're right, they
are identical. If this were a matter of winning the contest (or
winning one of our mini-contest challenges), we would award the prize
to the person who first submitted the code that did the best. In this
case, you would get the prize. But since there's no prize at stake,
we just let stuff like this ride.

As the contest nears its end, people are often working near the
"noise floor" of our measuring capability. They are making tiny
improvements that could easily be negated by a passing cosmic ray. We
like to think that this is part of the charm of the contest. In any
event, we ask that people not intentionally resubmit identical code.
It won't help you win a prize.

-Ned.

Hi Mike and all

For the record, these two entries were developed independently. In
fact, according to the "based on" credits, both came from BirdBrain's
Bill Murray's Explosive Gerbil, which was the leader at the time. I
was just fiddling with the obvious parameters - it's not surprising
that two of us would come up with identical tweaks. It's right that
the earlier submission should get the credit if a prize is at stake.

Nathan

PS thanks, Mathworkers, for another great contest.

MikeR wrote:

> My entry 'Lions' : ID - 41452 - 2007-05-15 14:26:18 - Score -
> 3947.6295
> and
> nathan q's entry 'Filigree Siberian Hamster 2': ID - 41457 -
> 2007-05-15 14:29:33 - Score - 3947.3199

The "Best Result by 4 PM Challenge" seems a bad idea in some senses.
The big tweaking bomb will suppress the all the remaining time of
Tuesday.(100*3/60=5hours) The most are waiting for the random
*magic*. Maybe contest team could add more PCs to process the queue?

Jin wrote:
>
>
> The "Best Result by 4 PM Challenge" seems a bad idea in some
> senses.
> The big tweaking bomb will suppress the all the remaining time of
> Tuesday.(100*3/60=5hours) The most are waiting for the random
> *magic*. Maybe contest team could add more PCs to process the
queue?
  

To the contrary, I think this was a brilliant move on their part. By
effectively 'shutting down the feedback loop' they've dropped us into
a 'dusk' like state. Unlike twilight where we can see all the scores
but not the code, here we can see the code but not the scores.
Something like this has been suggested several times in the past as a
way to reduce the effect of last minute tweaking on the final grand
prize winner and put more focus on algorithm development.

I personally hope the queue gets filled up even more overnight such
that tomorrow morning we are in a similar situation.

AC, if considered for a algorithm development, you are really
right^_^ And I like your well-documented codes^_^

Anybody who wants to overload queue and create “dusk” state can
easily do it.
I just do not know if it is consistent with extremely cooperative
spirit of current contest.
On another side, last second meaningless tweak of somebody else
significant code improvement is not good either.

Sergey

My thoughts on improving future contests:

- Round cpu time to 0.1 sec to avoid timing inconsistencies.

- Add column for cyclomatic complexity.

- Show statistics page earlier in the contest.

- Add a reasonably accurate timestamp of The Mathwork's official time
to the top of the submit page. It doesn't have to be perfect, but it
would help with last minute entries.

- For the 1000 character challenge, don't count whitespace
(whitespace = spaces, tabs, and newlines). That way, entries can have
commands on different lines and keep proper indentation. I included a
simple script below that can do the counting.

All that said, it has been another great contest. Thanks Mathworks
team! Also thanks to all the contestants for the well-commented code
and following the 'no welching' rule.

Steve

------------------------------------------------

function c = charcountnowhitespace(fn)
% Count the characters in a file, excluding whitespace (spaces, tabs,
and
% newlines). Returns the character count, or -1 if file error.
%
% Example call: c = charcountnowhitespace('charcountnowhitespace.m')

% Steve Hoelzer 2007-05-16

fid = fopen(fn);
if fid == -1
    c = -1; % error opening file
    return
end

% Count chars
c = 0;
line = fgetl(fid);
while isempty(line) || line(1) ~= -1
    line(line == 32) = []; % remove spaces
    line(line == 9) = []; % remove tabs
    line(line == 10) = []; % remove newlines
    c = c + length(line);
    line = fgetl(fid);
end

if fclose(fid)
    c = -1; % error closing file
end

and don't let anyone post a new code five times a minute...

Helen Chen wrote:
>
>
> Hello Community!
>
> This is just a quick message to let everyone know that the MATLAB
> Contest Masters have been hard at work!

So, it's all over but the crying. Thanks to the team for an
exceptionally smooth contest. I was really happy that obfuscation
didn't really enter, and that folks adhered to the request for no
Welching. The most infuriating part of the last couple contests was
when the queue broke down completely, so it was nice that that did
not happen this time around.

Good luck to all entries still in the queue. I estimate that it will
be done processing by around 15:00 EDT, all the entries run in about
the same CPU time as the current leader.

the cyclist (aka "tev")

Community,

I concur, this contest has been blast! The Matlab team deserves
thanks for keeping this running without any hitches!

Now we get to eagerly await the final outcome, I have a strong
feeling that "tev" will overtake me. It will be interesting if
another approach bests the current leader.

My effective entry popped a little to early,~10mins, so the masses
have consumed :)

sidenote: Ken Eaton you sure do know how to make this suspenseful.

- MikeR

the cyclist wrote:
>
>
> Helen Chen wrote:
>>
>>
>> Hello Community!
>>
>> This is just a quick message to let everyone know that the
MATLAB
>> Contest Masters have been hard at work!
>
> So, it's all over but the crying. Thanks to the team for an
> exceptionally smooth contest. I was really happy that obfuscation
> didn't really enter, and that folks adhered to the request for no
> Welching. The most infuriating part of the last couple contests
> was
> when the queue broke down completely, so it was nice that that did
> not happen this time around.
>
> Good luck to all entries still in the queue. I estimate that it
> will
> be done processing by around 15:00 EDT, all the entries run in
> about
> the same CPU time as the current leader.
>
> the cyclist (aka "tev")

MikeR wrote:

> It will be interesting if
> another approach bests the current leader.

I am curious what improvements are in the queue. Obviously, there is
some pure parameter tweaking, and that is always a threat.

I personally have two separate time improvements. They are small but
"real", and should both get over the timing variability, I think.

1) I replaced "sum(board(:)>0)" with "nnz(board)".

2) I defined iii=[i;i], and did a wholesale replacement of "i;i" with
"iii", along with a couple related efficiencies. Ditto with jjj.

I had a third replacement that I thought would be an improvement,
which was to define a variable "peg=board(:)>0", which identified
where pegs were. This could be used later in the calculation of the
count of pegs, and a couple of other ways. However, it seems this
did not really improve the time.

We have been working offline for a bit, so have only now had the
chance to take a look of some of the code in the queue.

We are a bit baffled by how the following code could possibly come to
exist without some probing of the contest suite going on. Yet many
appear to be using it??

fc=((pegCount < 250)||...
    (pegCount==272)||...
    (pegCount==516)||...
    (pegCount==544)||...
    (pegCount==535)||...
    (pegCount==540)||...
    (pegCount==542)||...
    (pegCount==542)||...

To be clear, we are not accusing anyone of anything. just asking...?

Thanks to the Mathworks contest team for one of he best contests yet.

Regards
Hannes & Cobus
a.k.a. Jacob & matlabboy
P.S. Yes we now our aliases and submission titles are stupid but you
do what you can to avoid being picked up by cyc's improvement radar.
Allthough it looks like this time it was Yi that caught us.

I want to thank organizers and participants for great competition. It
was a real pleasure to be here. Very good cooperative spirit this
time. (It would be really unfortunate if somebody decided to use
probing. Frankly speaking it just kills competition)

At the end I was trying to introduce three minor algorithm
modifications:

1. Make “random loop” run longer for board with higher mean weight
2. Combine subsol and solveri (run solveri inside subsol when there
are few pegs left) . Too much time penalty here, probably.
3. Count pegs on “black fields and white fields” (imagine that board
is colored as chess board, black pegs always stay black and always
remove white and vise versa) and introduce additional weight
parameter depending on ratio of sizes of two peg groups.

Best wishes to everybody,

Sergey

MikeR wrote:
>
> sidenote: Ken Eaton you sure do know how to make this suspenseful.

Is that in reference to my frantic last-minute submissions of what
will likely be unsuccessful attempts?

First I'd like to say thanks to all the MathWorks staff. Although I
am a long time MATLAB user, this was only the first contest I
submitted anything for (I tried for the Black Box, but never finished
anything in time to submit). Unfortunately, for this contest I didn't
have enough time to really dig in and see what other algorithms were
being tried by others. Still had fun though!

Most of my attempts centered around the idea of "black" and "white"
squares competing with one another (mentioned by a few people on
here), hence why I prefaced all my submissions with "predator/prey".
We'll see how my newest ones do (probably not as good as the top
contenders).

Tev,

How did you send over 15 tweaks of entries in the queue in less than
2 minutes? That is 1 every 8 seconds! You must have been pedaling
really fast...

Joseph

 MikeR wrote:
>
>
> Community,
>
> I concur, this contest has been blast! The Matlab team deserves
> thanks for keeping this running without any hitches!
>
> Now we get to eagerly await the final outcome, I have a strong
> feeling that "tev" will overtake me. It will be interesting if
> another approach bests the current leader.
>
> My effective entry popped a little to early,~10mins, so the masses
> have consumed :)
>
> sidenote: Ken Eaton you sure do know how to make this suspenseful.
>
> - MikeR
>

Hannes Naudé & Cobus Potgieter wrote:
>
>
> We have been working offline for a bit, so have only now had the
> chance to take a look of some of the code in the queue.
>
> We are a bit baffled by how the following code could possibly come
> to
> exist without some probing of the contest suite going on. Yet many
> appear to be using it??
>
> fc=((pegCount < 250)||...
> (pegCount==272)||...
> (pegCount==516)||...
> (pegCount==544)||...
> (pegCount==535)||...
> (pegCount==540)||...
> (pegCount==542)||...
> (pegCount==542)||...
>
> To be clear, we are not accusing anyone of anything. just
> asking...?
>
> Thanks to the Mathworks contest team for one of he best contests
> yet.
>
> Regards
> Hannes & Cobus
> a.k.a. Jacob & matlabboy
> P.S. Yes we now our aliases and submission titles are stupid but
> you
> do what you can to avoid being picked up by cyc's improvement
> radar.
> Allthough it looks like this time it was Yi that caught us.

Hannes & Cobus,

Thanks let us know your aliases. I pick up entries submitted by
matboy by chance. This morning, when I opened an IE window to look
the queue, I found a suspicious entry in the queue by matlabboy
without a valid email address. By searching matlabboy I found three
entries. All codes have a return with moves = [0 0 0 0] at the end.
Clearly, these entries is to test some improvement on solveri code.
Therefore, I copied one of these codes into my codes for the final
submission. For the above codes, I found from Jin's entry Iamcrazy31,
I belieave this is a prob series.

I wish to think to Mathwork team to organize this contest. This is a
very interesting problem. One can easily get an idea to improve the
algorithm. However, the time penalty makes many of them. This
morning, I just got an idea to improve the speed. After an hour's
work, finally I made it works. To make this code more valuable, I
waited until almost last minutes to scan the queue to try to catch
some new code to combine with this improvement. Wish myself good
luck.

Yi Cao

Yi Cao wrote:
>
> Thanks let us know your aliases. I pick up entries submitted by
> matboy by chance. This morning, when I opened an IE window to look
> the queue, I found a suspicious entry in the queue by matlabboy
> without a valid email address. By searching matlabboy I found three
> entries. All codes have a return with moves = [0 0 0 0] at the end.
> Clearly, these entries is to test some improvement on solveri code.
> Therefore, I copied one of these codes into my codes for the final
> submission. For the above codes, I found from Jin's entry
> Iamcrazy31,
> I belieave this is a prob series.
>

  
Wow. And I thought I was using radar. I am using two tin cans and a
piece of string compared to this.

I am pretty sure I am out of the running. My best entry will not
beat Yi Cao.

Hi all

I found a timing improvement in subsol and subsoltweak, in the most
expensive line of code:

validMoves(allMoves) = Bpos(F(allMoves)) & Bzero(T(allMoves)) &
Bpos(M(allMoves));

becomes

for i=1:length(allMoves)
    validMoves(allMoves(i)) = Bpos(F(allMoves(i))) &&
Bzero(T(allMoves(i))) && Bpos(M(allMoves(i)));
end

and knocks about 3 seconds off the runtime. The motivation for this
was to use the short-circuit && operators, but in fact the loop form
is nearly as quick with ordinary &. I don't know why it works - the
vectorised form is just a lot slower. Can anybody explain?

I was pretty pleased with this improvement, but Yi Cao has blown it
away! Well done Yi- maybe there is more to come...?

I was watching the queue in the last few minutes of the contest and
patching the above code into entries from some of the more notorious
competitors in the queue. I even did a diff of Yi's new code against
the current leader, but at a first glance the new code (like the
segment mentioned by Hannes and Cobus) looked like harmless parameter
tuning, so I moved on. I should have known better :)

Thanks again to the organising team, and to all the competitors, for
a great contest.

Nathan

the cyclist wrote:
>
> Wow. And I thought I was using radar. I am using two tin cans and
> a
> piece of string compared to this.
>
> I am pretty sure I am out of the running. My best entry will not
> beat Yi Cao.

Thanks. However, on Tuesday, my entry CollaborationSolver was
submitted with several improvements, but even did not get to the top
because of tuning parameters. But then, I found this entry had been
taken by Jin with other tuning parameters to win the Tusday Push
Prize. It was so sad to me at that time.

Yi

Yi Cao wrote:

> It was so sad to me at that time.

I expect you are feeling better now. Congrats on winning the contest!

Nathan Quinlan wrote:
>
>
> Hi all
>
> I found a timing improvement in subsol and subsoltweak, in the most
> expensive line of code:
>
> validMoves(allMoves) = Bpos(F(allMoves)) & Bzero(T(allMoves)) &
> Bpos(M(allMoves));
>
> becomes
>
> for i=1:length(allMoves)
> validMoves(allMoves(i)) = Bpos(F(allMoves(i))) &&
> Bzero(T(allMoves(i))) && Bpos(M(allMoves(i)));
> end
>
> and knocks about 3 seconds off the runtime. The motivation for this
> was to use the short-circuit && operators, but in fact the loop
> form
> is nearly as quick with ordinary &. I don't know why it works - the
> vectorised form is just a lot slower. Can anybody explain?
>
> I was pretty pleased with this improvement, but Yi Cao has blown it
> away! Well done Yi- maybe there is more to come...?
>
> I was watching the queue in the last few minutes of the contest and
> patching the above code into entries from some of the more
> notorious
> competitors in the queue. I even did a diff of Yi's new code
> against
> the current leader, but at a first glance the new code (like the
> segment mentioned by Hannes and Cobus) looked like harmless
> parameter
> tuning, so I moved on. I should have known better :)
>
> Thanks again to the organising team, and to all the competitors,
> for
> a great contest.
>
> Nathan

The improvement I submitted was to move most calculations of allMoves
out of the main loop by using a new matrix, rMap. I also tried to do
the same for subsoltweak, but was not successful because the matrix
becomes ao complicated that it take even more time to calculate
before the loop because subsoltweak was lightly used. I also combined
codes from matlabboy, Jin, David Jones and MikeR to make it be the
current top. Thanks to all of you contributed to the code. Wish to
see you all next time.

Yi

the cyclist wrote:
>
>
> Yi Cao wrote:
>
>> It was so sad to me at that time.
>
> I expect you are feeling better now. Congrats on winning the
> contest!
  

Congrats Yi. It's another testament to the uniqueness of this
particular competition that you were able to pull together a variety
of small tweaks to create the final winning entry (and not rely just
on parameter tweaking like some others do). I particularly find it
interesting that you neither had the fastest entry in the top ten nor
the best scoring one. You were able to strike a good balance between
the tradeoff of the two components of the score.

Yi Cao wrote:
>
>
> Nathan Quinlan wrote:
>>
>>
>> Hi all
>>
>> I found a timing improvement in subsol and subsoltweak, in the
> most
>> expensive line of code:
>>
>> validMoves(allMoves) = Bpos(F(allMoves)) & Bzero(T(allMoves)) &
>> Bpos(M(allMoves));
>>
>> becomes
>>
>> for i=1:length(allMoves)
>> validMoves(allMoves(i)) = Bpos(F(allMoves(i))) &&
>> Bzero(T(allMoves(i))) && Bpos(M(allMoves(i)));
>> end
>>
>> and knocks about 3 seconds off the runtime. The motivation for
> this
>> was to use the short-circuit && operators, but in fact the loop
>> form
>> is nearly as quick with ordinary &. I don't know why it works -
> the
>> vectorised form is just a lot slower. Can anybody explain?
>>
>> I was pretty pleased with this improvement, but Yi Cao has
blown
> it
>> away! Well done Yi- maybe there is more to come...?
>>
>> I was watching the queue in the last few minutes of the contest
> and
>> patching the above code into entries from some of the more
>> notorious
>> competitors in the queue. I even did a diff of Yi's new code
>> against
>> the current leader, but at a first glance the new code (like
the
>> segment mentioned by Hannes and Cobus) looked like harmless
>> parameter
>> tuning, so I moved on. I should have known better :)
>>
>> Thanks again to the organising team, and to all the
competitors,
>> for
>> a great contest.
>>
>> Nathan
>
> The improvement I submitted was to move most calculations of
> allMoves
> out of the main loop by using a new matrix, rMap. I also tried to
> do
> the same for subsoltweak, but was not successful because the matrix
> becomes ao complicated that it take even more time to calculate
> before the loop because subsoltweak was lightly used. I also
> combined
> codes from matlabboy, Jin, David Jones and MikeR to make it be the
> current top. Thanks to all of you contributed to the code. Wish to
> see you all next time.
>
> Yi
  

Good Job Yi,

You were quick to incorporate all the improvements that had been
posted.

I will be very interested in understanding what the test machine
threw at the scripts. I optimized my entries largely to reduce scores
and secondly to reduce processing time. Alan Chalker pointed out in
his summary yesterday the interesting relationship between time and
score.

Unfortunately the test machine must be very different from my
computer because dramatic improvements on my machine were always
registered as steps backwards on the test machine.

Overall a very interesting and exciting contest. I look forward to a
post analysis and the next contest.

- MikeR

the cyclist wrote:
>
> So, it's all over but the crying. Thanks to the team for an
> exceptionally smooth contest. I was really happy that obfuscation
> didn't really enter, and that folks adhered to the request for no
> Welching. The most infuriating part of the last couple contests
> was
> when the queue broke down completely, so it was nice that that did
> not happen this time around.
>

I have to second your sentiments here. Hopefully having a very
'clean' contest will set a precedence for future contests. It
definitely made it more enjoyable throughout. Now if only something
can be done to reduce the amount of parameter tweaking without
completely eliminating it from the equation........

See you all in the Fall.

Nathan Quinlan wrote:
>
> I found a timing improvement in subsol and subsoltweak, in the most
> expensive line of code:
>
> validMoves(allMoves) = Bpos(F(allMoves)) & Bzero(T(allMoves)) &
> Bpos(M(allMoves));
>
> becomes
>
> for i=1:length(allMoves)
> validMoves(allMoves(i)) = Bpos(F(allMoves(i))) &&
> Bzero(T(allMoves(i))) && Bpos(M(allMoves(i)));
> end
>
> and knocks about 3 seconds off the runtime. The motivation for this
> was to use the short-circuit && operators, but in fact the loop
> form
> is nearly as quick with ordinary &. I don't know why it works - the
> vectorised form is just a lot slower. Can anybody explain?
>
I just tried two different versions:

1)
    for i=1:length(allMoves)
        ii=allMoves(i);
        validMoves(ii)=Bpos(F(ii)) && Bpos(M(ii)) && Bzero(T(ii));
    end
This reduces my winning code time from 31 sec to 28 sec on my PC.

2)
    for i=allMoves
        validMoves(i)=Bpos(F(i)) && Bpos(M(i)) && Bzero(T(i));
    end
Initially, I thought the second version should be quiker because it
saves time to calculate the index. However, time actually increases
to 50 seconds!

All these are due to JIT acceleration. The first version is more
standard, hence it is a simple loop for JIT to accelerate. The second
version looks more clever, but for JIT, it is non-simple loop, hence
refuces to accelerate it. A good explaination about JIT is available
on the contest website: <http://www.mathworks.com/contest/protein.cgi/jitstory.html>

But personally, I am not used to work with JIT. Vectorization is
still my favorable way to solve problems. I delight to see
vectorization played a central role in this contest

Yi

Yi,

thanks for that note, and congratulations on a stylish win.

Nathan

 Yi Cao wrote:

> I just tried two different versions:
>
> 1)
> for i=1:length(allMoves)
> ii=allMoves(i);
> validMoves(ii)=Bpos(F(ii)) && Bpos(M(ii)) && Bzero(T(ii));
> end
> This reduces my winning code time from 31 sec to 28 sec on my PC.
>
> 2)
> for i=allMoves
> validMoves(i)=Bpos(F(i)) && Bpos(M(i)) && Bzero(T(i));
> end
> Initially, I thought the second version should be quiker because it
> saves time to calculate the index. However, time actually increases
> to 50 seconds!
>
> All these are due to JIT acceleration. The first version is more
> standard, hence it is a simple loop for JIT to accelerate. The
> second
> version looks more clever, but for JIT, it is non-simple loop,
> hence
> refuces to accelerate it. A good explaination about JIT is
> available
> on the contest website: <http://www.mathworks.com/contest/protein.cgi/jitstory.html>
>
> But personally, I am not used to work with JIT. Vectorization is
> still my favorable way to solve problems. I delight to see
> vectorization played a central role in this contest
>
> Yi

Congratulations Yi, it is nice to see the contest being won by some
strategy other than random parameter tweaking, or obfuscation.

Speaking of which, thank you Alan for your great and selfless effort
on documenting the code. I had to stay on the spectator side for this
contest, and you are the one who made it possible for me to keep up
until the end.

Volkan,

Yi Cao and other participants,
My Iamcrazy series is really a probe series in the last segement.
This probe is based on the analysis of two solver. In the big
pegCount board, the solveri is very slower than subsol. But I find
even in the this case there are relatively big improvement for
solveri im sample testsuite. I do a detail analysis to testsuite to
try to understand the well condition of solveri. I failed. The subsol
is 2-step-lookfor based algorithm, a strategy-fixed algorithm. So,in
some case, this algorithm is definitely not good. And So I think do
some probes may be not bad. Then I do about 30 probes in 3-4 hours.
Then...
One thing I must say I do *NOT* like tweaking bomb. And I will *NOT*
do this. For my case, I just do some fit(smart) probes to improve the
fun of contest. In the last segement(several hours), it is hard to
develope a new algorithm to beat the Highly *MAGIC* entries(before my
probes, such as ddlist, rand(57,1)...). We know it is impossible to
build one code to win in all cases. This leave magic to the every ML
contests.
Jin

By the way, somethings fishy about complexity values.

Contest winner 'Buy a ticket' and second place holder 'buy two
tickets' differ only by the following lines:

Buy a ticket has:
if (pegCount < 272) && (fill < .96)*(score < maxsum*0.775)

While the line is replaced by the following in buy two tickets:
fc=((pegCount < 250)||...
    (pegCount==272)||...
    (pegCount==516)||...
    (pegCount==544)||...
    (pegCount==535)||...
    (pegCount==540)||...
    (pegCount==542)||...
    (pegCount==542)||...
    ((pegCount>251)&&(pegCount<271))||...
    ((pegCount>550)&&(pegCount<555)))...
    &&(fill < .96)*(score < maxsum*0.775);
if fc

However, Buy a ticket has a complexity of 10, while buy two tickets
claims it to be as large as 21. Any ideas?

Volkan:

'Buy a ticket' has not combined with my guessed *magic* number. The
*magic* number can improve the results but waste more time. for cyc -
21 and 10, there are a trick not employed by YiCao. That is,
converting "||" to "|".( I'm not sure whether this is a bug or not,
but it really works.) If cyc goes from 21 to 10(or11), maybe 'buy two
tickets' will win.

Jin

Can the MATLAB team post the best score they were able to get from
their solution - just to compare with how close the leading entry
came.

This was my first contest and I am amazed at how well people code. I
am addicted. Looking forward to Fall contest.

Vishal

WARNING : LONG POST WITH RAMBLING SENTENCES ! ;-)

Hi all

Just a couple of random thoughts.

Firstly, my subjective opinion is that the amount of algorithmic
"heavy lifting" that goes into contest entries has declined
significantly since the early contests. It seems as if the algorithm
developers are one by one realising that they can't compete with
heavily tweaked and tuned leaders during daylight.

My first contest was trucking and I remember completely new
"homebrew" solvers being added to the mix throughout the run of the
contest. A quick look at the "differences from winner" plot reveals
that the leading code at the start of the final day still differed by
70-80% from the final winning code. This plot hasn't been present in
recent contest evolution reports so it is hard to make direct
comparisons and they may be spurious anyway.

Some other circumstantial evidence for the theory that fewer and
fewer people are focussing on algorithms is the fact that the leading
solvers were optimising an objective function that was WRONG and can
be shown to be wrong with a fairly elementary argument. Fixing this
objective function would have a significant impact, but apparently no
one picked up on it. Perhaps because we were all too busy adjusting
random seeds and shaving picoseconds off runtime ;-). This lasted
right up until the point where Yi's entries made it through the
queue. I think it is safe to say that after 7 days we are still quite
far away from a near-optimal solution.

Anyway, now that that is off my mind, some constructive suggestions.

Firstly it would be very nice if the contest machinery allowed one to
schedule a posting. In other words, when you submit an entry you can
choose to only have it appear at a later time. It may actually be
processed by the server earlier, but will only appear on the queue
when the scheduled time arrives (If it has allready been processed it
can appear directly on the rankings). This will significantly ease
the load on the contest server during submission "rush hour", it
hugely decrease the amount of time that is required for the queue to
finish processing entries after a given deadline has passed, and it
levels the playing field for those of us in other time zones and on
dial-up connections.

I can only assume that the above suggestion may very well fall into
the category of "Nice idea, but we don't have the time to implement
it." and I fully understand that, which brings me to my secnd
suggestion.

The entire contest is run in the spirit of open source so why not
extend this to the contest machinery. If the community agrees that a
specific change would be a good thing (I think there is fairly wide
agreement on a submission CAPTCHA for example) and the contest
machinery code is available, I am sure there would be volunteers to
implement the proposed changes. In the past making the code for the
contest machinery visible may have been considered a security risk
but since contest hacking and probing has now been consigned to the
dusbin of history based on the honour system, this is no longer a
concern.

Sorry for the long post and thanks again to all contestants and
especially the contest team for making this a brilliant event.

Regards
Hannes Naudé

Jin wrote:
>
>
> Volkan:
>
> 'Buy a ticket' has not combined with my guessed *magic* number. The
> *magic* number can improve the results but waste more time. for cyc
> -
> 21 and 10, there are a trick not employed by YiCao. That is,
> converting "||" to "|".( I'm not sure whether this is a bug or not,
> but it really works.) If cyc goes from 21 to 10(or11), maybe 'buy
> two
> tickets' will win.
>
> Jin

Does that mean cyc disencourages probing?

Yi

1.
“Firstly it would be very nice if the contest machinery allowed one
to schedule a posting. In other words, when you submit an entry you
can choose to only have it appear at a later time. It may actually be
processed by the server earlier, but will only appear on the queue
when the scheduled time arrives”

Really good idea. Poor man modification of this idea may be something
like:
“If submission title contains word ‘final’ time stamp it but do not
put it into queue until deadline”
It will resolve only one issue mentioned by Hannes Naudé, but,
probably,much easy to implement

2.
“Does that mean cyc disencourages probing?”
Probably not. Looks like all “||” are counted as nested loops. One
can use switch… case and avoid cyc penalty.

Regards,
Sergey

Erratum:

I mean “nested ifs” not “nested loops”

Sergey

 Sergey Yurgenson wrote:
>
>
> 1.
> “Firstly it would be very nice if the contest machinery allowed one
> to schedule a posting. In other words, when you submit an entry you
> can choose to only have it appear at a later time. It may actually
> be
> processed by the server earlier, but will only appear on the queue
> when the scheduled time arrives”
>
> Really good idea. Poor man modification of this idea may be
> something
> like:
> “If submission title contains word ‘final’ time stamp it but do not
> put it into queue until deadline”
> It will resolve only one issue mentioned by Hannes Naudé, but,
> probably,much easy to implement
>
> 2.
> “Does that mean cyc disencourages probing?”
> Probably not. Looks like all “||” are counted as nested loops. One
> can use switch… case and avoid cyc penalty.
>
> Regards,
> Sergey

Congrats to Yi Cao for winning the final contest with an entry
leading to such a big improvement in score.

Moreover, thanks to the contest team for making this such a smooth
and interesting contest. And of course, thanks to all contestants.

Hope to see you all in Fall,
srach

Sergey Yurgenson wrote:
>
>
> 1.
> “Firstly it would be very nice if the contest machinery allowed one
> to schedule a posting. In other words, when you submit an entry you
> can choose to only have it appear at a later time. It may actually
> be
> processed by the server earlier, but will only appear on the queue
> when the scheduled time arrives”
>
> Really good idea. Poor man modification of this idea may be
> something
> like:
> “If submission title contains word ‘final’ time stamp it but do not
> put it into queue until deadline”
> It will resolve only one issue mentioned by Hannes Naudé, but,
> probably,much easy to implement
>
> 2.
> “Does that mean cyc disencourages probing?”
> Probably not. Looks like all “||” are counted as nested loops. One
> can use switch… case and avoid cyc penalty.
>
> Regards,
> Sergey

OK, I see the point. As Jin suggested, replacing all || to | and &&
to & can reduce cyc to 10. Hence it can save 11 points in the score.
In this case, "buy two tickets" would be the winner.

Yi

Replacing || by | will generate small time penalty (probably not
significant).
“The real winner” I think is “but four tickets”.
In any case, congratulations with wonderful job.

Sergey

 Yi Cao wrote:
> OK, I see the point. As Jin suggested, replacing all || to | and &&
> to & can reduce cyc to 10. Hence it can save 11 points in the
> score.
> In this case, "buy two tickets" would be the winner.
>
> Yi

Yeah, the "but four tickets" has passed by the subsol and save some
seconds^_^
Jin

The constranit of cyc<=10 may be just used to reduce the
complexity of programme. Maybe the constranit is not very useful.
Jin
>
> Does that mean cyc disencourages probing?
>
> Yi

I would like to congratulate Yi Cao for winning this contest and also
the Matlab contest team for organizing another exicting contest. I
would like to especilly thank Lucio for being so responsive on the
first day of the contest.

I have participated in the last three contests of Matlab and I am
glad that this time someone won the contest who has throughly
contribued to the developement of winning code in all stages of the
contest, not a tweaker or a prober.

In the current format of the contest, there is simple strategy that
one can pick and have a high chance to win the grand prize: In the
last minutes of the contest, look into each entry, pick any parameter
from that entry and just change it by +/- 0.5% and submit two new
enteries based on that.

There have been several nice suggestions on how to make this contest
better. If they take time to implement, I woule like to reiterate one
which is fairly simple to implement: After darkness, let each day be
a twilight phase on its own where we can see the enteries from
previous days but not the ones from the current day. This way, both
objetive of fairness and cooperation can be achieved.

 Jin wrote:
>
>
> The constranit of cyc<=10 may be just used to reduce the
> complexity of programme. Maybe the constranit is not very useful.
> Jin
>>
>> Does that mean cyc disencourages probing?
>>
>> Yi

" after 7 days we are still quite far away from a near-optimal
solution".
I definitely argee with you. One example is mentioned in the
mid-contest analysis by Lucio. However, this mid-contest analysis is
very far from mid-contest^_^ One thing, to my interesting, is who
consider the ideas mentioned by Lucio carefully. I think his solution
seem very promising in the small-scale peg's case. I sugguest doing
some discuss this agorithm more.
Jin

 Hannes Naudé wrote:
>
>
> WARNING : LONG POST WITH RAMBLING SENTENCES ! ;-)
>
> Hi all
>
> Just a couple of random thoughts.
>
> Firstly, my subjective opinion is that the amount of algorithmic
> "heavy lifting" that goes into contest entries has declined
> significantly since the early contests. It seems as if the
> algorithm
> developers are one by one realising that they can't compete with
> heavily tweaked and tuned leaders during daylight.
>
> My first contest was trucking and I remember completely new
> "homebrew" solvers being added to the mix throughout the run of the
> contest. A quick look at the "differences from winner" plot reveals
> that the leading code at the start of the final day still differed
> by
> 70-80% from the final winning code. This plot hasn't been present
> in
> recent contest evolution reports so it is hard to make direct
> comparisons and they may be spurious anyway.
>
> Some other circumstantial evidence for the theory that fewer and
> fewer people are focussing on algorithms is the fact that the
> leading
> solvers were optimising an objective function that was WRONG and
> can
> be shown to be wrong with a fairly elementary argument. Fixing this
> objective function would have a significant impact, but apparently
> no
> one picked up on it. Perhaps because we were all too busy adjusting
> random seeds and shaving picoseconds off runtime ;-). This lasted
> right up until the point where Yi's entries made it through the
> queue. I think it is safe to say that after 7 days we are still
> quite
> far away from a near-optimal solution.
>
> Anyway, now that that is off my mind, some constructive
> suggestions.
>
> Firstly it would be very nice if the contest machinery allowed one
> to
> schedule a posting. In other words, when you submit an entry you
> can
> choose to only have it appear at a later time. It may actually be
> processed by the server earlier, but will only appear on the queue
> when the scheduled time arrives (If it has allready been processed
> it
> can appear directly on the rankings). This will significantly ease
> the load on the contest server during submission "rush hour", it
> hugely decrease the amount of time that is required for the queue
> to
> finish processing entries after a given deadline has passed, and it
> levels the playing field for those of us in other time zones and on
> dial-up connections.
>
> I can only assume that the above suggestion may very well fall into
> the category of "Nice idea, but we don't have the time to implement
> it." and I fully understand that, which brings me to my secnd
> suggestion.
>
> The entire contest is run in the spirit of open source so why not
> extend this to the contest machinery. If the community agrees that
> a
> specific change would be a good thing (I think there is fairly wide
> agreement on a submission CAPTCHA for example) and the contest
> machinery code is available, I am sure there would be volunteers to
> implement the proposed changes. In the past making the code for the
> contest machinery visible may have been considered a security risk
> but since contest hacking and probing has now been consigned to the
> dusbin of history based on the honour system, this is no longer a
> concern.
>
> Sorry for the long post and thanks again to all contestants and
> especially the contest team for making this a brilliant event.
>
> Regards
> Hannes Naudé

Farhad wrote:
>
>
> I would like to congratulate Yi Cao for winning this contest and
> also
> the Matlab contest team for organizing another exicting contest. I
> would like to especilly thank Lucio for being so responsive on the
> first day of the contest.
>
> I have participated in the last three contests of Matlab and I am
> glad that this time someone won the contest who has throughly
> contribued to the developement of winning code in all stages of the
> contest, not a tweaker or a prober.
>
> In the current format of the contest, there is simple strategy that
> one can pick and have a high chance to win the grand prize: In the
> last minutes of the contest, look into each entry, pick any
> parameter
> from that entry and just change it by +/- 0.5% and submit two new
> enteries based on that.
>
> There have been several nice suggestions on how to make this
> contest
> better. If they take time to implement, I woule like to reiterate
> one
> which is fairly simple to implement: After darkness, let each day
> be
> a twilight phase on its own where we can see the enteries from
> previous days but not the ones from the current day. This way, both
> objetive of fairness and cooperation can be achieved.
>
I wish to support this idea. Maybe not exactly one day delay, but a
few hours at least? We wish to encourage true algorithm development.

Yi

Jin wrote:
>
>
> " after 7 days we are still quite far away from a near-optimal
> solution".
> I definitely argee with you. One example is mentioned in the
> mid-contest analysis by Lucio. However, this mid-contest analysis
> is
> very far from mid-contest^_^ One thing, to my interesting, is who
> consider the ideas mentioned by Lucio carefully. I think his
> solution
> seem very promising in the small-scale peg's case. I sugguest doing
> some discuss this agorithm more.
> Jin
>
I have thought this direction, but do not have time to develop. The
key point here is that different solutions can be compared in several
subsections. In this way, we can reduce the number of total
combinations to a manageable level. Since we have significantly
improved the efficiency of subsol, here is my rough idea to implement
such comparison:

1. prepara the initial moves suing subsol get moves and scores
corresponding to each move.
2. set t=1;
3. call a recurrent function to find an improvement to the reference
moves:

Inputs to the recurrent function:
Bpos, Bzero, Bmax, rMap, F, M, T, moves, scores and t

Output of the recurrent function:
new_moves, new_scores

In the function:
1) find validMoves
2) loop to go through each element of valid Moves
3) at k element, form a new_move and score for step t.
4) update Bpos, Bzero and Bmax based on the t step of the reference
moves and update another set of Bpos, Bzero, Bmax based on the t step
of the new moves.
5) if 2 sets of Bpos and Bzero are equal, then this section of the
new move is parallel to the reference move. Compare sum of score of
this section between new_move and reference move and return the
better one.
6) if not equal, then parallel section has not been found. Hence, we
need one step further. Call the recurrent function again.

Current subsol tries to optimize each step of moves, but the above
algorithm aims to optimize a section of moves, hence should be
better. If the comparison includes Bmax, then it will be the true
optimal solution. But, it will take more steps to get converged or
may even never get converged hence runing out of time. To avoid
runing over time, we have to limit the maximum number of recureent
calls. If the maximum step reaches, them we assume we faild to find
parallel sections. We have to change the mode to single step optimal
from that point to the end.
If you wish to test this idea, please let me know the outcome.

Yi

Very interesting.
One simpler (and much faster) modification of this approach maybe
based on the fact that in our current version we are calculating
multiple paths already.
One can cheek if those solutions are intercepting each other
somewhere on graph and then choose the best segment.

Sergey

 Yi Cao wrote:
>
>
> I have thought this direction, but do not have time to develop. The
> key point here is that different solutions can be compared in
> several
> subsections. In this way, we can reduce the number of total
> combinations to a manageable level. Since we have significantly
> improved the efficiency of subsol, here is my rough idea to
> implement
> such comparison:
>
> 1. prepara the initial moves suing subsol get moves and scores
> corresponding to each move.
> 2. set t=1;
> 3. call a recurrent function to find an improvement to the
> reference
> moves:
>
> Inputs to the recurrent function:
> Bpos, Bzero, Bmax, rMap, F, M, T, moves, scores and t
>
> Output of the recurrent function:
> new_moves, new_scores
>
> In the function:
> 1) find validMoves
> 2) loop to go through each element of valid Moves
> 3) at k element, form a new_move and score for step t.
> 4) update Bpos, Bzero and Bmax based on the t step of the reference
> moves and update another set of Bpos, Bzero, Bmax based on the t
> step
> of the new moves.
> 5) if 2 sets of Bpos and Bzero are equal, then this section of the
> new move is parallel to the reference move. Compare sum of score of
> this section between new_move and reference move and return the
> better one.
> 6) if not equal, then parallel section has not been found. Hence,
> we
> need one step further. Call the recurrent function again.
>
> Current subsol tries to optimize each step of moves, but the above
> algorithm aims to optimize a section of moves, hence should be
> better. If the comparison includes Bmax, then it will be the true
> optimal solution. But, it will take more steps to get converged or
> may even never get converged hence runing out of time. To avoid
> runing over time, we have to limit the maximum number of recureent
> calls. If the maximum step reaches, them we assume we faild to find
> parallel sections. We have to change the mode to single step
> optimal
> from that point to the end.
> If you wish to test this idea, please let me know the outcome.
>
> Yi

Having peripherally participated in this contest, I would like to
second the motion. I think each day should be twilight, independent
of the day before. This levels the playing field for all our
international participants and those of us with full-time jobs!

Thanks to the Mathworks team for a fun distraction.

 Farhad wrote:

> There have been several nice suggestions on how to make this
> contest
> better. If they take time to implement, I woule like to reiterate
> one
> which is fairly simple to implement: After darkness, let each day
> be
> a twilight phase on its own where we can see the enteries from
> previous days but not the ones from the current day. This way, both
> objetive of fairness and cooperation can be achieved.

Yi Cao wrote:
...
> To avoid
> runing over time, we have to limit the maximum number of recureent
> calls.

I guess finding that this limit would not be a problem, since the
contest engine already limited the number of recursions to 100.
Trying to code a recursive connectivity graph, this limit seemed to
me quite harsh.

Another thing that crossed my mind, how about awarding Alan Chalker
with a "Fair Play" price or such. The "guided tour ..."
submissions,his comments about the weighting coefficients of the
score calculation and the relation between time and results seemed
really helpful to me and supported the idea of the contest.

Best,
srach

Hi Hannes

> Some other circumstantial evidence for the theory that fewer and
> fewer people are focussing on algorithms is the fact that the
> leading solvers were optimising an objective function that was
WRONG
> and can be shown to be wrong with a fairly elementary argument.

Are you referring to the objective function C0+CV*d? Score of first
move + weight*(score of second move), as I understand it. It seems
weird that this works with weight values far from 1, but the
fundamental flaw with the function itself is not obvious to me. Could
you elaborate on your comment?

thanks

Nathan

Yi Cao wrote:
>
>

> I wish to support this idea. Maybe not exactly one day delay, but a
> few hours at least? We wish to encourage true algorithm
> development.
>
> Yi
  

For all those calling for changes to eliminate the ability to tweak
and just focus on 'algorithm development', please keep in mind that
The Mathworks runs these contests to engage and excite the MATLAB
community AT LARGE. A balance needs to be struck between those
people with the time and expertise to really dive deep into the
problem at hand and those people who just want to be more
superficially involved (yet potentially learn something new about
MATLAB).

I'd suggest that the balance is reasonably good right now, due to the
fact that the vast majority of the winners for the past few
competitions haven't been 'tweakers'. However, as I suggested
earlier, there are small changes that could be made to the contest
mechanisms that wouldn't eliminate the ability the parameter tweak,
yet would drastically improve the experience of 'algo guys'.

The sub-contests are obviously geared towards different types of
players. The Tuesday leap is an algorithm improvement one, whereas
the Sunday push is a tweaking one.

Also, I think the Contest team is sensitive to the various time zones
involved. Just look at the range of end times for the various
sub-contests we just had. Everything from 9AM, Noon, 4PM, 9PM to
Midnight. This covers most of the possible time zones. Perhaps a
4-5AM one could be added in the future to cover the only gap that
exists.

All in all, I think the Contest Team does a really good job of trying
to cater to the spectrum of possible participants (except of course
for maybe us 'white-hat' types who want to probe and hack a bit;) and
should be commended for what is clearly a difficult task.

Any event like this will obviously evolve and improve based upon
lessons learned. As you make suggestions to the Content Team, please
keep these points in mind and maintain the proper mindset regarding
these wonderful and cost-free (to us at least) events that regularly
held for OUR enjoyment.

I'm sure I echo the sentiments of all the participants when I say
THANK YOU once again to the Contest Team and The Mathworks management
for holding these events. Please let us know if there is anything we
can do to encourage or facilitate the contests in the future.

Jin wrote:

> very far from mid-contest^_^ One thing, to my interesting, is who
> consider the ideas mentioned by Lucio carefully. I think his
> solution
> seem very promising in the small-scale peg's case. I sugguest doing
> some discuss this agorithm more.

Has anyone tried Lucio's function? I just found it does not work with
even very small problems, such as the first board in the testsuit. ML
gives an error. I think it is simply because
sum(2.^(numel(hs)-1:-1:0)) is too large to be used as a size to
construct a sparse matrix.

Yi

Alan Chalker wrote:
>
> The Mathworks runs these contests to engage and excite the MATLAB
> community AT LARGE. A balance needs to be struck between those
> people with the time and expertise to really dive deep into the
> problem at hand and those people who just want to be more
> superficially involved (yet potentially learn something new about
> MATLAB).
>
> I'd suggest that the balance is reasonably good right now, ...

I just want to add my voice in agreement with Alan Chalker.

The Matlab Contest, as it is currently organized,
provides something that is ENGAGING and EXCITING
for a wide variety of people who use Matlab and
want to learn more and improve (or show off) their skills.
I hope the organizers will stick with the current contest format.

Perhaps Darkness or Twilight winners deserve greater respect
for their own algorithmic insights, ... but through the rest
of the contest the actual algorithmic insights that arise
are remarkably few and far between. We rarely see wholesale
shifts from one high-level algorithm to another.
Instead, we see incremental changes at various levels.
Yes, realizing an advantage by "padding" the board
is more "algorithmic" than realizing that "nnz(B(:)>0)"
is faster than "sum(B(:)>0)", but in the end they are
both incremental and the main algorithm remains the same.

In previous contests, winners have *sometimes* been rewarded
for ignoring the ongoing tweakfest and focusing on their
own independent algorithm development ... which then needs
to be kept secret and submitted at the last strategic moment.

A big difference between writing efficient programs
in Matlab versus "C" is recognizing how to "vectorize"
your algorithm and eliminate things like "for" loops.

I have equal respect for a Tuesday Leap winner
who dreams up a new algorithm that suddenly takes the lead
by a wide margin and another contest winner who recognizes
a major speedup of the same algorithm that further advances
the lead by a wide margin. Which is more insightful?
the algorithm change or the program tweak? I'd say, ...
the one that makes the larger leap.

We could debate endlessly whether adding randomization
to an algorithm is insightful or just a tweak ...

... but I think over the years the Matlab Contest organizers
have optimized the contest format to be engaging and exciting
for a wide variety of Matlab users and I hope they keep it
pretty much the same for future contets.

Regards,
  David Jones

Congratulations to the organizers for another great Matlab contest!

Everything ran smoothly. I only noticed two tiny glitches:
with just a brief bug-fix in the sample code,
and the queue stalled late one night.

... and Congratulations to all the prize winners on well-deserved
victories.

I would like to share some thoughts and feedback.

In terms of suggestions for future contests, ...

(1) add a "captcha" to the entry submission form.

As Markus already suggested, this will slow the pace of tweakers
filling up the queue. Most importantly, it will prevent
the automated submission (by software) of dozens of entries per
second.

I don't think we want to go any further than that, since tweakers
do seem to play an important role to the optimizations that emerge
over the course of the contest. It would also be difficult to
police
any limits on submissions per hour, since people can use aliases.

(2) keep the "Best Result by 4pm Challenge" (as a way to create
"dusk")

I agree with Alan Chalker, the "Best Result ..." prize
was a brillant move. When the queue filled up with these
3-minute programs, it allowed people to see code, but not the
results
and encouraged most people to think more about algorithm development
instead of simple tweaks as we got closer to the end of the contest.
It also encouraged people to think about how to program
the optimal tradeoff between: better results and better times
to get the best overall score near the 2 critical execution times
(60 and 180 seconds).

(As far as I can tell, a good understanding of this "tradeoff"
is how Yi Cao score the impressive victory.)

I don't think there is any need to create an official "dusk" period,
since it worked out so well in this contest.

(3) add more "high level" algorithm description to the mid-contest
analysis

Everyone appreciated Alan Chalker commenting the code,
which also improved upon my "dreamland" series to take the lead,
so he gets double credit for that.

In addition to his line-by-line comments, I think it would be
particularly educational for participants who have less expertise
if there was also more of a high-level roadmap of the leading entry.
To many programmers, I think the comments still remain rather
cryptic
because they don't know how each step fits into the big picture.

Perhaps Lucio Cetto could take on the role of high-level algorithm
description.

For example, Alan's comments indicated the board was being padded
by rows and columns of -1's, but didn't really explain why this was
beneficial, or why that number of rows and columns were chosen.
Of course, experts realized this saved time by eliminating the need
to check boundary conditions when considering possible moves.

Also, some Matlab novices would appreciate an explicit explanation
about how 2 different algorithms could be combined in one
submission,
since "solveri()" gave better results, but was only fast enough on
smaller boards.
Again, this was obvious to many participants, but it would be nice
to make the contest accessible to more Matlab programmers.

And finally, I bet many students would appreciate some comments
or links to resources about the overall algorithm and concepts
like "branch-and-bound" and "lookahead" ...

(4) keep the cyclomatic complexity in the scoring

Including the "cyclomatic complexity" added an interesting dimension
to the scoring.

(5) ignore whitespace in the 1K challenge, or reformat 1K submissions

It would be nice if there was a way to avoid the obfuscation
that seems to come with the 1K challenge.
One possibility would be an automatic pre-processor
strips out whitespace, comments, and long variable names.
Another possibility would be to keep the current submission style
but automatically display the submitted code
in a standardized format with added whitespace.
Are there existing reformatting tools that could be used?


- - - - -


And now some personal comments on the contest, ...

Despite the fact that I didn't win any of the prizes in this contest,
it was still one of the most enjoyable for me.
The "Peg Jumping" puzzle was a great choice.
I realize the organizers put a lot of careful thought into
preparing for the contest and I hope the next puzzle will be
a similar combination of "easy to understand, but difficult to
solve".

The overall contest organization is brilliant, since there are
many opportunities for lots of different participants (25+)
to be "in the lead" in one category or another at various stages
of the competition.

Coming in a respectable 6th and 11th in Darkness and Twilight
I felt I had a good understanding of this particular contest problem
(though clearly others had a more insightful understanding!).
I anxiously sat in 1st place for the 1K challenge
until "SY" skillfully took my place with 2 minutes before the 9pm
deadline.

If there was a "Tweaker" prize for the most incremental improvements
over the course of the contest, I would have won it
with a total of 78.2770 on the "Statistics" page.
(hint, hint, to the contest organizers ... I would love a Matlab
T-shirt :-)

(By the way, I wonder if "tgs" should also get a prize, or at least
honorable mention for the "Best Result" (38544.27), although
it occurred after the 4pm deadline.)

Even though it's clear I'm a hard core tweaker, and I know some
people
must find this infuriating, I do favour the addition of a "captcha"
on the entry submission page to limit (but not eliminate)
the flow of tweaks into the queue. Fortunately, the queue never
really
got out of hand for this contest.

I think I also take some of the blame for launching us all
into the realm of randomization. In past contests there has often
been someone who had an algorithmic insight that finally cut through
all the randomization nonsense and brought us back into a more
predictable deterministic algorithm. I was fully expecting
this to happen again, but it never did. In fact, others
pushed randomization in new directions. Perhaps we should challenge
the organizers to dream up a future contest puzzle that does not
lend itself to a randomized solution.

As many participants must have realized from the names on my
submissions,
I was in the Sarasota Airport using their free wireless access
during the final day of the contest. I was later amused to see
that my submission "Boarding Flight 905" had briefly taked the lead
at 10:43am. I had to board my plane and I was in the air during the
final hour of the contest, but it wouldn't have mattered anyay,
since Yi Cao's submission took the victory so decisively.

I only mention being in the airport since I noticed
that "srach" titled one of his submissions:
"I'm leaving for my son's birthday party - good luck to all of you!"

Congratulations once again to all the contest organizers and winners.

Warmest Regards,
  David Jones

I wonder if the Contest organizers might be willing to release the
actual test suite used in the contest so people who are curious to
continue analyzing the problem would be able to benchmark their new
programs in comparison with the program(s) that won in various
categories.

-- David Jones

Nathan wrote:
>
>
> Hi Hannes
>
>> Some other circumstantial evidence for the theory that fewer
and
>> fewer people are focussing on algorithms is the fact that the
>> leading solvers were optimising an objective function that was
> WRONG
>> and can be shown to be wrong with a fairly elementary argument.
>
> Are you referring to the objective function C0+CV*d? Score of first
> move + weight*(score of second move), as I understand it. It seems
> weird that this works with weight values far from 1, but the
> fundamental flaw with the function itself is not obvious to me.
> Could
> you elaborate on your comment?
>
> thanks
>
> Nathan
  
Sure

Like I am sure most people do, I kept the information overload
manageable by scanning the leading entry from time to time to
maintain an overview, but only really focussing on and staying up to
date with one particular solver. In my case that was solveri the
deterministic recursive solver, so I dont know too much about what
weights were used for C0+CV*d. The recursive solver searched for the
chain had the highest score of the function F=(total weight
removed)-(lifting penalty). This seems to be the obvious choice, but
it is wrong, because it neglects the fact that you can have as many
moves as you want.

If you think about it, the final result will be made up of two
components:
Total weight left on the board + Total lifting penalties paid during
run.
The critical insight is to realise that none of our current solvers
could actually significantly affect the value of the first term. Even
the recursive solver that finds tremendously high scoring hopchains
is just as likely to get stuck relatively early in the endgame as a
simple greedy approach. This is not obvious, but it is true right up
to two moves from the end where the recursive can sometimes under
special circumstances see that one high scoring move will result in a
dead end whereas another possibly lower scoring move will set up
another chain to follow.

So, the way in which our objective function was derived, is to assume
at the outset that the amount of weight that will be removed from a
given board IN TOTAL is essentially fixed (it is not, but it is
outside the control of a reasonable objective function). Therefore we
should focus on minimizing the lifting penalty. This leads naturally
to the objective function F=(weight removed in this move)/(lifting
penalty for this move). switching to this metric has a dramatic
impact. This is the ratio metric that was introduced in our "All
frayed out" series (which were crippled so as not to attract undue
attention). Unfortunately for us Yi picked up on this and utilised it
to power him to an impressive win.

Not sure if that explanation was clear so will conclude with an
example. Lets assume we have two moves to choose between:
Move 1 : Removes 10 weights for a lifting penalty of 5.
Move 2 : Removes 5 weights for a lifting penalty of 1.
Move 1 results in a larger net gain in score (5 points) and so will
be chosen by the greedy objective function. Move 2 removes less but
does so more efficiently and will be chosen by the ratio metric. So
if we removed a total of 100 units of weight from a board, using
moves like move 1, we would end up paying a 50 unit lifting penalty.
If we removed the same amount using moves like move 2, we would only
pay a 20 unit lifting penalty.

This should obviously affect subsol and subsoltweak as well but the
implementation is not obvious (because the amount of weight that will
be lifted by a given hopchain is not known at decision time). A
simple start would be to weigh the lifting penalty heavier. We didn't
have time to investigate this.

Sorry to everyone that understood immediately and have had the pants
bored off them by the long dissection, but more often than not I
don't understand explanations offered here by others, so I try to be
as clear as possible.

If anyone feels this is wrong, I'd really like to hear why.

Cheer

David Jones wrote:
>
> I have equal respect for a Tuesday Leap winner
> who dreams up a new algorithm that suddenly takes the lead
> by a wide margin and another contest winner who recognizes
> a major speedup of the same algorithm that further advances
> the lead by a wide margin. Which is more insightful?
> the algorithm change or the program tweak? I'd say, ...
> the one that makes the larger leap.
>
It was me dreamed the new algorithm, (see CollobrationSolver). But
unfortunately, it did not get to the top due to new tweak parameter
was found just before the new algorithm was submitted. Fortunately,
the algorithm was quickly picked up by Jin then the Leap winner SY to
win the Leap price. I respect both of them. Without their tweaking,
this algorithm would be buried by random tweakers like many other
algorithms developed dring the week. But my point is that this is by
lucky. Many novel ideas might have been killed because the style of
contest during daylight phase does not encourage those ideas to be
developed further. I do respect all tweakers' contributions. But we
need to give some rooms for novel ideas to be developed. For example,
the owner of a code would get the result through email one hour
earlier than it shows on the queue. This may also avoid submissions
with fake addresses.

By the way, tgs is my alias. I used it to test a bug-fix in subsol.

Finally, I wish to thank you for your magic number rand(57,1) which
helped me win the contest.

Yi

Hannes Naudé wrote:
>
>
> Nathan wrote:
>>
>>
>> Hi Hannes
>>
>>> Some other circumstantial evidence for the theory that
fewer
> and
>>> fewer people are focussing on algorithms is the fact that
the
>>> leading solvers were optimising an objective function that
> was
>> WRONG
>>> and can be shown to be wrong with a fairly elementary
> argument.
>>
>> Are you referring to the objective function C0+CV*d? Score of
> first
>> move + weight*(score of second move), as I understand it. It
> seems
>> weird that this works with weight values far from 1, but the
>> fundamental flaw with the function itself is not obvious to me.
>> Could
>> you elaborate on your comment?
>>
>> thanks
>>
>> Nathan
>
> Sure
>
> Like I am sure most people do, I kept the information overload
> manageable by scanning the leading entry from time to time to
> maintain an overview, but only really focussing on and staying up
> to
> date with one particular solver. In my case that was solveri the
> deterministic recursive solver, so I dont know too much about what
> weights were used for C0+CV*d. The recursive solver searched for
> the
> chain had the highest score of the function F=(total weight
> removed)-(lifting penalty). This seems to be the obvious choice,
> but
> it is wrong, because it neglects the fact that you can have as many
> moves as you want.
>
> If you think about it, the final result will be made up of two
> components:
> Total weight left on the board + Total lifting penalties paid
> during
> run.
> The critical insight is to realise that none of our current solvers
> could actually significantly affect the value of the first term.
> Even
> the recursive solver that finds tremendously high scoring hopchains
> is just as likely to get stuck relatively early in the endgame as a
> simple greedy approach. This is not obvious, but it is true right
> up
> to two moves from the end where the recursive can sometimes under
> special circumstances see that one high scoring move will result in
> a
> dead end whereas another possibly lower scoring move will set up
> another chain to follow.
>
> So, the way in which our objective function was derived, is to
> assume
> at the outset that the amount of weight that will be removed from a
> given board IN TOTAL is essentially fixed (it is not, but it is
> outside the control of a reasonable objective function). Therefore
> we
> should focus on minimizing the lifting penalty. This leads
> naturally
> to the objective function F=(weight removed in this move)/(lifting
> penalty for this move). switching to this metric has a dramatic
> impact. This is the ratio metric that was introduced in our "All
> frayed out" series (which were crippled so as not to attract undue
> attention). Unfortunately for us Yi picked up on this and utilised
> it
> to power him to an impressive win.
>
> Not sure if that explanation was clear so will conclude with an
> example. Lets assume we have two moves to choose between:
> Move 1 : Removes 10 weights for a lifting penalty of 5.
> Move 2 : Removes 5 weights for a lifting penalty of 1.
> Move 1 results in a larger net gain in score (5 points) and so will
> be chosen by the greedy objective function. Move 2 removes less but
> does so more efficiently and will be chosen by the ratio metric. So
> if we removed a total of 100 units of weight from a board, using
> moves like move 1, we would end up paying a 50 unit lifting
> penalty.
> If we removed the same amount using moves like move 2, we would
> only
> pay a 20 unit lifting penalty.
>
> This should obviously affect subsol and subsoltweak as well but the
> implementation is not obvious (because the amount of weight that
> will
> be lifted by a given hopchain is not known at decision time). A
> simple start would be to weigh the lifting penalty heavier. We
> didn't
> have time to investigate this.
>
> Sorry to everyone that understood immediately and have had the
> pants
> bored off them by the long dissection, but more often than not I
> don't understand explanations offered here by others, so I try to
> be
> as clear as possible.
>
> If anyone feels this is wrong, I'd really like to hear why.
>
> Cheer

This is innovative thinking. I wish I could get this idea earlier. I
tested this idea with subsol and want to confirm it also works with
subsol. What I did is introducing another score vector C1 =
C0-0.5board(F(h)); to be used for optimization (only for the
isempty(c) case), but keep C0 to record actual score of the move. It
reduces overall results from 42725.167 to 42451.5929 for the testsuit
(based on my "Buy a ticket" code). Tweaking the weight can reduce the
results even further.

Yi

Yi

David Jones wrote:
[...]
> I only mention being in the airport since I noticed
> that "srach" titled one of his submissions:
> "I'm leaving for my son's birthday party - good luck to all of
> you!"

Yes, this was actually my last submission for this Spring contest,
because I spend the last 5 hours of the contest with a bunch of
five-year-olds.

One thing I would like to add to the "timezone vs. deadline"
discussion. Yes, living in a different timezone collides with some
deadlines, but, compared to previous contests, this has improved a
lot. (However, I still had to get up at 2 a.m. (local time) for the
1000-character contest. ;) ). However, although being one of the top
submitters (or SPAMers, if you prefer...), I never had to wait more
than 2 minutes for my entries to be processed (only exeption was, of
course, the "best result by 4pm contest"), because the contest
machine was nearly idle during my working hours (8pm to 4pm local
time, which is EDT+6). Thus, I felt free to optimize some parameters
online, because offline parameter optimization was rather useless.

Best,
srach

srach wrote:
> "timezone vs. deadline" discussion.

Yes, this has turned into a bit of a timezone vs. Deadline
discussion. To be honest, I feel that the times for the latest
contest has suited me better as well (alltough Cobus feels it is
worse, so its a matter of taste I suppose). However, that was hardly
the main driver for requesting a scheduling feature, if we need to
stay up until 3AM we will. The main thing is that we find it very
hard to submit our submissions at the exact right time due to
significant latency between ourselves and the contest machine. The
submission confirmation takes ~15s to come up and the queue and top
20 has taken as long as a minute.

The net result is that we either submit too early and get tweaked out
of top spot (this happened to us in blockbuster) or too late and miss
the deadline (this happened to Cobus in blackbox). Maybe it is like
this for everyone, but looking at how prolific cyc is during the last
few minutes I seriously doubt it. In addition our power and internet
connections are not as reliable as they should be (this is Africa
afterall ;-) ). In the ants contest our power went down 30 minutes
before the end and we had to get in a car and race to work where we
have UPS. Our submissions were ready well before this, so scheduling
would have helped a lot.

Of course the one day twilight concept achieves the same thing, as
does the suggestion of "final" tagged submissions. In effect we
currently have 1 minute darkness at the end of the contest (entries
that are submitted after 11:59 won't be seen before the deadline has
passed) so we are not really asking for a rule change, just for an
extension of the existing 1 minute darkness to accomodate those with
iffy connectivity, even 5 minutes would be great, allthough 1 day
would be way better.

I would really like to know what the contest team thinks of this
proposal, and would like to make clear my willingness to implement
it, if that would be required. Of course integration and testing on
your side will still require some of your time, but do you at least
agree with the idea in principle?

Regards
Hannes

Hannes

thanks for the explanation. Simple in hindsight, like most good
ideas.

I've tried your ratio metric in subsol, crudely (based only on the
known first two hops of a chain). It does not improve "buy a ticket"
(too finely tuned for the difference metric?) but in a mid-contest
code, it makes a significant improvement.

Nathan

Hannes Naudé wrote:

> So, the way in which our objective function was derived, is to
> assume
> at the outset that the amount of weight that will be removed from a
> given board IN TOTAL is essentially fixed (it is not, but it is
> outside the control of a reasonable objective function). Therefore
> we
> should focus on minimizing the lifting penalty. This leads
> naturally
> to the objective function F=(weight removed in this move)/(lifting
> penalty for this move). switching to this metric has a dramatic
> impact. This is the ratio metric that was introduced in our "All
> frayed out" series (which were crippled so as not to attract undue
> attention). Unfortunately for us Yi picked up on this and utilised
> it
> to power him to an impressive win.

Nathan wrote:
>
>
> Hannes
>
> thanks for the explanation. Simple in hindsight, like most good
> ideas.
>
> I've tried your ratio metric in subsol, crudely (based only on the
> known first two hops of a chain). It does not improve "buy a
> ticket"
> (too finely tuned for the difference metric?) but in a mid-contest
> code, it makes a significant improvement.
>
> Nathan
>
> Hannes Naudé wrote:
>
>> So, the way in which our objective function was derived, is to
>> assume
>> at the outset that the amount of weight that will be removed
from
> a
>> given board IN TOTAL is essentially fixed (it is not, but it is
>> outside the control of a reasonable objective function).
> Therefore
>> we
>> should focus on minimizing the lifting penalty. This leads
>> naturally
>> to the objective function F=(weight removed in this
> move)/(lifting
>> penalty for this move). switching to this metric has a dramatic
>> impact. This is the ratio metric that was introduced in our
"All
>> frayed out" series (which were crippled so as not to attract
> undue
>> attention). Unfortunately for us Yi picked up on this and
> utilised
>> it
>> to power him to an impressive win.

But my test shows that the ratio index works very well with subsol
based on "Buy a ticket" code. What I did is to replat C0+CV*d to
(C0+Cv*d)./board(F(h)). It reduces overall results from 42725.1617 to
41913.0357. Yes, more than 800 scores!

Yi

But it does not work with subsoltweak.

David Jones wrote:
> Perhaps Darkness or Twilight winners deserve greater respect
> for their own algorithmic insights, ... but through the rest
> of the contest the actual algorithmic insights that arise
> are remarkably few and far between. We rarely see wholesale
> shifts from one high-level algorithm to another.
> Instead, we see incremental changes at various levels.
> Yes, realizing an advantage by "padding" the board
> is more "algorithmic" than realizing that "nnz(B(:)>0)"
> is faster than "sum(B(:)>0)", but in the end they are
> both incremental and the main algorithm remains the same.
>
> In previous contests, winners have *sometimes* been rewarded
> for ignoring the ongoing tweakfest and focusing on their
> own independent algorithm development ... which then needs
> to be kept secret and submitted at the last strategic moment.

> In addition to his line-by-line comments, I think it would be
> particularly educational for participants who have less expertise
> if there was also more of a high-level roadmap of the leading
entry.
> To many programmers, I think the comments still remain rather
> cryptic
> because they don't know how each step fits into the big picture.

> Perhaps Lucio Cetto could take on the role of high-level algorithm
> description.

I think David has some nice points here. I would certainly welcome a
high-level overview of the code, as it would make it easier to
spectate, and (who knows?) maybe jump in again if I had a bright
idea.

In some sense the collaborative code development that emerges is a
greedy process: we follow and develop the code that is in the lead
at the end of twilight, and this leads us down one particular path.
It is fully possible that an algorithm designed some other way would
develop more successfully in the end. For example, someone may have
a great algorithmic idea that runs too slowly, but others might be
able to speed it up significantly to the point where it would
overtake the leader. It is very hard (not to mention daunting) for
one person to compete with the collective efforts of the group. The
early bird contest does encourage exploration of alternate paths a
little bit, but not in a very comprehensive way. Most algorithms
developed in Darkness and Twilight never get another look.

I don't have a real solution here, but it would be great if we could
somehow encourage parallel development on a number of different
approaches. Speaking selfishly, I would love to see what people
could have done with the approach I started with in Darkness. And in
the end, we might reach a more satisfying conclusion if we explore
more paths in the beginning.

To follow up a bit on my last post, it would be nice if we could
somehow separate categories by their high-level approach -- "Best
Recursive Solver," "Best Heuristic Solver," "best Combined Solver,"
etc., to encourage development on each separate front. Of course, I
don't really know how you would define the categories or implement
this in the contest framework. But it would be nice.

Nick Howe wrote:
>
>
> To follow up a bit on my last post, it would be nice if we could
> somehow separate categories by their high-level approach -- "Best
> Recursive Solver," "Best Heuristic Solver," "best Combined Solver,"
> etc., to encourage development on each separate front. Of course,
> I
> don't really know how you would define the categories or implement
> this in the contest framework. But it would be nice.

How about a parallel twilight queue, where we can see the result but
cannot read the code. Of cause, entries of this queue will not claim
any prize. It just provides a platform for code developers to develop
their own ideas.

Yi

Nick Howe wrote:
> It is fully possible that an algorithm designed some other way
> would
> develop more successfully in the end. For example, someone may
> have
> a great algorithmic idea that runs too slowly, but others might be
> able to speed it up significantly to the point where it would
> overtake the leader. It is very hard (not to mention daunting) for
> one person to compete with the collective efforts of the group.
> The
> early bird contest does encourage exploration of alternate paths a
> little bit, but not in a very comprehensive way. Most algorithms
> developed in Darkness and Twilight never get another look.

I agree. Maybe one way to draw attention to a variety of algorithms
is to display a second set of "top 20" entries for darkness and
twilight with ranking based purely on score (ignore time). The best
scoring entries may have better algorithms and some speed
optimization could lead to a better solution in the end.

Steve

Helen Chen wrote:
>
>
> Hello Community!
>
> This is just a quick message to let everyone know that the MATLAB
> Contest Masters have been hard at work! They have been crafting a
> really exciting new challenge for our Spring event with some very
> cool prizes waiting for our champions.
>
> It's time to clear your calendars so that you can come join the
> fun!
> The contest will start at noon Eastern time on May 9, ending at
> noon
> on Mary 16th.
>
> We will be announcing more details about the contest as we get
> closer, so if you want a refresher about MATLAB Central contests,
> check out the contest overview page at <http://www.mathworks.com/contest/overview.html>.
> ou can checkout past contests using links on that page.
>
> Stay tuned for more information...
>
> Best wishes,
> Helen Chen
> MATLAB Central Team

Steve Hoelzer wrote:
>
> I agree. Maybe one way to draw attention to a variety of algorithms
> is to display a second set of "top 20" entries for darkness and
> twilight with ranking based purely on score (ignore time). The best
> scoring entries may have better algorithms and some speed
> optimization could lead to a better solution in the end.
>
> Steve

There's already a notion of 'code clans' in the statistics Maybe a
start would be to group all entries connected by syntactic
similarities, and somewhere have a listing of the top entry for each
of the top 5-10 clans.

I updated the File Exchange submission to include the actual test
suite we used to score the entries.

The quality of commentary on this thread is blowing us away. It's
great to see the participants sharing stories, crediting sources, and
discussing algorithms. The level of gamesmanship from the top
players is impressive. We're also paying close attention to your
suggestions for improving the contest. I'm particularly interested
in finding ways to encourage innovation from participants and ways to
make the action easier to follow for spectators. Thanks for the
thoughtful suggestions on these and many other topics.

Hannes Naudé wrote:
[...]
> Not sure if that explanation was clear so will conclude with an
> example. Lets assume we have two moves to choose between:
> Move 1 : Removes 10 weights for a lifting penalty of 5.
> Move 2 : Removes 5 weights for a lifting penalty of 1.
> Move 1 results in a larger net gain in score (5 points) and so will
> be chosen by the greedy objective function. Move 2 removes less but
> does so more efficiently and will be chosen by the ratio metric. So
> if we removed a total of 100 units of weight from a board, using
> moves like move 1, we would end up paying a 50 unit lifting
> penalty.
> If we removed the same amount using moves like move 2, we would
> only
> pay a 20 unit lifting penalty.

How does this approach pay respect the fact, that the second kind of
moves needs a higher number of moves to reach the same amount of
weight removed from the board? Since the number of moves is limited,
I would think that the number of moves a strategy needs to reach a
certain amount of weight needs to be considered in the objective
function, too.

Best,
srach

srach wrote:
>
>
> Hannes Naudé wrote:
> [...]
>> Not sure if that explanation was clear so will conclude with an
>> example. Lets assume we have two moves to choose between:
>> Move 1 : Removes 10 weights for a lifting penalty of 5.
>> Move 2 : Removes 5 weights for a lifting penalty of 1.
>> Move 1 results in a larger net gain in score (5 points) and so
> will
>> be chosen by the greedy objective function. Move 2 removes less
> but
>> does so more efficiently and will be chosen by the ratio
metric.
> So
>> if we removed a total of 100 units of weight from a board,
using
>> moves like move 1, we would end up paying a 50 unit lifting
>> penalty.
>> If we removed the same amount using moves like move 2, we would
>> only
>> pay a 20 unit lifting penalty.
>
> How does this approach pay respect the fact, that the second kind
> of
> moves needs a higher number of moves to reach the same amount of
> weight removed from the board? Since the number of moves is
> limited,
> I would think that the number of moves a strategy needs to reach a
> certain amount of weight needs to be considered in the objective
> function, too.
>
> Best,
> srach

We may also consider potential moves desdroyed and creadted by a
move. We have found a vector of indices of triples (F M T) which
will be affected by conducting a move. Use this vector we can evalue
potential score increment and add this increment to the optimization
criterion. But time may increase significantly.

Yi

srach wrote:
>
>
> Hannes Naudé wrote:
> [...]
>> Not sure if that explanation was clear so will conclude with an
>> example. Lets assume we have two moves to choose between:
>> Move 1 : Removes 10 weights for a lifting penalty of 5.
>> Move 2 : Removes 5 weights for a lifting penalty of 1.
>> Move 1 results in a larger net gain in score (5 points) and so
> will
>> be chosen by the greedy objective function. Move 2 removes less
> but
>> does so more efficiently and will be chosen by the ratio
metric.
> So
>> if we removed a total of 100 units of weight from a board,
using
>> moves like move 1, we would end up paying a 50 unit lifting
>> penalty.
>> If we removed the same amount using moves like move 2, we would
>> only
>> pay a 20 unit lifting penalty.
>
> How does this approach pay respect the fact, that the second kind
> of
> moves needs a higher number of moves to reach the same amount of
> weight removed from the board? Since the number of moves is
> limited,
> I would think that the number of moves a strategy needs to reach a
> certain amount of weight needs to be considered in the objective
> function, too.
>
> Best,
> srach

But the number of moves is NOT limited as such and this is why the
first metric is wrong. The only sense in which the number of moves
are limited is that at some point you will reach a board
configuration that does not allow any further legal moves and you
will be stuck. But there is no reason to believe that the second
approach will get stuck any earlier (on average) than the first. How
early you get stuck is largely determined by the number of moves your
solver can lookahead.

On a slightly different topic, I have not had a chance to investigate
this, but I am reasonably certain that you will find that running the
improved subsol metric against the actual contest suite will NOT
result in an improvement. This is because any modification to the
non-deterministic solver will cause you to drop out of the local
minimum into which the leading code has been tweaked, and chances are
very high that the increased performance of the algorithm will be
outweighed by the absence of a "magic number". Many algorithmic
improvements and bugfixes have bitten the dust in this manner. This
is why we focussed our efforts on the deterministic part of the code.

Maybe Yi can test this conjecture and let us know?

Regards
Hannes

Hannes Naudé wrote:
>
> On a slightly different topic, I have not had a chance to
> investigate
> this, but I am reasonably certain that you will find that running
> the
> improved subsol metric against the actual contest suite will NOT
> result in an improvement. This is because any modification to the
> non-deterministic solver will cause you to drop out of the local
> minimum into which the leading code has been tweaked, and chances
> are
> very high that the increased performance of the algorithm will be
> outweighed by the absence of a "magic number". Many algorithmic
> improvements and bugfixes have bitten the dust in this manner. This
> is why we focussed our efforts on the deterministic part of the
> code.
>
> Maybe Yi can test this conjecture and let us know?
>
I have tested this improvement with actual suit. You are partially
right, the improvement is not as large as that achhieved on the
sample suit. But still there is a significant improvement: for "but a
ticket" code, the overal results reduced from 39072.4778 to
38866.2520, more than 200 points.

Yi

I agree with srach, the number of moves is limited (It is limited by
number of pegs).
My explanation of new metric is simpler:
New metric gives preferences to moves when medium weighted pegs are
tacking out by light pegs (medium-light) comparing to old metric
heavier pegs being tacking out by medium pegs (moves heavy-light will
be selected up by both metrics). As a result at the end of game we
will have more moves heavy-light.
In other words, light pegs first remove competing medium pegs and
then heavy pegs making lifting penalty smaller.
Actually, slightly weaker metric is better.
I played with “buy two tickets”:
Competition result 38976.72
Result with (C0+CV*d)./board(F(h)) 38792.95
Result with (C0+CV*d)./(board(F(h)).^0.6) 38580.22
Result with (C0+CV*d)./(board(F(h))+1) 38536.85

Sergey Yurgenson wrote:
>
>
> I agree with srach, the number of moves is limited (It is limited
> by
> number of pegs).
> My explanation of new metric is simpler:
> New metric gives preferences to moves when medium weighted pegs are
> tacking out by light pegs (medium-light) comparing to old metric
> heavier pegs being tacking out by medium pegs (moves heavy-light
> will
> be selected up by both metrics). As a result at the end of game we
> will have more moves heavy-light.
> In other words, light pegs first remove competing medium pegs and
> then heavy pegs making lifting penalty smaller.
> Actually, slightly weaker metric is better.
> I played with “buy two tickets”:
> Competition result 38976.72
> Result with (C0+CV*d)./board(F(h)) 38792.95
> Result with (C0+CV*d)./(board(F(h)).^0.6) 38580.22
> Result with (C0+CV*d)./(board(F(h))+1) 38536.85

Interesting. The weaker metric is also better for solveri. For "Buy a
ticket" I got the following results:
Original result: 39072.4778
with (C0+CV*d)./board(F(h)) 38866.2520
with (C0+CV*d)./(board(F(h))+1) 38567.5729
plus solveri metric hop_value/(liftPenalty+0.4)+1 38322.2292

It is an amazing improvement without increase computing time!

Yi

Yi Cao wrote:
> Interesting. The weaker metric is also better for solveri. For "Buy
> a
> ticket" I got the following results:
> Original result: 39072.4778
> with (C0+CV*d)./board(F(h)) 38866.2520
> with (C0+CV*d)./(board(F(h))+1) 38567.5729
> plus solveri metric hop_value/(liftPenalty+0.4)+1 38322.2292
>
> It is an amazing improvement without increase computing time!
>
> Yi
  
I agree. We already lower than 3min competition (“Best Result”).
Unfortunately current contest format does not encourage open exchange
of ideas during competition.

Sergey (SY)

Hannes Naudé wrote:
[...]
> But the number of moves is NOT limited as such and this is why the
> first metric is wrong. The only sense in which the number of moves
> are limited is that at some point you will reach a board
> configuration that does not allow any further legal moves and you
> will be stuck. But there is no reason to believe that the second
> approach will get stuck any earlier (on average) than the first.
> How
> early you get stuck is largely determined by the number of moves
> your
> solver can lookahead.

Like SY already mentioned, I would think that the number of moves is
indeed limited by the number of pegs on the board. Anyway, my comment
was not in favor for the first metric or against the second one
proposed by you. I was just curious.

Best,
srach

Nick Howe wrote:
>
>
> Incidentally, here is a solution to the Weighted English Board with
> a
> score of 359. It is not as satisfying since it leaves 4 pegs
> behind,
> but the score is lower.
>
> 4 2 4 4
> 6 3 4 3
> 5 5 5 3
> 7 5 5 5
> 4 4 4 2
> 2 3 4 3
> 4 3 6 3
> 6 3 6 5
> 3 5 3 3
> 3 7 3 5
> 5 7 3 7
> 5 5 5 7
> 3 2 3 4
> 3 4 3 6
> 3 6 5 6
> 7 3 7 5
> 7 5 5 5
> 5 5 3 5
> 1 4 3 4
> 3 4 3 6
> 4 1 4 3
> 1 5 3 5
> 5 1 5 3
> 5 3 3 3
> 3 6 3 4
> 3 4 3 2
> 5 7 5 5

Well done! I would say this is a near optimal solution. It does not
matter it leaves 4 pegs because the final score will be sum of pegs
left + sum of lifting pegs. Hence, it is equivalent: a peg is used
for lifting then removed later or the same peg is left in the board
without touch. A trick of this solution which makes the score is so
low is that it repeatly uses pegs with scores 1 and 2 as lifting
pegs. In Lucio's solution, each lifting peg has been used only once.
This is an example which supports the principle of the ratio metric.

Yi

srach wrote:
 Anyway, my
> comment
> was not in favor for the first metric or against the second one
> proposed by you. I was just curious.
>
> Best,
> srach

No worries mate. I understood your comment the way it was intended.
Besides, criticism of the approach is exactly what I was after. By no
means do I believe that the ratio metric is the final solution. This
process of feeding off of each other's ideas is what I enjoy most
about these contests.

I still do not quite understand the "we are limited by the number of
pegs on the board" argument. (An example of what I mentioned earlier:
I tend not to follow many discussions on here, I'm a bit slow that
way ;-)) Will sleep on it and get back to you.

Cheers
H

Hannes Naudé wrote:
[...]
> I still do not quite understand the "we are limited by the number
> of
> pegs on the board" argument.

For each move you complete, you have to remove one peg (the one you
jumped across). Thus, if you have N pegs on your board, you can
perform a maximum of N-1 jumps before you run out off pegs to jump
across. The N-th peg will always stay on the board.

Best,
srach

Hannes Naudé wrote:
>
>
> srach wrote:
> Anyway, my
>> comment
>> was not in favor for the first metric or against the second one
>> proposed by you. I was just curious.
>>
>> Best,
>> srach
>
> No worries mate. I understood your comment the way it was intended.
> Besides, criticism of the approach is exactly what I was after. By
> no
> means do I believe that the ratio metric is the final solution.
> This
> process of feeding off of each other's ideas is what I enjoy most
> about these contests.
>
> I still do not quite understand the "we are limited by the number
> of
> pegs on the board" argument. (An example of what I mentioned
> earlier:
> I tend not to follow many discussions on here, I'm a bit slow that
> way ;-)) Will sleep on it and get back to you.
>
> Cheers
> H

In terms of the limitation of number of moves, I think both of you
are right, just different view point. Natually, the number of moves
of a game has a top limit, which is the number of pegs -1. However,
this actually is not a real limitation to an algorithm because
because one never requires more than this number of moves.

In terms of ratio metric, my explanation is that it actually a way
to trade off a multi-objective optimization problem. If we can
perform a brute force search, the metric is uniquely determined.
However, we can only have limited numbers of searchs locally in a
stage. That means the local optimal solution may not lead to the
global optimal. Therefore, we have many different way to "guess" what
metric would lead to the global optimal. Here, we end up with two
ideas, maximum I1=board(M0)-board(F0) or I2=minimize board(F). The
ratio metric I1/(I2+alpha) is a way to trade off these two goals.
Another way is I1 + alpha*I2.

Yi

Yi Cao wrote:
> In terms of ratio metric, my explanation is that it actually a way
> to trade off a multi-objective optimization problem. If we can
> perform a brute force search, the metric is uniquely determined.
> However, we can only have limited numbers of searchs locally in a
> stage. That means the local optimal solution may not lead to the
> global optimal. Therefore, we have many different way to "guess"
> what
> metric would lead to the global optimal. Here, we end up with two
> ideas, maximum I1=board(M0)-board(F0) or I2=minimize board(F). The
> ratio metric I1/(I2+alpha) is a way to trade off these two goals.
> Another way is I1 + alpha*I2.
>
> Yi

I suspect that the ratio metric is best used towards the start of the
search, since it tries to set up high-scoring moves later in the
game. The original metric will probably be best towards the end,
since it prioritizes the actual measured score. Perhaps a smooth
tradeoff that shifts the parameters from one to the other would work
best.

Nick Howe wrote:
>
> I suspect that the ratio metric is best used towards the start of
> the
> search, since it tries to set up high-scoring moves later in the
> game. The original metric will probably be best towards the end,
> since it prioritizes the actual measured score. Perhaps a smooth
> tradeoff that shifts the parameters from one to the other would
> work
> best.

I have the similar feeling and tried to include the current step
index t into the metric, for example,
(C0+CV*d)./(board(F(h))+alpha*log(t)) and
(C0+CV*d)./(board(F(h))).^((pegCound-t)/pegCound) but none was
successful.

Yi

Yi Cao wrote:
>
>
> Nick Howe wrote:
>>
>> I suspect that the ratio metric is best used towards the start
of
>> the
>> search, since it tries to set up high-scoring moves later in
the
>> game. The original metric will probably be best towards the
end,
>> since it prioritizes the actual measured score. Perhaps a
smooth
>> tradeoff that shifts the parameters from one to the other would
>> work
>> best.
>
> I have the similar feeling and tried to include the current step
> index t into the metric, for example,
> (C0+CV*d)./(board(F(h))+alpha*log(t)) and
> (C0+CV*d)./(board(F(h))).^((pegCound-t)/pegCound) but none was
> successful.
>
> Yi

I was trying to switch from one metric to another if number of pegs
on board is less than N, but without success too.

Another unsuccessful idea – “punish” for removing lightest pegs from
board (or maybe my implementation was incorrect). The idea was to
prevent removing light pegs during multijump sequences.

Just minor additional comment:
New metric has to be applied to “negative moves” in different way.
When I changed code accordingly:

If v<0 …… (C0+CV*d).*board(F(h))

final result went down by
additional 70 points (result of “buy two tickets” with all discussed
modifications
now is 38240.9693)

Sergey

Another way of looking at it is this: early in the game, we can
afford to lift relatively heavy weights because there is a high
probability we'll have a chance to remove them later. As the board
clears, it is more important to avoid lifting heavy pegs.

This metric gives an improvement:

(C0+CV*d) ./ ( board(F(h)) + 0.2* avgPeg*(1-fracClear^2))

where avgPeg is the mean value of remaining pegs (to give a
meaningful scale to the added term) and fracClear is the fraction of
all positions that don't have pegs in them. This gives a result of
38498.9517 with Buy a ticket, compared with 38624.5902 for (C0+CV*d)
./ ( board(F(h))+1) ). There is a time penalty (about 5%) for keeping
these board statistics up to date.

Nathan

On May 20, 10:01 pm, "Yi Cao" <y...@cranfield.ac.uk> wrote:
> Nick Howe wrote:
>
> > I suspect that the ratio metric is best used towards the start
of
> > the
> > search, since it tries to set up high-scoring moves later in
the
> > game. The original metric will probably be best towards the
end,
> > since it prioritizes the actual measured score. Perhaps a
smooth
> > tradeoff that shifts the parameters from one to the other
would
> > work
> > best.
>
> I have the similar feeling and tried to include the current step
> index t into the metric, for example,
> (C0+CV*d)./(board(F(h))+alpha*log(t)) and
> (C0+CV*d)./(board(F(h))).^((pegCound-t)/pegCound) but none was
> successful.
>
> Yi