Thoughts of a geek

28 July 2007

ICFP programming contest

Filed under: Computers, Interface, University — qwandor @ 12:18 pm

Last weekend I competed with a team of VUW students in the ICFP programming contest. This is an annual, international contest lasting 72 hours. It is run by a different university each year, so the format tends to vary from year to year. There are no restrictions on team size, programming languages or computing resources.

Our team (called ‘interfacers’, for want of a better name) consisted in the end (after several people did not end up participating for various reasons, and one person who happened to be in the lab joined us) of Andrew Childs (hereafter referred to as lorne), Timothy Goddard, Clinton Scott, Samuel Hegarty, Michael Welsh (yomcat) and me.

This year, it ran from 10:00 pm on Friday 20th July until 10:00 pm on Monday 23th July. The story behind this year’s task was that an alien (of the Funn species) named Endo had been dumped on Earth by an Interstellar Garbage Collector and then hit by a cargo container. Endo was unconscious, and could not survive on Earth in his then-current form. Therefore our help was urgently needed to provide the necessary modifications to his DNA to adapt him to Earth’s environment. Our proposed modifications were to be evaluated by his spaceship Arrow and the proposal most likely to ensure Endo’s survival would be performed by Arrow.

We were given a copy of Endo’s DNA (a 7.2 MiB string of the letters I, C, F and P), and a specification of how Funn DNA works. The DNA works by repeatedly modifying itself through a long series of matching and replacing according to certain rules (which we were given) until it is all consumed, and in the process producing RNA. We were also provided with a specification of how to transform the RNA into a 600×600 px image. We were given a source image (which is produced by running Endo’s DNA as provided), and a target image (which we were to attempt to reproduce by constructing a prefix to be prepended to Endo’s DNA):
Source image Target image

We started by looking at the specification on Friday night when it was released, and talking about it on IRC for a short time. We then started work the next day in one of the computer labs at VUW, with various people turning up between 9:00 am and about 2:30 pm. I started by writing a Java program to render RNA to am image, while Timothy started writing a Haskell program to run DNA and output RNA. When lorne turned up he took over writing the DNA executer, while Timothy wrote various Ruby scripts to generate test cases. yomcat was also writing some test RNA at around this point, as my RNA renderer was mostly finished (apart from a few minor bugfixes and improvements).

This left us mostly waiting on lorne to get the DNA executer working (so that we could start working on creating a prefix), which proved difficult to do efficiently. The problem was that executing the DNA requires around 2 million iterations, each of which would typically involve searching the whole (several million base) string, cutting it up and then joining it together again in a different order and with some parts added and removed. I learnt that I did not know Haskell as well as I had thought, and unfortunately our other team member who knew Haskell well did not end up participating. This meant the rest of us were stuck with little useful to do. I ended up leaving at about 10:00 pm, after eating pizza.

That night I considered starting an alternative implementation of the DNA executer, in C++ or Java. By the time I got in the next day, Timothy, Clinton and Samuel had already started doing so in Java. I joined them, among other things spending quite a bit of time trying to create a Rope-based datastructure to store the DNA string and effeciently perform the operations needed (it should have had θ(log n) time seek, split and concatenation, I believe). Unfortunately I never got this finished in time, and ended up giving up on it on Sunday night (or was it Monday morning?). We ended up using a linked list of arrays, with each list node keeping an offset and length for the part of the array it was actually using. From my understanding, this would have had θ(1) split and append but θ(n) seek (though with a fairly small constant factor).

By this point lorne had his Haskell DNA executer working, but it was very slow and tended to run out of memory. By Monday morning he had it running better, but still taking almost an hour to run on his laptop or several hours on the lab computers.
With this we managed to access various pages of a ‘Funn Field Repair Guide’, the first page of which we found by using a prefix which was written out but then erased when the DNA ran normally. The first page of this gave us a prefix for another image explaining (somewhat cryptically) how to find more pages, and also one which made the Endo image output sunny as a first step towards the target output. We submitted this ‘make-it-sunny’ prefix, which ended up being the furthest we ever got towards the target. I also attempted to work out how to generate prefixes to call gene ‘functions’ in the provided DNA based on some information provided in the repair guide, but unfortunately never got this working.

We (well, Timothy) eventually got our Java DNA executer working on Monday night, but it was not much faster than our Haskell implementation. I ended up leaving for home (and dinner) at around 9:30 pm, as there was no way I could make any progress towards producing a better prefix in the remaining half hour.

