Тексты

  Тексты:

Пхова 2004
ICFPC 2007
ICFPC 2008
Sapka 2009
ICFPC 2009
ICFPC 2010
Защита от взлома

  Переводы:

Природа Будды
Махамудра



Если обнаружите в тексте ошибку, выделите ее мышкой и нажмите Ctrl-Enter.

ICFPC 2007

С 20 по 23 июля 2007 года проходило соревнование ICFP Contest, проводимое ежегодно при конференции International Conference on Functional Programming. В этом году в нем участвовало 869 команд, из которых мне в одиночку удалось занять 42 место. Ниже описывается в чем это задание состояло и как я его решал.

Соревнование этого года было уже десятым по счету, но я о нем узнал совсем недавно - в конце июня, когда прочитал замечательный рассказ _adept_'a об участии в ICFPC 2006. Мне очень понравилась прошлогодняя задача, и я подумал, что если и в этом году задача будет не менее интересной, можно попробовать поучаствовать. Участвовать в соревновании может любой желающий, в одиночку или в команде. В команде, конечно, предпочтительней, т.к. задачи обычно непростые, а на решение дается ровно 72 часа.

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

К началу соревнования организаторы написали, что им удалось расшифровать сообщение из того письма, и оказалось, что оно от той летающей тарелки. В нем говорилось, что инопланетянин по имени Endo из расы Fuun, который летел на этой тарелке, сильно пострадал при падении, и поскольку он не приспособлен к земным условиям, то скоро умрет, если его не мутировать в нечто более приспособленное. Корабль его умеет перестраивать пришельца по заданной ДНК, но вот ДНК, которая описывает новую приспособленную к жизни форму, у него нет. И он просит поскорее найти такую ДНК и прислать ему, потому что энергии хватит на 3 с небольшим дня, после чего он отключится, и спасти Эндо не выйдет. Причем сам процесс изменения пришельца доступен только его кораблю, но данный процесс можно промоделировать. Организаторам "удалось" расшифровать алгоритм построения РНК по ДНК (он сильно отличается от нашего) и способ нарисовать картинку по РНК, показывающую что же данная ДНК/РНК кодирует.

В итоге задание сводилось к следующему. Дано описание процесса создания РНК по ДНК и процесса превращения РНК в картинку. Дана картинка, описывающая текущую форму пришельца, и картинка, описывающая его желаемую форму.
source target
И дана сама текущая ДНК (файл в 7,5 МБ, состоящий из символов I,C,F,P - инопланетных нуклеиновых оснований). Предлагалось присылать такие цепочки символов I,C,F,P, которые будучи присоединены к началу исходной ДНК Эндо изменяют ее работу так, чтобы получающаяся из нее РНК кодировала картинку, как можно более похожую на желаемую. И была задана мера "риска": (число точек, где построенная картинка отличается от целевой)*10 + длина префикса. Чем ниже эта величина, тем ближе Эндо к жизнеспособной форме и тем меньше нужно кораблю энергии на трансформацию. Префикс с минимальным "риском" будет через 72 часа после объявления задания отправлен кораблю Эндо, а команда, его приславшая, окажется победителем соревнования.

Задание было опубликовано в пятницу 20 июля в 14:00 по Москве. С этого момента отсчитывались 72 часа до окончания приема префиксов. Первый час у меня ушел на то, чтобы прочитать текст задания, в котором было более 20 страниц, на которых подробно описывались процессы трансляции ДНК в РНК и отрисовки РНК в картинку. Трансляция ДНК в РНК выглядела как итеративный процесс, где каждая итерация состоит из следующих шагов: Начало ДНК трактуется как зашифрованные разными комбинациями нуклеиновых оснований (символов I,C,F,P) маска и шаблон. В процессе расшифровки ДНК "съедается" слева-направо. Маска описывает набор подстрок в ДНК, а подстановка говорит во что найденные подстроки превратить. Например, маска может говорить: ( пропустить 1000 символов ) IC (? FIIC). Это означает: запомнить первые 1000 символов как строка0, потом должны быть основания I,C, потом от этого места искать подстроку "FIIC", и все найденное после IC, включая FIIC, запомнить как строка1. Если на нужном месте не окажется нужных символов (IC в этом примере) или не найдется искомая подстрока, значит маска не подошла и в этой итерации ничего не делаем. Если маска подошла, то "съедаем" ту часть ДНК, которая подошла по этой маске, и вместо нее вставляем результат подстановки полученных подстрок в шаблон. Шаблон может выглядеть, например, так: ICIC 0/0 |0| PC 1/1 FF. Это значит записать символы ICIC, потом строку0, потом длину строки 0 в двоичном виде, потом символы PC, потом строку1, экранированную 1 раз, потом символы FF. В результате выполнения шаблона получается последовательность оснований, которая присоединяется слева к текущей ДНК. Т.е. нечто вроде нормальных алгоритмов Маркова, но посложнее.

В процессе расшифровки маски и шаблона могут попадаться комбинации из 10 оснований, где первые три - I. 7 последних символов такой комбинации кодируют команду РНК, их необходимо приcоединить справа к выстраиваемой РНК. Когда процесс разбора ДНК завершится (это происходит, если вся ДНК "съедена"), процесс построения РНК будет закончен.

Сама же РНК состоит из комбинаций все тех же оснований I,C,F,P, но теперь каждая комбинация имеет фиксированную длину 7 символов и означает команду для отрисовщика. Команд описано около 20 разных (но есть и такие, которые в задании не описаны). Рисование происходит примерно так: есть некая текущая позиция и текущее направление, есть текущий слой. Можно двигаться вперед на N точек, поворачивать по и против часовой стрелки, запоминать текущую позицию, рисовать линию от последней запомненной позиции в текущую, делать заливку области текущим цветом, создавать новый слой и объединять два слоя в один с учетом полупрозрачности точек. Текущий цвет и прозрачность получаются путем размешивания в "ведре" нескольких базовых цветов. Т.е. есть команды "очистить ведро", "добавить красного", "добавить желтого", "добавить непрозрачного" и т.д. Сложные цвета получаются смешиванием десятков или даже сотен простых цветов.

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

Итак, потратив час на изучение задания, я решил, что оно достаточно интересное, и что стоит попробовать его решить. Из языков программирования я лучше всего знаком с С++ и Руби, но Руби для этой задачи был бы слишком медлителен. В конце задания приводились цифры о том, что на трансляцию исходной ДНК пришельца уходит почти 2 миллиона итераций. Было решено писать транслятор на С++. Об оптимизации я вначале не думал и просто перевел псевдокод из задания в код на С++. В результате уже к 19 часам вечера у меня был транслятор, который корректно работал на коротких примерах, приведенных в тексте задания. Когда я запустил на нем ДНК Эндо, он дошел до двадцать какой-то итерации и повис, пытаясь выполнить экранирование подстроки 46 тысяч раз. Это был баг, который был чуть позднее исправлен. К 10 вечера у меня был вроде бы работающий транслятор, но очень медленный - около 1 итерации в секунду. Потому что сделан был максимально близко к псевдокоду - где надо было копировать строку, копировал строку, где надо было удалять символы из начала строки, удалял символы (копируя всю многомегабайтную ДНК). Такая скорость никуда не годилась, поэтому была проведена первая оптимизация - удаление символов из начала строки (очень частая операция) не удаляло символы, а лишь смещало свой индекс начала строки. Ну и остальные операции с ДНК были переделаны с учетом этого нового подхода. Скорость возросла на порядок - уже около 10 итераций/сек. Мне показалось, что этой скорости для начала хватит и я продолжил исследования. Запуск "интересного" префикса из задания приводил к падению транслятора, поэтому я его пока не трогал.

Тем же вечером пятницы, во время изучения файла с ДНК пришельца, была замечена странная область недалеко от начала файла. Выглядела она примерно так:

Это очень похоже на буквы, которые вскоре удалось увидеть, рассматривая по 16 символов в строке:

Надпись гласила: ACHTUNG! PORTABLE NETWORK GRAPHICS FOLLOWS
Т.е. дальше где-то лежала картинка в формате PNG. Я подумал, что там лежит картинка с пришельцем в одном из состояний, но жена высказала мысль, что там какая-нибудь подсказка. После области с буквами шла область, состоящая из символов C и I, т.е. что-то двоичное. Я взял несколько PNG файлов, посмотрел, как выглядит их заголовок, представил его в двоичном виде и попытался найти в той области. Сначала безуспешно. Потом попробовал перевернуть биты в байте (т.е. поместить наименее значимый бит в начало), тогда заголовок нашелся - прямо в начале той двоичной области. Двоичных данных там было около 24 КБ, но внутри в одном месте недалеко от начала была пара символов, отличных от С и I. На Руби был написан скрипт, который берет нужную область файла, переводит ее в бинарный вид и сохраняет. Так я сохранил все 24 КБ в файл, который действительно оказался с корректным заголовком PNG. Открыл его смотрелкой и увидел черные буквы на белом фоне:

Т.е. дальше должен был быть спрятан звук. Где кончались данные картинки и начинался звук, было пока непонятно. Статья в википедии подсказала: в конце PNG файла бывает специальный маркер конца. Он там действительно был, благодаря чему удалось вычислить точную длину данных с картинкой. Оказалось, что в той области на 24 КБ, те символы, отличные от C и I, как раз отделяли картинку от следующего файла. Данные со звуком были так же выдернуты в отдельный файл. В каком они формате было неизвестно. Знакомых мне заголовков в файле я не увидел. Попытался открыть его в Cool Edit'e, он умеет расшифровывать разные форматы несжатого звука, но ничего осмысленного услышать не удалось. Потом почти случайно заметил, что раз в 72 байта там идет повторение короткой сигнатуры. Т.е. звук сжат чем-то в блоки по 72 байта. Спросил у гугла какой кодек жмет блоками по 72 байта. Оказалось, это бывает в MPEG audio. Переименовал файл в mp3 - точно, открывается WinAmp'ом, там 11 секунд голоса. Голос диктует буквы: IIPIFFCPICPI... Записываю их по слуху, получаю цепочку из 39 символов.

Присоединяю эту цепочку к исходной ДНК пришельца, запускаю в своем трансляторе. Он довольно быстро выдает 2900 команд РНК, после чего долго что-то делает, не увеличивая длину РНК. Повис? Прерываю транслятор, рассматриваю полученный файл с РНК. Поскольку команд всего около 20, и они имеют фиксированную длину, сделать их разбор совсем несложно. Пишу на С++ программу, которая читает РНК и пишет в текстовый файл команды отрисовки. Вижу, что там в основном движения, повороты, и рисование линий. Очень похоже на рисование букв. Тогда делаю простую рисовалку, которая знает команды движения и поворота и умеет рисовать линии (прямо на экране, средствами GDI). В такой простой рисовалке запускаю имеющуюся РНК и вижу нарисованные символы:

Записываю этот префикс, присоединяю к исходной ДНК, запускаю транслятор. Он работает уже дольше, но довольно быстро выдает уже более длинную РНК (42 тысячи команд) и успешно завершает работу. Полученную РНК запускаю в своей рисовалке, получаю следующее послание:

Все префиксы, которые до этого момента были получены в этом "квесте" я первым делом отправлял на сервер, в надежде, что они являются решениями в смысле приближения картинки к целевой. До этого момента ни один из префиксов не уменьшал "риска". Здесь же было сразу два новых префикса, про один из которых было сказано, что он должен включить свет ("повернуть небесное тело к его солнцу"). Отправляю этот префикс и вижу, что он выстреливает: риск уменьшен с 3,5 миллионов до 1,1. При этом я оказываюсь в top20 из 800 команд. Было это полшестого утра субботы, т.е. через 15 с половиной часов после начала соревнования.

Второй префикс обещает пролить свет на навигацию по инструкции по починке ДНК. Запускаю его в своем трансляторе, но быстрого результата не получаю. Иду спать.

В субботу понимаю, что с моей примитивной рисовалкой РНК я не смогу увидеть многие элементы картинок и найти новые префиксы. Начинаю делать уже полную реализацию рисовалки, благо алгоритмы все в задании описаны подробно. Единственное затруднение возникает с заливкой. В псевдокоде она описана рекурсивно, если точно так же ее реализовать на С++, получается переполнение стека. Изменил алгоритм на тоже рекурсивный, но с меньшим числом вызовов (точки в пределах одной строки рисуются без рекурсии). Запускаю в новой рисовалке ту часть РНК, которую успел сгенерить, транслируя ДНК с префиксом для repair guide. Сначала показалось, что там рисуется исходная картинка, но потом увидел, что рисуется все же другая. Надо получить ее полностью, а я утром прервал трансляцию. Запустил трансляцию еще раз, жду.

Начинаю рассматривать все полученные на этот момент куски РНК. Вижу, что РНК, полученная при трансляции ДНК с "интересным" префиксом из задания, выводит пункты Self-check'a. Запускаю еще раз ДНК с этим префиксом, транслятор падает, т.е. где-то в нем ошибка. Нахожу ошибку (один краевой случай, который описан в алгоритме, но у меня не учтен), исправляю. Теперь self-check срабатывает полностью, выдавая РНК, которая сообщает об этом и заодно проверяет различные возможности рисовалки.

Параллельно приходит мысль попытаться выудить из ДНК зашитые в нее РНК, т.к. коды ДНК, генерирущие РНК, известны. Делаю на Руби скрипт, отыскивающий все последовательности таких 10 байтовых кодов и их трансляцию в РНК. Получаю пару тысяч последовательностей, но лишь некоторые из них длиннее десятка команд. Рассматриваю их в своей рисовалке и вижу части уже известных мне картинок - сообщения от FuunTech и Self-Check'a. Больше ничего не видно, видимо остальное зашифровано или создается динамически.

Время 8 вечера субботы, транслятор все еще работает над repair guide, уже вырисовывается фон с градиентами и большая буква лямбда. Сколько еще ждать - неизвестно. Что делать кроме этого - тоже непонятно. На МГУ-шном форуме мое внимание обращают на слова из задания, которым я не придал большого значения вначале: It seems particularly important to ensure that performing skips and appending unquoted references perform better than in linear time. Т.е. архитектура транслятора с копированием строк обречена быть слишком медленной, надо искать принципиально более быстрые решения. После некоторых раздумий появляется идея, как сделать быстрее. Возникает образ поезда, состоящего из соединенных в список вагонов, где каждый из вагонов содержит ссылку на подстроку, и кондуктора, который может двигаться по поезду в одном направлении, переходя из вагона в вагон, и умеет обрубать поезд в произвольном месте. Любому программисту ясно, что такой кондуктор - самый обыкновенный итератор, но мне было просто веселее обдумывать алгоритм именно в таких терминах. В итоге родилась такая схема: ДНК есть односвязный список из частей, где каждая часть либо содержит ссылку на кусок массива символов, куда изначально читается из файла ДНК пришельца, либо ссылку на созданную в динамической памяти новую строку. Управление памятью для этих новых строк с подсчетом ссылок и копированием путем простого копирования указателя и увеличения числа ссылок брал на себя CString из MFC (да, он это все умеет!). От заката до рассвета я занимался реализацией этого нового способа хранения ДНК, который как раз удовлетворяет приведенной цитате из задания. В половине шестого утра воскресенья новая версия транслятора вроде бы работала, но на self-check'e вела себя ужасно, захватывая неимоверное количество памяти. Трансляция ДНК, запущенная еще в 2 часа дня, все еще продолжалась. Пошел спать.

В воскресенье удалось встать только часам к двум дня, потом надо было собираться и идти на день рождения брата, так что сделать ничего не удалось. С дня рождения вернулся около 11 вечера, сел доделывать новый транслятор. К половине первого ночи быстрый транслятор был готов: успешно работал на self-check'e, памяти требовал совсем мало и главное - работал в 300 раз быстрее. Еще чуть позже удалось довести скорость до 5000 итераций в секунду, причем без ухудшения скорости в процессе трансляции.

К этому моменту старый медленный транслятор все-таки родил картинку с большой лямбдой, на которую он потратил больше суток:

Данную инструкцию я воспринял слишком буквально. В префиксе, который дал эту картинку, есть подстрока из 11 символов С и I. А в числе 1337 как раз 11 бит. Я вставил двоичное представление этого числа вместо тех 11 символов, получил вполне корректную пару маска/шаблон, запустил и... ничего. Рисуется исходная картинка с Эндо. Попробовал еще несколько вариантов - ничего. Вспомнил, что в свое время прервал выполнение ДНК с префиксом, продиктованным голосом. Запустил его в новом трансляторе, получил еще одну картинку с лямбдой:

Пробовал разные упомянутые числа вместо 1337 по той же схеме - ничего хорошего. Нашел статью про 1729 и того математика. Ничего. Тупик. А до конца соревнования остается уже менее 12 часов. Принимаю решение завязывать с квестом и приниматься за план Б, благо он уже был.

План Б состоял в том, чтобы взять картинку с включенным солнцем и дорисовать на ней недостающие части. Беглый взгляд на картинки показал, что их легко представить набором горизонтальных отрезков. Вначале надо было получить разницу между имеющейся картинкой и целевой. Добавил нужный код в свою рисовалку, разницу получил. Стал изучать более пристально и увидел новую проблему: оказалось, что обе картинки испоганены наложением незаметной сетки, состоящей из двух пучков линий, где в каждом пучке все линии выходят из одной точки (т.е. сетка из непараллельных линий). Более того, цвет у линий разный. А незаметна сетка, потому что линии эти почти прозрачны. В итоге они слегка изменяют цвет точек картинки, что глазом даже и не заметно, но непрерывных областей одного цвета на картинке практически нет. Приходится план корректировать на ходу и от отрезков отказываться.

Заглядывание в таблицу результатов показало, что многие участники нашли префикс, который на 1 символ короче того, что включает солнце, а картинку генерит в точности ту же (по очкам видно). Значит, имеющийся префикс можно укоротить. И действительно, там был поиск подстроки, вместо которой можно было искать чуть более короткую строку. Сделал такой префикс, отправил. Вернулся обратно к дорисовке.

Сравнение картинок в фотошопе показало, что если какая-то точка меняет цвет, то все ее соседи того же цвета меняют цвет точно так же. Т.е. области одного цвета меняют цвет синхронно. Что можно промоделировать, используя заливку. Рождается новый план: из тех областей, которые у целевой картинки отличаются от имеющейся, найти самые часто используемые цвета. Потом брать эти цвета, обходить меняющиеся области этого цвета и заливать их новым цветом. Так можно минимумом команд покрыть максимум площади. Написал нужную функцию, получил отсортированный по числу использований список измененных цветов. Сделал на С++ обход картинки с поиском областей нужного цвета и их заливкой. При исполнении этой процедуры в текстовом виде пишется последовательность команд рисования. Дальше на Руби был сделан эдакий компилятор: созданная последовательность команд интерпретируется как последовательность вызовов функций Руби-скрипта, эти функции генерят соответствующие РНК комбинации. Отдельная часть компилятора эти РНК комбинации превращает в соответствующие коды ДНК (по 10 байт) и создает префикс, который эту последовательность кодов помещает в конец ДНК, чтобы она выполнилась после выполнения основной ДНК и получилась дорисовка.

Отдельный вопрос был - как узнать с какой позиции происходит дорисовка? Ведь у нас нет абсолютных координат, есть лишь неизвестная текущая позиция и возможность двигаться вперед и поворачивать. Сделал префикс, который дорисовывает стрелку после отрисовки основной ДНК. Послал на сервер, чтобы увидеть картинку. Но оказалось, что сервер показывает лишь лучшую на данный момент картинку (раньше я об этом не знал, просто просмотрел), поэтому картинку со стрелкой он не показал. Пришлось запускать всю отрисовку Эндо у себя, заодно сделал вывод текущей позиции после отрисовки. Дождался генерации РНК Эндо, нарисовал, получил искомую позицию. Теперь ясно, откуда начинать дорисовку.

Следующая проблема: исходя из формулы расчета риска, одна отличающаяся точка картинки стоит столько же, сколько 10 оснований префикса. Ровно столько оснований ДНК нужно, чтобы выдать 1 команду РНК. При таком подходе дорисовка стоит гораздо больше, чем те точки, что она дорисовывает. Т.е. общий риск ухудшается. Нужно сжатие. Делаю простейшее сжатие: маска, которая берет 10 байт и шаблон, который их повторяет нужное число раз. На каждое повторение нужно 4 символа, т.е. сжатие в пределе 10 к 4. Этого все равно недостаточно. Тогда делается еще один шаг: префикс, который распаковывает N команд генерации РНК, сам повторяется K раз по той же схеме. Так их можно вкладывать друг в друга несколько раз. Пытаюсь аналитически вычислить оптимальную формулу для упаковки, плохо получается. Тогда пишу рекурсивную функцию такой многоуровневой упаковки с одним параметром алгоритма - максимальным числом повторений в одной пачке. Теперь, когда компилятор на Руби еще и сжимает, наконец что-то получается.

Еще одной преградой стало то, что многие области, которые находились и заливались, имели небольшую площадь. Выигрыш от их заливки оказывался меньше, чем стоимость команд по их отрисовке. Добавил еще один параметр в свою схему: минимальная площадь области, при которой стоит ей заниматься. Т.е. маленькие области просто игнорировались. Путем серии экспериментов с изменением этого параметра, а также параметра сжатия и числа используемых цветов, был получен префикс с максимальным (из перепробованных) выигрышем: он приближал картинку к целевой почти на 3 тысячи точек, но имел длину 20 тысяч оснований, т.е. "стоил" двух тысяч точек. Полученная разница давала 7 или 8 тысяч очков. Отправил этот префикс, тут же поднялся с шестьдесят какого-то места на тридцать какое-то. Было уже утро понедельника.

За час до окончания соревнования по подсказке с форума RSDN путем изменения префикса repair guide получил еще одну картинку:

Что с ней делать совершенно неясно. Дальше продвинуться в квесте не удалось. Путь с дорисовкой ничего не дал лучше того, что было послано. Есть понимание, что сжатие можно сильно улучшить, применив не RLE-подобный алгоритм, как сейчас, а LZ-подобный. Тем более, что сама процедура с маской и шаблоном очень хорошо для этого должна подходить. Пытаюсь нечто такое изобразить, но за оставшееся время не успеваю. Наступает 14:00 по Москве, соревнование заканчивается. Из 869 команд я на 42 месте. Хорошее число. :)


Как потом уже выяснилось, я, как и 90% участников, не дошел до самого основного и интересного. Те, кто смог пройти в квесте с repair guide дальше, открыли еще десятки картинок, описывающих общие принципы функционирования ДНК и конкретные функции и целые языки, зашитые в нее. Вот некоторые из найденных не мной картинок, выложенные psha:








Т.е. видно, что поле для деятельности там немерянное.

А кому-то удалось расшифровать следующее послание:

Help! We are a group of computer scientists held prisoner on the remote planet of Utrecht in the Orion nebula by the evil Fuun The Fuun have already conquered thousands of worlds, and it appears that Earth is next Their modus operandi is always the same: they organize a fake `programming contest' on the victim world to repair a supposedly disabled Fuun This enables them to identify that planet's best and brightest minds, who are then eliminated in advance of the actual invasion, leaving the planet defenseless against the Fuun's superior weaponry You must not, under any circumstances, repair the Endo creature, as he when reactivated will surely destroy his `rescuers' and give the attack signal to the Fuun invasion force massing near Sullust Do not give in to the lure of rewards, monetary or otherwise! It is too late for us, but in the unlikely event that Earth manages to stave off the Fuun invasion, we would appreciate a monument of some sort to honour us especially since we sabotaged the Fuun DNA by swapping some parabolas We are: Alexey Rodriguez Andres Loeh Arie Middelkoop Bastiaan Heeren Chris Eidhof Clara Loeh Eelco Dolstra Eelco Lempsink Jeroen Leeuwestein Johan Jeuring John van Schie Jurriaan Hage Maaike Gerritsen Mark Stobbe Martijn van Steenbergen Stefan Holdermans

© Dee Mon, 2004-2010.