Google SA Office

Little under a year ago, Google advertised three job positions in South Africa. Yesterday it was announced that Novell SA country manager, Stafford Masie, has taken one of those positions. He will be heading operations here from 3 September.

This is a very exciting move for SA. They have yet to decide whether the office will run from Cape Town or Johannesburg. This is only the beginning, however. What I'm waiting for is for Google to open up an engineering office in SA. That would be awesome! Amazon recently opened an engineering office in Cape Town, so there is definitely interest. We have a fair number of talented computer scientists coming out of our universities every year.

There is already a google.co.za domain with some of our official languages, which has been around for a good couple of years now. Google Maps data for SA is aweful and that is generally one of the first projects when a new engineering office opens. If you don't know what I'm talking about, do a search in America (you can even drag the route!).

ICFP Contest Losing It's Functional Nature?

When I first participated in the ICFP Contest last year I was expecting an AI problem from looking at previous years. I was attracted to the contest because of this. My team had won the Java Challenge (renamed the Parallel Challenge for that year) in the ACM ICPC the previous year, so I thought it would be nice to try out the longer version.

So I got a team together telling them to expect some AI. None of us knew any functional programming and although we could see from previous years that it was beneficial we weren't taking it seriously. We get the problem and boom, "code a VM". Ok, where's the AI? We immediately jumped in with C++ and even then we initially had efficiency problems, although those were quickly rectified. Everyone complained afterwards that functional languages lost out there.

Then the mini problems started revealing themselves one by one. I will admit we didn't get very far with them (mainly due to factors out of our control and a lack of interest from some who expected an AI problem). Some of the problems were slightly functional in nature, but I still don't think there was any major benefit in using a functional language.

After the lack of AI in 2006, I was able to gather some people into the team that previously wouldn't participate because of the AI nature in the past. This year we were far more prepared for a non-AI problem. I also got a larger team together after 2006 being multiple small problems. Once again, none of were functional programming gurus (although by now I have at least know a bit of Haskell).

We get the problem this year and once again it starts off with a VM (DNA->RNA). With most of our team being C++ fanatics, we quickly got it running and even discovered ropes pretty quickly. From reading other peoples comments, the functional languages suffered with the VM. Although it was possible to get an efficient VM, the sub-linear data structures appear to be fairly uncommon. Yes, they're not that common in C++ either, but the functional teams sure seemed to rush over to C++.

Then there were the problems once you've passed the VM. Our team used Perl, Python and a bit of Bash to glue the scripts together. I don't see how a functional language could have been beneficial in any way. Even if someone does find a way of using a functional language, I sure would like to see how functional languages can do a better job.

The idea of the ICFP Contest is to promote functional programming. Or at least, that used to be one of its goals. Has this emphasis changed? There sure still seem to be many teams whose primary tools are functional languages. Last year, none of the top three teams nominated a functional language as their primary tool. I'm confident the same will occur this year.

I certainly do not mean for this to be an attack on the contest. I still love it. This is just something that has been on my mind making me wonder what the connection to the ICFP is. Is it possible that the functional programming community can learn from the lack of results from functional teams and make the functional languages more powerful? Maybe that's the aim?

I Have a TV

Remember my post about my home theater? All I was waiting for back then was the TV. Well, it arrived on Friday and was installed on Saturday. Unfortunately the news of its arrival has been swamped by my participation in the ICFP. Nevertheless, it is here!

Up until a week ago we were going for the 42". Well, that all changed when the price dropped by a huge amount. We are now stuck with an even bigger 50"! I tell you, seeing these things in the stores is one thing. Having them in your own home...that's the first time you truly see how beatiful and how enormous these beasts truly are! Here's an attempt at trying to awe you readers out there, although it barely touches the true beauty this thing reveals:


A couple of weeks ago we got a PS3. I was amazed at the graphics on an SD TV..you can imagine my amazement when connected to this beast. Currently we're waiting for the real games to come out so we only have Resistance and Motor Storm. I am anticipating the launch of GT5, which is said to be the first ever full 1080p game.

We also have one of these wonderful devices hooked up. It streams divx content over the network. I tell you, with an HD panel you can't not notice the low quality of divx. That's to be expected, but I didn't realise just how noticeable it would be.

Then finally we have Multichoice's PVR, which there isn't much to talk about.

You have to see and hear it for youself to understand just how amazing the whole setup we have going is. The guy that came to install the TV said the sound was the best he's ever heard, and he even has the same amp! He also loved the Ziova - to the point where he's trying to get one for himself now. :P