We ended up coming 91st-equal, along with 74 other teams who found the same ‘make-it-sunny’ prefix. A large number of teams acheived a slightly better result by reducing the ‘sunny’ prefix from 28 to 27 bases, while still having exactly the same effect.

Shortly after the end of the contest, lorne found some problems which were causing his Haskell to be so slow and managed to get it running in about 3 minutes.

After the contest ended, and after some hints on IRC, I was able to extract a PNG and MP3 from the DNA, which were encoded with a base for each bit after some ASCII-art text visible when viewing the DNA in a 16-character wide column (e.g. in a hex editor).

A lot of other teams also had similar problems getting their DNA executer program working in reasonable time, though some did create some very fast implementations. One team had a C implementation which took about 10 seconds to run.

All in all, our result was a little dissapointing, but it was still fun and I think that I learned something from the experience (at least, that writing a key part of a system in a language that only one member of the team knows well is a bad idea).

In case anybody is interested, our code is available from our git repository.

Advertisements

2 Comments »

  1. […] Forgot your password?Remember MeYou are viewing _adept_’s journalCreate a LiveJournal Account   Learn more dump -0f – /dev/mindБаечки о мобильной связи (GSM, CDMA) и IT индустрииPrevious EntryNext EntryRecent EntriesArchiveFriends’ EntriesUser InfoMemories ICFPC-2007: как наша трава оказалась хуже голландской (окончание)  29th-Jul-2007 08:55 pmЭто окончание рассказа о моем участии в ICFPC-2007. Тут начало, а тут – продолжение.Глава шестая, в которой моя “теория заговора” получает самое убедительное подтверждение22 июля, 08:30 EET (третий календарный день соревнования)Проснувшись утром, я вытягиваю пачку свежих патчей и вижу, что народ (zeeeee и Cale) всю ночь развлекался тем, что вылавливал огрехи в коде, ускорял отрисовку и добился в конце-концов того, что на моем ноутбуке процесс получения source.png из endo.dna занимает примерно минуту с константным потреблением памяти (около 300Мб).Я пишу скрипт, который принимает с командной строки префикс или файл с ним, получает RNA и грузит его в GUI. Проверяю. Все работает. Красота! И тут я вспонимаю про увиденный вчера “скрытый” префикс, который отрисовывается в самом начале процесса создания картинки с “грустным Эндо”.Я делаю прогон с этим префиксом, открывается GUI, я давлю на кнопку “Run full RNA” и … комната делает оборот вокруг меня, в кровь выбрасывается адреналин и я понимаю, что вот он – прорыв, и может быть даже еще не слишком поздно. Полученная картинка абсолютно недвусмысленно говорит о том, что перед нами – очередной puzzle.Я дрожащими руками переписываю с экрана два указанных префикса, делаю прогон и получаю инструкцию по доступу к “Руководству по ремонту ДНК в полевых условиях” и осветленную картинку с грустным Эндо. Увидев ее, я тут же отправляю соответствующий префикс на сайт организаторов, и мы попадаем в число тех, кто продвинулся как минимум на первый шаг.22 июля, 10:00 EET, тайное становится явнымЯ быстро запихиваю все свои находки в darcs и начинаю теребить всех на IRC с криками “Я же говорил! Это так чертов puzzle! Делайте pull и втыкайте”. Сообщение производит эффект разорвавшейся бомбы. Начинается безумная активность, все что-то пробуют и делают. Утренняя “статусная встреча” откладывается на 30 минут из-за общего ажиотажа.На встрече мы решаем первый делом понять, как же все-таки доступаться к repair guide и вынуть оттуда все, что попадется под руку. В инструкции сказано – “закодируйте номер нужной вам страницы при помощи оснований ДНК и подставьте результат вместо уже имеющегося в префиксе числа”. Некоторое время мы тупим, пытаясь кодировать числа не так, как указано, а так, как делает функция “asnat()” из спецификации. Но в 11:55 Lemmih все делает правильно, и мы получаем перечень страниц в repair guide.В следующие три или четыре часа мы достаем из guide-а все указанные в оглавлении страницы + еще одну, отсутствующую в перечне (номер 3). Страницы содержат завуалированные описания того, как вызывать “подпрограммы”, лежащие в endo.dna (процесс называется “активацией генов”), причем им можно передавать параметры и они могут возвращать значения. Оказывается ДНК разделено на три зоны, ограниченные строками-маркерами, причем у каждой зоны есть своя функция – в одно хранится “библиотечный код”, в другой организуется что-то вроде стэка для аргументов и результатов, а в третью “исполняется” скопированный из библиотеки код. Кроме того, в руководстве есть намеки на то, что не все гены активируются одинаково, есть минимум две схемы передачи параметров, существует какая-то система шифрования кода, компрессии-декомпресии ДНК и т.д. и т.п. Кроме того, нам достается таблица с частью перечня “генов”, имеющихся в ДНК. На странице есть примечание: “page 1 of 14”, но остальные 13 страниц сходу найти не удается.После суток информационного голода и медленного соскальзывания в бездны отчаяния мы оказываемся буквально завалены информацией, но что с ней делать – решительно непонятно. По приведенной в руководстве процедуре получается вызвать только “ген” appletree, который привел к тому, что перед рисованием стандартной грустной картинки было нарисована яблоня с яблоками.В процессе ковыряния мы пишем код вагонами. В GUI добавляется tab с кучей сервисных кнопочек и строк ввода: генерация префикса для страницы с указаным номером, мы доделываем язык для написания pattern-ов и template-ов и в GUI появляется компиляция введенных руками pattern-а и template-а в ДНК. Можно запускать преобразование DNA->RNA и потом отрисовывать результат, а можно запускать в режиме параллельной генерации и рисования, и т.д. и т.п.Объктами нашего пристального внимания становятся “гены” AAA_geneTablePageNr и addInts. С помощью первого мы надеемся добыть 13 недостающих страниц таблицы генов, а с помощью второго – понять, как передавать аргументы и получать возвращаемые значения. Мы реализовываем свой язык (транслируемый в ДНК), который позволяет нам писать (в коде или в комстроке ghci) вещи вида:callGene “addInts” [1,2]dumpBlueZone 1000executeи смотреть, что происходит в “синей зоне” ДНК, т.е. на стеке.И как-то так получается, что ничего хорошего у нас не получается. Мы пытаемся выяснить, как сами организаторы вызывают “гены”, но их способ явно отличается от описанного в guide-е, и нам не удается аннотировать лог трансляции DNA в RNA именами “вызываемых функций”. Мы пытаемся перебором найти еще какие-то страницы в руководстве и всемером с помощью скрипта перебираем все номера с 0 до 2500 (найдя всего одну страницу 1024, которой у нас до этого не было). Мы пытаемся трассировать “вызов” гена appletree – единственного, который у нас получается вызвать – и извлечь что-то из лога. Cale даже пытался писать по смещению AAA_geneTablePageNr какие-то числа, но ничего хорошего у него не получилось – как правило, обработка DNA досрочно завершалась либо выводился какой-то мусор. Надо было бы кому-то еще проверить его результат, но мы поверили на слово.Получается, что крокодил не ловится, не растет кокос. Все опять начинают потихоньку “залипать” пробуя и перепробуя по кругу одно и то же.22 июля, 23:00 EET. Большой привет любителям rankk.org и pythonchallengeВ 23:00 я понимаю, что последние пол-часа топчусь на месте. И тут я случайно вспоминаю про надпись “Auchtung! Portable Network Graphics follows!”, которую Cale видел в hex-дампе ДНК в виде ascii art. Проверяю – и действительно, при помощи букв I и С символами 16×16 “ascii-точек” в ДНК написана эта надпись. А следом за ней идет еще один большой кусок из букв I и C, который не складывается в ascii art, зато имеет длину, делящуюся на 8 нацело. Ха! Мы ведь это проходили, нам ведь это задавали (в pythonchallenge.com).Превращаю буквы в битики, их – в байты, и дамплю в файл. Получается натуральный PNG. В котором на белом фоне написано “Human audio follows” 😉 Тааак. Повторяю со следующим куском из I и С, получаю mp3. В котором ускоренный “инопланетный голос” быстро-быстро произносит по буквам префикс. Делаю “sox prefix.mp3 slow.wav speed 0.5” и записываю не торопясь :)Делаю прогон с полученным префиксом … 1.8 млн итераций …. 1.9 млн итераций … 2 млн итераций. Волевым усилием я отрываю себя от стула и иду спать.Глава седьмая, про то как перед смертью не надышишься23 июля, 08:30 EET, 4.5 часа до окончания соревнованияОказалось, что через много-много итераций из найденого в аудиофайле префикса получится страничка guide-а про perfect numbers. Как мы эти perfect numbers ни крутили – не выходит каменный цветок 😦 Пробовали и сами perfect numbers, и taxicab numbers, и еще 10-20 разных последовательностей из “Internet encyclopedia of integer sequences” – не генерятся новые странички и всё тут.В какой-то момент я смотрю на Scoreboard и вижу, что кроме когорты участников с префиксом в 28 символов и одинаковым результатом есть когорта участников с таким же результатом, но префиксом в 27 символов. Быстрая проверка показывает, что в pattern-е можно сократить “?IFCIP” до “?IFCI” (за точность строчки не ручаюсь), и мы перемещаемся в следующую группу пелетона. И тут Cale в очередной раз что-то правит hex-редактором прямо в endo.dna и в результате прогона получает (в какой-то момент отрисовки) картинку с фотографией разработчиков, держащих в руках таблички с буквами, из которых можно сложить префикс, причем сразу после отрисовки картинка заливается черным цветом. У него получается сделать screenshot и записать префикс. Прогнав его, мы получаем картинку с регистрационным кодом, который выглядит многообещающе (ранее нам попадалось описание алгоритма шифрования, для применения которого требовалось что-то подобное).Кроме того, Lemmih решает самостоятельно попробовать что-то записать по смещению AAA_geneTablePageNr и выясняется, что Cale неправильно рассчитывал смещение в своих экспериментах и по этой причине ничего не получил. А Lemmih получил вторую страницу Gene Table. И третью, и четвертую и так далее, вплоть до четырнадцатой.Правда, на часах у нас уже 12:10, до окончания соревнования 50 минут, и все, что нам остается – это пытаться суматошно вызывать какие-то гены с многообещающим названием в надежде, что вот он – долгожданный прорыв. Увы и ах, чуда не происходит. К моменту закрытия scoreboard-а у нас нет результата лучшего, чем “осветленная картинка с грустным Эндо” и префиксом в 27 символов. Фактически, это “гол престижа” и не более того. Сравните наш результат с достижением jabber-ru – команды, состоявшей из одного человека. Он набрал больше 50% survival chance следующим нехитрым способом: генерируем (чуть ли не вручную) цепочку RNA для самостоятельного рисования картинки, максимально похожей на целевую, после чего превращаем ее в DNA очевидным способом и submit-им. Что это – свидетельство его гениальности/прагматичности, нашей глупости/замороченности, баг в идее соревнования, или … ?PSДа, а при чем же тут трава, вынесенная в заголовок поста? Да очень просто – посмотрите на нашу картинку и на target.png. Сразу видно, что наша трава хуже – и цвет не тот, и нарисована не там, где у организаторов.Эпилог. Итоги, благодарности и lessons learnedНачнем с краткого перечисления того, что мне понравилось и не понравилось:Понравилось:* Получил бесценный опыт участия в большой команде* То, что команда в целом не сдавалась до последних минут, все друг другу помогали и поддерживали.* В принципе, мы получили достаточно удовольствия от процесса, невзирая на скромный результат.* То, как мы совместно писали код в gobby. Это как парное программирование за одним компьютером, но с двумя клавиатурами :)* Замороченность задания, которое напомнило мне беззаботное детство и ломание защит на ZX Spectrum :)* Наша предварительная подготовка сыграла на 110%* Я не пропускал еду и сон, каждый день гулял и делал перерывы, как и планировалось.Не понравилось:* Замороченность задания, которое местами сводило соревнование по программированию к соревнованию по решению головоломок.* То, что я сам не использовал часть lessons learned от ICFPC-2006.* Проблемы с общением, которые мы испытывали из-за нашей териториальной разобщенности.* То, как мы затупили с реализацей DNA->RNALessons learned:* Нам надо было держать отдельное место для накопления безумных идей и иметь выделенного человека для их проверки* Нам надо было больше проверять друг друга* Нам надо было больше использовать тот факт, что мы несколько раз писали реализацию DNA->RNA – договорится о формате тестовых данных, генерировать их в этом формате, сравнивать между собой* Нам надо было больше экспериментировать с данными нам материалами. С помощью ручки и бумаги посмотреть, как происходят первые пару итераций обработки исходного ДНК, поразглядывать его в hex-редакторе и т.п.* Нам надо было четко сформулировать нашу Главную Цель, и уже потом идти к ней (постоянно уточняя). А так мы дошли до мысли о том, что нам надо глубже разобраться в семантике различных операций, скрытых в ДНК, только в последний день. * Команда должна сидеть в одной комнате или в соседних комнатах, иначе проблемы с коммуникацией убивают обмен идеями.* Идеально – когда вся команда спит и бодрствует по более-менее одному и тому же графику.* Один алгоритм кодируется одним человеком. Мы пытались передавать код DNA->RNA из рук в руки, и у семи нянек дитя осталось без глаз, зубов, ушей и мозгов.* По ходу обсуждения надо сразу писать “протокол”.Как правильно заметил oal, очень похоже на правила кодинга в Больших Конторах…Благодарности:Юлька! Без твоей поддержки и участия ничего этого бы не было. Спасибо за идеи, обсуждение, советы, моральную поддержку и, конечно же, за организацию быта для ушедшего в задачу меня.:-*БонусыСсылки на отчеты других участников (взято отсюда, из mailing list-а icfpc2007 и собрано самостоятельно):http://blogs.msdn.com/cashto/archive/2007/07/23/the-icfp-10th-annual-programming-contest.aspxhttp://community.livejournal.com/evan_tech/229595.htmlhttp://grayproductions.net/icfp07/http://haskell.org/haskellwiki/ICFP_Programming_Contest/Teams_2007http://heisenbug.blogspot.com/2007/07/endo-at-end.htmlhttp://jfkbits.blogspot.com/2007/07/diffing-endo.htmlhttp://jfkbits.blogspot.com/2007/07/not-programming-for-icfp-2007.htmlhttp://jsnell.iki.fi/blog/archive/2007-07-25icfp-2007.htmlhttp://marco-za.blogspot.com/2007/07/icfp-how-we-reached-top-15.htmlhttp://nibot.livejournal.com/597628.htmlhttp://nibot.livejournal.com/597762.htmlhttp://sambangu.blogspot.com/2007/07/python-to-rescue-icfp-contest-2007http://schani.wordpress.com/2007/07/23/why-ocaml-is-not-my-favorite-programming-language/http://stereotype441.livejournal.com/45150.htmlhttp://useless-factor.blogspot.com/2007/07/icfp-results.htmlhttp://varsztat.com/clfp/http://vikipedia.wordpress.com/2007/07/23/icfp-with-haskellpython-ocaml/http://wiki.freaks-unidos.net/icfp/2007/http://www.pley.de/icfp/http://66.249.91.104/translate_c?hl=en&langpair=ja%7Cen&u=http://d.hatena.ne.jp/shinichiro_h/20070723http://translate.google.com/translate?u=http%3A%2F%2Fkzk9.net%2Fblog%2F2007%2F07%2Ficfp_2007.html&langpair=ja%7Cen&hl=en&ie=UTF8http://dfyz.livejournal.com/41941.htmlhttp://diary.ru/~himself/?comments&postid=32637307http://yole.livejournal.com/355405.htmlhttp://faceted-jacinth.livejournal.com/78761.htmlhttp://larubin.livejournal.com/72322.htmlhttp://yole.livejournal.com/355745.htmlhttp://ender4.dsic.upv.es:81/darcs/tnt/http://existentialtype.net/?p=153http://existentialtype.net/?p=156http://panicsonic.blogspot.com/2007/07/icfp-07-post-mortem-i.htmlhttp://people.cs.uct.ac.za/~mgallott/icfp/https://qwandor.wordpress.com/2007/07/28/icfp-programming-contest/http://rmathew.blogspot.com/2007/07/icfpc-2007.htmlhttp://tapani.cs.chalmers.se/cgi-bin/ssi/icfp/writeup.htmlhttp://www.nabble.com/My-Haskell-ICFP-’07-Programming-Competition-entry-t4133666.htmlhttp://marco-za.blogspot.com/2007/07/icfp-how-we-reached-top-15.htmlhttp://oal.livejournal.com/475038.htmlhttp://zelych.livejournal.com/3959.htmlhttp://minorityblog.wordpress.com/2007/07/24/failure-story-on-icfp07/Если знаете те, которых нет тут – присылайте/пишите в комментариях.Копия нашего репозитория:http://adept.linux.kiev.ua/repos/icfpc2007/Tags:haskell, icfpc […]

    Pingback by dump -0f - /dev/mind - ICFPC-2007: как наша трава оказалась хуже голландской (окончание) — 30 July 2007 @ 8:30 am

  2. Диз у блога не очень. Может поменяешь?давай помогу.

    Comment by трусаг — 7 March 2009 @ 3:21 pm


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: