Dmitry Astapov (_adept_) wrote,
Dmitry Astapov
_adept_

Category:

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

Это окончание рассказа о моем участии в 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 и собрано самостоятельно):

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

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

Если вдруг вам интересна полная история - убирайте "--partial" и качайте все 300 патчей ;)
Tags: haskell, icfpc
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 58 comments
Previous
← Ctrl ← Alt
Next
Ctrl → Alt →
Previous
← Ctrl ← Alt
Next
Ctrl → Alt →