Debitoor is hiring. No bureaucracy, no legacy code, no bullshit, fury continuous deployment, trips #js #node #react #mongo
×Закрыть

Разбор 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.
Надо было найти:
Префикс как можно более короткой длины, который приблизит результирующую картику как можно ближе к требуемой.
Исходная и требуемая картинки:

source150.pngtarget150.png

Пятница. Первый день.
Я принимаюсь за преобразователь 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%}.

repairguiderepairguidenavigation

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

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

pattern: ( S ’IFPFCFP’ ) II

template: N0,0 IC

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

repairguidecatalog

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

structureoffuunegenomegene-table-01.pngencodings
fieldrepairingguidecharactersetsecurity features

Лихорадочно мы начинаем просматривать их одну за одной. Информации так много что она не хочет помещаться в голове. Страница с каталогом (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, которые к сожелению никаких баллов не дали.

elephantocaml

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

  • Сложность задачи преобразования 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]).
impldoc8fuun-doc-1

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

genetable08checked

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

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

Перебрал страницы каталога 1-100 наугад. В результат еще нашлось три страницы.
page-00003-steganographysuperadaptivegenesalian-virus-alert

Страницу virus alert расшифровал тем же способом что и encoding.
alian-virus-alert-decrypted

Путем прямого вызова генов получил еще две страницы (initial condition и vmu).
initialconditionpage-vmu

На этом пока все. В свободное время я продолжаю исследование DNA. Если кто-то достиг большего с удовольствием почитаю (послушаю) о его достижениях.

  • Популярное

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

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

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