dastapov: (Default)
[personal profile] dastapov
Прошел год с тех пор, как я в составе команды Lazy Bottoms боролся за победу в ICFPC-2006. Победить нам не удалось, но мы заняли достаточно почетное 18 место (среди 360 команд), причем упорная борьба шла до самых последних минут и в течении последнего часов соревнования top 10 достаточно сильно изменялся.

В этом году наша команда собралась в несколько измененном и расширенном составе и выступила под старым названием. Результат, увы, оказался не столь впечатляющим - 56 место среди 860 команд, из которых 500 не сделали вообще ничего.

Классическое короткое вступление для тех, кто не в теме (беззастенчиво стянутое из прошлогоднего отчета)

Каждый год проводится международная конференция ICFP - International Conference on Functional Programming. К этой конференции приурочен програмерский contest под названием ICFPC. Несмотря на название конференции, участвовать в контесте может любой желающий, и пользоваться можно любыми языками, не только функциональными, кроме того - участники могут объединяться в команды произвольного размера. Contest отличается от соревнований типа ACM и topcoder тем, что он менее "заточен" под какие-то конкретные языки или наборы навыков, а задачи в нем прикольные и позволяют получить удовольствие не только от победы, но и от участия.

Это четвертый ICFPC, в котором я принимал участие.


Глава первая, подготовка. (в которой автора преследуют жизненные неприятности, а организаторы развлекаются комиксами)



После прошлого ICFPC у меня было большое желание поучаствовать в русскоязычной команде, или собрать ее самому. Причем готовится надо начинать месяца за два-три, т.к. процесс это хоть и не очень сложный, но при распределенной команде "упаковать" его в меньшее время очень тяжело, т.к. требуется наличие в online всех участников и наличие у них свободного времени. Такие моменты случаются эпизодически, пару раз в неделю, и "размазывание" подготовки по ним как раз и приводит к тому, что процесс растягивается на месяцы.

Соответственно, я предполагал, что готовится надо начинать в где-то в мае. В то же время vincenz, прошлогодний организатор Lazy Bottoms, явно решил перестраховаться и в середине января(sic!) стал спрашивать меня, собираюсь ли я участвовать в этом году, и примкну ли я к его команде? Я рассказал ему о своих планах, мы пошутили по поводу будущего соперничества и разошлись.

Однако, в конце апреля в моей жизни случились определенные печальные события, которые достаточно сильно выбили меня из колеи и заставили пересмотреть свои планы. Стало ясно, что об организации своей команды речь идти не может - на это не было времени (ни свободного, ни календарного) :(

Поэтому я связался с vincenz-ом и в результате стал седьмым участником обновленного состава Lazy Bottoms, в который, кроме меня, вошли (в алфавитном порядке):

  • Cale (Канада. Аспирант - прикладной математик),
  • jethr0 (Германия. Программист + CPA),
  • Lemmih (Дания. Програмист, GHC hacker),
  • psykotic (Корея. Программист компьютерных игр),
  • vincenz (Бельгия. Программист, IT-консультант),
  • zeeeee (США. PhD в MIT, интерн в Google)


Как можно увидеть на картинке справа, наша команда "закрывала" практически полные рабочие сутки, хотя (забегая наперед) обнаружилось, что Cale и zeeeee проще сдвинуть свое рабочее время ближе к европейскому).

А в это время один из организаторов ICFPC - Johan Jeuring - развлекался тем, что вел блог про подготовку к contest-у. Блог был построен в форме литературного повествования, а посты сопровождались загадочными картинками типа таких:



Сейчас всё это - и история, рассказанная в блоге, и картинки - кажется вполне понятным и очевидным. А в июне все это выглядело бредом сумасшедшего и рассмотрев и отвергнув несколько версий касательно написанного, мы решили блог всерьез не принимать и на его основе никаких предположений не строить. Кроме одного - исходя из этого поста (и нескольких соседних) мы сделали вывод, что в этом году задание ICFPC не будет похоже на прошлогодние, а будет больше похоже на "классические" ICFPC прежних лет. (Тут и далее я буду подчеркивать вещи, которые существенно повлияли на наш неуспех).

