Current location:	Home sweet home
Current mood:	calm
Entry tags:	abbyy, icfpc, комп, позитив

Последние семь дней
Вечная серая жизнь наконец была разбавлена чем-то. Причем даже два-три раза.


Итак. На понедельник мне было назначено собеседование в ABBYY. Контора известная, попасть туда на стажировку очень хотелось. ПРиехав туда, удивился, что офис такой солидной фирмы находится.... эммм... в таком неудобом месте. Ну да ладно, внутри мне понравилось. Собеседование заключалось в заполнении анкеты и решении двух задач. Первая - на логику, из серии тех, которые я в большом количестве решал в школе. Её решил. Вторая задача была на лингивистику (т.е. есть штук пять чисел, которые на каком-то африканском языке звучат следующими разами. Как на том языке звучат следующие числа?. Сию задачку я не решил, допер только до того, что в том племени система счисления - пятиричная. Но она у них была не истинно пятиричная, а с некоторыми наворотами, посему задача решена не была. Хотя решал я эти задачи суммарно три часа, потом устал и сдался. Впрочем, мне предложили придти на повторное собеседование в среду. Резюме - понравилось.
Среда. Собеседование назначено на 12.00. Задачку на логику мне уже не дают, но дают более полный комплект: лингвистика+2*программирование. Лингвистика попалась более простая, отрешал. На программирование - первая более менее простая (посчитать функцию, которая напрашивается на то, что бы считать рекурсивно, но при это хавает дофига лишних ресурсов. Написал её без лишних вычислений. Вторая - з серии фирменных задач ABBYY, разработать алгоритм, с ограничением на количество операций и на память. Условие мне сейчас рассказывать влом.
Я сидел над решением 5(пять) часов!!!. успел даже 20 минут подремать (сидел в отдельной комнате). в середине сдал лингвистику, оказалась правильно. Потом меня повели на собеседование к программистам, с этими задачками по программированию. ПО пути было сказано "мы по столько времени никому не даем, поэтому ты решал не 5 часов, а 2". Спасибо, порадовали.
Короче, завалил так же и допвопрос по первой (сводилось к графам, но я там тупил с подсчетом).
Дали две допзадачи, из "фирменных", с комментарием "разговор продолжим только если решишь обе, за 40 минут". Решил только одну. Результат очевиден.
Но, тем не менее, первая экспа собеседований. И не самая плохая.



Так. Теперь ICFPC. Для тех, кто не знает что это такое - http://www.icfpcontest.org/
Смысл - трехдневное соревнование функциональных программистов, на которое мы полезли с С/С++/С# =(.
Задание текущего года жгло. Имеется ДНК инопланетянина. ДНК - это самомодифицирующийся по определенным правилам скрипт, который по ходу выполнения вырабатывает РНК. Выполнение итерационное (разбить ДНК на паттерн-темплейт-остаток, построить по паттерну и остатку энвайромент, по темплейту и остатку кусок, приписать кусок к началу остатка). Я это так понял, я в эту часть не сильно вникал.
В итоге мы получаем РНК. РНК - последовательность действий для рисования картинки. Из исходной ДНК получается картинка с инопланетянином. Надо получить такой префикс, который надо приписать к ДНК в начале, что бы рисовалась совсем другая картинка. Вот такая жесть.
Задание выложили в пятницу в 14.00.
Читали и осознавали его мы до 15.00.
Потом мы разделились. Я и Лост стали писать рнк-bmp, остальные сели за днк-рнк. Мы с Лостом достаточно хорошо распараллелили написание нашего куска, управились за пару часов, потом накатали пару тулзов для удобноой работы. После чего рнк-бмп была оставлена на мне, я приписывал туда всякие недокументированные в спецификации, но нужные фичи типа дампа слоёв.
Лост пошел следить за днк-рнк.
К вечеру пятницы появились сообщения о посланиях в оригинальном днк. Там в самом деле был текст "Aсhtung! The Рortable Network Graphics follows". Мы с Лостом над этим задумались, но сами ничего найти не смогли. Так кончилась пятница.
Суббота началась с того, что Шарп выложил на свн выдранные из днк пнг-шку и мп3-шку. пнг гласила "human audio follows", в мп3 шел некий префикс. На флокале появилось сообщение, что идущий в конце пдф префикс - есть селф-чек.
СтепЛг сообщил мне, что он уходит погулять, и просит меня протестить его днк-рнк. Я с него слил проект, и обнаружил в папке дебага некий файл резалт.тхт. Прогнал его через рнк-бмп и офигел - там рисовался слой с ещё одним префиксом, который потом затирался черным слоем. Вызвали Степу. Он офигел, узнав, что мы у него нашли рабочую РНК, но потом ситуация разъяснилась. В начале оригинальной ДНК идет код, который просто выводит чистый кусок РНК. Собственно, этот кусок в том файле и хранился. К вечеру появилась более менее рабочая версия днк-рнк. Решили проверить с префиксом селфчека. У Степы его конвертер вылетел, но успел написать большую часть рнк. мы прогнали его через рнк-бмп. Там получилась чудесная картинка с текстом проверки модулей на крайние ошибки. Пофиксили небольшую багу в рнк-бмп, небольшую багу в днк-рнк. В результате стали проходиться все тесты, кроме последнего, на End of DNA. Степа несколько раз перепроверял код, но так и не нашел ошибку.
В это время Лост решил прекратить маяться бездельем, и сел писать свою версию днк-рнк. К утру воскресенья она была готова, и она правильно проходила селфчек! Мы обрадовались. Загнали код, который получили вчера.
Получили картинку с двумя кодами. Первый решили посчитать сами, второй из интереса залили на их сервер (ибо там был клевый сервис - вывода картинки из префикса с наименьшим на данный момент у команды риском). Это был один из правильных префиксов, правильность составляла 1.2% :).
Теперь о грустном. Одна итерация у нас считалась несколько секунд, благо там было применение регэкспов к и копирование кусков днк. Семимегабайтных кусков, надо заметить. А исходное днк, по сообщениям авторов, считалось за 2 миллиона итераций... с этим надо было что-то делать.
Итого, к вечеру воскресенья мы имели Лоста, который переписывал днк-рнк на ускорение. В это врея на флокале появилось сообщение о том, что товарищ написал транслятор на 3000 итераций в секунду. Почитал рсдн. Там хвастались 200000 итераций/сек. Я погрустнел, и всю ночь гамал/гонял имевшийся у нас транслятор через профайлер.
С утра Лост объяснил мне восхитительную концепцию связного списка связных списков. Дописать его до 14.00 понедельника он не успел, а заодно у нас ещё и сеть упала. Вот такие пироги.
Впрочем, с первой попытки, с хреновой организациеё мы получили 131 место из 865. А команда "Стыдно за МГУ", например (SzM) вошла в топ-15. хнык.
Но мне офигенно понравилось. Через год надо будет повторить.