?

Log in

dump -0f - /dev/mind
Я знаю Haskell, OCaml, GSM, эндофункторы и много других страшных слов
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 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 патчей ;)
Comments 
29th-Jul-2007 08:53 pm (UTC)
Спасибо за отчет. Было очень интересно прочитать.
29th-Jul-2007 09:03 pm (UTC)
Спасибо, ждём, что же напишет yole, он таки в top15 причём с генами, а не рисованием.
29th-Jul-2007 09:18 pm (UTC)
ооо, спасибо огромное за такой подробный отчёт. Постараюсь рассказать, как наша команда шла к намеченной цели, сюда кину ссылку, как напишу.
30th-Jul-2007 09:24 am (UTC)
Хе-хе


"Он набрал больше 50% survival chance следующим нехитрым способом: генерируем (чуть ли не вручную) цепочку RNA для самостоятельного рисования картинки, максимально похожей на целевую, после чего превращаем ее в DNA очевидным способом и submit-им."
29th-Jul-2007 09:22 pm (UTC)
Я не удивлюсь, если и на этот раз C++ окажется языком для разборчивых хакеров.
29th-Jul-2007 09:31 pm (UTC)
Весьма и весьма на то похоже.
29th-Jul-2007 09:23 pm (UTC)
Год ждал продолжения истории )) Получил огромное наслаждение! Спасибо!
29th-Jul-2007 10:40 pm (UTC)
Спасибо за отчёт, очень интересно. Буду ждать продолжения в след. году!
29th-Jul-2007 11:57 pm (UTC)
Класс! Спасибо! В след. году я участвую! :)
30th-Jul-2007 12:48 am (UTC) - супер!
спасибо, Дима
очень интересно
30th-Jul-2007 04:35 am (UTC)
отлично написано.
30th-Jul-2007 05:02 am (UTC)
Очень интересно, как в другой мир попал — где всё быстро, взрывно, что ли. Функционально, короче.
Единственно, что удручает — за временнЫм ограничением нет продолжения. В этом году результат был слабее, чем в предыдущем,— и это сразу сказывается на интересности. В прошлом году читал как детектив, в этом детектив начинается только в окончании и тут же заканчивается, полное ощущение облома.
Вот если бы команда продолжала изыскания даже после окончания… Но, думаю, это к организаторам, ведь многое можно получить, только взаимодействуя с ними. Хотя, думаю, было бы интересно даже и без них.
30th-Jul-2007 06:23 am (UTC)
В этом году вполне можно продолжать и после окончания соревнования - ведь успешность своего решения вполне можно оценить и без организаторов. Так что дело все-таки в команде, точнее - в наличии у нее свободного времени :)
30th-Jul-2007 06:08 am (UTC) - Task
Интересно. Очень.
Содержательно это скорее соревнование в прикладной криптологии (codebreaking).
Желателен криптоаналитик (способный "точить пилу") в составе команды.
30th-Jul-2007 06:43 am (UTC)
спасибо. очень интересно. какой же там все-таки драйв...
30th-Jul-2007 06:53 am (UTC)
Спасибо за историю.
Подготовка и выводы - очень поучительны.

Успехов в следующем году! ;)
30th-Jul-2007 07:23 am (UTC)
У меня такое ощущение, что либо надо учить язык IDA Pro, чтобы нацеливать дизассемблер на подобные вещи, либо писать свой.
30th-Jul-2007 12:06 pm (UTC)
А IDA Pro умеет/позволяет исполнять код в процессе дизассемблирования? Потому как через статический анализ тут дальше первой итерации не продвинуться.
30th-Jul-2007 07:42 am (UTC)
>>Сравните наш результат с достижением jabber-ru - команды, состоявшей >>из одного человека. Он набрал больше 50% survival chance следующим >>нехитрым способом

Ну дык, прям как в реальной жизни. Очень много софта написано быстро но топорно, достигнуто 50% результата и хрен вытянешь еще больше.
30th-Jul-2007 08:01 am (UTC)
Благодарю. :)
30th-Jul-2007 09:15 am (UTC)
димка, отчет офигительный!
читал - прям как сам участвовал :)
30th-Jul-2007 04:11 pm (UTC)
Я в этом году планировал участвовать, но фирма работодатель внесла свои коррективы :) и хотя часть из них была веселой, но потерял первые полтора суток соревнования.
очень вспоминал, почитав спецификацию, твой отзыв про твой первый участие в ICFP, в одиночку :)

а вот очень понравилось:
http://stereotype441.livejournal.com/45150.html
"So jes5199 rented about 20 more Amazon "supercomputers" and set them all to running Endo's functions."
1st-Aug-2007 12:06 pm (UTC)
Пока тормозило мы использовали наш рабочий JetBrains TeamCity, в гриде 25 машин.
31st-Jul-2007 04:02 am (UTC)
Спасибо, очень интересно!
31st-Jul-2007 09:27 am (UTC)
Такое впечатление, что вам просто не хватило QA, который просто шел бы позади и проверял, проверял...
4th-Aug-2007 09:48 pm (UTC)
Угу. Было бы такое QA - совсем другая сказочка бы получилась, особенно - если бы еще убрать териториальную разнесенность :)
31st-Jul-2007 10:23 am (UTC)
Спасибо за интересный отчет.

Кстати, ещё после прочтения прошлогоднего отчета мне пришла такая мысль: а не стоит ли иметь в команде человека, который будет координировать действия остальных, при этом минимально занимаясь самим программированием? Такого себе Project Manager?
4th-Aug-2007 09:49 pm (UTC)
У нас такой был, но он слишком много програмировал :)
31st-Jul-2007 11:36 am (UTC)
Классный рассказ, спасибо :)

Организаторы и на этот раз не разочаровали с необычностью задания.
1st-Aug-2007 03:54 pm (UTC)
Спасибо, отличный отчет!
2nd-Aug-2007 07:26 am (UTC)
Спасибо за великолепный отчет.
2nd-Aug-2007 12:49 pm (UTC)
Офигенно, читается моментально. Больше таких бы вот статей. Автору огромное спасибо.
Page 1 of 2
<<[1] [2] >>
This page was loaded Jun 23rd 2017, 3:44 am GMT.