Глава вторая, приборы, материалы и методы (которую читатель, жаждущий приключений, может смело пропустить)


После этого ICFPC я окончательно уверился в том, что для распределенной команды, а тем более - БОЛЬШОЙ распределенной команды, решающее значение имеет организация коммуникаций между участниками. Если бы мы все сидели в одной комнате или в соседних комнатах, то, я уверен, мы достигли бы в несколько раз больше того, что у нас получилось.

В принципе, часть "узких мест" была понятна еще после 2006-го года: незнание текущего статуса и планов каждого из членов команды ведет к дублированию работы и напрасно потраченному времени. Поэтому в этом году мы сразу договорились, что у нас будет минимум два часовых "status meeting-а" в день, на котором мы будем обстоятельно рассказывать о нашем прогрессе и обсуждать планы на ближайшее будущее (время этих совещаний можно увидеть на нижней картинке с тайм-зонами). Чтобы обмениваться информацией и результатами работы, у нас были:

  1. общий репозиторий для хранения исходного кода и сопутствующих файлов (darcs + ssh + public keys)
  2. IRC-канал #lazybottoms для "текущего обсуждения" (закрытый, invite-only),
  3. отдельный IRC-канал, в который специальный бот постил сообщения о commit-ах в репозиторий
  4. mailing list, куда предполагалось выносить "резюме" наших статусных совещаний
  5. skype для общения и голосовых конференций


Все это было настроено и так или иначе протестировано где-то за месяц до начала. Кроме того, был известен "резервный хостинг", куда бы мы могли переехать в случае проблем с компьютером, на котором жил репозиторий и бот (вот, кстати, одна из выгод распределенной системы контроля версий - каждая локальная копия является полноценным репозиторием, который может быть использован для создания нового "центрального репозитория" в случае переезда на новый хостинг).

Мы постоянно (хоть и не подолгу) общались в #lazybottoms, и в процессе стало известно, что jethr0 скорее всего будет в занят в течении первых трех часов соревнования, zeeeee (и, возможно, Cale) появится только ко времени первой "статусной встречи" и таким образом к моменту старта будут активны четверо-пятеро участников. Поэтому мы договорились, что после старта все в течении одного часа читают задание, потом мы (впятером) обсуждаем, какого рода framework и сопутствующие инструменты нам могут понадобится для его решения, а через пять часов, на первой статусной встрече, мы устраиваем настоящий brainstorming и формируем пути решения.

Глава третья, близкие контакты третьего рода, в которой организаторы изгаляются над участниками, как хотят


20 июля, 12:49 EET (11 минут до начала соревнования)
Выдержка из бортового журнала:

12:49:07 <vincenz> http://johanjeuring.blogspot.com/
12:49:08 <vincenz> new post
12:51:11 <vincenz> "Because of that, and also because it is really the only thing we can think of to still give Endo a chance, we will change our plans. We will abandon the original topic we had in mind for the ICFP contest (writing generic programs in order to design boilerplates). Instead, we make it the task of the contest to Morph Endo!
12:51:19 <vincenz> During the last days, we have been able to decipher large parts of the original message, found out that it is about DNA and describes how Fuun DNA works. We therefore have some understanding now about the process involved. Unfortunately and we feel really guilty about it we have given all of this a low priority due to the upcoming contest, and the one thing we didn't find out until after we actually made contact with Arrow, ..."
12:51:40 <vincenz> so...a language
12:51:41 <vincenz> (DNA)
12:51:51 <vincenz> I guess, we'll have to modify the DNA ...
12:51:57 <vincenz> to make it stronger?
12:52:05 <vincenz> probably it will be impossible to code in
12:52:11 <vincenz> so we'll have to develop higher combinators (выделение мое)
12:53:06 <vincenz> presumably, "morphing endo" will allow it to travel to the Arrow or something


Выделенные слова оказались пророческими. К сожалению, все уже были, словно намыленные в бане в ожидании горячей воды, и никто не обратил на них внимание. А жаль.

13:00 EET, на сайте организаторов появляется задание

Пошел час, запланированный нами на чтение и понимание задачи. Я читаю задание с экрана, Юлька печатает его на принтере. В принципе, уже тут можно было бы среагировать на спецификацию длиной в 20 станиц, и изменить наш подход - ведь за час прочесть и досконально вникнуть в документ такого размера не представляется возможным. В результате, я уверен, ни кто из нас не прочел спецификацию от корки до корки, вникая в каждый абзац, какие-то части мы пропускали или пролистали по диагонали.

Через час мы собираемся, чтобы поделиться друг с другом своими версиями происходящего.

Выдержка из бортового журнала:

13:50:26 <vincenz> 10 more minutes till initial discussion
13:50:26 <vincenz> how I propose
13:50:26 <vincenz> each gives his proposal
13:50:26 <vincenz> in a brief amount of time
13:50:26 <vincenz> without getting into too much detail
13:50:26 <vincenz> then people ask Qs
13:50:26 <vincenz> then next proposal
13:50:26 <vincenz> and then after everyone did his
13:50:26 <vincenz> we discuss the optimal solution


В результате нашего обсуждения вырисовывается такая картина (далее идет вольное изложение задания, пересыпанное нашими идеями):

Некий инопланетянин Эндо с планеты Фуун (явная ссылка на эндофункторы) в результате ДТП совершил аварийную посадку на Земле. Разумный корабль инопланетянина (имеющий имя Arrow) связался с землянами и передал им информацию о ДНК Эндо и просьбу помочь адаптировать инопланетянина к земным условиям.

ДНК Эндо состоит из четырех аминокислотных оснований - I, C, F, P (инфинин, континуин, функциорин и полмиорфин соответственно). Чтобы адаптировать Эндо, необходимо составить цепочку-префикс из этих оснований и передать ее Arrow. Умный корабль присоединит этот префикс к ДНК пришельца, и покажет (визуально), как будет выглядеть модифицированный генотип в земных условиях.

За счет чего будет модифицирован генотип? За счет того, что ДНК пришельца - это хитрый код, который при "исполнении" может модифицировать сам себя. В процессе "исполнения" ДНК генерируется РНК, которое по определенным правилам можно превратить в картинку. Исполнением ДНК занимается интеллектуальный космический корабль.

Слева - это то, как Эндо выглядит на момент начала соревнований, а справа - как должен выглядеть Эндо, полностью адаптированный к жизни на Земле.



Если отбросить всю словесную мишуру (а её там, блин, 20 страниц!), то получается вот что: нам дана длинная строка/список/стэк из букв I,C,F,P и набор правил переписывания, который циклически применяется к этой строке до тех пор, пока это возможно. Люди, знакомые с правилами sendmail.cf, алгоритмами Маркова или любыми другими системами правил переписывания (rewrite rules) могут начинать понимающе кивать головой :)

При этом правила переписывания - не статические (как, например, в классических алгоритмах Маркова), а закодированы в самой строке ДНК и динамически декодируются из нее на каждой итерации. Правила состоят из "образца" (pattern-а) и "шаблона" (template-а) и работают следующим образом:

  1. Обозначим имеющееся ДНК как dna. Отрежем от него слева два префикса (по определенным правилам) и декодируем из них образец pattern и шаблон template.
  2. Далее выберем из оставшейся части ДНК префикс, совпадающий с образцом (pattern-ом)
  3. Заменим совпавшую часть на шаблон (template)
  4. Приклеим сзади оставшуюся часть dna. Мы получили ДНК для новой итерации. Смыть, повторить, и так пару миллионов раз