ICFP: How We Reached the Top 15

The United Coding Team once again tackled the ICFP Contest this year. This time we managed to hit the top 15. How did we manage that? Well, read on I say!

The team this year consisted of the following members, all students at the University of Cape Town, South Africa:

• Richard Baxter
• Carl Hultquist
  
• Marco Gallotta
  
• James Gray
• Alexander Karpul
  
• Julian Kenwood
  
• Bertus Labuschagne
  
• Bruce Merry
  
• Max Rabkin
• Harry Wiggins

and two team managers:

• Hayley McIntosh
• Ian Saunder

The problem of this year's ICFP Contest started off with us receiving Endo's DNA, which was 7MB. The DNA was interpreted as a sequence of patterns, which searched for some DNA, and templates, which described how to manipulate the DNA at that point. Some of the DNA caused RNA to spew out. The RNA was then interpreted as drawing commands to draw an image. Endo's original DNA sequence created this image:


Our task was to reverse engineer the DNA and poke away by coming up with a prefix to prepend to Endo's DNA to morph him to stand a better chance of survival on Earth, where he has crashed. We were given a target image to aim for (below) and we were scored by the number of pixels we got correct and the length of our prefix, with a shorter prefix being better.


Being in South Africa, we fitted nicely into the same timezone as the organisers so we started at noon on Friday. We took about an hour to read through the problem statement to decipher the meaning of the DNA. We then split up the tasks of writing a DNA->RNA and RNA->image converter.

Carl, Alex, Harry and I worked on the DNA converter while Bruce and James did the RNA->Image converter, both in C++. The RNA->image converter didn't take too long, but the DNA->RNA converter had efficiency issues. We got a working version by about 17:00, but it was horrendously slow compared for what we needed. Max joined us after work and quickly gave us the idea of ropes. None of us had used them before though so we had to read up on them to decide if they would be useful. We went for them in the end, but they caused us major headaches. The rope substr function defaults to taking only one character from the string instead of the usual running to the end.

After working on all these annoying bugs we finally got it working some time around 20:00 or so. We then used the prefix given to us in the problem text which ran some self checks. Unfortunately one of them failed and it was back to debugging. The bug appeared to be related to ropes, since our strings version passed all the self checks. It was also odd that it worked with compiler optimisations, but not without them enabled. While Carl worked on debugging, Bruce worked on some OpenGL code to display the image as it was being generated so we could see any hidden messages that were covered by later layers.

With the OpenGL code we discovered a hidden prefix which when run gave us a field repair guide which led us to a catalogue page and a prefix to rise the sun. Julien and Richard spent some time trying to figure out how to use the catalogue prefix to view other pages, but only ended up at invalid pages. When Bruce had a moment of free time we gave it to him and he solved it very quickly. We replaced the number in the prefix with the page number we needed. Page 1337 gave us the catalogue index page. This opened up a whole bunch of new pages which both helped us understand the DNA and gave us new problems to solve.

We did a brute force search on the page number to see if we could find any undocumented pages. Of note were pages 100 and 1024. We searched up to about 20000 pages, but didn't find much else. The stegonography hint gave us the number 9546 in the ET page, although we never figured out a use for it. The Virus Alert page we noticed was Wingdings, but we didn't find a use for the message. The Intergalactic Character Set pointed us to ebcdic. The Undocumented RNA helped us print a stack trace of function calls.

One of the pages extracted was a Gene Table. It said "Page 1 of 14" on the top. We got the remaining 13 pages by setting the value AAA_geneTablePageNr to the one we wanted. We also later discovered from the ImpDocs that printGeneTable took a boolean parameter that when set to true ran integrity checks. This proved valuable later on when we got to fixing functions in the various ways. We got some of our team, including team managers, to transcribe the gene table. From this we wrote scripts to call a function in a human readable format. This was the start of our scripting language that generated a prefix.

