dastapov: (Default)
[personal profile] 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 из рук в руки, и у семи нянек дитя осталось без глаз, зубов, ушей и мозгов.
* По ходу обсуждения надо сразу писать "протокол".

Как правильно заметил [livejournal.com profile] oal, очень похоже на правила кодинга в Больших Конторах...

Благодарности:
Юлька! Без твоей поддержки и участия ничего этого бы не было. Спасибо за идеи, обсуждение, советы, моральную поддержку и, конечно же, за организацию быта для ушедшего в задачу меня.
:-*

Бонусы


Ссылки на отчеты других участников (взято отсюда, из mailing list-а icfpc2007 и собрано самостоятельно):

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

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

Если вдруг вам интересна полная история - убирайте "--partial" и качайте все 300 патчей ;)
Page 1 of 2 << [1] [2] >>

(no subject)

Date: 2007-07-29 08:53 pm (UTC)
From: [identity profile] ndion.livejournal.com
Спасибо за отчет. Было очень интересно прочитать.

(no subject)

Date: 2007-07-29 09:03 pm (UTC)
From: [identity profile] jerom.livejournal.com
Спасибо, ждём, что же напишет yole, он таки в top15 причём с генами, а не рисованием.

(no subject)

Date: 2007-07-29 09:18 pm (UTC)
From: [identity profile] http://users.livejournal.com/_navi_/
ооо, спасибо огромное за такой подробный отчёт. Постараюсь рассказать, как наша команда шла к намеченной цели, сюда кину ссылку, как напишу.

(no subject)

Date: 2007-07-30 09:24 am (UTC)
From: [identity profile] lomeo.livejournal.com
Хе-хе


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

(no subject)

From: [identity profile] http://users.livejournal.com/_navi_/ - Date: 2007-07-30 09:27 am (UTC) - Expand

(no subject)

From: [identity profile] nealar.livejournal.com - Date: 2007-07-30 10:57 am (UTC) - Expand

(no subject)

From: [identity profile] http://users.livejournal.com/_adept_/ - Date: 2007-07-30 12:02 pm (UTC) - Expand

(no subject)

From: [identity profile] http://users.livejournal.com/_navi_/ - Date: 2007-07-31 11:08 am (UTC) - Expand

(no subject)

Date: 2007-07-29 09:22 pm (UTC)
From: [identity profile] spamsink.livejournal.com
Я не удивлюсь, если и на этот раз C++ окажется языком для разборчивых хакеров.

(no subject)

Date: 2007-07-29 09:31 pm (UTC)
From: [identity profile] http://users.livejournal.com/_adept_/
Весьма и весьма на то похоже.

(no subject)

Date: 2007-07-29 09:23 pm (UTC)
From: [identity profile] artimind.livejournal.com
Год ждал продолжения истории )) Получил огромное наслаждение! Спасибо!

(no subject)

Date: 2007-07-29 10:40 pm (UTC)
From: [identity profile] antimirov.livejournal.com
Спасибо за отчёт, очень интересно. Буду ждать продолжения в след. году!

(no subject)

Date: 2007-07-29 11:57 pm (UTC)
From: [identity profile] eraplee.livejournal.com
Класс! Спасибо! В след. году я участвую! :)

супер!

Date: 2007-07-30 12:48 am (UTC)
From: [identity profile] mr-vally.livejournal.com
спасибо, Дима
очень интересно

(no subject)

Date: 2007-07-30 04:35 am (UTC)
From: [identity profile] neograff.livejournal.com
отлично написано.

(no subject)

Date: 2007-07-30 05:02 am (UTC)
From: [identity profile] daregod.livejournal.com
Очень интересно, как в другой мир попал — где всё быстро, взрывно, что ли. Функционально, короче.
Единственно, что удручает — за временнЫм ограничением нет продолжения. В этом году результат был слабее, чем в предыдущем,— и это сразу сказывается на интересности. В прошлом году читал как детектив, в этом детектив начинается только в окончании и тут же заканчивается, полное ощущение облома.
Вот если бы команда продолжала изыскания даже после окончания… Но, думаю, это к организаторам, ведь многое можно получить, только взаимодействуя с ними. Хотя, думаю, было бы интересно даже и без них.

(no subject)

Date: 2007-07-30 06:23 am (UTC)
From: [identity profile] http://users.livejournal.com/_adept_/
В этом году вполне можно продолжать и после окончания соревнования - ведь успешность своего решения вполне можно оценить и без организаторов. Так что дело все-таки в команде, точнее - в наличии у нее свободного времени :)

(no subject)

From: [identity profile] heavywave.livejournal.com - Date: 2007-07-30 09:51 am (UTC) - Expand

Task

Date: 2007-07-30 06:08 am (UTC)
From: [identity profile] qualexander.livejournal.com
Интересно. Очень.
Содержательно это скорее соревнование в прикладной криптологии (codebreaking).
Желателен криптоаналитик (способный "точить пилу") в составе команды.

