Отчет: участие команды dou в соревновании ICFP Programming Contest 2007

www.icfpcontest.org
Команда dou

Основным языком для команды был выбран Питон.

Наиболее активно в команде учавствовало 3 человека:

• decorator — Роман Безручко, Донецк
• koder — Константин Данилов, Харьков
• bialix — Александр Бельченко, Запорожье

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

О задании своими словами

Целью соревнования было изучить некий набор данных, который являлся «ДНК инопланетной формы жизни»
по имени Endo, по несчастливому стечению обстоятельств попавшей на нашу бренную планету.
При помощи специального генетического компьютера под названием Arrow необходимо было найти
способ модифицировать жизненную форму Endo, сделав ее более приспособленной к проживанию на Земле.

Организаторы снабдили участников достаточно подробной инструкцией, как сделать эмулятор
Arrow — по сути предоставив подробный алгоритм, просто бери и кодируй. Однако,
повторение работы генетического компьютера было лишь первой частью задачи.
В результате прогона ДНК с некоторым префиксом должна была получаться некоторая картинка.
При прогоне без префикса имеем исходную картинку Endo. Конечная цель — найти
такой префикс, который даст нам конечную картинку.

Например, в качестве подсказки в описании давался префикс, который приводил к получению
картинки самотестирования системы:

Сами картинки формировались из нескольких слоев, и в некоторых слоях могли содержаться
подсказки. Эти подсказки надо было найти, затем использовать для построения новых картинок,
и так далее до полной победы.

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

Как мы делали это

День 1й. Пятница, 20 июля

Соревнования началось в 13 часов по киевскому времени. Ребята начали кодировать уже вечером,
я присоединился только в 10 вечера. Когда я появился, часть кода уже была написана,
работу разделили по функциям, каждый делал, что считал нужным. Общего плана работы не было
видно.

Ночью пятницы Сергей aka maluke зафиксировал в репозиторий свою версию конвертора и результат
его работы. Больше он ни в чате, ни в логах svn не появлялся. Его реализация была с ошибками,
хотя результат ввел нас в легкое заблуждение.

День 2й. Суббота, 21 июля

Продолжаем кодировать. Макс начал утилиту для отрисовки картинки, decorator и koder дописывают
конвертор ДНК и ловят глюки в коде. Я немного поковырял исходную ДНК в надежде найти подсказку.
После обеда имеем первую картинку, наверное с подсказкой. Однако рисовалка все еще не закончена,
а уверенности в правильности работы конвертора нету. Небольшое обсуждение в чате показало,
что мы по-разному понимаем некоторые части текста задания, и понимания, как достичь конечной цели,
по-прежнему не было.

У меня крепло стойкое убеждение, что текущий конвертор работает с ошибкой. Поскольку четкого
плана у нас по-прежнему не было, я потратил несколько часов на то, чтобы практически с нуля
написать свою версию конвертора. Немного глупая трата времени, тем более что я тоже сделал
одну ошибку в коде, которую нашел только на следующий день.

Попутно decorator запускает конвертор вместе с префиксом из текста задания. Выясняется, о ужас,
что реализация конвертора на питоне тормозит просто не по-детски. koder начинает переписывать
самую медленную функцию на C++. Я начинаю думать, о глобальной оптимизации программы, а не
только отдельных кусков. Прихожу к мысли, что надо почти все переписать на Си/С++. Также прихожу
к мысли, что нужно прикрутить листинг для анализа происходящего.

День 3й. Воскресенье, 22 июля

Макс пересылает в наш список рассылки письмо от организаторов соревнования с листингом первых
10 итераций конвертора. Это письмо помогло нам найти ошибки в наших реализациях конвертора.
Я прикрутил листинг к своей реализации, быстро обнаружил, что ошибка у меня происходит в 4й
итерации, и потом дебагером нашел ошибку. Это была обидная ошибка из разряда опечаток.

Основная реализация имела тоже ошибку в 4й итерации, но при этом была и похожа и непохожа
на мою.

koder пытается дописать рисовалку.

decorator нагуглил репозиторий конкурентов. Они продвинулись намного дальше: у них уже был
нормальный и достаточно быстрый конвертор, плюс рисовалка. Также у них в папке images
лежали некоторые готовые раскодированные картинки. Посмотр этих картинок дал представление
о замысле организаторов. Получая каждую новую подсказку и декодируя ее, участники получали
бы новую картинку с дополнительной информацией о системе Arrow вообще и о ДНК в частности.
Были там и шутки и приколы. Вобщем завидую тем, кто смог расколоть этот орешек.

Попутно я наконец-то запустил исправленную реализацию своего конвертора у себя на ноуте.
Скорость работы этой питон-программы была страшно низкой. Так, по цифрам из описания
задачи следовало, что для конвертации исходной ДНК без префикса конвертор должен сделать
1891886 итераций. У меня же после 4х часов непрерывной работы прошло только примерно
5000 итераций.

Нам всем стало понятно, что в отведенное время мы никак не уложимся, и на этом работа
по молчаливому согласию была прекращена.

Ночью в воскресенье я начал писать реализацию конвертора на чистом Си — без иллюзий,
что успею к утру, просто в голове накопились мысли, которые требовали выхода. Примерно
за 4 часа я переписал на Си около 25% требуемого кода. Если учесть, что на реализацию
на питоне у меня в целом ушло около 3-4 часов (и еще пару часов на отлов багов), то
получалось, что на Си я писал раза в 4 медленнее, чем до этого на питоне. Для тестирования
использовались тесты, ранее написанные для питон-реализации.

Постмортем

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

Отрицательными факторами оказались:

• дикая жара в эти дни по всей территории Украины (в Запорожье было около 40 градусов, хотя в суботу вечером прошла
  буря, а потом и гроза, легче от этого не стало). Как известно в жару думать не хочется, хочется лежать на пляже с пивом и девчонками, а не потеть перед компьютером
• слабая организационная подготовка
• отсутствие сплоченности команды
• общение через джабер-конференцию имело свои недостатки

Что было сделано правильно:

• с самого начала применялся TDD: из описания задачи были выдраны все примеры и использовались
  как данные для юнит-тестов, однако их (как оказалось) было недостаточно

Что было сделано неправильно:

• не было общего плана и предварительного анализа главной задачи
  
• реализация кода была подроблена слишком мелко, реально надо было разделиться на две группы
  по 2 человека: первая группа грызла бы конвертор и писала юнит-тесты для него, а вторая группа
  грызла бы рисовалку и писала бы юнит-тесты для нее.
  
• малое количество юнит-тестов не позволило сразу обнаружить все ошибки в реализации. В описании задачи
  приводились примеры, однако их было немного и они не покрывали все ветки исполнения. В своей реализации
  конвертора я пытался допридумывать недостающие тесты, однако время поджимало и я это бросил.
  
• не было предварительной договоренности между участниками:
  

• какие бибилиотеки используем,
  
• организация кода в виде модулей и пакетов,
  
• как будем ускорять питон, если потребуется
  
• стандарт оформления программ (хотелось бы PEP-8)

Фактически до начала соревнований не было понятно кто реально будет участвовать,
кто нет, и кто сколько времени готов уделять.

Что еще:

• мы использовали бесплатный svn-хостинг на гуглкод. Небольшой поиск в воскресенье дал
  возможность найти свободный репозиторий конкуретнов, которые продвинулись гораздо дальше.
  Это нужно учитывать, поскольку кто-нибудь может легко воспользоваться готовыми результатами
  других участников
  
• кто-то должен проводить поиск в инете, сидеть в общем чате #oasis и вообще собирать всю
  новую информацию.

Впечатления участников

koder

1. IMHO, все согласятся что готовы мы были слабо, ну по крайней мере я
   точно.
2. задача была интересной, таких по информатике со школы не
   видел.
3. Ну и питон подходил не сильно, как раз двое основных граблей
   наложились — отсутствие нормальных строк (для таких случаев нужны были
   mutable строки + некопирующие срезы) и общая тормознутость интерпретатора.
   +(и отсутствие времени на переписывание частей кода на C/PyRex/Whatever)

decorator

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

Однако авторы конкурса проделали удивительною работу, почувствовать
свою причасность к процессу было приятно даже без претензий на
выигрыш.

Я доволен, что принял участие и планирую участвовать в следующем году.

Некотырые выводы. Нужно сразу и четко разделять задачу на части и
делать их паралельно. Причем, отдавать каждую задачу «на откуп» члену
команды полностью, в том числе и выбор языка. Привязываться к какому-
то одному языку, видимо, не лучшая идея.

Ну, и если хочется серьезно выступить — надо зарание серьезно
готовиться.

bialix

Последний раз в соревнованиях по программированию я учавствовал еще в институте, в 1994 году.
Поэтому поучавствовать сейчас было интересно.

Организаторы ICFPC проделали огромную работу и придумали действительно интересную и забавную задачу
одновременно. При этом сам базовый алгоритм, который надо было повторить — был достаточно прост. Но
фишка задания была в том, что необходимо было написать очень оптимальную реализацию по
производительности.

К сожалению, Python — выбранный основным языком для нашей команды — традиционно проигрывает в этой
области. Поэтому имело смысл его использовать только для unit-тестов и начального макетирования
алгоритмов. Я не думаю, что выбор Питона был ошибкой с самого начала, просто надо было
сразу морально готовиться к переписыванию каких-то кусков на C/C++/Pyrex. В идеале сразу писать на
Pyrex, а тесты на чистом Питоне.

Главный вывод: в одиночку с такими заданиями в отведенное время (72 часа) не справиться. Но команда
должна быть подготовленной и знать друг друга если не в лицо, то хотя бы представлять кто что и как
может.

Макс Ищенко

Насчет подготовки — стоило хотя бы день-два побездельничать перед началом
соревнований, чтобы мозги немного отдохнули. Питон оказался не очень
подходящим выбором, согласен с Ромой что разные части можно и нужно делать
на разных языках. Перспективно наверное подбирать команду не по языку, а по
максимально разносторонним наклонностям/навыкам, чтобы было больше шансов.
Тесты рулят.

По организации — стоит больше времени уделять планированию, разделению
труда, а не бросаться сразу с места в карьер. Еще джаббер конференция
неудобна тем, что лог не сохраняется и приходится дергать остальных чтобы
ввели в курс дела.

Относительно личных достижений и «прорывов» у меня иллюзий не было. Надежда,
правда, какая-то была — но она не оправдалась. ;)

Наш результат

Хотя мы остались далеки от выигрыша, но все же не на последнем месте: 298 место из 869.

Успехи других команд

Немного интересных ссылок по теме.

Отчет раз: wiki.freaks-unidos.net/icfp/2007.

Отчет два: community.livejournal.com/evan_tech/229595.html
Цитата из отчета:
«Tobin had an awesome find of a textual message hidden in the letters
of the DNA (that is, if you viewed it in a text editor at the right
width), which led him to extracting another region, which was a binary-
encoded PNG, which led to another region which was a binary-encoded
MP3 that was of a person reading a patch.»

Еще один участник: sambangu.blogspot.com/...​-rescue-icfp-contest-2007,
сначала писал на Scala (функциональный язык под JVM), потом на питоне,
и в конце концов на Си. Его Питон-версия работала похоже быстрее нашей, по крайней
мере с ее помощью он смог нарисовать первую картинку.

А это, видимо, картинка победителей: people.cs.uct.ac.za/~rbkmax001/output.png.
_Почти_ требуемое target.png.

Какой-то важный слайд с кодом: tapani.cs.chalmers.se/icfp/2007/cracking.png.
Это что-то из запредельно далеких от нас уровней соревнования. Там в
папке еще много картинок.

Darcs-репозиторий командый haskell’истов: r6.ca/icfp2007. Есть
и картинка, которую они получли. Не такая впечетляющая как у
предполагаемых победителей.

И напоследок некоторые наработки из самого разгара процесса поиска
префикса, чтобы понять как проходила «основная» часть соревнования:
docs.google.com/...​ew?docid=dccx65q8_1f88ffp. Наработки какой-то
русской команды. Вошли в top15.

Game over?

From: ICFP contest 2007 Date: Jul 23, 2007 1:03 PM Subject: [Icfpcontest-announce] The ICFP Programming contest 2007 has ended! The ICFP Programming Contest 2007 has come to an end! Thank you all so much for participating. It has been heart-warming to see all participants trying so hard to save the poor Endo. It was a hard struggle, but we are very optimistic Endo will survive. We have sent the best submitted prefix to Arrow, but haven't heard anything since. We hope that this is due to the fact that Arrow is using all its remaining energy to apply the DNA prefix to Endo, and not because something has gone wrong. For now, we can do nothing but wait for a sign of life. Repairing DNA takes time, but we expect that we will know whether or not it has been successful by the time of the ICFP Conference in Freiburg. We will announce the results of the contest at ICFP in October. For the top-15 teams: we discourage revealing the final scores before then. At that time we will also release details of how we created the contest. We wish to recognize the remarkable amount of work that teams put into participating in this contest. In all, 357 teams submitted at least one prefix, more than 160 teams saw daylight, and around 50 teams made substantial progress on repairing Endo's DNA. We plan to create a permanent site for Endo's DNA, so that programmers can continue to test their skills and experiment with it indefinitely. We might switch submission on again after some time. Please remember to submit your contest materials and set your team information for the final standings. You can do this from your private team page any time until 15:00 CEST. Thank you all again, we'll keep you informed. Invariably yours, The 2007 ICFP Contest Organizers

Все про українське ІТ в телеграмі — підписуйтеся на канал DOU