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

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

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

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

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

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

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

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

sourcetarget

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

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

selfcheck

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

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

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

День 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

  • Популярное

25 комментариев

Подписаться на комментарииОтписаться от комментариев Комментарии могут оставлять только пользователи с подтвержденными аккаунтами.

А что с использованием numpy? не разрешалось или еще что? Для некопирующих срезов очень удобно было бы пользоваться numpy.ndarray

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

Лог сохраняется на стороне сервера, либо ботом. http://ejabberd.jabber.ru/mod_...

кстати, а почему команда TBD на 501 месте? У вас же все так круто получалось?

Как раз из-за хромающей организации ^_^ Мы умудрились зарегистрировать команду два раза, как TBD и как Tibetan Biodiversity Display. В результате первую регистрацию бросили и все сабмиты публиковали от второй.Мораль: оповещайте соратников по команде о всех своих действиях. Тем более таких важных.

кстати, а почему команда TBD на 501 месте? У вас же все так круто получалось?

mantycore говорит:

У нас (TBD) первый блин оказался весьма вполне. Организация прихрамывала, конечно, но упомянутых грабель мы счастливо избежали.

Я искренне рад за вас.Лично я считаю, что наш главный промах — это все-таки слишком мелкое дробление задач. Вполне реально было уже в пятницу ночью иметь хоть медленный, но рабочий Dna2Rna. Тогда бы мы всю субботу занимались проблемами скорости. А так — получилось что получилось.

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

У нас (TBD) первый блин оказался весьма вполне. Организация прихрамывала, конечно, но упомянутых грабель мы счастливо избежали.

Сергей говорит:

Соревнование как вы знаете идет за титулы присваиваимые языкам команд победителей. Питон конечно ни разу ничего не взял, поэтому предлагаю дать ему титул «Язык не подходящий для реализации идей Сумасшедших Ученых» =)

да, согласен.

P.S. ’x’ это такой ник у него был)).

общение через джабер-конференцию имело свои недостаткиНе раскроете тему?

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

Я в общем-то не думал серьезно участвовать, но и пропадать после первого дня тоже не собирался — вмешались обстоятельства. Та реализация которую я залил, могла бы работать достаточно быстро (после вычистки багов), но проверить это не сложилось. Вообще с момента как я прочитал задание стало ясно что нам не светит в соревновании вообще ничего =), т.к. все участники насколько я понимаю програмисты-практики, а задание совсем другого рода и надо сказать очень надуманное. Конечно иначе быть и не может, так как организаторам всё таки нужно создать целую «подвселенную».Поэтому же и скорость питона оказалась неадекватной — алгоритмы необходимые в реализации виртуальной машины высосаны из пальца. Впрочем опять таки это было ясно заранее, что в соревновании нужна будет скорость.Честно говоря само по себе задание в этом году совсем не показалось мне забавным, хотя любителям низкоуровневых штучек, чтения hex-кодов итп должно прийтись по вкусу.Соревнование как вы знаете идет за титулы присваиваимые языкам команд победителей. Питон конечно ни разу ничего не взял, поэтому предлагаю дать ему титул «Язык не подходящий для реализации идей Сумасшедших Ученых» =) Вообще организаторам спасибо, прикольно что такая штука есть.

общение через джабер-конференцию имело свои недостаткиНе раскроете тему?

Цитата с rsdn:

DM> Я тоже не сразу заметил там нужную фразу. Сейчас сделал быструю реализацию (3000 итераций в секунду).Спросил у Адепта. Их машина даёт 100−200К итераций в секунду.

как раз тот случай, когда brute force не помог. А закодировать linked list of buffers, даже на питоне, наверное можно было. Просто в пылу «соревнований» никто об этом не думал.

> На rna-> dna у меня psyco дал прим 2.5Забыл написать что это на маленьких — тестовых кусках, на больших вообще было-бы тяжко из-за строковых операций.

> Ребята, а использовать python-psyco не пробовали? В принципе не намного хуже, чем > pyrex, зато не нужно переписывать код.psyco ЗНАЧИТЕЛЬНО хуже pyrex, кроме крайне редких исскуственных случаев.Для реальных задач прирост от psyco не превышает 4-х раз, а в среднем около 2−3 раз (для сравнения PyRex это почти С т.е. около 100 раз). И наш случай как раз был не из тех, где сильно ускорится (много операций со срезами строк и ducktyping) ((. На rna-> dna у меня psyco дал прим 2.5раза, конечно лучше чем ничего, но, к сожалению, очень далеко от требуемой скорости.

Ребята, а использовать python-psyco не пробовали? В принципе не намного хуже, чем pyrex, зато не нужно переписывать код.

decorator запускал под psyco. Вопрос в оптимальности работы с самими данными. Там в процессе куча данных постоянно копировалась и двигалась туда-сюда. На выделениях памяти и копировании мегабайтных массивов все быстродействие и умирало. Посмотрите по ссылкам из раздела «Успехи других команд», там несколько раз этот момент упоминается.

import array

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

Фу. Гуглить репозиторий конкурентов — не спортивно. (К тому же — запрещено правилами).

Да, не спортивно.

RulesSubmissions: You can submit your solutions for the lightning division until 24 hours into the contest. Your solution for the 72-hour division should obviously be submitted within 72 hours into the contest.To qualify for any prize, you will have to submit your contest materials. Contest materials may include any programs and documentation you have written in order to solve the task. You can submit your contest materials by sending them to icfp@cs.uu.nl. We will accept contest material submissions until three hours after the end of the contest. This deadline also applies to the lightning division.Teams: This is an open contest. There is no entry fee or need to pre-register. Teams may work from any location.Teams with members from the faculty, students, or staff of the Information and Computing Sciences department of Utrecht University are not eligible for any of the Prizes.A team consists of every person who contributes ideas or code towards a submission. Individuals may only be member of a single team and teams may not divide or collaborate with each other once the contest has begun.Teams may have any number of members.Language and tools: Teams may work in any programming language (s) that they wish. They may employ any computational resources at their disposal.

отсутствие нормальных строк (для таких случаев нужны былиmutable строки + некопирующие срезы)

import array

Ребята, а использовать python-psyco не пробовали? В принципе не намного хуже, чем pyrex, зато не нужно переписывать код.

Фу. Гуглить репозиторий конкурентов — не спортивно. (К тому же — запрещено правилами).

; -) pourqoi pas?

Супер!

decorator нагуглил репозиторий конкурентов

Времени мало, так что наведаемся-ка к конкурентам!...;)

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

Адепта мы не читали, да;) Молодцы конечно, что себя попробовали, но все же эти грабли уже описывались Адептом в отчете об участии прошлом...Можно и нужно делать выводы, а не наступать на те же грабли. Ну ничего — в следующем году будет лучше; -)

Подписаться на комментарии