Got Questions? Get Answers.
Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Fall 2011 MATLAB Contest, November 2 - November 9

Subject: Fall 2011 MATLAB Contest, November 2 - November 9

From: Helen Chen

Date: 2 Nov, 2011 15:44:08

Message: 1 of 73

Dear MATLAB Central Community -

The Fall MATLAB Programming Contest will start at noon, Boston time/16:00 UTC today, Wednesday November 2 and will run through noon, Boston time the following Wednesday November 9.

Please post any comments or questions about this contest as replies to this thread so that we can track the conversations.

If you have not participated in any of our past contests, you can learn more by going to the contest website at http://www.mathworks.com/matlabcentral/contest/

We look forward to seeing you online!
 
Best,
Helen Chen
MATLAB Central Team

Subject: Fall 2011 MATLAB Contest, November 2 - November 9

From: Helen Chen

Date: 2 Nov, 2011 16:12:11

Message: 2 of 73

And we're off and running! This season's contest is Vines! You can participate by going to http://www.mathworks.com/matlabcentral/contest/contests/34 .

Have fun and good luck!
Helen

"Helen Chen" <helen.chen@mathworks.com> wrote in message <j8rog8$li5$1@newscl01ah.mathworks.com>...
> Dear MATLAB Central Community -
>
> The Fall MATLAB Programming Contest will start at noon, Boston time/16:00 UTC today, Wednesday November 2 and will run through noon, Boston time the following Wednesday November 9.
>
> Please post any comments or questions about this contest as replies to this thread so that we can track the conversations.
>
> If you have not participated in any of our past contests, you can learn more by going to the contest website at http://www.mathworks.com/matlabcentral/contest/
>
> We look forward to seeing you online!
>
> Best,
> Helen Chen
> MATLAB Central Team

Subject: Fall 2011 MATLAB Contest, November 2 - November 9

From: proecsm

Date: 2 Nov, 2011 17:15:29

Message: 3 of 73

"Helen Chen" <helen.chen@mathworks.com> wrote in message <j8rq4r$r74$1@newscl01ah.mathworks.com>...
> And we're off and running! This season's contest is Vines! You can participate by going to http://www.mathworks.com/matlabcentral/contest/contests/34 .
>
> Have fun and good luck!
> Helen
>
> "Helen Chen" <helen.chen@mathworks.com> wrote in message <j8rog8$li5$1@newscl01ah.mathworks.com>...
> > Dear MATLAB Central Community -
> >
> > The Fall MATLAB Programming Contest will start at noon, Boston time/16:00 UTC today, Wednesday November 2 and will run through noon, Boston time the following Wednesday November 9.
> >
> > Please post any comments or questions about this contest as replies to this thread so that we can track the conversations.
> >
> > If you have not participated in any of our past contests, you can learn more by going to the contest website at http://www.mathworks.com/matlabcentral/contest/
> >
> > We look forward to seeing you online!
> >
> > Best,
> > Helen Chen
> > MATLAB Central Team

I think the modified board shown in the worked example on the rules page is incorrect, can anyone confirm?

Subject: Fall 2011 MATLAB Contest, November 2 - November 9

From: Richard

Date: 2 Nov, 2011 17:27:28

Message: 4 of 73

The rules have a minor typo in that the printed table does not replace the 15 with the 20. Minor confusion.

raz

Subject: Fall 2011 MATLAB Contest, November 2 - November 9

From: Enkh

Date: 2 Nov, 2011 17:50:14

Message: 5 of 73

You're right. The example modified board has a typo. The 15 should be a 20.

"proecsm" wrote in message <j8rtrh$avl$1@newscl01ah.mathworks.com>...
> I think the modified board shown in the worked example on the rules page is incorrect, can anyone confirm?

Subject: Fall 2011 MATLAB Contest, November 2 - November 9

From: Ned Gulley

Date: 2 Nov, 2011 18:00:15

Message: 6 of 73

Enkh wrote:
> You're right. The example modified board has a typo. The 15 should be a 20.

I've fixed this in the rules. Thanks for pointing out the problem.

Subject: Fall 2011 MATLAB Contest, November 2 - November 9

From: Nan Liu

Date: 2 Nov, 2011 19:02:28

Message: 7 of 73

It looks that you slide tiles after the path is found. Path does not change once it is found. Is it correct?





"Helen Chen" <helen.chen@mathworks.com> wrote in message <j8rog8$li5$1@newscl01ah.mathworks.com>...
> Dear MATLAB Central Community -
>
> The Fall MATLAB Programming Contest will start at noon, Boston time/16:00 UTC today, Wednesday November 2 and will run through noon, Boston time the following Wednesday November 9.
>
> Please post any comments or questions about this contest as replies to this thread so that we can track the conversations.
>
> If you have not participated in any of our past contests, you can learn more by going to the contest website at http://www.mathworks.com/matlabcentral/contest/
>
> We look forward to seeing you online!
>
> Best,
> Helen Chen
> MATLAB Central Team

Subject: Fall 2011 MATLAB Contest, November 2 - November 9

From: Alan Chalker

Date: 2 Nov, 2011 19:21:11

Message: 8 of 73

It appears that the contest machinery is broken somehow. All entries submitted for the past 2 hours or so are showing as 'pending queue'.

Subject: Fall 2011 MATLAB Contest, November 2 - November 9

From: Helen Chen

Date: 2 Nov, 2011 23:16:28

Message: 9 of 73

"Alan Chalker" wrote in message <j8s577$7mu$1@newscl01ah.mathworks.com>...
> It appears that the contest machinery is broken somehow. All entries submitted for the past 2 hours or so are showing as 'pending queue'.

Thanks for reporting this Alan. The queue seems to be processing now. All the entries have been scored now.

Thank you to everyone for your patience with this hiccup!

Helen

Subject: Fall 2011 MATLAB Contest, November 2 - November 9

From: Yongjia steven

Date: 2 Nov, 2011 23:42:14

Message: 10 of 73

just a question, is it a vine that the it's index start from first to last in matrix? obviously it have maximum value (sum(board)) if it is a vine.

Subject: Fall 2011 MATLAB Contest, November 2 - November 9

From: Yongjia steven

Date: 2 Nov, 2011 23:43:10

Message: 11 of 73

just a question, is it a vine that the it's index start from first to last in matrix? obviously it have maximum value (sum(board)) if it is a vine.

Subject: Fall 2011 MATLAB Contest, November 2 - November 9

From: Peter Stobbe

Date: 2 Nov, 2011 23:48:20

Message: 12 of 73

Just in case anyone else is as forgetful as I am - I had to look up the precise definition of the phrase "monotone increasing". I wasn't sure if it meant "strictly increasing" or "nondecreasing". It's the latter.

Subject: pass/fail visible in darkness

From: Michael Bindschadler

Date: 3 Nov, 2011 00:14:28

Message: 13 of 73

I just noticed that it is possible to see whether an entry passed or failed for this contest, even in Darkness. That's nice, since in many previous contests I've accidentally left in a debugging command which disqualified many a Darkness entry. Thanks, contest team!

Subject: Fall 2011 MATLAB Contest, November 2 - November 9

From: Enkh

Date: 3 Nov, 2011 00:22:28

Message: 14 of 73

"Nan Liu" <liunan22@gmail.com> wrote in message <j8s444$3vm$1@newscl01ah.mathworks.com>...
> It looks that you slide tiles after the path is found. Path does not change once it is found. Is it correct?

It appears I posted to the wrong board. Sorry for the delay.

For scoring, the slides are processed first then anything on the vine is accounted for.

Otherwise, the sliding moves don't change the indexing of the board. So whether you choose to determine the path or the sliding first shouldn't affect the mechanics.

Subject: Fall 2011 MATLAB Contest, November 2 - November 9

From: Enkh

Date: 3 Nov, 2011 00:28:28

Message: 15 of 73

"Yongjia steven" <jaodan2003@yahoo.com> wrote in message <j8skie$qut$1@newscl01ah.mathworks.com>...
> just a question, is it a vine that the it's index start from first to last in matrix? obviously it have maximum value (sum(board)) if it is a vine.

I don't understand the question fully. But taking a stab at it, 'sum(board(:))' just returns the total points available on the board. It does not mean all points on the board can be obtained by a single vine, this may or may not be possible.

Subject: pass/fail visible in darkness

From: Enkh

Date: 3 Nov, 2011 00:30:28

Message: 16 of 73

@Peter
Thanks for clarifying the definition!

@Michael
Thanks for the input!

Subject: Fall 2011 MATLAB Contest, November 2 - November 9

From: Yongjia steven

Date: 3 Nov, 2011 00:44:10

Message: 17 of 73

thanks Enkh, my question is, can I choose a vine who's indices are from first index of board (1,1) to last index (n,n)? because there is no length and direction limitation.



"Enkh " <mandakh.enkh@mathworks.com> wrote in message <j8sn7c$4n7$1@newscl01ah.mathworks.com>...
> "Yongjia steven" <jaodan2003@yahoo.com> wrote in message <j8skie$qut$1@newscl01ah.mathworks.com>...
> > just a question, is it a vine that the it's index start from first to last in matrix? obviously it have maximum value (sum(board)) if it is a vine.
>
> I don't understand the question fully. But taking a stab at it, 'sum(board(:))' just returns the total points available on the board. It does not mean all points on the board can be obtained by a single vine, this may or may not be possible.

Subject: Fall 2011 MATLAB Contest, November 2 - November 9

From: Enkh

Date: 3 Nov, 2011 00:59:15

Message: 18 of 73

"Yongjia steven" <jaodan2003@yahoo.com> wrote in message <j8so4q$7bi$1@newscl01ah.mathworks.com>...
> thanks Enkh, my question is, can I choose a vine who's indices are from first index of board (1,1) to last index (n,n)? because there is no length and direction limitation.

It depends on the board. While there is no hard-coded length and direction limit, the fact that your vine can only move to non-decreasing numbers and can't overlap itself means the path of your vine is restricted by the numbers of the board.

Subject: Fall 2011 MATLAB Contest, November 2 - November 9

From: Robert Macrae

Date: 3 Nov, 2011 01:06:14

Message: 19 of 73

"Yongjia steven" <jaodan2003@yahoo.com> wrote

> can I choose a vine who's indices are from first index of board (1,1) to last index (n,n)? because there is no length and direction limitation.

You could, but because the contents of the vine would not be monotone increasing the grade function would delete most of it. The easiest way to see what is going on is to write a function like the one you suggest and then debug grade to see what happens to it and how it is scored.

Robert

Subject: Fall 2011 MATLAB Contest, November 2 - November 9

From: Yongjia steven

Date: 3 Nov, 2011 01:18:13

Message: 20 of 73

Thanks, I got the point.

"Robert Macrae" wrote in message <j8spe6$b3g$1@newscl01ah.mathworks.com>...
> "Yongjia steven" <jaodan2003@yahoo.com> wrote
>
> > can I choose a vine who's indices are from first index of board (1,1) to last index (n,n)? because there is no length and direction limitation.
>
> You could, but because the contents of the vine would not be monotone increasing the grade function would delete most of it. The easiest way to see what is going on is to write a function like the one you suggest and then debug grade to see what happens to it and how it is scored.
>
> Robert

Subject: Fall 2011 MATLAB Contest, November 2 - November 9

From: mavs favs

Date: 3 Nov, 2011 07:34:11

Message: 21 of 73

Question from me:

We can slide into only 15tile? So the board has to have one and only one 15tile?

Thanks!

Subject: Fall 2011 MATLAB Contest, November 2 - November 9

From: Robert Macrae

Date: 3 Nov, 2011 10:48:10

Message: 22 of 73

"mavs favs" wrote in message <j8tg5j$g9p$1@newscl01ah.mathworks.com>...

> We can slide into only 15tile? So the board has to have one and only one 15tile?

You can slide any tile. If the destination has a value it is overwritten by what moves in. After a lot of moves you usually have several spaces (zeros) on the board.

Robert

Subject: Fall 2011 MATLAB Contest, November 2 - November 9

From: Martin Rees

Date: 3 Nov, 2011 11:24:27

Message: 23 of 73

Is the contest broken?
There is a big list of entries saying 'Pending Queue'.

Regards,
Martin

"Helen Chen" <helen.chen@mathworks.com> wrote in message <j8rog8$li5$1@newscl01ah.mathworks.com>...
> Dear MATLAB Central Community -
>
> The Fall MATLAB Programming Contest will start at noon, Boston time/16:00 UTC today, Wednesday November 2 and will run through noon, Boston time the following Wednesday November 9.
>
> Please post any comments or questions about this contest as replies to this thread so that we can track the conversations.
>
> If you have not participated in any of our past contests, you can learn more by going to the contest website at http://www.mathworks.com/matlabcentral/contest/
>
> We look forward to seeing you online!
>
> Best,
> Helen Chen
> MATLAB Central Team

Subject: Fall 2011 MATLAB Contest, November 2 - November 9

From: Lindsay Coutinho

Date: 3 Nov, 2011 12:13:13

Message: 24 of 73

The queue is back up and running! Sorry about the backup. The queue seems to be choking on submissions with non-English comments, so for now, we have removed these.

Again, my apologies for the inconvenience.

Lindsay and the Contest Team

"Martin Rees" wrote in message <j8ttlb$p4p$1@newscl01ah.mathworks.com>...
> Is the contest broken?
> There is a big list of entries saying 'Pending Queue'.
>
> Regards,
> Martin

Subject: Fall 2011 MATLAB Contest, November 2 - November 9

From: Alan Chalker

Date: 3 Nov, 2011 16:04:11

Message: 25 of 73

"Robert Macrae" wrote in message <j8trha$j13$1@newscl01ah.mathworks.com>...
> "mavs favs" wrote in message <j8tg5j$g9p$1@newscl01ah.mathworks.com>...
>
> > We can slide into only 15tile? So the board has to have one and only one 15tile?
>
> You can slide any tile. If the destination has a value it is overwritten by what moves in. After a lot of moves you usually have several spaces (zeros) on the board.
>
> Robert

I don't believe this is correct. You'll only end up with 1 space. Only the first move overwrights a tile. All subsequent moves must be 'connected' to that empty tile in order to be valid.

Subject: Fall 2011 MATLAB Contest, November 2 - November 9

From: Robert Macrae

Date: 3 Nov, 2011 16:33:28

Message: 26 of 73

"Alan Chalker" wrote in message <j8ue1r$lja$1@newscl01ah.mathworks.com>...

> > > We can slide into only 15tile? So the board has to have one and only one 15tile?
> >
> > You can slide any tile. If the destination has a value it is overwritten by what moves in. After a lot of moves you usually have several spaces (zeros) on the board.
>
> I don't believe this is correct. You'll only end up with 1 space. Only the first move overwrights a tile. All subsequent moves must be 'connected' to that empty tile in order to be valid.

I'm pretty sure. From rules page "For this contest, you don't have to worry about whether or not the square you're moving to is empty"; also I haven't seen any evidence of grade penalising my mover code and it leaves plenty of spaces.

Robert

Subject: Fall 2011 MATLAB Contest, November 2 - November 9

From: Lucio Cetto

Date: 3 Nov, 2011 16:35:27

Message: 27 of 73

You can actually blow away all the tiles if you want, of course if you do so your vine cannot have any value and you'll get the worst possible score for that board. In a winning strategy, you may want to blow the less number of tiles possible, so your vine can include more of them.
HTH
Lucio

"Alan Chalker" wrote in message <j8ue1r$lja$1@newscl01ah.mathworks.com>...
> "Robert Macrae" wrote in message <j8trha$j13$1@newscl01ah.mathworks.com>...
> > "mavs favs" wrote in message <j8tg5j$g9p$1@newscl01ah.mathworks.com>...
> >
> > > We can slide into only 15tile? So the board has to have one and only one 15tile?
> >
> > You can slide any tile. If the destination has a value it is overwritten by what moves in. After a lot of moves you usually have several spaces (zeros) on the board.
> >
> > Robert
>
> I don't believe this is correct. You'll only end up with 1 space. Only the first move overwrights a tile. All subsequent moves must be 'connected' to that empty tile in order to be valid.

Subject: Fall 2011 MATLAB Contest, November 2 - November 9

From: Alan Chalker

Date: 3 Nov, 2011 17:08:27

Message: 28 of 73

"Robert Macrae" wrote in message <j8ufoo$rbt$1@newscl01ah.mathworks.com>...
>
> I'm pretty sure. From rules page "For this contest, you don't have to worry about whether or not the square you're moving to is empty"; also I haven't seen any evidence of grade penalising my mover code and it leaves plenty of spaces.
>
> Robert

You're correct. Looking at the grade.m file shows this is indeed the case. Sorry for the confusion.

Subject: Fall 2011 MATLAB Contest, November 2 - November 9

From: Alan Chalker

Date: 3 Nov, 2011 19:46:13

Message: 29 of 73

Since I misunderstood how the moves were being scored, I decided to update the visualize abilities of the runcontest code to better illustrate what's going on. I've uploaded it to the File Exchange since I thought it might be helpful to others: http://www.mathworks.com/matlabcentral/fileexchange/33600

The additions I made are:
-Add board # to the tile so you know which board you are looking at

-Color code the vine. Green parts are 'good' and scored, red parts are 'bad' and truncated by the grade code. An arrow shows the 'start direction' of the vine, while and X shows the end of it.

-Color code the moves. Blue moves are 'good' and scored, yellow moves are 'bad' and truncated by the grade code. A circle indicates the 'source' of the move.

Hopefully you all will find this helpful too.

Subject: Fall 2011 MATLAB Contest, November 2 - November 9

From: Helen Chen

Date: 3 Nov, 2011 20:45:27

Message: 30 of 73

We have applied a patch to the contest engine to fix the queue stalling problem experienced last night and again this morning. We found that non-english comments in submissions was causing the scoring infrastructure to choke. Our test submission made it through the queue successfully, so Twilight should be much less distracting that Darkness was!

Thank you for your patience with us as we worked out the fix today. We do apologize for the inconvenience this caused you. Also, thanks to those of you who took the time to report the problem!

Helen

"Lindsay Coutinho" wrote in message <j8u0gp$4dl$1@newscl01ah.mathworks.com>...
> The queue is back up and running! Sorry about the backup. The queue seems to be choking on submissions with non-English comments, so for now, we have removed these.
>
> Again, my apologies for the inconvenience.
>
> Lindsay and the Contest Team
>
> "Martin Rees" wrote in message <j8ttlb$p4p$1@newscl01ah.mathworks.com>...
> > Is the contest broken?
> > There is a big list of entries saying 'Pending Queue'.
> >
> > Regards,
> > Martin

Subject: Fall 2011 MATLAB Contest, November 2 - November 9

From: Robert Macrae

Date: 3 Nov, 2011 22:33:10

Message: 31 of 73

"Alan Chalker" wrote in message <j8ur25$8cu$1@newscl01ah.mathworks.com>...

> Since I misunderstood how the moves were being scored, I decided to update the visualize abilities of the runcontest code to better illustrate what's going on.

I like the idea of colour-coding vines, but your implementation only works for boards with no moves -- you need to validate and apply the moves before testing the vine.

At least I hope so, if not thats why Alfonso is scoring 1,000,000 points better than me 8-/

Robert

Subject: Fall 2011 MATLAB Contest, November 2 - November 9

From: Alan Chalker

Date: 4 Nov, 2011 12:49:30

Message: 32 of 73

"Robert Macrae" wrote in message <j8v4r6$a5k$1@newscl01ah.mathworks.com>...
> "Alan Chalker" wrote in message <j8ur25$8cu$1@newscl01ah.mathworks.com>...
>
> > Since I misunderstood how the moves were being scored, I decided to update the visualize abilities of the runcontest code to better illustrate what's going on.
>
> I like the idea of colour-coding vines, but your implementation only works for boards with no moves -- you need to validate and apply the moves before testing the vine.
>
> At least I hope so, if not thats why Alfonso is scoring 1,000,000 points better than me 8-/
>
> Robert

Robert:

Unless there is some bug I can't find, it indeed works for boards with both moves and no moves. I only made changes to the visualization code, not to the grading code. Thus the grading code should work the same as before, which involves updating the board with the moves before testing the vine. The visualization shows the original board layout, with the moves and vine overlaid. I'm not sure it makes sense to show the final modified board layout.

Subject: Fall 2011 MATLAB Contest, November 2 - November 9

From: Robert Macrae

Date: 4 Nov, 2011 13:17:14

Message: 33 of 73

"Alan Chalker" wrote in message <j90n0q$3ol$1@newscl01ah.mathworks.com>...

> Unless there is some bug I can't find, it indeed works for boards with both moves and no moves. I only made changes to the visualization code, not to the grading code. Thus the grading code should work the same as before, which involves updating the board with the moves before testing the vine. The visualization shows the original board layout, with the moves and vine overlaid. I'm not sure it makes sense to show the final modified board layout.

OK, but your test for good/bad vines looks at the unmodified board. If moves have been made then a vine that would be bad on the old board may be good on the modified one. Scoring isn't affected but the visual distinction between good and bad vines won't be right?

Robert

Subject: back into darkness

From: Leendert Combee

Date: 4 Nov, 2011 16:08:14

Message: 34 of 73

Twilight just ended, and now we're back into darkness! Scored and codes are not visible in daylight it says. Ergo sum : darkness. Oh well....

Subject: back into darkness

From: Helen Chen

Date: 4 Nov, 2011 16:34:11

Message: 35 of 73