Some of the function calls yielded further help pages and more problems to solve. We noticed that the contest-xxxx pages had some yellow letters (ICFP's). When combined these gave us another prefix. The Encodings page helped us search for strings and polygons in the DNA. Some of these strings were helpful, while most of them we had already seen. The Fuun Security Features page was easily noticed to be encrypted with rot13.

We extracted the hitMeWithAClueStick function from the DNA. Removing the C's and trying different widths gave us the message "PORTABLE NETWORK GRAPHICS FOLLOWS". We then noticed the data was split into three sections by P's. The second chunk gave us a PNG image, which told us that an audible voice followed and we then interpreted the remaining segment as an MP3, which read out yet another prefix. This gave us the Beautiful Numbers page, which didn't get us anything extra since we had already found page 496 by brute force.

All the above was about sub-problems in the contest. However, none of this helps morph poor Endo into a cow to save him. At least, not directly. Most of the sub-problems yielded clues which in turn helped us find the right DNA to poke into Endo's DNA, call functions and do other interesting things to it. These all helped us morph the source image into the target image. Since we've been asked by the organisers not to reveal our score I think this is as far as I should go.

Hopefully what I have said should be sufficient for those that did not get very far to poke around and at least get some satisfaction from the problem. I can imagine that many of you spent the entire weekend and got nowhere.

Has Endo been saved? More importantly, have we saved Endo? We have to wait until the International Conference on Funtional Programming in October where the results will be announced.

Post mortems from other teams:

• United Coding Team (2nd)
• Celestial Dire Badger (3rd)
  
• ryba (more pages) (4th)
• Purely Functional Infrastuructre (5th)
• jabber-ru (6th)
• Begot (7th)
• SwtPl (9th)
  
• shinh (10th)
• SzM (11th)
  
• kuma- (12th)
• Unknown? (13th)
  
• kokorush (15th)
  
• The Caml Riders (17th)
• The Corn Worf Strategy (28th)
  
• fun (31st)
• solo r6 (32nd)
  
• jsnell (45th)
• /void/ im Kopf der Mensch (48th)
  
• LazyBottoms (more) (56th)
• efg (64th)
  
• on byte nirvana (more pages) (79th)
• tnt (80th)
  
• cashto (84th)
• DylanHackers (88th)
• cultboundvariable (98th)
  
• Side-Effects (more) (116th)
• interfacers (121st)
• The Great Indian Rope Trick (127th)
  
• Raptors (354th)

Other writeups I haven't been able to link to a team:

• Programming contest postmortem
• ICFP '07 Contest
• ICFP with haskell/python ...ocaml??
• Python to the rescue: ICFP contest 2007
• Russian pages translated
  
• clfp
• RNA Debugger
  
• ICFP Programming Contest/Teams 2007
  
• Not Programming for the ICFP 2007 Programming Contest
• Diffing Endo
  
• ICFP '07 Post-Mortem
  

Top 15 in ICFP Contest

The ICFP Contest ended just four hours ago. I'm so excited to tell you that we, the United Coding Team, have found ourselves somewhere in the top 15 out of 869 teams. We suspect that we're reasonably high up within the top 15 as well from looking at positions 16+ on the scoreboard, although we've been asked to keep our score private until the final standings are announced at the ICFP (a conference) during 1-3 October.

I am extremely exhausted right now and it's time to catch up on some much needed sleep. Once I've regained some energy I will post some details of how we tackled the problem. In the meantime, here are a couple of pictures of our team (unfortunately with me being the photographer I'm not in any of them).

Saving Endo!

Over the past 47 hours we have been transforming this image:


into this image:


This year's ICFP task is to save the alien Endo who has crash landed on Earth by morphing him to stand a better chance of survival in this unfamiliar environment. We are given his DNA which for the purposes of the problem draws the image on top. Our task is to prepend DNA to get the bottom image. The full problem description can be read here.

On Friday we jumped into the top 20 and have remained their since. Other than that I shall refrain from discussing our results as the contest is still underway for another 25 hours.

Go United Coding Team!

PS: Thanks Bruce, without you we would still be interpreting the meaning of the DNA. :)

ICFP Contest Tomorrow

The ICFP Contest is finally underway tomorrow at noon and continues non-stop through till Monday noon. That's 72 hours of coding goodness! Sweet!!

Currently we're sitting on a total team size of 19. I think that's a record. :P We have the 4th ranked TopCoder, 6 IOI participants, 2 IMO participants and 4 ACM world finalists on our team. Not to mention the circus guy whose primary form of transportation is a unicyle and some silly man who likes his hair green.

Unfortunately there's a scheduled power cut on Saturday from 11:00-13:00, although we're not sure if we'll be affected.

One of the contest organisers has a blog in which he's been going on about this story about a spam message they received from which they've decrypted and posted several pictures. They are obviously connected to the contest, since recent postings have mentioned that they're getting close to cracking its secrets and it looks like they will "crack" it when the contest begins.

If I get a break I might be posting brief updates during the contest. So keep your eyes glued!