ICFPC-2007: как наша трава оказалась хуже голландской (окончание)

[dastapov]

Это окончание рассказа о моем участии в 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 1000
execute

и смотреть, что происходит в "синей зоне" ДНК, т.е. на стеке.

И как-то так получается, что ничего хорошего у нас не получается. Мы пытаемся выяснить, как сами организаторы вызывают "гены", но их способ явно отличается от описанного в 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 и С символами 16x16 "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->RNA

Lessons 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.aspx
  
• http://community.livejournal.com/evan_tech/229595.html
  
• http://grayproductions.net/icfp07/
  
• http://haskell.org/haskellwiki/ICFP_Programming_Contest/Teams_2007
  
• http://heisenbug.blogspot.com/2007/07/endo-at-end.html
  
• http://jfkbits.blogspot.com/2007/07/diffing-endo.html
  
• http://jfkbits.blogspot.com/2007/07/not-programming-for-icfp-2007.html
  
• http://jsnell.iki.fi/blog/archive/2007-07-25icfp-2007.html
  
• http://marco-za.blogspot.com/2007/07/icfp-how-we-reached-top-15.html
  
• http://nibot.livejournal.com/597628.html
  
• http://nibot.livejournal.com/597762.html
  
• http://sambangu.blogspot.com/2007/07/python-to-rescue-icfp-contest-2007
  
• http://schani.wordpress.com/2007/07/23/why-ocaml-is-not-my-favorite-programming-language/
  
• http://stereotype441.livejournal.com/45150.html
  
• http://useless-factor.blogspot.com/2007/07/icfp-results.html
  
• http://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/20070723
  
• http://translate.google.com/translate?u=http%3A%2F%2Fkzk9.net%2Fblog%2F2007%2F07%2Ficfp_2007.html&langpair=ja%7Cen&hl=en&ie=UTF8
  
• http://dfyz.livejournal.com/41941.html
  
• http://diary.ru/~himself/?comments&postid=32637307
  
• http://yole.livejournal.com/355405.html
  
• http://faceted-jacinth.livejournal.com/78761.html
  
• http://larubin.livejournal.com/72322.html
  
• http://yole.livejournal.com/355745.html
  
• http://ender4.dsic.upv.es:81/darcs/tnt/
  
• http://existentialtype.net/?p=153
  
• http://existentialtype.net/?p=156
  
• http://panicsonic.blogspot.com/2007/07/icfp-07-post-mortem-i.html
  
• http://people.cs.uct.ac.za/~mgallott/icfp/
  
• http://qwandor.wordpress.com/2007/07/28/icfp-programming-contest/
  
• http://rmathew.blogspot.com/2007/07/icfpc-2007.html
  
• http://tapani.cs.chalmers.se/cgi-bin/ssi/icfp/writeup.html
  
• http://www.nabble.com/My-Haskell-ICFP-'07-Programming-Competition-entry-t4133666.html
  
• http://marco-za.blogspot.com/2007/07/icfp-how-we-reached-top-15.html
  
• http://oal.livejournal.com/475038.html
  
• http://zelych.livejournal.com/3959.html
  
• http://minorityblog.wordpress.com/2007/07/24/failure-story-on-icfp07/
  
• http://www.developers.org.ua/archives/bialix/2007/07/24/icfpc-2007-report/
  
• http://www.cs.cmu.edu/~tom7/icfp2007/
  
• http://infthi.livejournal.com/17846.html
  

Если знаете те, которых нет тут - присылайте/пишите в комментариях.

Копия нашего репозитория:
darcs get --partial http://adept.linux.kiev.ua/repos/icfpc2007/

Если вдруг вам интересна полная история - убирайте "--partial" и качайте все 300 патчей ;)

Comments

[ndion.livejournal.com]

Спасибо за отчет. Было очень интересно прочитать.

[jerom.livejournal.com]

Спасибо, ждём, что же напишет yole, он таки в top15 причём с генами, а не рисованием.

[http://users.livejournal.com/_navi_/]

ооо, спасибо огромное за такой подробный отчёт. Постараюсь рассказать, как наша команда шла к намеченной цели, сюда кину ссылку, как напишу.

[lomeo.livejournal.com]

Хе-хе


"Он набрал больше 50% survival chance следующим нехитрым способом: генерируем (чуть ли не вручную) цепочку RNA для самостоятельного рисования картинки, максимально похожей на целевую, после чего превращаем ее в DNA очевидным способом и submit-им."

[spamsink.livejournal.com]

Я не удивлюсь, если и на этот раз C++ окажется языком для разборчивых хакеров.

[http://users.livejournal.com/_adept_/]

Весьма и весьма на то похоже.

[artimind.livejournal.com]

Год ждал продолжения истории )) Получил огромное наслаждение! Спасибо!