Thanks Leendert! This is fixed now.

Helen

"Leendert Combee" wrote in message <j912le$g7d$1@newscl01ah.mathworks.com>...
> Twilight just ended, and now we're back into darkness! Scored and codes are not visible in daylight it says. Ergo sum : darkness. Oh well....

Subject: back into darkness

From: Nicholas Howe

Date: 5 Nov, 2011 01:57:29

Message: 36 of 73

I promised to write a description of what's going on inside "Revenge of Antichaff" to give a leg up to anybody who was thinking about joining the fun. So here it is -- I hope it encourages somebody who was on the fence about jumping in.

The most important piece is the trickle2 function, which I originally wrote as a standalone submission. It carries out a fairly fast, greedy search for the most valuable vine possible without moving any tiles. It considers tiles in order from highest to lowest, updating their cumulative vine potential based on the highest potential of any bigger neighbors, or starting from scratch if there are none. It also stores an index pointing to the neighbor with the biggest vine potential. Once the whole image has been processed, we just need to look for the largest vine potential found, which will be the tail of the best vine, and follow the indices up the vine.

I think this will find the optimal vine if there are no plateaus of more than one pixel of equal value. But plateaus make the problem much harder, and aren't perfectly solved. To try to do a little better I apply two heuristics to improve the vine originally found. First, I extend it as far as I can at the top. (The method above will end the vine on just one pixel of a multi-pixel top plateau.) Second, I look for areas where the vine can be expanded to further fill a plateau.

All this works pretty well: "Revenge of Antichaff" adopts this solution for 71 of the 100 training boards. But the boards vary a lot, and there are some that it just doesn't do very well on. Furthermore, it isn't making any use of the ability to move tiles. If the board pixel values are random or close to it, then the best vine available tends to be pretty short. If you can move things around, you'll probably do a lot better.

With enough moves, you can pretty much ignore the starting configuration and construct whatever arrangement of tiles you like. Moving all the tiles to the left side of the image turned out to be easier for me computationally than trying to connect them in place, so that's what I did in the routine called 'pusher'. Basically, I find the biggest tile available and move it to the upper left, and then put the next biggest under it, and so on, building up a winding snake pattern. At each step I find the largest remaining tile and move it to the goal position, choosing to move it either horizontally or vertically depending on which neighbor is smaller. (You don't want to zero out the larger tiles if you can help it because you'd like to incorporate them in your vine if possible.) The version used in "Revenge of Antichaff" also has a target protection scheme that moves some tiles slated
for destruction out of the way if they in turn have smaller neighbors next to them. So anyway you move tiles to assemble a snaking ramp, and when you run out of moves you call trickle2 to build the vine.

This routine actually gets called four times, with the image flipped around so that the snake accumulates on each of the four sides. The success varies enough to make this worthwhile. (You could actually generate eight different configurations to try, but I compromised at four to save on running time. The early bird winner works by choosing a different four of the eight configurations -- vertically flipping the right-hand accumulator, which works better on a few images.)

All this wasn't enough to catch Alfonso's clever entries, and I couldn't think of any other general approaches to try. But the beauty of this contest topic is that there are many different subcategories of boards, and a specialized approach that solves one of them very well can make a difference. I decided to focus on a category of board that the methods above weren't solving very well, exemplified by boards 47 and 74 on the training set. These boards look like a perfect snaking ramp, with a small minority of noise pixels getting in the way and gumming things up. If you can detect the noise pixels and move the others together, you unite the snake and get one very long and valuable vine. So that's what 'dofilter' does: it identifies noise pixels and shoves the rest together. The result is very effective on the small minority of boards that have the necessary form.

The moral of this all for me is that it's easier than ever to get involved in this contest. You don't need to come up with a fancy solution to everything. Just identify one type of board that the current solution isn't getting as well as it should. Build a better specialized solver for that category, and add it to the mix. With a bit of luck, when combined with the group's collective wisdom, your entry will be sitting at the top of the heap!

Subject: Fall 2011 MATLAB Contest, November 2 - November 9

From: Alan Chalker

Date: 5 Nov, 2011 04:16:14

Message: 37 of 73

"Robert Macrae" wrote in message <j90okq$9dp$1@newscl01ah.mathworks.com>...
>
> OK, but your test for good/bad vines looks at the unmodified board. If moves have been made then a vine that would be bad on the old board may be good on the modified one. Scoring isn't affected but the visual distinction between good and bad vines won't be right?
>
> Robert

Great point! And an easy fix to make, since I can just copy the relevant part from the grade.m code. Thanks!

Subject: back into darkness

From: Volkan

Date: 5 Nov, 2011 15:37:30

Message: 38 of 73

"Nicholas Howe" wrote in message <j92569$84s$1@newscl01ah.mathworks.com>...
> I promised to write a description of what's going on inside "Revenge of Antichaff" to give a leg up to anybody who was thinking about joining the fun. So here it is -- I hope it encourages somebody who was on the fence about jumping in.

Thank you Nick for the heads up, was just what I needed. Specializing on one puzzle type was the only thing I could do for the last contest, and it looks like I will have to do same here.

On a totally different note, I saw the "Japanese rules / Chinese rules" on the front page and just thought about the board game GO, for which there are slightly different rules for the two countries above. I was like "What now? Do we have two sets of rules for the same contest?" I had to click them to figure out they were just rules in different languages.

Happy coding and good luck to all,
Volkan

Subject: Statistics

From: Nicholas Howe

Date: 5 Nov, 2011 16:01:27

Message: 39 of 73

Something seems odd about the "results vs. cpu time" chart on the statistics page. The red line indicating the current leader at one point seems to jump backwards across several iso-lines. Is it possible that the chart is not computing something correctly?

Subject: Statistics

From: Helen Chen

Date: 5 Nov, 2011 22:06:10

Message: 40 of 73

Hi Nick -

We'll look into this.

Helen

"Nicholas Howe" wrote in message <j93mkn$suk$1@newscl01ah.mathworks.com>...
> Something seems odd about the "results vs. cpu time" chart on the statistics page. The red line indicating the current leader at one point seems to jump backwards across several iso-lines. Is it possible that the chart is not computing something correctly?

Subject: Statistics

From: the cyclist

Date: 5 Nov, 2011 22:37:10

Message: 41 of 73

The graph is incomplete, in that it does not account for node count and cyclomatic complexity, which both factor into the actual score. An entry that reduces those factors, while increasing the time and having a worse result, could nonetheless be the leader.

"Helen Chen" <helen.chen@mathworks.com> wrote in message <j94c0i$1b8$1@newscl01ah.mathworks.com>...
> Hi Nick -
>
> We'll look into this.
>
> Helen
>
> "Nicholas Howe" wrote in message <j93mkn$suk$1@newscl01ah.mathworks.com>...
> > Something seems odd about the "results vs. cpu time" chart on the statistics page. The red line indicating the current leader at one point seems to jump backwards across several iso-lines. Is it possible that the chart is not computing something correctly?

Subject: Fall 2011 MATLAB Contest, November 2 - November 9

From: Michael Bindschadler

Date: 6 Nov, 2011 08:28:13

Message: 42 of 73

