MATLAB Programming Contest BlogNovember 8th, 2011Vines 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!
April 13th, 2011The Crossword Contest is Underway!The Spring 2011 MATLAB Programming contest is underway. In this season’s challenge, you are an intern at a major math software newspaper. Read Ned’s rules to find out what task the paper’s Editor has given you for this week’s paper. Better put on your thinking caps, ’cause it looks like your job may be depending on your MATLAB skills!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 or About the contest. To be truly inspired, take a look at our Hall of FameThis contest runs from now through 16:00 UTC Wednesday April 20. 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
March 15th, 2011Spring Contest Dates AnnouncedSpring is in the air and that means that the Spring contest is coming soon. It time for you to check your calendars as the contest starts Wednesday April 13th and ends the following Wednesday, April 20th. Start and end times are noon Boston time, or 16:00 UTC. If you haven’t participated in one of our contests in the past, take a look at last Fall’s Sailing Home to see how the game is played. See you all soon! Helen
November 17th, 2010A photo-finish win for AndréCongratulations to André Fioravanti for his victorious entry Lost Sailor Final5. The winner was submitted just under the wire, with only 32 seconds to spare! It was a fascinating photo finish… Sebastian Ullmann was in the lead for a long time during the tense final minutes. Many of us here thought he was going to carry away the prize, but then André’s tweak on Sebastian’s chancessss pushed him out of the winner’s circle at the last possible minute. So close, Sebastian! As it turns out, had André NOT submitted his winning entry, Rafal Kasztelanic would have won with an entry that appeared 20 seconds later! If we follow the ancestry for the winning entry, it’s remarkable that André’s winner is based on Sebastian’s, which is based on one from David Jones, which is based one from Magnus, which is based on one from the cyclist, and so on past contributions from Cameron Nowzari, Gwendolyn Fischer, Mike Russell, and previous winner Alfonso Nieto-Castanon. And of course, this is just the ancestry that the contest machinery happens to capture. Certainly the ideas of many others are expressed in the winning entry. Altogether the lead changed hands some 244 times, which I believe to be a record. And so we on the contest team offer thanks to all of you who participated and who brought your ideas to the communal table. André wins the prize, but everyone deserves congratulations.
The Queues are now closed!The magic hour has crept up on us once again and we have reached the end of this season’s contest. We have closed the contest queue. We will announce the winner once everything has processed. So stay tuned! Helen
Sergey againOur friend Sergey has another feather for his cap by claiming the 100 Node Challenge prize. His winning entry came in last night with minutes to spare. In fact, his entry would have claimed the 98 Node Challenge too, since his thrifty code didn’t even use all 100 nodes. Because it’s so short, it’s easy enough to show you the complete winning entry. Well done Sergey!
And now we are into the final minutes of the contest. Good luck everyone!
|
|
|||
|
These postings are the author's and don't necessarily represent the opinions of MathWorks. |
Recent Comments