[antimirov.livejournal.com]

Спасибо за отчёт, очень интересно. Буду ждать продолжения в след. году!

[eraplee.livejournal.com]

Класс! Спасибо! В след. году я участвую! :)

супер!

[mr-vally.livejournal.com]

спасибо, Дима
очень интересно

[neograff.livejournal.com]

отлично написано.

[daregod.livejournal.com]

Очень интересно, как в другой мир попал — где всё быстро, взрывно, что ли. Функционально, короче.
Единственно, что удручает — за временнЫм ограничением нет продолжения. В этом году результат был слабее, чем в предыдущем,— и это сразу сказывается на интересности. В прошлом году читал как детектив, в этом детектив начинается только в окончании и тут же заканчивается, полное ощущение облома.
Вот если бы команда продолжала изыскания даже после окончания… Но, думаю, это к организаторам, ведь многое можно получить, только взаимодействуя с ними. Хотя, думаю, было бы интересно даже и без них.

[http://users.livejournal.com/_adept_/]

В этом году вполне можно продолжать и после окончания соревнования - ведь успешность своего решения вполне можно оценить и без организаторов. Так что дело все-таки в команде, точнее - в наличии у нее свободного времени :)

Task

[qualexander.livejournal.com]

Интересно. Очень.
Содержательно это скорее соревнование в прикладной криптологии (codebreaking).
Желателен криптоаналитик (способный "точить пилу") в составе команды.

[stifff.livejournal.com]

спасибо. очень интересно. какой же там все-таки драйв...

[dimiii.livejournal.com]

Спасибо за историю.
Подготовка и выводы - очень поучительны.

Успехов в следующем году! ;)

[migmit.livejournal.com]

У меня такое ощущение, что либо надо учить язык IDA Pro, чтобы нацеливать дизассемблер на подобные вещи, либо писать свой.

[http://users.livejournal.com/_adept_/]

А IDA Pro умеет/позволяет исполнять код в процессе дизассемблирования? Потому как через статический анализ тут дальше первой итерации не продвинуться.

[kmmbvnr.livejournal.com]

>>Сравните наш результат с достижением jabber-ru - команды, состоявшей >>из одного человека. Он набрал больше 50% survival chance следующим >>нехитрым способом

Ну дык, прям как в реальной жизни. Очень много софта написано быстро но топорно, достигнуто 50% результата и хрен вытянешь еще больше.

[guerrero de terracota (from livejournal.com)]

Благодарю. :)

[barch.livejournal.com]

димка, отчет офигительный!
читал - прям как сам участвовал :)

[grizagufo.livejournal.com]

Я в этом году планировал участвовать, но фирма работодатель внесла свои коррективы :) и хотя часть из них была веселой, но потерял первые полтора суток соревнования.
очень вспоминал, почитав спецификацию, твой отзыв про твой первый участие в ICFP, в одиночку :)

а вот очень понравилось:
http://stereotype441.livejournal.com/45150.html
"So jes5199 rented about 20 more Amazon "supercomputers" and set them all to running Endo's functions."

[neuro159.livejournal.com]

Пока тормозило мы использовали наш рабочий JetBrains TeamCity, в гриде 25 машин.

[genn-org.livejournal.com]

Спасибо, очень интересно!

[dewfy.livejournal.com]

Такое впечатление, что вам просто не хватило QA, который просто шел бы позади и проверял, проверял...

[http://users.livejournal.com/_adept_/]

Угу. Было бы такое QA - совсем другая сказочка бы получилась, особенно - если бы еще убрать териториальную разнесенность :)

[shlema.livejournal.com]

Спасибо за интересный отчет.

Кстати, ещё после прочтения прошлогоднего отчета мне пришла такая мысль: а не стоит ли иметь в команде человека, который будет координировать действия остальных, при этом минимально занимаясь самим программированием? Такого себе Project Manager?

[http://users.livejournal.com/_adept_/]

У нас такой был, но он слишком много програмировал :)

[spaceinvaderz.livejournal.com]

Классный рассказ, спасибо :)

Организаторы и на этот раз не разочаровали с необычностью задания.

[dtim.livejournal.com]

Спасибо, отличный отчет!

[angelizer-is-me.livejournal.com]

Спасибо за великолепный отчет.

[niro.biz (from livejournal.com)]

Офигенно, читается моментально. Больше таких бы вот статей. Автору огромное спасибо.