Thread Subject:

Fall 2011 MATLAB Contest, November 2 - November 9

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

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

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

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

raz

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?

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.

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

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

"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

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.

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.

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.

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!

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

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

@Peter
Thanks for clarifying the definition!

@Michael
Thanks for the input!

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.

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

"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

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

Question from me:

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

Thanks!

"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

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

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

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

"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

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.

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

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.

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

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

"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

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

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

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!

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

"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

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?

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?

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?

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

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

"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

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

"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

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.

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

"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

"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

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

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

"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

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

"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

"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

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

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

"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

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

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

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.

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

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

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

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

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

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

"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

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

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.

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.

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