При этом в замена pattern-а на template происходит примерно так же, как поиск с заменой по регулярным выражениям: части pattern-а могут быть использованы в templat-е.

Типичный пример выглядит так:

pattern="пропустить 64312567 символов, убедится, что дальше идет PPICFP";
template = "скопировать все, что попало под pattern и дописать CI".

Нетрудно убедится, что таким нехитрым образом можно поместить "CI" внутрь ДНК в любое нужное место.

Чтобы не возникало большого соблазна взять листик и ручку, и поглядеть, что же происходит при "трансляции" предоставленного ДНК, добрые организаторы участливо сообщили, что при этом должно произойти порядка 1.8 млн. итераций до тех пор, пока процесс не остановится. Мы испугались, и за листик и ручку не брались. А если бы взялись, то ... Впрочем, обо всем по порядку.

Кроме того, нетрудно заметить, что:

  1. Фиг угадаешь, какими будут pattern и template на следующем шаге, пока не выполнишь текущий
  2. Использовать массив или список для хранения ДНК - смерти подобно, т.к. прогораешь либо на скорости операций "поиск подстроки/пропуск N символов", либо на скорости дописываний в начало ДНК.


Внимательный читатель спросит - а откуда же берется картинка? А картинка получается в качестве "побочного продукта" процесса трансформации. Если в ходе декодирования pattern-а мы встречаем последовательность "III", при этом мы ожидаем начало очередной лексемы pattern-а, Луна находится в Весах, а Меркурий - восходит, и рак на горе вот-вот свистнет, то следующие семь символов ДНК копируются в список под названием "РНК" и в дальнейшем используются для рисования картинки.

Картинка рисуется при помощи продвинутого варианта "черепашьей графики" вида "поставить маркер; вперед 20; провернуть направо; вперед 30; линию до маркера; сменить цвет; вперед 40; ...". Можно явно задать всего восемь цветов, все полутона получаются путем операций сложения слоев (да-да, там были слои, прямо как в фотошопе :) и смешения цветов.

Из данного нам ДНК при его трансляции должно было "выпасть" свыше 300К команд РНК, с помощью которых и рисуется картинка с "грустным Эндо" (см. выше). Кроме того, в спецификации приводился некий префикс, при применении которого получалась вот диагностическая таблица тестирования DNA-транслятора.

После обсуждения (в ходе которого выяснилось, что нормально работающая skype-конференция на 7 человек - это что-то из области фантастики) у нас созрел такой план атаки:
0)Мы договариваемся об типах данных, используемых для внутреннего представления информации
1)Мы формально описываем язык рисования картинок (называем его ImageOps) и пишем транслятор RNA->ImageOps и ImageOps->RNA (это делает Cale)
2)Мы пишем рендерер, который будет из набора команд ImageOps делать PNG (это делает psykotic)
3)Мы формально описываем язык замен pattern-ов на template-ы (называем его TemplateLanguage) и пишем "конвейер": DNA->TemplateLanguage+RNA (это делаю я и jethr0)
4)Мы пишем альтернативную реализацию "в лоб", которая сразу из DNA делает PNG (это делает Lemmih).
5)Мы пишем GUI, которое позволит увязать все части вместе, легко запускать трансляцию DNA с указаным префиксом и видеть весь процесс в деталях (этим занимается vincenz)

Вдох, выдох, налили чаю и вперед - кодить! На чтение спецификации, размышления, обсуждение и согласование интерфейсов между частями решения у нас ушло без малого 3 часа.

Читаем продолжение и окончание.icfpc-2007
From:
Anonymous
OpenID
Identity URL: 
User
Account name:
Password:
If you don't have an account you can create one now.
Subject:
HTML doesn't work in the subject.

Message:

 
Notice: This account is set to log the IP addresses of everyone who comments.
Links will be displayed as unclickable URLs to help prevent spam.

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