It looks to me like the solver "alfie" has been doing most of the work on most of the boards, so I've been working on taking it apart to understand it. I've just submitted a partially commented version of it. It doesn't have the other solvers in it, so it won't score as highly, but if you're interested, take a look. If I get a chance I'll work on it some more.

-Mike Bindschadler

Subject: Fall 2011 MATLAB Contest, November 2 - November 9

From: the cyclist

Date: 6 Nov, 2011 15:24:11

Message: 43 of 73

"Alan Chalker" wrote in message <j92dae$1ho$1@newscl01ah.mathworks.com>...
> "Robert Macrae" wrote in message <j90okq$9dp$1@newscl01ah.mathworks.com>...
> >
> > OK, but your test for good/bad vines looks at the unmodified board. If moves have been made then a vine that would be bad on the old board may be good on the modified one. Scoring isn't affected but the visual distinction between good and bad vines won't be right?
> >
> > Robert
>
> Great point! And an easy fix to make, since I can just copy the relevant part from the grade.m code. Thanks!

Hey Alan. Did you edit your FEX program to reflect this?

Subject: back into darkness

From: Robert Macrae

Date: 6 Nov, 2011 16:34:13

Message: 44 of 73

"Nicholas Howe" wrote in message <j92569$84s$1@newscl01ah.mathworks.com>...

> I promised to write a description of what's going on inside "Revenge of Antichaff" to give a leg up to anybody who was thinking about joining the fun.

Great idea Nicholas, and though its a bit late I'll do the same for The Fragrant Honeysuckle. Actually our code seems to have set off down very similar trails, though obviously you managed to follow them a lot further!

In the face of the awesome efficiency of other vines I don't think my vine-growing code is at all competitive if plateaux are present. FWIW the idea was to grow up from the bottom and to handle plateaux by superimposing a back-and-forth pattern on them, with 4 possible orientations for the pattern. If there are no plateaux then the code from my earlier Gluvine entries is faster.

Boardwalk is very similar in concept to Pusher, though crucially I didn't think of trying multiple orientations. I aim to avoid wasting tiles by designating every 3rd row as a channel down which tiles move; this could be improved by making a guess at what tiles will actually be used and moving them out of the channel before they are squashed. The gain in average tile value would be modest, but average movelength would also be improved so more tiles could be added.

In principle growing a spiral in the centre of the board should lead to substantially lower average move lengths. Its much more work to calculate paths, but go on -- you know you want to 8-)

Monotonous echos Dofilter: a specialist solver for the maps that have a continuous back-and-forth gradient corrupted by relatively few obstacles. Since board 47 is very high-scoring it seems well worth solving these problems efficiently. The idea is to construct a trial vine, and whenever it turns upwards check if there are unused values in the row that can be used to overwrite whatever obstacle caused the turn. If so these are moved in. The test for what values should be moved isn't very clever, and ignores whether the adjacent row will have a suitable value to form a new link. Coding is very dull and iterative and I'm sure it could be much improved.

Robert

Subject: back into darkness

From: Nicholas Howe

Date: 7 Nov, 2011 01:50:13

Message: 45 of 73

We seem to think alike, Robert! I also considered a spiral and decided against it at least for the time being. Maybe someone else will try it. The multiple orientation trick has been used before on many other contests; I've been burned by others using it so I was determined to take advantage of it myself this time!

"Robert Macrae" wrote in message <j96cu5$5s3$1@newscl01ah.mathworks.com>...
> Boardwalk is very similar in concept to Pusher, though crucially I didn't think of trying multiple orientations. I aim to avoid wasting tiles by designating every 3rd row as a channel down which tiles move; this could be improved by making a guess at what tiles will actually be used and moving them out of the channel before they are squashed. The gain in average tile value would be modest, but average movelength would also be improved so more tiles could be added.
>
> In principle growing a spiral in the centre of the board should lead to substantially lower average move lengths. Its much more work to calculate paths, but go on -- you know you want to 8-)

Subject: back into darkness

From: Doug Hull

Date: 7 Nov, 2011 15:45:16

Message: 46 of 73

"Nicholas Howe" wrote in message <j92569$84s$1@newscl01ah.mathworks.com>...

> I think this will find the optimal vine if there are no plateaus of more than one pixel of equal value. But plateaus make the problem much harder, and aren't perfectly solved. To try to do a little better I apply two heuristics to improve the vine originally found. First, I extend it as far as I can at the top. (The method above will end the vine on just one pixel of a multi-pixel top plateau.) Second, I look for areas where the vine can be expanded to further fill a plateau.

We made sure there were plenty of plateaus for that exact reason. Just another service we provide! Good to see someone noticed. :)

Nate, one of our internal contestants in the beta, found that plateaus caused a lot of difficulties. Enkh made sure to add a class of boards that included them for you all!

-Doug

Subject: contest suite

From: Michael Bindschadler

Date: 7 Nov, 2011 22:19:29

Message: 47 of 73

I'm sure I'm not the first to notice this, but the real contest suite of boards must not contain any quite like board 10, with a very high limit (>15100) but low value overall (largest value <200), since the current leaders choke on this board in the test suite. This happens because no solvers actually get run in this case (alfi runs if the limit<15100, and the rest run if largest value>200). Running the current leader on the test suite actually gives you an error when use_more_moves implicitly assumes that the incoming vine is not empty.

Subject: contest suite

From: Enkh

Date: 7 Nov, 2011 22:45:31

Message: 48 of 73

"Michael Bindschadler" wrote in message <j99lhh$14s$1@newscl01ah.mathworks.com>...
> I'm sure I'm not the first to notice this, but the real contest suite of boards must not contain any quite like board 10, with a very high limit (>15100) but low value overall (largest value <200), since the current leaders choke on this board in the test suite. This happens because no solvers actually get run in this case (alfi runs if the limit<15100, and the rest run if largest value>200). Running the current leader on the test suite actually gives you an error when use_more_moves implicitly assumes that the incoming vine is not empty.

There should be boards very similar to it in the contest suite, but perhaps not any exactly like it to choke the solvers. Thanks for pointing this out!

Subject: Scoring plateaux

From: Robert Macrae

Date: 7 Nov, 2011 22:50:30

Message: 49 of 73

"Doug Hull" <hull@mathworks.SPAMPROOFcom> wrote in message <j98uec$7ef$1@newscl01ah.mathworks.com>...

> We made sure there were plenty of plateaus for that exact reason. Just another service we provide! Good to see someone noticed. :)

Doug,

If you are going to take credit for this, can I point out a problem? Your plateau levels average a score of about 3 per square, compared to 1000+ on the most valuable boards. Despite the great aesthetic appeal of the result, growing good vines are I think a couple of orders of magnitude less important than good tile-moving.

This is a pity, and it could have been fixed by simply multiplying the relevant board values by around 100... and in a way it echos the problem from the "crossword" problem, in which forming anything that looked like a real crossword was so under-rewarded that it was almost never worthwhile.

In a sense it isn't critical to the nature of the competition, but aesthetic results make it all more fun and should if possible be rewarded by the scoring.

Robert

Subject: Scoring plateaux

From: Volkan

Date: 8 Nov, 2011 00:44:14

Message: 50 of 73

"Robert Macrae" wrote in message <j99nbm$6s4$1@newscl01ah.mathworks.com>...

