MATLAB Programming Contest BlogDecember 5th, 2011See You at the Spring Contest!The Contest team is finishing up our last activities for the Vines Contest. Prizes to the winners have been packaged up and are on the way to their various final destinations. Stories from the contest winners are posted to the Hall of Fame. It’s well worth a read! You might learn something that helps you in next season’s contest! ;-) Thank you to everyone who participated and to those of you who watched from the sidelines. If you are in the latter category, please do consider joining in next time. It really was another great season. We look forward to seeing you in the spring! Best, Helen
November 9th, 2011Alfonso is the Winner!Wow! What a finish. A lot of us thought that Nick was going to do it again. The cyclist even named one of his last entries Can’t beat Nicholas Howe. We knew the end was near, because Magnus S. named one of his last entries Some say that he is soon running out of titles (by the way, you should read the complete list of Magnus’s titles). The minutes ticked by, and sure enough here comes Nick with pf3pushmixfull. It’s a significant improvement, and he’s got a few more right behind. But wait… hold the phone! Could it be? Yes, here comes Alfonso with a killer punch. BAM! lastttry01. Look out! Here comes another. BANG! lasttry02. And the final blow. KAPOW! lasttry03. Alfonso has set a new standard in terms of dominating the end game. Not one, but two of his final entries improved on the previous leader by more than half a percent. Which is, as we say here in New England, wicked hard to do. So hats off and three cheers for Alfonso Nieto-Castañón, our latest champion. And, as always, thanks to everyone who played. The code that wins carries with it a little bit of all of you. See you in six months! Vines Contest queue is now closedThe Vines contest queue is now closed. The Grand Prize Winner will be declared after all entries submitted before noon (Natick time) are processed. You can check the queue at the Vines Contest website to see how your entry is doing. Helen
Alex P. and the Anatomy of a TweakCongratulations to Alex P., winner of the Square One Challenge with his SOC tweak. Michael Bindschadler came close… so close! to winning. But from the newsgroup, we read this heartbreaking story.
His closing comment shows that Michael is a good sport and that he understands the brutal reality of the contest: tweaks can happen at any time. Alex P., who has narrowly missed on prizes of his own, deserves our recognition too. But I can’t resist showing you the one line out of 1675 lines where the code differs. On line 478, where Michael had Alex had substituted And that, my friends, is all it takes. Assuming your answer is actually better, which is harder than it looks. There is one exception to the Iron Law of Tweaking, though, and it will soon be upon us. Once we get so close to the end of the contest that your code can’t be scored until after the deadline has passed, nobody can see and modify your code before the end. All the hardcore competitors (and who else is left by now?) are aware of this. They’ve reached deep into the shot locker for their last tricks. Now they are slowly circling the submit button, waiting… waiting for the moment to blaze away. I’m picturing the ships of the line at Trafalgar drifting slowly toward each other, almost within range. The slow match is burning. All is silent. Good luck! November 8th, 2011Amitabh wins the Best Result prizeJust before midnight last night, Greenwich Mean Time, Amitabh Verma submitted All Guns Blazing. Using 174 seconds worth of CPU time, it cruised limbo-style beneath the timeout limit, generating a world-beating result of 65558057, the best seen up to that point. Magnus S. has since bettered that with an impressive 65492821, but Amitabh takes the Best Result prize, since the timing deadline was for end-of-day November 7th. Congratulations Amitabh on your second prize for this contest! Remember that midnight tonight (UTC) is the deadline for the Square One Challenge. Mark your entry with the naming sentinel SOC to be eligible. For more details, refer to the earlier blog post. Vines Mid-Contest AnalysisThis season’s mid-contest analysis is from my coworker Lucio Cetto I ran a small analysis over the solvers that were among the first five positions at the end of Twilight. The leaders at that time were Nick Howe (Revenge of Antichaff), Alfonso Nieto (test05_tweak10), Robert Macrae (The Fragrant Honeysuckle), Kurt Janssens (v 11), and Martin F (Sixth shot). First, let’s look at the solutions given by the solvers to the original Fifteen puzzle. My initial configuration placed all odd number at the top and even numbers at the bottom. I had to change the original puzzle a little because Kurt’s solver choked if I passed an initial board with a zero. I replaced that piece with a 16. Nick’s solution was able to interleave the even and odd numbers properly. Notice that there was a lot sliding and few pieces were blown out. Alfonso and Kurt seemed to concentrate on creating their vines and cared less about moving pieces. Robert and Martin preferred to move all the high value pieces to a given region before building a simple vine.
Let’s scale the problem a little bit. In my second board, I placed random pieces in a slightly different configuration. Higher value pieces are toward the bottom of the board. Note the excellent job by Alfonso’s solution – it appears to have the right balance between moving pieces and growing the vine. In a board like this, on one side you need to do a lot of sliding in order to bring the monotonically increasing pieces together. On the other side, you want to minimize sliding because “easy” sliding requires blowing pieces out that could eventually be part of your vine. More difficult sliding, like the one that actually occurs in the real fifteen puzzle where you have restricted space, is much harder to program. In this situation, Nick’s solver changed mode and operated more like Robert’s and Martin’s solutions. It moved pieces to the edges to build the vine. Note that Kurt’s solver did not move any piece at all, yet his strategy of focusing on growing a high value vine permitted Kurt to be among the leaders.
Finally, let’s see how the solvers behave with a random board with only ones and twos. Nick’s solver apparently changed strategy again. The new operating mode refuses to move the pieces. The solution is very similar to Kurt’s solver. Again, note that non-mover solvers are doing fine in several of the problems. Alfonso’s solvers seem to have found the right combination between moving and growing the vine, while Robert’s and Martin’s move all the high value pieces to the edges again. Notice the best scoring solvers left most of the twos out of the vine.
In closing, here’s a quick look at results of the current leader, at the time of writing this post.
November 7th, 2011Two more mini-contests: Best Result and Square OneThe contest ends on Wednesday. Between now and then we’ll try two more mini-contests to keep things interesting. First, we’ll do a Best Result contest. As usual with this prize, there is no penalty for time. If you can get it to run without timing out, then it qualifies. We’ll be looking at the “Result” column only of the “Best Result” table on the Statistics page. Deadline for this contest is midnight tonight, UTC, or 8 November 00:00:00 UTC. Alan had a number of interesting, one might say poetic, suggestions for other mini-contests. My favorite: “Solvers that when viewed in the MATLAB editor form ASCII art, yet are still able to run.” I’m not sure how to score that one, so I’ll go with his first suggestion. We’ll call this one the Square One Challenge. You’re trying to get the best score possible given the constraint that you always have to start with square one (row = 1, column = 1, index = 1). As with the No Bogus Words Challenge in the last contest, you’ll need to signal your intent so we can determine the winner. Put the three letters SOC at the beginning of your entry’s name (e.g. “SOC Killer Kudzu”). We’re not changing the contest scoring code, so we’ll be checking your code after the fact. When the deadline has passed, we’ll look at the leading SOC entry and check it. Beware: if any of your vines don’t start on square one, you will be disqualified from winning the Square One Challenge on any other entries, and we’ll move on to the next potential winner. The SOC winner needs to be submitted before midnight tomorrow, 9 November 00:00:00 UTC. Amitabh and Sergey Y.The weekend is over and the dust has cleared. It’s time to hand out some crowns. For the second time in a row, Amitabh wins the Saturday Leap prize (see his badges here) with his Vines & Vines, which kept the lead for almost two hours. Amitabh’s remarkable Saturday contributions are especially obvious on our “Percent Improvement” chart. His name appears three times in the stretch following 11/05, or midnight UTC.
Sergey Y. (look at all these badges) takes the Sunday Push prize. You have to appreciate the extraordinary focus that Sergey brings to the Sunday Push. He knew what he wanted to do and he set about it very methodically, racking up a total of ten leading entries, mostly in the small hours of Sunday morning. His focus paid off. Nobody else came near him for the Sunday Push prize. Well done, and congratulations Amitabh and Sergey! More MATLAB-themed booty will be headed your way. And thanks to all of you who spent your valuable discretionary weekend time trying to squeeze a few atoms of efficiency out of MATLAB program. It’s been fun to watch! November 4th, 2011Early Bird Closes: So close, Sebastian!Look at the list of submissions and you’ll see that Sebastian Ullmann’s entry cheaper ? ranked the highest as of 21:00. But our listing only shows minutes, not seconds. The question is 21:00 and how many seconds? If he had managed to get it in by 21:00:00, he would now be wearing our Early Bird Sport Jacket emblazoned with the golden crest that says “I Won!” But close inspection revealed that his entry came in at 21:00:37 UTC, which means he narrowly lost to none other than… wait a second… I have the name around here somewhere… Nick Howe! I was going to say “Oh Sebastian, you waited a little too long to submit your entry.” But, once again, close inspection reveals that his entry was actually based on Nick’s winning entry, Cheap Reverse, which wasn’t even scored until 20:58:50 UTC. So, far from being slow, I have to commend Sebastian for his nimble typing. He modified and resubmitted his runner-up (here’s the diff) in about 90 seconds. Nick’s entry was based on Pori 13 by Abhisek Ukil, which was based on -1 by Alex P. which was based on … well, you get the idea. A lot of people have contributed ideas by now. Nick left us a nice comment in his winner:
Funny how often that turns out to be the case. And that reminds me: be sure to look at the comments from time to time. There’s a lot of good stuff in there, and some of it’s very funny. You can leave comments on any entry at any time. You can ask questions, give congratulations, or propose new ideas. It makes the game more fun. Upcoming Mini-contestsHere are some upcoming mini-contests:
Nick Howe to the winner’s podium pleaseI’m sure that Nick Howe doesn’t need any more prizes from the MATLAB programming contest, but he keeps winning them just the same. For the third contest in a row, Nick is our Crepuscular Conqueror, the Duke of Dusk, Lord of the Twilight, and Prince of Dimly Lit Regions. Two of his late-breaking entries were good enough to sneak past Alfonso to claim the Twilight Prize, with the actual winner being Revenge of Antichaff. Well done Nick! Nice to have you back on the podium. November 3rd, 2011Twitter and the MATLAB ContestAs in the past, we have turned on a service that automatically tweets whenever there’s a new leader. All you have to do is follow @ContestLeaders and you’ll be the first to know when those critical shifts in power occur. On a more functional level, we have another account that gives some indication of how healthy the queue is. Following @ContestStatus will tell you how long the queue is and how long it’s been since the last entry was processed. Meet Alfonso, Prince of DarknessFor the second contest in a row, Alfonso Nieto-Castañón walks away with the Darkness prize. You may remember that his winning Crossword entry was called tryagain01. His winner this time around is called try04. Fortunately for Alfonso the prize isn’t about coming up with exciting names. It’s about the code, and Alfonso brought the code. And now he takes away the prize. Congratulations Alfonso! What is the secret to his winning entry? You’ll have to wait until Daylight to see what tricks he’s using. In the meantime, you can work toward the Twilight Prize (Prince of Twilight?), which will be awarded tomorrow at 16:00 UTC (noon Natick time). For those of you looking ahead to other prizes, we’ll have an Early Bird prize on Friday afternoon (21:00 UTC), as well as our regular weekend prizes, the Saturday Leap and the Sunday Push. Have you got ideas for another mini-contest? Please tell us! We’re open to suggestions. November 2nd, 2011Fall Contest Underway!The Fall 2011 MATLAB Programming contest is underway. This season’s challenge is going to remind many of you of a favorite childhood game – the game 15-Puzzle! In this contest, use your MATLAB skills to create vines on a grid. Read Ned’s rules to learn more. If you are new to our contests, take a look at If this is your first contest, you might want to read the Contest FAQ. To be truly inspired, take a look at our Hall of Fame . This contest runs from now through noon Boston time Wednesday November 9. If you have questions or comments, you may post them here or reply to this contest’s thread in Newsreader. Good luck to everyone! Helen and the Contest team
October 27th, 2011Fall Contest begins November 2ndFall is here and that means that it is time for our Fall MATLAB Programming Contest. Our Fall contest starts at 16:00 UTC/noon Eastern, Wednesday November 2nd. It will run through 16:00 UTC/noon Eastern, Wednesday November 9th. If you’ve never participated in a contest before, check out some of our previous contests. You can also find out about folks who have won previous contests in our Hall of Fame. Hope to see you online!
April 21st, 2011Nick Crushes ItNear the end, everybody has the same idea. It’s obvious, really. Hold back a trick or two and throw it into the mix in the last few minutes. Then cross your fingers and hope that your number comes up. Ideas are cheap, but who can deliver the goods? I’ll tell you who, ladies and gentlemen. Mr. Nicholas Howe of Smith College, that’s who. I think I can, without hyperbole, say that I have never seen anyone so thoroughly dominate the closing minutes of a contest. Look at this scoring cliff.
Amitabh’s Sneaker was on top for a surprisingly long time, given the closing onslaught. I thought maybe that tough old Sneaker might go the distance. It was a timing game: no one was resetting the result of 6877358, but the race was on to shave seconds from the clock. And then along came Nick, with one fist of iron and one fist of steel, smashing the score lower with each blow. When the dust settled, Rapid Weight Loss May Be Harmful was high atop a list of 2713 ranked entries. Well done Nick. We send our congratulations to you (and your wife). And well done everyone! Thanks for joining in the fun and making this contest such a pleasant experience. It’s a lot of fun for us at MathWorks to watch the pros go to work. We are amazed by the display of skill. As always, now is a good time to reflect on how the contest. What did you like, and what would make it run better? How can we get more people to play? How can we get more people to watch? Some of these questions are already being discussed on the newsgroup. Join in the conversation there or leave a comment here. April 20th, 2011It’s official: Alan Isn’t BogusAlan Chalker, no stranger to the Contest Hall of Fame, wins our No Bogus Words mini-contest. His NBW endgame trio numbers 2, 3, and 4 topped the list at 21:00, and David Hruska, our master code wrangler on the contest team, has verified the non-bogosity of the answers. It was an exciting finish… I thought for a moment that Sergey was going to claim another prize. And there were fine last-minute efforts from Victoria, Amitabh, Andreas Bonelli, Oli, and Jin. As Alan observes in the comments, he may have been destined to win, since he suggested the No Bogus Words challenge. Alan, you should suggest more mini-contests in the future! Congratulations on this latest victory. Albert, who had a higher scoring NBW entry that came in just six minutes too late, deserves a prize for the most heartbreaking title: NBW just realized there was a deadline …. Ouch! We feel your pain, Albert. That’s a hard way to go. Albert’s entry was an interesting outlier in that it took almost 6 times longer than Alan’s winner but compensated with a substantially better result. The queue is quiet, and yet I see the end of the contest is a short hour away. This is the calm before the storm. Algorithmic ammunition, long held in reserve, is being readied for the final battle. This is our first darkened queue endgame, which should significantly change the dynamics. Soon the event horizon for inspecting competitive code will close. Then the floodgates will open and dozens of innovations will do battle for ultimate supremacy. Good luck everyone! April 19th, 2011Ned’s Contest AnalysisNed’s been thinking a lot about this season’s Crossword Contest. You can read about what he’s been thinking by reading his Contest Analysis. Enjoy! Crossword Contest CommentaryHere are some snapshots from the latest contest. ContentsDarkness WinnerLet’s start with Alfonso’s Darkness winner, tryagain01. We’ll run it against problem 41 of the test suite. It produces this picture.
Bogus!Right away we notice that the output is mostly red. This reflects the fact that solvers are rewarded for packing in lots of short words as long as they create a smaller number of long crossing words. In retrospect, we made the bogus word penalty too low, since the result is aesthetically a little unappealing. But the rules are what they are, and within this framework, we see plenty of innovation. There’s nothing wrong with red if it gets you a good result. Sample WordsSince these letters are meaningless, I’m going to switch to some real words to make it easier to follow what’s going on. Let’s consider the words in the first paragraph of the rules. I realize it’s a little unfair to compare codes based on an example they never encountered in the test suite, so you can take this exposition with a grain of salt. YOU ARE THE NEW CROSSWORD PUZZLE INTERN FOR MAJOR MATH SOFTWARE NEWSPAPER THE NEW YORK MULTIPLY ALL THE NEWS THAT BITS AND INTS YOUR EDITOR HAS GIVEN YOU LIST WORDS USE THIS WEEK PUZZLE KNOWS YOU CAN POSSIBLY USE ALL THE WORDS HIS LIST GAVE EACH WORD WEIGHT AND TOLD YOU THE BEST YOU CAN YOU HAPPEN KNOW THAT GAVE THE SAME CHALLENGE ANOTHER INTERN YOU BETTER GOOD JOB YOU WANT KEEP YOUR POSITION MAYBE SOME SOFTWARE WOULD HELPFUL HERE Naturally, the character of the answer depends on the weights and the penalties. For this problem, let’s say that the weight is the length of the word. Penalty = 0For zero penalty and grid size of 15, Alfonso’s code returns this.
Penalty = 4For a penalty of 4 (the median weight of the words in our dictionary), we get this.
Penalty = 9The highest weight word is 9. When the penalty is 9, there are no more bogus words. Legal crossing words are completely absent in all three solutions.
Twilight Winner, Penalty = 0Let’s move on to Nick Howe’s Twilight winner, Star Crossed X. This is the zero penalty solution.
Yow! That’s a jam-packed grid. Here’s what happens when we boost the penalty to 9. Twilight Winner, Penalty = 9
Now there are no bogus words again, but still no usage of crossing words anywhere on the grid. No Bogus WordsThe other mini-contest winners from Saturday and Sunday that I looked at returned very similar results to those shown above. From the point of view of looking at “interesting” results, we need to skip ahead all the way to the No Bogus Words entries. For NBW entries, the penalty is effectively infinite. This is NBW Weighty matters from the cyclist. We’ve finally got some crossing words! Three, to be precise, but that’s more than none.
Scrabble ScoresSuppose instead of rewarding solvers for the length of each word, we instead rewarded them for their Scrabble scores. The longest words used to be 9. But now the highest value word is PUZZLE, with a score of 26.
The Last Example: A Recent LeaderThis is Oli’s NBW Hoola Hoop. It’s the highest ranking NBW entry as of Tuesday morning, Natick Time. We’ve still only got a couple of crossing words.
How Do the Pros Do?As a quick taste of what is possible with these same words, here is the output from a free crossword grid construction program, EclipseCrossword. Here we are fitting 30 words into the same space where the leading contest entry can only fit 20. Again, it isn’t a fair comparison, since these two programs are working on different optimization problems. But it’s fun to compare.
Published with MATLAB® 7.12
Sergey, Master of a Thousand NodesDidn’t I tell you? Watch out for Sergey, I said. He’s the master of the Short Form, I said. And sure enough, he swooped in with seven tightly packed entries between 15:44 and 16:00 UTC, and now he’s at home counting his prize money. Or he would be if there were any prize money. Congratulations (again) to 1000 Node challenge winner Sergey Yurgenson. I have a sneaking suspicion that he’s really good at tuning up small cars, fixing watches, and maybe building sailing ships in bottles. In any event, he sure knows his way around a few hundred lines of MATLAB code. Here is his winner, CrossCat7. Nice work Sergey! April 18th, 2011Three Mini-contestsWe’re in the final few days of the contest, and we know that you’re anxious to know what prizes remain to be claimed. We’ll give you a few options. First of all, we’re bringing back the venerable 1000-Node Challenge. The 1000-Node Prize will go to the entry with the best score that
Remember, you don’t need to shorten your variable names or remove comments to win this challenge. That’s exactly why we made it a node-count prize and not a character-count prize. This is how you calculate your node count. t = mtree(filename,'-file'); length(t.nodesize) Sergey is the acknowledged master of the Short Form. Can you beat him? Next, as suggested we’re going to try a No Bogus Words Challenge. If you want to enter, you need to signal it to us by putting the three letters NBW at the beginning of your entry’s name (e.g. “NBW My Super Duper Entry”). We’re not changing the contest scoring code, so we’ll be checking your code after the fact. When the deadline has passed, we’ll look at the leading NBW entry and check it. Beware: if it actually does use any bogus words, the author will be disqualified from winning the NBW prize on any other entries, and we’ll move on to the next potential winner. The NBW winner needs to be submitted before 21:00 UTC on 19 April. (If we had it all to do over again, we’d probably have made the bogus word penalties higher. But you never know how things are going to go until you start the contest and see what entries come in.) Finally, there’s the Six Million Dollar Man prize. If you can break 6,000,000 for your “result”, regardless of any other consideration, you win the prize (note that you don’t actually win $6,000,000). Naturally, you can’t exceed the time limit, but other that that, all that matters is the result. My friend Dave on the contest team says it can’t be done. I realize it’s a stretch goal. We’ll just throw it out there and see what happens. Haiku WinnerIt gives me great pleasure to award the Haiku Challenge prize to Nick Howe’s wife Susannah. Her inspired poetical lament, haunting and epigrammatic, I now reproduce in its entirety: Oh no! Contest time. Here at the Global Contest Headquarters we have a special place in our hearts for the MATLAB widows and widowers out there who tolerate our twice-yearly shenanigans. So it was delightful to hear from one, in poignant verse form no less! Perhaps it is no surprise that, in the name of marital harmony, we have been asked at various times over the years to keep the contests short and infrequent. Thank you for your patience Susannah, and now you’ll have a prize of your own to put on the mantel next to Nick’s. The judges also send an Honorable Mention to Alan Chalker for his prodigious poetical outpouring, and especially his versification in MATLAB. So many choices Weekend Winners: Amitabh and FelIf you’ve been watching the statistics over the weekend, you know the result. We’ll make it official by awarding a Saturday Leap prize to Amitabh Verma for the breakthrough entry Crazy Ivan on Kangaroo Jack. I always like entries with entertaining names, so extra marks for that and well done Amitabh! At 1.11% improvement over the previous leader, Crazy Ivan was the biggest single advance since Alfonso’s Darkness leaders. As we like to point out, it gets harder with each passing minute to make a big improvement, so congratulations to Amitabh for advancing the state of the art so dramatically. And based on his profile picture, I’m guessing he’s a mean bowler too. Double threat: bowling and MATLAB. Maybe there’s some sort of biathlon competition in there? The Sunday Push prize goes to Fel for his “Dead End Strategies” series. Notice that Fel’s best entry for the day would have won the prize all by itself. The mysterious Fel revealed himself to be David Felguera in the last contest where he also did some weekend work, winning the prestigious Sailing Home Saturday Leap prize. Now he’s got both weekend prizes for his trophy room. I think that might be a first… Congratulations to Fel for the largest aggregate improvement for all of Sunday! April 15th, 2011Saturday Leap and Sunday PushAs has become our custom, we will be running two mini-contests this weekend. The Saturday Leap prize goes to the person who makes the single biggest percent improvement for any entry with a submit time on Saturday, 16 April. Keep in mind that our times are registered against Universal Time; the time stamp on your submission is the thing that matters. The Sunday Push prize goes to the person who makes the biggest cumulative improvement for any number of submissions received on Sunday, 17 April. Watch the statistics page for information showing who’s doing the best as the weekend progresses. We will also be awarding a prize to the author of the best MATLAB Programming Contest Haiku. Whereas most of the contest is a purely objective competition that rewards steely logic and intellectual firepower, the Haiku Challenge judging will be completely subjective and arbitrary. It’s just a fun exercise for your neglected right brain. The prize is certain to be cheap. Submit your entries in the blog comments. Have a great weekend! Nick, How Do You Do It?The indefatigable Nick Howe has claimed yet another prize to add to his virtual shelf-full. If you visit his author page (make sure you’re on the one that corresponds to all contests), you’ll see he’s won no fewer than eight prizes of one kind or another. I won’t guarantee this is all of them, since we’ve done an imperfect job so far of matching up badges with past prizes. It’s clear from this list that Nick does his best work at night, with six of those prizes coming in either Darkness or Twilight. Nick had some good competition from James White and Victoria (not to mention Darkness winner Alfonso). But in the end, Nick’s Star Crossed X had more gas in the tank. Congratulations Nick! April 14th, 2011Alfonso is our Prince of DarknessAlfonso Nieto-Castañón is at the top of the list for the Darkness phase of our Crossword puzzle, making him our latest Prince of Darkness. He has submitted only two entries so far (try01 and tryagain01), but these were enough to net him first and second place. Who needs quantity when you’ve got quality? His name seems familiar somehow… where have I seen it before? Ah yes! Alfonso was our Grand Prize winner for the Fall 2009 Color Bridge contest. Congratulations and welcome back to the winner’s circle Alfonso! |
|
|||
|
These postings are the author's and don't necessarily represent the opinions of The MathWorks. |
Recent Comments