ICFPC CCCICICCCCCP CCP
Отчет о ICFP 2007, часть 3 и, наверное, последняя

(начало тут, продолжение тут, )


В понедельник пришлось приехать в 7-15 раньше чем в сб/вск, в частности потому, что срок поджимал, да и на работу не к 12 всё-таки приезжать. Так что в 8:40 я уже был на месте. bamsicа в этот день уже с нами не было (присутствовал виртуально), зато Коля сменил присутствие с виртуального на реальное.

Решили (еще в конце воскресенья), что надо бросать неблагодарное дело вытаскивания инфы из ДНК, а надо уже начинать работать на результат - получать префиксы и из них проценты успеха. Опять же в воскресенье вечером было замечено, что среди запостивших 28-символьный (или как в правильной терминологии надо говорить - 28-кислотный) префикс и получивших законные 1.2719% шанса/1160658 риска начинает всё больше разрастаться группа запостивших 27-кислотный префикс и уменьшивших риск до 1160657 с тем же процентом успеха. Стало очевидно, что они просто уменьшили данный префикс на одну кислоту. Простой анализ показал, что сигнатура поиска в префиксе была избыточная - превый символ можно было выкинуть, сигнатура всё равно находилась бы, что и было проделано, в результате чего в конце воскресенья мы перешли из группы "ламеров" в группу "хитрожопых ламеров".

Но надо было двигаться дальше. Какие виделись направления:
1) описание вызовов генов через адаптер (с передачей параметров) наводило на мысль, что можно было оттрейсить все вызовы генов и их параметры.
2) Т.к. каждый ген выдавал из себя сигнатуру РНК, то по ней можно было найти его, гена, начало в зеленой зоне, т.к. похоже выдача сигнатуры РНК была первой командой гена (по крайней мере на примере генов apple и appletree).
3) Можно поискать текстовые мессаджи (коих много должно быть), в частности мессадж Morph Endo! из исходной картинки, которые должны быть якобы закодированны известным методом
4) Можно поискать полигоны, способ кодирования коих тоже описан, и, например, найти полигоны тарелки и других ненужных объектов и свести их к одной точке, тем самым приблизив картинку к таргету.
5) Перекрасить наконец ящик, который занимает стольо много пикселей, а закрашен равномерным цветом (не считая наложенной в конце на всю картинку сетки геном anticompressant, направленной, видимо, против еще более хитрожопых, которые за RLE-ют всю картинку и зарастеризуют её линиями).

Перекрасить ящик мы пытались еще в воскресенье ночью, но ниасилили, только выяснили, что его исходный и результирующий цвет есть просто перестановка B и G в RGB. Это радовало, ибо не надо было считать количество цветов для смешивания, ибо это было сложно - каждый цвет там собирался из комбинаций набора стандартных цветов, коих было восемь - (0,0,0) (255,0,0) (0, 255, 0) (255,255,0) итд до (255,255,255) и результирующий цвет был средним арифметическим по каждой компоненте. Соответственно для обратного анализа надо было искать наибольший общий делитель по трём компонентам итд.. А так надо было просто найти нужные команды и заменить их на другие аналогичные, не меняя общее количество. Осложнилось это тем, что цвет набирался из 91 (девяносто одного) базового, и поиск куска ДНК, который бы из себя генерил нужную последовательность, результата не дал. Видимо, цвет собирался не в одной команде (= паре паттерн-темплейт), в возможно даже не в одном гене. Возможно даже там есть ген, который генерит нужный цвет исходя из параметров.

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

С текстовыми мессаджами - та же история. Правда тут были конкретные непонятки с кодировкой, т.к. Intergalactic Charset выглядел полной чухнёй, которая так осознана и не была. А ASCII-строчек в 9-кислотной кодировке не нашлось.

Трейс дерева вызовов генов уткнулся в проблему - сама ДНК в оригинале не использовала вызовы через адаптеры, а вызывала на прямую через известные ей смещения. Только под конец контеста Серега расковырял адаптер и увидел, что вызов генов из других генов идёт через характерные паттерны и пострил дерево, заодно увидев, что мы были правы, и каждый ген действительно начинается с сигнатурной РНК-команды, и прорисовав РНК-последовательность по шагам можно понять какой ген что рисует.

Чуть раньше я расковырял ген яблока (ссылка на него была в таблице) и увидел, что в первой же команде там идёт установка красного цвета. Было очевидно как его менять на зеленый, сгенерил префикс, проверил (на явном вызове отрисовки яблока) что ябочки покрасились (я бы не удивился, что после первой команды цвет опять сбрасывается и устанавливается еще раз где-то), склеил префикс с ранее известным нам 27-кислотным префиксом и результат засабмиттил на сайт. Увидел команду (по моему, это был kokorush) у которых был очень сходный результат, но более короткий префикс, прооптимизировал префикс на 10 кислот, запостил еще раз :)

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

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


Выводы:
1. В целом неплохо для первого раза.

2. Фан получен. Силы оценены.

3. Очень хорошо что мы сидели в основном в одной комнате. Я не представляю как можно делать это удаленно. Коля, который на два дня был оторван от нас, это подтвердил - он за нами просто не успевал, поэтому мог быть только на подхвате.

Я еще представляю что можно было это делать на прошлогоднем контесте, где каждый мог сидеть и долбать свою задачу, но в этом году это было ИМХО нереально.

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

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