> If you are going to take credit for this, can I point out a problem? Your plateau levels average a score of about 3 per square, compared to 1000+ on the most valuable boards. Despite the great aesthetic appeal of the result, growing good vines are I think a couple of orders of magnitude less important than good tile-moving.

In previous contests sample and actual test suites were quite equivalent, but for this one I'm beginning to think that's not the case. I coded a solver to handle the structured boards (24 and 72) which gave astronomical result advantage in the sample suit. Unfortunately I realized the actual suite does have such board(s), but with low values and also different in some aspect (very thin perhaps?).

So there is the chance that there may be plateau levels in the hidden suite with boosted values. It is a long shot but may be worthwhile to go with this assumption, especially for people like me who ran out of easier ideas. (Another failed attempt by me was an optimal solver for 1 x n boards, which the hidden suite doesn't seem to contain.)

Volkan

Subject: Fall 2011 MATLAB Contest, November 2 - November 9

From: Alan Chalker

Date: 8 Nov, 2011 00:44:14

Message: 51 of 73

"the cyclist" wrote in message <j968qr$n3c$1@newscl01ah.mathworks.com>...
>
> Hey Alan. Did you edit your FEX program to reflect this?

I just did and it's been approved. Sorry for the delay, but I've been out of town for an extended weekend and not online.

Subject: Scoring plateaux

From: Enkh

Date: 8 Nov, 2011 02:00:29

Message: 52 of 73

"Robert Macrae" wrote in message <j99nbm$6s4$1@newscl01ah.mathworks.com>...
>
> Doug,
>
> If you are going to take credit for this, can I point out a problem? Your plateau levels average a score of about 3 per square, compared to 1000+ on the most valuable boards. Despite the great aesthetic appeal of the result, growing good vines are I think a couple of orders of magnitude less important than good tile-moving.
>
> This is a pity, and it could have been fixed by simply multiplying the relevant board values by around 100... and in a way it echos the problem from the "crossword" problem, in which forming anything that looked like a real crossword was so under-rewarded that it was almost never worthwhile.
>
> In a sense it isn't critical to the nature of the competition, but aesthetic results make it all more fun and should if possible be rewarded by the scoring.
>
> Robert


Thanks Robert, excellent point. Will keep in mind for future contests.

Subject: Scoring plateaux

From: Robert Macrae

Date: 8 Nov, 2011 13:48:27

Message: 53 of 73

"Volkan " <volkan@buyukgungor.gmail.com> wrote in message <j99u0u$pq7$1@newscl01ah.mathworks.com>...

> So there is the chance that there may be plateau levels in the hidden suite with boosted values. It is a long shot...

Long indeed, because an improved vine grower seemed to score just a few thousand points more on the hidden suite, very much in line with its gain on the public problems. Of course it could be that the hidden high-value plateaux were very different in a way that foiled my tests but I lean towards the simpler explanation!

Robert

Subject: Scoring plateaux

From: Doug Hull

Date: 8 Nov, 2011 15:30:32

Message: 54 of 73

"Robert Macrae" wrote in message <j99nbm$6s4$1@newscl01ah.mathworks.com>...

> In a sense it isn't critical to the nature of the competition, but aesthetic results make it all more fun and should if possible be rewarded by the scoring.

Robert,

You are right, these could have been balanced better because the aesthetic appeal is cool for the long vine problems. In the end, the winner tends to edge out the runner-up by a *very* small margin, so every bit does help. That being said, we should normalize the boards better between the classes of problems.

Everyone,

As far as the test suites differing, here is the procedure that we go through in making test suites once the rules are set (possibly iterating the rules based on results.)

* Imagine the typical solvers that will be built
* Figure out what test suites will make those solvers not work
* Build a script that will randomly generate test suites of that form, often taking inputs such as
  - size of board
  - maximum value on board
  - a target length for a long snake in the board
  - number of slides to undo the optimal snake above
  - etc

* Repeat this process for several classes of problem. For instance, this contest, we had a
   -Plateau generator (Enkh)
   -Completely random (David)
   -Gradient pattern (David)
   -Long path hidden in noise (Enkh)
   -Long path, interrupted by a bunch of slides (Doug)
   -Spikes of high values (David)

Once we have the generators, we make a range of boards of a set distribution of parameters as discussed above. These are placed into test suites, arbitrarily labeled:
* Internal
* External
* Sample
* Back-up.

We run all of these through the working solvers from the internal contest to validate them. If they work, we lock them down for the release.

So, there are going to be random fluctuations between boards and test suites. If there is a particularly meaningful variation in one of the boards in one of the suites, it is the will of MATLAB's random number generator. Who am I to question The MATLAB! :)

Subject: Scoring plateaux

From: Volkan

Date: 8 Nov, 2011 17:05:14

Message: 55 of 73

"Doug Hull" <hull@mathworks.SPAMPROOFcom> wrote in message <j9bhuo$26v$1@newscl01ah.mathworks.com>...
> So, there are going to be random fluctuations between boards and test suites. If there is a particularly meaningful variation in one of the boards in one of the suites, it is the will of MATLAB's random number generator. Who am I to question The MATLAB! :)

Good to know, thank you. I think I was just being a sore looser because my ideas didn't work, but then again there is the chance that my code is bugged or not generic enough.

Ugly solutions outranking beautiful ones has never been a problem for me since Matlab Contest is collaborative by design. There always are puzzle types for which better results are the beautiful ones, and focusing on them takes up all my time anyway.

Volkan

Subject: Scoring plateaux

From: Volkan

Date: 8 Nov, 2011 17:06:31

Message: 56 of 73

"Doug Hull" <hull@mathworks.SPAMPROOFcom> wrote in message <j9bhuo$26v$1@newscl01ah.mathworks.com>...
> So, there are going to be random fluctuations between boards and test suites. If there is a particularly meaningful variation in one of the boards in one of the suites, it is the will of MATLAB's random number generator. Who am I to question The MATLAB! :)

Good to know, thank you. I think I was just being a sore looser because my ideas didn't work, but then again there is the chance that my code is bugged or not generic enough.

Ugly solutions outranking beautiful ones has never been a problem for me since Matlab Contest is collaborative by design. There always are puzzle types for which better results are the beautiful ones, and focusing on them takes up all my time anyway.

Volkan

Subject: submission search

From: Michael Bindschadler

Date: 8 Nov, 2011 22:42:11

Message: 57 of 73

Searching the submissions for "SOC" doesn't seem to work, it just returns ALL the entries as far as I can tell. Other searches (e.g. for "some say") seem to work fine.

Mike Bindschadler

Subject: submission search

From: Helen Chen

Date: 8 Nov, 2011 23:57:27

Message: 58 of 73

Hi Mike -

I checked the first 15 submissions that came up on searching for "soc". Doing an in page search for this did find the string on each page. I think a longer text string would improve the likelihood of finding content that you are looking for.

If you have more concerns about this search, feel free to contact me directly at Helen.Chen@mathworks.com.

hths,
Helen


"Michael Bindschadler" wrote in message <j9cb83$1dd$1@newscl01ah.mathworks.com>...
> Searching the submissions for "SOC" doesn't seem to work, it just returns ALL the entries as far as I can tell. Other searches (e.g. for "some say") seem to work fine.
>
> Mike Bindschadler

Subject: submission search

From: Michael Bindschadler

Date: 9 Nov, 2011 00:44:28

Message: 59 of 73

"Helen Chen" <helen.chen@mathworks.com> wrote in message <j9cfl6$e42$1@newscl01ah.mathworks.com>...
> Hi Mike -
>
> I checked the first 15 submissions that came up on searching for "soc". Doing an in page search for this did find the string on each page. I think a longer text string would improve the likelihood of finding content that you are looking for.
>
> If you have more concerns about this search, feel free to contact me directly at Helen.Chen@mathworks.com.
>
> hths,
> Helen

Thanks for responding Helen. I was hoping to find all the entries submitted for the square one challenge minicontest, which were all supposed to be identified by starting with the letters "SOC". Is there a way to limit the fields being searched to the solver name?

Thanks,
Mike

Subject: Congrats to Alex P on the SOC challenge

From: Michael Bindschadler

Date: 9 Nov, 2011 01:19:11

Message: 60 of 73

Curses!! I tried to hold my SOC code for as long as I could, but I was going to be away from the computer for the last hour before the deadline and I knew I hadn't really kept up with the leader developments since I forked from "m" to develop my SOC solver, so there were a lot of tweaks that could probably quickly improve my code. I went so far as to make sure I could do the submission at the last minute from my phone. I submitted from my phone at 8 min before the deadline because I wanted to have time to log back in to matlabcentral, find my entry, and resubmit with the SOC tag, in case my phone had mysteriously logged out or I was in a dead zone or something. I was hoping 8 min was not going to be enough time for someone to find and insert a winning tweak. I should have known better :)

Congrats to Alex P, who only needed 7 min to find something to improve and resubmit it, winning by improving the time by 0.16 seconds!

Anyway, the way the code works is as follows. If there are no moves allowed, I run a version of alfi I modified to force to start at square one. I spent a lot of time trying to understand how alfi worked, so that paid off here when I wanted to make it do something related, but different. If there are moves available, then I reserve some of them to use for SOC-specific code later, but then run all the normal solvers (with the reduced move limit) under the normal conditions. Then I wrote a convert2soc function which takes the resulting optimal vines and tries to graft a path onto them which starts at square one. It does this by making a channel of zeros from square one to the lowest reachable point on the existing vine. Then the SOC vine is just the channel of zeros and the vine from the graft point upward. If there aren't enough moves to make a successful graft, then I just use the
SOC-modified alfi code to generate a backup vine. This combination of approaches significantly outscores the few other SOC entries. I just had too little faith in my phone :)

-Mike Bindschadler

Subject: submission search

From: Helen Chen

Date: 9 Nov, 2011 02:13:10

Message: 61 of 73

So sorry that I misunderstood your question, Mike.

Ned is looking into this with the engineers.

Helen

Michael Bindschadler" wrote in message <j9cidc$lsa$1@newscl01ah.mathworks.com>...
> "Helen Chen" <helen.chen@mathworks.com> wrote in message <j9cfl6$e42$1@newscl01ah.mathworks.com>...
> > Hi Mike -
> >
> > I checked the first 15 submissions that came up on searching for "soc". Doing an in page search for this did find the string on each page. I think a longer text string would improve the likelihood of finding content that you are looking for.
> >
> > If you have more concerns about this search, feel free to contact me directly at Helen.Chen@mathworks.com.
> >
> > hths,
> > Helen
>
> Thanks for responding Helen. I was hoping to find all the entries submitted for the square one challenge minicontest, which were all supposed to be identified by starting with the letters "SOC". Is there a way to limit the fields being searched to the solver name?
>
> Thanks,
> Mike

Subject: submission search

From: Ned Gulley

Date: 9 Nov, 2011 15:52:11

Message: 62 of 73

Helen wrote:
> Ned is looking into this with the engineers.

This is indeed a bug in our search code. I was hoping the sentinel would be a simple way to differentiate the mini-contest entries from the rest, but it didn't turn out that way. Unfortunately, I don't think we'll have a fix before the contest comes to a close. But we will fix it.

Subject: Fall 2011 MATLAB Contest, November 2 - November 9

From: Lindsay Coutinho

Date: 9 Nov, 2011 17:00:30

Message: 63 of 73

The contest queue is now closed from adding new entries. Once these entries have processed, we will announce the Grand Prize Winner! Stay tuned…

As always, a big thank you to everyone who participated! It's been another fun contest!

Lindsay and the Contest Team

Subject: Fall 2011 MATLAB Contest, November 2 - November 9

From: the cyclist

Date: 9 Nov, 2011 17:32:27

Message: 64 of 73

"Lindsay Coutinho" wrote in message <j9ebje$ent$1@newscl01ah.mathworks.com>...
> The contest queue is now closed from adding new entries. Once these entries have processed, we will announce the Grand Prize Winner! Stay tuned…
>
> As always, a big thank you to everyone who participated! It's been another fun contest!
>
> Lindsay and the Contest Team

Thanks for putting together another fun contest. Really sorry I wasn't able to participate much this time around.

Subject: Fall 2011 MATLAB Contest, November 2 - November 9

From: Michael Bindschadler

Date: 9 Nov, 2011 19:43:15

Message: 65 of 73

"Lindsay Coutinho" wrote in message <j9ebje$ent$1@newscl01ah.mathworks.com>...
> The contest queue is now closed from adding new entries. Once these entries have processed, we will announce the Grand Prize Winner! Stay tuned…
>
> As always, a big thank you to everyone who participated! It's been another fun contest!
>
> Lindsay and the Contest Team

Congratulations to Alfonso!! And thanks to the Contest Team for another great contest! I'll look forward to the next one!

Subject: Fall 2011 MATLAB Contest, November 2 - November 9

From: Alfonso Nieto-Castanon

Date: 9 Nov, 2011 20:06:11

Message: 66 of 73


For those curious, the winning entry was based on 'rsk-red vs tm' by amit rajora. I added there some modifications to the alfi solver mostly aimed at speeding it up and improving the logic that chooses the order of post-processing movements (greedy maximization of the average gain per movement at each step). The modifications to the alfi solver are the only ones present in the lasttry01 entry (which pushed the results down from 6565 to 6504). Then, following Robert and Nick suggestion, I also added a very rough additional solver for the boards with very high movement count that attempts to grow a spiral centered on the board (this version tried several combinations that limited the radius of movements used to bring additional elements to the current vine). Adding a couple of additional calls to this spiral algorithm brought down the results to 6447 .

Thanks to all for a great contest experience, and special thanks as always to the contest team for yet another extremely interesting and challenging problem!! (and very smooth contest operation)

Alfonso

Subject: Congrats to Alex P on the SOC challenge

From: Alex P.

Date: 9 Nov, 2011 20:26:10

Message: 67 of 73

Excuse me Michael, I understand your excitement. Quite probably it was not me, because you've made ??a really good script. My scripts were about 90k points behind yours SOC entries.
I had studied the algorithm in advance, created some charts about the behavior of the parameters (see for example my "magic number" entries). So it's not only the work within the last 7min. But for me it was lucky that in this case I just had time available (but unfortunately missed the final spurt due to professional activity) and there were still this algorithm inside.The parameters are usually optimal for only one set of boards and a specific machine. Even the other sub-algorithm can inluence due to the choices.
But I think the interesting thing is that we all have learned from alfi.
Congratulations to all winners (great job by all active),
and many thanks to the contest team . It was once again very interesting and you could learn a lot here.
Alex

Subject: Fall 2011 MATLAB Contest, November 2 - November 9

From: Nicholas Howe

Date: 9 Nov, 2011 21:12:29

Message: 68 of 73

"Alfonso Nieto-Castanon" <alfnie@gmail.com> wrote in message <j9emfj$mqm$1@newscl01ah.mathworks.com>...
>
> For those curious, the winning entry was based on 'rsk-red vs tm' by amit rajora. I added there some modifications to the alfi solver mostly aimed at speeding it up and improving the logic that chooses the order of post-processing movements (greedy maximization of the average gain per movement at each step). The modifications to the alfi solver are the only ones present in the lasttry01 entry (which pushed the results down from 6565 to 6504). Then, following Robert and Nick suggestion, I also added a very rough additional solver for the boards with very high movement count that attempts to grow a spiral centered on the board (this version tried several combinations that limited the radius of movements used to bring additional elements to the current vine). Adding a couple of additional calls to this spiral algorithm brought down the results to 6447 .
>
> Thanks to all for a great contest experience, and special thanks as always to the contest team for yet another extremely interesting and challenging problem!! (and very smooth contest operation)
>
> Alfonso

Excellent work by Alfonso winning this contest! His elongated spirals look quite elegant and work on a lot more boards than the square ones I developed.

This has been a fun competition, and I want to thank all the members of the contest team at the Mathworks. You make it all possible!

One note on the side: I think that the very long files developed for this contest may be revealing a limitation of the Matlab UI, and I thought I'd mention it because I know Mathworks people are reading this thread. My editor window gets very slow, sometimes freezes up, and even generates error messages (something to do with GC out of memory). I think it may be related to the new option that pops up offering to change variable names automatically when you press Shift+Enter, because it mostly seems to happen when I alter an identifier name. I may also be making matters worse by having many files open for editing at the same time.

Subject: Congrats to Alex P on the SOC challenge

From: Michael Bindschadler

Date: 9 Nov, 2011 21:30:27

Message: 69 of 73

"Alex P." wrote in message <j9enl2$qma$1@newscl01ah.mathworks.com>...
> Excuse me Michael, I understand your excitement. Quite probably it was not me, because you've made ??a really good script. My scripts were about 90k points behind yours SOC entries.
> I had studied the algorithm in advance, created some charts about the behavior of the parameters (see for example my "magic number" entries). So it's not only the work within the last 7min. But for me it was lucky that in this case I just had time available (but unfortunately missed the final spurt due to professional activity) and there were still this algorithm inside.The parameters are usually optimal for only one set of boards and a specific machine. Even the other sub-algorithm can inluence due to the choices.
> But I think the interesting thing is that we all have learned from alfi.
> Congratulations to all winners (great job by all active),
> and many thanks to the contest team . It was once again very interesting and you could learn a lot here.
> Alex

No hard feelings at all, Alex, you had a clean win, and I wasn't trying to minimize your effort. The change you made clearly represented a familiarity with and understanding of the code and wasn't just a random tweak.

And I wholeheartedly agree about alfi. As a self-taught programmer who learned on MATLAB, studying alfi was like a mini-course in computer science. Through it, I learned that what I had created in my twilight entries were (much cruder implementations of) Bellman-Ford and Dijkstra algorithms. I learned a bit about the power of sparse matrices (which I never think to use). I learned about the dperm function, which I had never encountered before. Anyway, thanks for the lesson, Alfonso!

-Mike Bindschadler

Subject: Fall 2011 MATLAB Contest, November 2 - November 9

From: Helen Chen

Date: 9 Nov, 2011 22:53:12

Message: 70 of 73

Congratulations to Alfonso on being this season's Grand Prize Winner, and, also congratulations to each of our daily challenge/prize winners.

Thanks to everyone who participated, it really was a fun week! As Alan pointed out in his comment http://blogs.mathworks.com/contest/2011/11/09/alex-p-and-the-anatomy-of-a-tweak/#comment-6725 to Ned's blog post, it really did feel like there was a great community spirit with all the collaboration going on.

We appreciate all the wonderful feedback that we have received about the contest. We're glad you had as much fun as we did this season. :-)

Best,
Helen and the MATLAB Contest Team

"Lindsay Coutinho" wrote in message <j9ebje$ent$1@newscl01ah.mathworks.com>...
> The contest queue is now closed from adding new entries. Once these entries have processed, we will announce the Grand Prize Winner! Stay tuned…
>
> As always, a big thank you to everyone who participated! It's been another fun contest!
>
> Lindsay and the Contest Team

Subject: Fall 2011 MATLAB Contest, November 2 - November 9

From: Helen Chen

Date: 9 Nov, 2011 22:59:11

Message: 71 of 73

Thanks Nick -

I will pass your comments on to the development team. I do appreciate you taking the time to report this. :-)

Helen
"Nicholas Howe" wrote in message <j9eqbt$6ng$1@newscl01ah.mathworks.com>...
> One note on the side: I think that the very long files developed for this contest may be revealing a limitation of the Matlab UI, and I thought I'd mention it because I know Mathworks people are reading this thread. My editor window gets very slow, sometimes freezes up, and even generates error messages (something to do with GC out of memory). I think it may be related to the new option that pops up offering to change variable names automatically when you press Shift+Enter, because it mostly seems to happen when I alter an identifier name. I may also be making matters worse by having many files open for editing at the same time.

Subject: Fall 2011 MATLAB Contest, November 2 - November 9

From: James White

Date: 12 Nov, 2011 04:45:29

Message: 72 of 73

I enjoy this contest every time and I love that the winners now get badges on their pages. However, I have to say that Nick's "Twilight" badge looks more like a "Partly Cloudy" badge.

Subject: Spring 2012 MATLAB Contest

From: Markus Buehren

Date: 31 Mar, 2012 17:38:11

Message: 73 of 73

Hi contest team, hi contestants,

in anticipation of the next contest I just had an idea for a rule change or at least a rule for a contest phase. Well, before having that idea, I thought of a thing that still bothers me a little since the color bridge contest. During that contest, I had a simple but, as I still think, clever idea to improve the solver. In fact, that little algorithmic change resulted in an enormous boost of the score using the sample test suite.

However, after excitedly waiting until my submission passed the contest queue, there was no improvement of the score using the contest test suite. I am quite sure that the reason for this was that the leading solution was pretty much overfitted to the test suite by parameter tweaks over many contest hours.

One sort of "optimizations" in former contests frequently was to let several good algorithms that have been developed during darkness and twilight run in parallel. This is usually done either by a top level decision (e.g. algorithm A for dense boards, algorithm B for sparse boards) or, even more simple, by letting several algorithms run after each other and select the solution with the best score.

Now let me explain my idea: What would you think about limiting the node count of solvers after the twilight phase to 120 or 150 percent of the maximum node count of the top 20 solvers during darkness/twilight? This would leave enough space for further algorithm development while it would not allow to simply combine several algorithms. If you think that this limit would be too strict for the whole daylight time, it could also be applied to one contest phase. This way the darkness/twilight algorithm developers could continue developing their own code aiming to win the contest phase where there will only be enough space for one algorithm per submission.

Good luck in the easter contest to all!

Yours
Markus

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us