As has become customary for me, I participated in the annual ICFP programming contest this weekend. I participated as a lone coder this time with the team name "rmathew". The contest this year was irritating and frustrating, not to mention quite humbling (as usual).
Showing posts with label icfpc. Show all posts
Showing posts with label icfpc. Show all posts
2010-06-22
2009-06-30
ICFPC 2009
I spent this weekend participating in the ICFP contest. This year the task was a series of problems of increasing difficulty in which we had to steer a satellite orbiting the Earth in order to accomplish various objectives. Like the task last year, it depended heavily on physics, mathematics, your knowledge of a particular domain and the stability of your numerical calculations, not to mention the need for the occasional compensating manoeuvre. It was fairly tedious and I didn't quite enjoy it as much as I did the tasks from some of the previous years.
2008-07-17
ICFPC 2008
I participated in the ICFP contest again this year. The task this year was to write a programme that guides a rover on the planet Mars towards its home base within a time-limit of 30 seconds, while avoiding boulders, craters and hostile Martians. The rover would get telemetry data from its sensors (which could see over a very limited portion of the terrain at a time) roughly every 100 milliseconds. As usual, we were given 72 hours to solve this problem. As it turned out, I encountered an unexpected problem during the contest and my final submission turned the rover into a "buggy", if you get the drift.
2008-07-02
Major Programming Contests This Month
There are a couple of major programming contests coming up this month. The first one is the ICFP Programming Contest 2008 (11-14 July). The second one is the Google Code Jam 2008 (qualification round on 16 July).
There was also an article in DDJ about programming contests a couple of months back. It is an interesting read, but there is nothing new in there for those who are already familiar with TopCoder.
There was also an article in DDJ about programming contests a couple of months back. It is an interesting read, but there is nothing new in there for those who are already familiar with TopCoder.
2007-10-11
ICFPC 2007: Epilogue
The results of ICFPC 2007 have finally been announced. Team Smartass from Google has come first (yet again), followed by United Coding Team from the University of Cape Town (South Africa) in the second place and Celestial Dire Badger (a lone hacker named Jed Davis) in the third place.
The organisers of the contest have an interesting report on the contest that also contains the "ideal" way one would go about solving the puzzles. Interestingly, Jochen Hoenicke managed to find a perfect DNA prefix some time after the contest was over. Impressively, Jed Davis came third by using a brute-force approach that won him the Judges' Prize - he was declared to be "an extremely cool hacker".
Update (2007-10-24): The organisers have now shared the video of their presentation about the contest at ICFP 2007.
The organisers of the contest have an interesting report on the contest that also contains the "ideal" way one would go about solving the puzzles. Interestingly, Jochen Hoenicke managed to find a perfect DNA prefix some time after the contest was over. Impressively, Jed Davis came third by using a brute-force approach that won him the Judges' Prize - he was declared to be "an extremely cool hacker".
Update (2007-10-24): The organisers have now shared the video of their presentation about the contest at ICFP 2007.
2007-07-25
ICFPC 2007
I spent most of this weekend taking part in the ICFP contest for 2007. As in 2005, I took part in the contest with Yumpee as my team-mate. Our team was called "Kalianpur Bakaits" (an IIT-K reference) in the beginning, but we changed it to "The Great Indian Rope Trick" later, for reasons that should become obvious in a while.
This year's task was very similar to that from last year, but it was a bit tougher and even more fun. The organisers surely must have spent a lot of time and effort in putting together the task description and the supporting materials. There were no mistakes discovered in the task description for this year's contest (unlike those for the previous years' contests). The mailing list also had an unusually low-traffic during the contest - perhaps it was because the task description was precise enough, perhaps it was because a lot of people were finding it difficult just to get started or perhaps the contest was affected by the release of the latest Harry Potter book during the same weekend.
This year's task was to save an alien named "Endo". Endo was a "Fuun" travelling in a spaceship named "Arrow", when it had a mishap with an "interstellar garbage collector" that picked it and then dumped it on Earth. This caused critical damage to both Endo and Arrow. Our job was to repair Endo's DNA in such a way that Arrow is able to restore it to its former condition using its limited remaining power.
Endo's DNA is a long sequence comprising four bases, 'I', 'C', 'F' and 'P'. This sequence can be interpreted to create an RNA sequence comprising the same four bases that in turn can be used to build the proteins necessary to restore Endo. Prefixes comprising the four bases can be attached to a DNA sequence to modify its behaviour - we had to find a cheap and low-risk prefix that Arrow could process to repair Endo's DNA.
This translates to creating an interpreter for the DNA sequence that produces an RNA sequence, creating another interpreter for this RNA sequence that creates an image out of it and finally discovering a prefix that could restore Endo. The organisers provided us the DNA sequence for Endo, a "source" image resulting from interpreting this DNA sequence and a "target" image representing a fully-restored Endo. We were asked to create a DNA prefix that results in an image that is as close to the target image as possible, while being as short and as cheap to process as possible.
The task description was detailed enough for us to readily build a DNA to RNA converter as well as an RNA to image converter. The challenge was to do the processing quickly enough since the given DNA sequence required about 2 million iterations over a string that was about 7.5MB long. I created the DNA-to-RNA converter, while Yumpee built the RNA-to-image converter.
Since we had to splice and join huge lists while interpreting the DNA, I started off with a C implementation that used Lisp-style "cons" cells. While it seemed to perform well (but not good enough for the task), it had hard to track bugs that caused segmentation faults, not to mention memory leaks. I then tried using Java for creating the interpreter, which resulted in a correct but even slower interpreter. By this time, I had wasted two out of the three days allotted for the task. We had not made much progress while a lot of teams seemed to have discovered the same "magical" prefix comprising 28 bases that had boosted their rankings.
This is when I finally decided to act on Yumpee's suggestion of looking into using "ropes" as the underlying data structure. He had been suggesting it repeatedly since the time he had seen the task description, but I kept putting it off since I was not familiar with it. I decided to check out the "cords" implementation of ropes that comes with Boehm-GC. I modified my original interpreter in C to use cords instead of my home-grown and buggy cons-cells implementation.
The difference in performance was startling! The very first implementation ran through all the 2 million iterations in about 10 minutes on my PC and in about 4 minutes on Yumpee's PC. The code had also become much simpler to read and much closer to the pseudo-code provided in the task description. I debugged it a little to remove a bug that resulted from a misreading of the specification and then handed it over to Yumpee. By this time, he had a working RNA-to-image converter (he was also busy barking up the wrong trees till that time) and had also discovered the magic 28-base prefix. Unfortunately for us, we had just nine hours left to finish the task.
We discovered that the fun had just started. Embedded in the DNA were a series of clues that formed a virtual treasure-hunt, involving encrypted pages, EBCDIC-encoded text, fractals, callable functions, etc. We discovered a lot of clues but we couldn't find a prefix in time that would improve our rankings. It felt good that we could make so much progress by the end of the contest, unlike the last time. However, I felt like an idiot for not having listened to Yumpee earlier and saving myself and our team a lot of wasted time.
As I always end up saying after such contests, I hope we have a better luck the next time.
Some more reports: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, etc.
Update (2007-07-26): I tweaked the code for the DNA-to-RNA converter a little bit to avoid creating a lot of unnecessary cords and that reduced its running time to about 1 minute 35 seconds on my PC (about 7 times better than before) and about 30 seconds on Yumpee's PC. Right now the garbage collector itself is the biggest consumer of CPU cycles (about 45% on the whole), but disabling it leads to the programme quickly running out of memory on my PC.
This year's task was very similar to that from last year, but it was a bit tougher and even more fun. The organisers surely must have spent a lot of time and effort in putting together the task description and the supporting materials. There were no mistakes discovered in the task description for this year's contest (unlike those for the previous years' contests). The mailing list also had an unusually low-traffic during the contest - perhaps it was because the task description was precise enough, perhaps it was because a lot of people were finding it difficult just to get started or perhaps the contest was affected by the release of the latest Harry Potter book during the same weekend.
This year's task was to save an alien named "Endo". Endo was a "Fuun" travelling in a spaceship named "Arrow", when it had a mishap with an "interstellar garbage collector" that picked it and then dumped it on Earth. This caused critical damage to both Endo and Arrow. Our job was to repair Endo's DNA in such a way that Arrow is able to restore it to its former condition using its limited remaining power.
Endo's DNA is a long sequence comprising four bases, 'I', 'C', 'F' and 'P'. This sequence can be interpreted to create an RNA sequence comprising the same four bases that in turn can be used to build the proteins necessary to restore Endo. Prefixes comprising the four bases can be attached to a DNA sequence to modify its behaviour - we had to find a cheap and low-risk prefix that Arrow could process to repair Endo's DNA.
This translates to creating an interpreter for the DNA sequence that produces an RNA sequence, creating another interpreter for this RNA sequence that creates an image out of it and finally discovering a prefix that could restore Endo. The organisers provided us the DNA sequence for Endo, a "source" image resulting from interpreting this DNA sequence and a "target" image representing a fully-restored Endo. We were asked to create a DNA prefix that results in an image that is as close to the target image as possible, while being as short and as cheap to process as possible.
The task description was detailed enough for us to readily build a DNA to RNA converter as well as an RNA to image converter. The challenge was to do the processing quickly enough since the given DNA sequence required about 2 million iterations over a string that was about 7.5MB long. I created the DNA-to-RNA converter, while Yumpee built the RNA-to-image converter.
Since we had to splice and join huge lists while interpreting the DNA, I started off with a C implementation that used Lisp-style "cons" cells. While it seemed to perform well (but not good enough for the task), it had hard to track bugs that caused segmentation faults, not to mention memory leaks. I then tried using Java for creating the interpreter, which resulted in a correct but even slower interpreter. By this time, I had wasted two out of the three days allotted for the task. We had not made much progress while a lot of teams seemed to have discovered the same "magical" prefix comprising 28 bases that had boosted their rankings.
This is when I finally decided to act on Yumpee's suggestion of looking into using "ropes" as the underlying data structure. He had been suggesting it repeatedly since the time he had seen the task description, but I kept putting it off since I was not familiar with it. I decided to check out the "cords" implementation of ropes that comes with Boehm-GC. I modified my original interpreter in C to use cords instead of my home-grown and buggy cons-cells implementation.
The difference in performance was startling! The very first implementation ran through all the 2 million iterations in about 10 minutes on my PC and in about 4 minutes on Yumpee's PC. The code had also become much simpler to read and much closer to the pseudo-code provided in the task description. I debugged it a little to remove a bug that resulted from a misreading of the specification and then handed it over to Yumpee. By this time, he had a working RNA-to-image converter (he was also busy barking up the wrong trees till that time) and had also discovered the magic 28-base prefix. Unfortunately for us, we had just nine hours left to finish the task.
We discovered that the fun had just started. Embedded in the DNA were a series of clues that formed a virtual treasure-hunt, involving encrypted pages, EBCDIC-encoded text, fractals, callable functions, etc. We discovered a lot of clues but we couldn't find a prefix in time that would improve our rankings. It felt good that we could make so much progress by the end of the contest, unlike the last time. However, I felt like an idiot for not having listened to Yumpee earlier and saving myself and our team a lot of wasted time.
As I always end up saying after such contests, I hope we have a better luck the next time.
Some more reports: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, etc.
Update (2007-07-26): I tweaked the code for the DNA-to-RNA converter a little bit to avoid creating a lot of unnecessary cords and that reduced its running time to about 1 minute 35 seconds on my PC (about 7 times better than before) and about 30 seconds on Yumpee's PC. Right now the garbage collector itself is the biggest consumer of CPU cycles (about 45% on the whole), but disabling it leads to the programme quickly running out of memory on my PC.
2007-05-23
ICFP Contest 2007
The 10th ICFP Contest is scheduled for the weekend of 20th July 2007. I hope it turns out to be as fun as the one held last year.
There is already a blog written by one of the organisers that contains some teaser puzzles. (Do these images use some form of steganography or can we simply work out the graphical transformations applied to the original image and apply them in reverse to obtain the desired image? I wonder.)
There is already a blog written by one of the organisers that contains some teaser puzzles. (Do these images use some form of steganography or can we simply work out the graphical transformations applied to the original image and apply them in reverse to obtain the desired image? I wonder.)
2006-09-27
ICFPC 2006: Epilogue
The results of the ICFP contest for 2006 are now available. "Team Smartass" came first, followed by "kuma-" and "You Can't Spell Awesome Without ASM" in the second and third places respectively. Amazingly, the lone hacker "Witrala" was able to take the fifth place. Congratulations!
There is also a a video of the presentation by the contest's organisers at ICFP 2006. It is quite shaky, there are audio and video synchronisation problems and there is a guy sitting near the camera who gets tickled by almost everything into laughing out loud, but it is still worth a watch, especially for those who participated in the contest or those who want to know just how the organisers created the task.
This year's contest has proved to be so popular that the organisers have created a separate site called boundvariable.org dedicated to the "Cult of the Bound Variable".
An interesting bit about this year's contest was that the teams in the first and the third places were both from Google. Another interesting bit is that the individual members of these teams are also ranked very high on TopCoder and have been toppers in various contests organised by TopCoder. "Team Smartass" comprised Christopher Hendrie (ChristopherH), Derek Kisman (SnapDragon), Ambrose Feinstein (ambrose) and Daniel Wright (dmwright). "You Can't Spell Awesome Without ASM" comprised John Dethridge (John Dethridge), Ralph Furmaniak (RalphFurmaniak), Tomasz Czajka (tomek) and Reid Barton (reid).
Update (2006-10-22): Yumpee has pointed me to the ICFP 2006 paper (PDF) written by the organisers.
There is also a a video of the presentation by the contest's organisers at ICFP 2006. It is quite shaky, there are audio and video synchronisation problems and there is a guy sitting near the camera who gets tickled by almost everything into laughing out loud, but it is still worth a watch, especially for those who participated in the contest or those who want to know just how the organisers created the task.
This year's contest has proved to be so popular that the organisers have created a separate site called boundvariable.org dedicated to the "Cult of the Bound Variable".
An interesting bit about this year's contest was that the teams in the first and the third places were both from Google. Another interesting bit is that the individual members of these teams are also ranked very high on TopCoder and have been toppers in various contests organised by TopCoder. "Team Smartass" comprised Christopher Hendrie (ChristopherH), Derek Kisman (SnapDragon), Ambrose Feinstein (ambrose) and Daniel Wright (dmwright). "You Can't Spell Awesome Without ASM" comprised John Dethridge (John Dethridge), Ralph Furmaniak (RalphFurmaniak), Tomasz Czajka (tomek) and Reid Barton (reid).
Update (2006-10-22): Yumpee has pointed me to the ICFP 2006 paper (PDF) written by the organisers.
2006-07-25
ICFPC 2006
I participated in the ICFP programming contest for 2006 over this weekend. I was taking part in it purely for the fun of it (yes, really). It turned out to be a very interesting task. Check out the task description to see what I mean.
You have to first implement an interpreter for a simple but quirky virtual machine called the Universal Machine (UM). You then use this interpreter on the given data file ("codex.umz") to run a small programme that takes a password and uses this password to decrypt and uncompress a binary image. You then use the interpreter on this extracted binary image to discover a small UNIX-like multi-user system where you can log in as "guest". This system, called "UMIX", includes a set of common UNIX utilities like "ls", "rm", "cat", "more", etc., an interpreter for BASIC (called "Qvikbasic", that only recognises numbers written with Roman numerals) and a file-transfer utility called "umodem".
Using the guest account, you complete a simple password-cracking utiliy written in BASIC and use it to discover the passwords of a couple of other user accounts. When you log in as those users, you find more tasks that you can complete to discover the passwords of other user accounts, which yield even more tasks and so on till you get the "root" password. For example, one of the tasks was in the form of an Adventure-like game and another was using a "2-dimensional" programming language, complete with ASCII-art boxes for each function, to solve a given problem.
It was incredible and this is easily one of the best ICFPC tasks I have ever attempted.
You might also want to check out Mark Probst's account, Mauricio Fernandez's account, Gregory Brown's accounts (1, 2, 3, 4), etc.
The organisers also provided a handy benchmark for testing your UM implementation (called "SANDmark") and a reference UM implementation (in the form of a UM binary of course). If you want to quickly check it out, here is my UM implementation (written in C). You can use "(\b.bb)(\v.vv)06AAVKIru7p0OmCvaT" as the password to extract the UMIX binary image from "codex.umz" using this interpreter. (Paul Ingemi has even implemented a JIT-ing UM using LuaJIT!)
When I first implemented the UM, it ran quite slowly - it took a very long time for the UMIX login prompt to appear and over three hours just to compile "hack.bas" with Qvikbasic. I first tried simple tricks like converting indexed array accesses to incremental pointer accesses, caching values that were being used often, using a function-pointer-based dispatcher table to decode and execute instructions instead of a big switch statement, etc. but nothing helped. I found that the UM binaries allocate and deallocate a lot of "arrays" of various sizes and inspired by one of the posts to the ICFPC 2006 mailing list, I even implemented a system where arrays were only allocated in sizes of the smallest power of two larger than the requested size and recycled internally instead of being returned back to the operating system. However, even that did not help much.
That is when I decided to stop fooling around and ran the interpreter through qprof (I feel gprof and oprofile are not as immediately useful as qprof is - try it out and you would probably agree). I discovered that the real bottleneck was in the code that searched for a free slot to assign an index to a newly allocated array. When I eliminated that bottleneck by explicitly keeping track of freed slots, the performance of the interpreter improved drastically and it became usefully responsive. I eliminated the power-of-two array size foolery and it was still pretty responsive - malloc()/free() are really implemented pretty well in GNU libc and it is not usually worth it to second-guess it (except perhaps in extreme cases). (Also check out Doug Lea's notes on the design of a memory allocator.)
One of the wicked ideas from the mailing list did help however - using the pointer to an array's memory as its index instead of maintaining an "array of arrays", yielded a 20% boost in the performance of my UM implementation (as measured by SANDmark) but reduced its "portability" to only those machines where both integers and pointers are 32 bits.
The lesson learnt? We programmers are really quite bad at guessing the hotspots in our programmes. We should always use a profiler to find out where the real bottlenecks are in our programmes.
By the way, a few hapless souls discovered that the lack of unsigned integers in Java makes it unnecessarily difficult to implement something like this in Java. Why exactly couldn't the creators of the language provide unsigned variants of the integral types?
You have to first implement an interpreter for a simple but quirky virtual machine called the Universal Machine (UM). You then use this interpreter on the given data file ("codex.umz") to run a small programme that takes a password and uses this password to decrypt and uncompress a binary image. You then use the interpreter on this extracted binary image to discover a small UNIX-like multi-user system where you can log in as "guest". This system, called "UMIX", includes a set of common UNIX utilities like "ls", "rm", "cat", "more", etc., an interpreter for BASIC (called "Qvikbasic", that only recognises numbers written with Roman numerals) and a file-transfer utility called "umodem".
Using the guest account, you complete a simple password-cracking utiliy written in BASIC and use it to discover the passwords of a couple of other user accounts. When you log in as those users, you find more tasks that you can complete to discover the passwords of other user accounts, which yield even more tasks and so on till you get the "root" password. For example, one of the tasks was in the form of an Adventure-like game and another was using a "2-dimensional" programming language, complete with ASCII-art boxes for each function, to solve a given problem.
It was incredible and this is easily one of the best ICFPC tasks I have ever attempted.
You might also want to check out Mark Probst's account, Mauricio Fernandez's account, Gregory Brown's accounts (1, 2, 3, 4), etc.
The organisers also provided a handy benchmark for testing your UM implementation (called "SANDmark") and a reference UM implementation (in the form of a UM binary of course). If you want to quickly check it out, here is my UM implementation (written in C). You can use "(\b.bb)(\v.vv)06AAVKIru7p0OmCvaT" as the password to extract the UMIX binary image from "codex.umz" using this interpreter. (Paul Ingemi has even implemented a JIT-ing UM using LuaJIT!)
When I first implemented the UM, it ran quite slowly - it took a very long time for the UMIX login prompt to appear and over three hours just to compile "hack.bas" with Qvikbasic. I first tried simple tricks like converting indexed array accesses to incremental pointer accesses, caching values that were being used often, using a function-pointer-based dispatcher table to decode and execute instructions instead of a big switch statement, etc. but nothing helped. I found that the UM binaries allocate and deallocate a lot of "arrays" of various sizes and inspired by one of the posts to the ICFPC 2006 mailing list, I even implemented a system where arrays were only allocated in sizes of the smallest power of two larger than the requested size and recycled internally instead of being returned back to the operating system. However, even that did not help much.
That is when I decided to stop fooling around and ran the interpreter through qprof (I feel gprof and oprofile are not as immediately useful as qprof is - try it out and you would probably agree). I discovered that the real bottleneck was in the code that searched for a free slot to assign an index to a newly allocated array. When I eliminated that bottleneck by explicitly keeping track of freed slots, the performance of the interpreter improved drastically and it became usefully responsive. I eliminated the power-of-two array size foolery and it was still pretty responsive - malloc()/free() are really implemented pretty well in GNU libc and it is not usually worth it to second-guess it (except perhaps in extreme cases). (Also check out Doug Lea's notes on the design of a memory allocator.)
One of the wicked ideas from the mailing list did help however - using the pointer to an array's memory as its index instead of maintaining an "array of arrays", yielded a 20% boost in the performance of my UM implementation (as measured by SANDmark) but reduced its "portability" to only those machines where both integers and pointers are 32 bits.
The lesson learnt? We programmers are really quite bad at guessing the hotspots in our programmes. We should always use a profiler to find out where the real bottlenecks are in our programmes.
By the way, a few hapless souls discovered that the lack of unsigned integers in Java makes it unnecessarily difficult to implement something like this in Java. Why exactly couldn't the creators of the language provide unsigned variants of the integral types?
2006-07-20
ICFP Contest 2006
Those interesting in programming might want to check out the ICFP Contest for 2006 which will be held during the coming weekend (21st to 24th July 2006). The problems are generally open-ended and fun to solve even if your entry does not make it to the top - check out the problems from the previous years' contests to see what I am talking about.
2005-09-30
Mauled in ICFPC 2005
Our entry in ICFPC 2005 was mauled by just the judges' cops! Looking at the playback of the robber's performance, I want to hide my head in shame.
(Originally posted on Advogato.)
(Originally posted on Advogato.)
2005-06-28
ICFP 2005 Programming Contest
Yumpee and I participated in the ICFP 2005 programming contest over this weekend. The problem was quite interesting and quite open-ended in that one could keep trying different strategies and play them against each other to see how they fare. In the end however, we ran out of time and we could only submit rather rudimentary cops and robbers - a cop that walks about randomly on the map hoping to catch a robber by serendipity rather than by design, a robber that just tries to rob the nearest bank while trying to avoid cops with a two-level lookup and a robber that walks about randomly on the map merely avoiding running into cops.
In terms of the implementation choice, the only middle-ground for the two of us turned out to be C++. I wasted much of the time debugging silly problems that arose mainly because C++ and the STL do not seem to have been designed with comprehension for lesser mortals like me in mind. Oh and we leaked memory with a perverse and gleeful abandon! (And our memory footprint at the end of any match was still less than the default no-op cop written in PLT Scheme that came with the BDK.)
I really enjoyed the coding binge and it was funky trying to coordinate rapid coding with a fellow hacker in a timezone that was 12 hours behind. At the risk of forfeiting the judges' prize, we still have two weeks to tweak our code and implement better strategies before the other half of the problem is announced. However, I'll be bang in the middle of my vacation during that period so it will entirely be up to Yumpee alone.
(Originally posted on Advogato.)
In terms of the implementation choice, the only middle-ground for the two of us turned out to be C++. I wasted much of the time debugging silly problems that arose mainly because C++ and the STL do not seem to have been designed with comprehension for lesser mortals like me in mind. Oh and we leaked memory with a perverse and gleeful abandon! (And our memory footprint at the end of any match was still less than the default no-op cop written in PLT Scheme that came with the BDK.)
I really enjoyed the coding binge and it was funky trying to coordinate rapid coding with a fellow hacker in a timezone that was 12 hours behind. At the risk of forfeiting the judges' prize, we still have two weeks to tweak our code and implement better strategies before the other half of the problem is announced. However, I'll be bang in the middle of my vacation during that period so it will entirely be up to Yumpee alone.
(Originally posted on Advogato.)
Subscribe to:
Comments (Atom)
