thedeemon: (office)
Готовить ICFPC-like контест оказалось в несколько раз интереснее, чем участвовать, ибо занятных задач пришлось решить намного больше. Задача была устроена в виде квеста из нескольких этапов, где более ранние рассказывают о более поздних, поэтому готовилось все в другом порядке. Сперва был сделан фрактальный компрессор, который сжал заветную картинку до 40 КБ (об этом в предыдущем посте). Затем готовился этап с векторным текстом. Для этого был сделан редактор шрифта. Каждая буква состояла из набора отрезков, точки которых лежат на фиксированной сетке:



Редактор проверял, чтобы в каждой точке встречалось не более двух отрезков. Это дает возможность нарисовать все, посетив каждую точку не более одного раза, что позволило использовать тот формат с хранением в точках изменений текущего вектора. Имея готовый шрифт, был сделан редактор текстов:
Read more... )
thedeemon: (office)
Фракталы бывают очень разные по своему устройству, но объединяет их самоподобие: какие-то части в них похожи на другие их же части в другом масштабе. Фрактальный метод сжатия изображений берется сделать фрактал из любой картинки, ведь если взять произвольную фотку, там можно найти немало похожих фрагментов:

:)
Ну, может не везде столь же хорошо, но если для какого-то куска не находится похожего, его можно разбить на кусочки поменьше и поискать для них. В конце концов, на уровне отдельных пикселей найти похожие уж точно не проблема. Итак, возьмем картинку, разобъем ее на блоки и для каждого блока будем искать похожий блок большего размера. Он может быть где угодно. Он может быть как угодно повернут и растянут, даже нелинейно. Разрешим этому блоку также иметь другой контраст (вплоть до инвертированного) и яркость, лишь бы контраст был больше. Запишем найденное в виде набора соотношений "блок такой-то очень похож на такую-то область, к которой применили вот такое геометрическое преобразование, а яркости умножили на k и добавили константу b" (константы для разных блоков будут разные). Оказывается, что этих соотношений нам достаточно, чтобы восстановить картинку. Если геометрическое преобразование сжимающее (уменьшает расстояние между любыми двумя точками), и преобразование яркости тоже (константа k по модулю меньше единицы), то, слава матану, взяв произвольные начальные значения яркости и применив эти преобразования в цикле некоторое количество раз, мы придем к неподвижной точке всей системы преобразований, она и будет картинкой. Теперь отложите ваши айпады на помоечку и полюбуйтесь вот этими 58 килобайтами флэша.

Тут видны получающиеся на разных итерациях из изначального хаоса картинки, а поводив мышкой по блокам, можно видеть, какие блоки берутся за источники. Как вы догадались, в прошедшем соревновании картинка была сжата именно этим способом. Чем сложнее доступное геометрическое преобразование для блока, тем выше можно получить качество, но тем больше данных придется хранить. В данном случае исходные блоки брались ровно вдвое больше текущего, никаких поворотов не делалось, поэтому сохранялись лишь координаты блока (по 9 бит на координату) и коэффициенты k и b (7 и 10 бит соответственно). Изначально картинка была разделена на 64х64 блока, некоторые из них поделились рекурсивно на 4 поменьше, некоторые из тех еще на 4 поменьше, всего чуть меньше 9000 блоков, что заняло 40 КБ данных.

Интересным свойством этого метода является то, что результат формулируется в векторном виде, и декодировать картинку можно в произвольное разрешение. Выше она декодирована в 512х512, в контесте декодировалась в 1024х1024, а вот тут, например, ее фрагмент при разжатии в 2048х2048. При увеличении картинка получается заметно более четкая, чем при увеличении растровых картинок каким-нибудь Ланцошом, линии сохраняют плавность, но все заметнее становятся границы блоков. На этой идее работают некоторые фрактальные увеличивальщики картинок.
thedeemon: (office)
Отведенные на контест 72 часа истекли, и таблица результатов на этот момент выглядела следующим образом:
Read more... )

Инструментами настоящих хакеров стали Джава, Питон, Си, Руби и C#. Хаскель пришел четвертым, а за ним нетипичные Racket и Vala. Мои поздравления всем победителям и участникам! Особенно добрый коллега [livejournal.com profile] _darkus_ вызвался наградить победившую команду THIRTEEN материальными призами, которые они могут получить при личной встрече в Москве или по почте (доставка за счет получателя). Подробности у него в посте.

Ссылки на кое-какие отчеты о соревновании есть в комментариях к посту с условием. Пополнения приветствуются!

Я очень рад, что все получилось, т.к. боялся, что спецификации могут быть слишком недоспецифицированными или непонятными, но полтора десятка команд/участников, набравших 100% - это очень хорошо. Для меня было неожиданностью, что в ВМ, реализующейся в 15 строк, народ сумеет наделать столько случайных ошибок (у кого не так NOT работал, у кого вместо OR'a XOR был), но даже с ошибками их ВМ будет работать достаточно хорошо, чтобы пройти дальше. Про устройство конкурса, как это все было сделано и как работало, скоро напишу отдельно.

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

Profile

thedeemon: (Default)
Dmitry Popov

September 2017

S M T W T F S
     12
3456789
10111213141516
17181920212223
24252627282930

Syndicate

RSS Atom

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Sep. 26th, 2017 07:16 am
Powered by Dreamwidth Studios