(no subject)

Date: 2007-07-30 06:43 am (UTC)
From: [identity profile] stifff.livejournal.com
спасибо. очень интересно. какой же там все-таки драйв...

(no subject)

Date: 2007-07-30 06:53 am (UTC)
From: [identity profile] dimiii.livejournal.com
Спасибо за историю.
Подготовка и выводы - очень поучительны.

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

(no subject)

Date: 2007-07-30 07:23 am (UTC)
From: [identity profile] migmit.livejournal.com
У меня такое ощущение, что либо надо учить язык IDA Pro, чтобы нацеливать дизассемблер на подобные вещи, либо писать свой.

(no subject)

Date: 2007-07-30 12:06 pm (UTC)
From: [identity profile] http://users.livejournal.com/_adept_/
А IDA Pro умеет/позволяет исполнять код в процессе дизассемблирования? Потому как через статический анализ тут дальше первой итерации не продвинуться.

(no subject)

From: [identity profile] migmit.livejournal.com - Date: 2007-07-30 02:50 pm (UTC) - Expand

(no subject)

Date: 2007-07-30 07:42 am (UTC)
From: [identity profile] kmmbvnr.livejournal.com
>>Сравните наш результат с достижением jabber-ru - команды, состоявшей >>из одного человека. Он набрал больше 50% survival chance следующим >>нехитрым способом

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

(no subject)

Date: 2007-07-30 08:01 am (UTC)
From: [identity profile] guerrero de terracota (from livejournal.com)
Благодарю. :)

(no subject)

Date: 2007-07-30 09:15 am (UTC)
From: [identity profile] barch.livejournal.com
димка, отчет офигительный!
читал - прям как сам участвовал :)

(no subject)

Date: 2007-07-30 04:11 pm (UTC)
From: [identity profile] 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."

(no subject)

Date: 2007-08-01 12:06 pm (UTC)
From: [identity profile] neuro159.livejournal.com
Пока тормозило мы использовали наш рабочий JetBrains TeamCity, в гриде 25 машин.

(no subject)

From: [identity profile] grizagufo.livejournal.com - Date: 2007-08-01 12:11 pm (UTC) - Expand

(no subject)

From: [identity profile] neuro159.livejournal.com - Date: 2007-08-01 12:21 pm (UTC) - Expand

(no subject)

From: [identity profile] grizagufo.livejournal.com - Date: 2007-08-01 12:28 pm (UTC) - Expand

(no subject)

From: [identity profile] neuro159.livejournal.com - Date: 2007-08-01 12:34 pm (UTC) - Expand

(no subject)

From: [identity profile] http://users.livejournal.com/_adept_/ - Date: 2007-08-03 06:25 pm (UTC) - Expand

(no subject)

From: [identity profile] ant0nio.livejournal.com - Date: 2007-08-04 09:55 am (UTC) - Expand

(no subject)

From: [identity profile] http://users.livejournal.com/_adept_/ - Date: 2007-08-04 09:47 pm (UTC) - Expand

(no subject)

Date: 2007-07-31 04:02 am (UTC)
From: [identity profile] genn-org.livejournal.com
Спасибо, очень интересно!

(no subject)

Date: 2007-07-31 09:27 am (UTC)
From: [identity profile] dewfy.livejournal.com
Такое впечатление, что вам просто не хватило QA, который просто шел бы позади и проверял, проверял...

(no subject)

Date: 2007-08-04 09:48 pm (UTC)
From: [identity profile] http://users.livejournal.com/_adept_/
Угу. Было бы такое QA - совсем другая сказочка бы получилась, особенно - если бы еще убрать териториальную разнесенность :)

(no subject)

Date: 2007-07-31 10:23 am (UTC)
From: [identity profile] shlema.livejournal.com
Спасибо за интересный отчет.

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

(no subject)

Date: 2007-08-04 09:49 pm (UTC)
From: [identity profile] http://users.livejournal.com/_adept_/
У нас такой был, но он слишком много програмировал :)

(no subject)

Date: 2007-07-31 11:36 am (UTC)
From: [identity profile] spaceinvaderz.livejournal.com
Классный рассказ, спасибо :)

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

(no subject)

Date: 2007-08-01 03:54 pm (UTC)
From: [identity profile] dtim.livejournal.com
Спасибо, отличный отчет!

(no subject)

Date: 2007-08-02 07:26 am (UTC)
From: [identity profile] angelizer-is-me.livejournal.com
Спасибо за великолепный отчет.

(no subject)

Date: 2007-08-02 12:49 pm (UTC)
From: [identity profile] niro.biz (from livejournal.com)
Офигенно, читается моментально. Больше таких бы вот статей. Автору огромное спасибо.
Page 1 of 2 << [1] [2] >>

Profile

dastapov: (Default)
Dmitry Astapov

April 2017

M T W T F S S
     12
3 45 6789
10111213141516
17181920212223
24252627282930

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags