Разбор ICFP 2007, команда qwertyteam: часть 1

В продолжение Отчет: участие команды dou в соревновании ICFP 2007: хочется раcсказать чего достигла наша команда во время, и после соревнования.

Команда называется qwertyteam и состоит из трех участников: wInuX (это я), tasman и suhoff. Для удобства общения было решено собраться вместе что бы не тратить время на icq и обмен файлами. Язык программирования каждый использовал по желанию. В результате все выбрали разный: я — java, tasman — python, suhoff — php. Как оказалось в последствии это абсолютно не помешало.
Описание задания. (для тех кто не в курсе)
Инопланетное существо Endo заснуло во время путешевствие в космосе и было подобрано сборщиком мусора, который впоследтсвии сбросил все на планету Земля (всегда подозревал, что весь хлам сгружают нам). Очнувшись в перевернутой тарелки Endo выбрался наружу и огляделся вокруг. Как раз в этот момент до земли долетел контейнер с мусором. Получив очередную моральную травму endo впал в кому. Командам участникам предлагалось переделать dna у endo таким образом чтобы он мог жить нашей планете.
Было дано:

7 Мб файл с текущей dna.
Описания процесса преобразования dna в rna (далее просто преобразователь) и rna в картинку (далее рисовалка).
Картинка которая получается на текущей dna
Картинка которую необходимо получить пребавив префикс в исходной dna.

Надо было найти:
Префикс как можно более короткой длины, который приблизит результирующую картику как можно ближе к требуемой.
Исходная и требуемая картинки:

Пятница. Первый день.
Я принимаюсь за преобразователь DNA -> RNA. tasman берется за RNA->Image. suhoff еще на работе. У меня работа идет очень медленно. Мешает отсутствие тестов и то что операции над DNA всегда допустимы (случайная строка на входе не привод к ошибкам.). Ближе к вечеру приходит suhoff. И начинает писать программу для сравнения двух картинок на соответствие. Так же постит префикс из документации и мы получаем тестовую картинку, которая помогает мне в написании правильной версии преобразователя . Время подходит к вечеру, дописав преобразователь DNA->RNA я понимаю, что моя реализация выполняет 5-10 итераций в секунду. А в документации сказано, что надо выполнить несколько милионов. У tasman дела лучше: рисовалка дописана, правда тестить ее пока особо не на чем. Мы решаем, что на сегодня хватит и расходимся по домам.

Суббота. День второй.
Я проснулся в 6 утра и начал переделывать структуру данных для увеличения производительности. Очень помогают результаты первых итераций полученных на медленной версии (они сразу же превратились в unit-тесты). В тому времени как все собрались была готова достаточно быстрая реализация имевшая всего маленький недостаток: преобразование не заканчивалось, а в самом конце входило в очень долгий цикл. Было решено пока это не исправлять, а заняться изучением результатов (как же мы были не правы!). В ходе отладки рисовалки tasman сразу же обнаруживает, что в начале (линиями) рисуется префикс dna, потом эта картинка стирается и начинается рисоваться оригинальная картика с endo. Запустив с этим префиксом получаем страницу repair guide. На которой еще два префикса. Первый выводит repair guide navigation, а второй сменяет ночь на день. В результате поста второго префикса получается первый (и последний :( ) не нулевой результат: {Risk: 1160658; Chance: 1.2703%}.

Каталог страниц документации

На странице repair guide navigation расказанно как кодируются целые числа и что есть каталог страниц, который находится на странице 1377. Только не совсем ясно (или даже совсем не ясно) как к нему обратиться. В этот момент я задался вопросом: что же такого делает коротенький префикс IIPIFFCPICPFPICIICCCIICIPPPCFICC, что полностью меняет результат преобразования dna? Разобрав префикс получаем:

pattern: ( S ’IFPFCFP’ ) II

template: N0,0 IC

пременив функцию matchreplace и replace видим что он где-то в dna меняет символы ’II’ на ’IC’. Прочитав еще раз о том как кодируются целые числа, я понимаю что он меняет число 0 на 2. Сразу появляется мысль, что надо бы заменить на 1377. Со второй попытки я создаю правильный префикс и попадаю на ту самую страницу 1377.

А на ней множество ссылок на другие страницы.

Лихорадочно мы начинаем просматривать их одну за одной. Информации так много что она не хочет помещаться в голове. Страница с каталогом (1-я из 14) в котором описаны смещение генов (как в последствии оказалось gene это подпрограмма или переменная). Страница где описано как вызывать гены, как передавать им параметры и получать результат. Страница (security features) на которой не понятно, что написанно. Страница с непонятными точками, озаглавленная Character set. В ходе просмотра страниц время пролетело быстро, наступил вечер и мы отложили дальнейшие поиски на завтра.

Воскресенье. Последний день (для нас последний. в понедельник надо бы идти на работу)
suhoff утром раскодировал страницу security features. Оказалось, что это вариация шифра Цезаря, в котором все буквы циклически сдвинуты на определенное число. В результате мы прочитали текст в котором описывается способ шифрования (нечто средние между простым хor и гаммированием ) а так же что есть некоторый cracker с помощью которого можно его сломать. Во время соревнований мы так и не поняли к чему все это. Так что мы отложили в сторону security и занялись таблицей генов (как я уже говорил 1-й из 14.). В первой строке таблице запись AAA_geneTablePageNr, которая как не сложно (за два часа это ведь не сложно?) догадаться задает номер страницы. После нескольких неудачный попыток (неправильно подсчитанное смещение в dna) мы попадаем на страницу 2, ну а потом на 3,4,...,14. Получаем еще имена генов и смещения. И вопросов становится на порядок больше чем было до этого :). Весь остальной день мы потратили на почти безуспешные попытки (удалось получить картинку с картой земли и описанием ICPF 2007) научиться вызывать гены. Как потом оказалось проблема была в моей реализации dna, которую я не посчитал необходимостью исправить. Еще в ходе безуспешних попыток поднятся по турнирной таблице были полученны картинки с рыжей коровой и слоном вметсто endo, которые к сожелению никаких баллов не дали.

Итого по соревнованию
Что понравилось:

Сложность задачи преобразования rna->dna.
Подробная, точная документация. За время соревнований не было найдено ни одной ошибки (в отличии от 2006, 2005 года).
Возможность командной игры. (В отличии от 2006, где задачи разбивалась на независимые части)

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

Плохая система оценки. Мы продвинулись достаточно далеко в исследование dna, а получили лишь баллы заработанные в первые 24 часа соревнований. В частности для их получения даже не надо было видеть catalog page.
Высокое требование к скорости. Оптимизированное решение rna -> image на python работает в 10 раз медленне чем тупое, как пробка, решение на java. Про преобразователь rna->dna я вообще молчу.
Логические задачи вместо программирования. На реализации преобразователя и рисовалки программирование закончилось
Большой фактор случайности в решении задач. Нам просто повезло, что мы заметили префикс который рисуется в начале, а потом стирается. Нам не повезло и мы не заметили, что в hex редакторе в dna есть надпись на ascii-art

Поиски после соревнования
В таблице генов были найдены ссылки на подробное описание параметров к некоторым их них (imlp-doc-[1-9]) и еще (fuun-doc-[1-3]).

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

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

Заменил шрифт font-dot на обычный. В результате удалось просмотреть страницу с описанием encoding