ICFP contest 2009

Продолжая добрую традицию подробно описывать контесты, начатую с Sapka contest, предлагаю вашему вниманию отчёт о ICFPC 09

Введение

ICFP Contest - командный контест, который проводится один раз в году. Количество участников в команде не ограничено. Задание одно, на весь контест отводится 72 часа(3 суток). Контест делится на lightning round(оцениваются решения, полученные в первые 24 часа) и main round(оцениваются все отосланные решения).

Команда

Страницу команды Concrete mixers можно найти здесь. Т.е., 4 человека, но после lightning A2K отошел от дел. С одним из оставшихся участников - xa4a - я уже участвовал в Sapka, и мы там даже взяли призовое место на Lightning. Со вторым из оставшихся - Murkt - до этого работать вместе не приходилось, но мы вроде неплохо сработались.

Инструменты

Основной язык - Python. В качестве системы контроля версий использовали Mercurial, в качестве хостинга - bitbucket. Для визуализации был использован pygame(также были попытки использовать Qt, но в итоге остался вариант с pygame). Для общения использовали конференцию в jabber.

Задание

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

• Перевод спутника с одной круговой орбиты на другую
• Рандеву с другим спутником, двигающимся по круговой орбите
• Аналогичное рандеву, но начальная орбита и конечная могут быть эллиптическими
• Упрощенное рандеву с 11-ю спутниками на произвольных орбитах. Также здесь присутствует Луна и заправочная станция

Таким образом, большая часть задания связана с орбитальными маневрами - сплошная математика и физика.

Ночь первая (26.06-27.06)

Получили задание, прочитали, пообсуждали, устранили непонимания, распределили задания. Где-то через два часа у нас наконец появился парсер бинарников, еще через час было две VM, из которых мы выбрали лучшую. Еще через два часа я сделал первый тестовый солвер с визуализатором, а к этому моменту xa4a уже залил нужные формулы для hohmann transfer, A2K доделывал логгер, который был нужен для формирования сабмишенов.
Т.о., через 5 часов после начала я приступил к прикручиванию формул к солверу, однако это оказалось не так просто. Murkt с чувством выполненного долга(написанная им VM работала, хоть и медленно) пошел спать, а мы с xa4a и A2K еще часа два пытались починить логгер и формулы, A2K писал визуализатор на Qt. Результат первой ночи - готова VM, визуализатор, основная инфраструктура, однако очков всё еще 0

День первый (27.06)

С утра Murkt и xa4a подхимичили формулы и у нас в нашем симуляторе появились первые очки. Однако при попытке сабмита тут же стало понятно, что написанный ночью логгер ошибочен и я взялся его переделывать. В 14:20 был "EPIC WIN!!!!!"(с)Murkt - первые очки, полученные после исправления логгера. Задачи 1001-1004 в этот момент времени перешли в статус решенных. И пока xa4a и Murkt продолжали изыскания с задачами 2001-2004, я в течение часа многократно ускорил VM путем генерации и последующей интерпретации кода на Python. Также скриншот, сохранившийся с этого временного участка:
В дальнейшем мы все вместе пытались побороть задачи 2001-2004. Напомню, в этих задачах нужно было не просто перелететь на другую орбиту, как в 1001-1004, а и попасть еще и в ту же точку этой орбиты, что и другой спутник. Для того, чтобы этого добиться, мы ввели понятие hohmann delay - время ожидания, нужное, чтобы после него при hohmann transfer попасть в нужную точку. В 18:40 Murkt получил первые очки этим методом. Однако метод оказался совсем не стабильным - решение он давал, но давал и большие погрешности. Поэтому оставшееся до окончания lightning время мы работали в двух направлениях - устранение погрешности и 3001-3004. Ничего существенно добиться мы не успели и lightning закончили с результатом где-то 945 баллов. В top lightning'a мы,естественно не попали, и место в lightning на данном этапе узнать невозможно, хотя и очень интересно.
Ниже - визуализатор, который писал A2K, но который так и не был использован:

Ночь вторая (27.06-28.06)

Появилась Луна и задачи 4001-4004. Часа через четыре усилиями Murkt и xa4a были существенно проапгрейджены решения наших 8 задач и получено 1127.44746 очков. Приблизительно этого хотелось добиться в lightning, но не успели, а жаль. Также xa4a очень красиво переделал солверы (стало чем-то похоже на twisted). С 3х до 6 утра я сделал алгоритм подгазовки через phasing - он работал идеально и позволял проходить 2001-2004 даже без hohmann delay.

День второй (28.06)

Murkt почистил код, а мы с xa4a пытались найти параметры эллиптических орбит и у нас никак не получалось вывести формулу, которая бы работала для всех задач 3001-3004. В поисках решения были привлечены ЧМ и придумано несколько странных методов определения. Однако это ни к чему не привело, а уравнение орбиты было выведено xa4a чуть позже, когда я отсутствовал.

Ночь третья (28.06-29.06)

Murkt сделал naive chase - подгазовку, которая плевала на всю астрофизику и просто заставляла суптник лететь к цели, сжигая при этом топливо(занятный пример представлен ниже).
Этот naive chase отлично работал на небольших расстояниях. Совместив его с hohmann elliptic transfer, который к этому моменту я докрутил до состояния бета, у нас получилось решить все задачи из 3001-3004. Также я пытался сделать phasing для эллиптических орбит, однако из-за каких-то погрешностей точность phasingа оказалась меньше, чем нужно. Тем не менее, применение одной итерации phasing, а потом naive chase привело к увеличению очков.

День третий (29.06)

Весь день был проведен в попытках улучшить переходы по эллиптическим орбитам для 3001-3004, чтобы затем использовать в 4001-4004. Я попытался еще ускорить виртуальную машину посредством psyco (работало отлично, но только на 32-битных системах) и cython(работало везде, но компиляция была слишком долгой, кеширование скомпилированного нужно было делать, а профит был меньше, чем с psyco, т.о. в итоге от него отказались). В 13:04 был эпический "OMFG", когда мы заметили, что в Orbital Mechanics (описание ее смотрите ниже) есть матлабовский код, в котором есть готовые нужные нам формулы и алгоритмы - только копируй, исправляй и пользуйся. По этому коду xa4a переделал определение параметров орбиты, а я пытался сделать smart chase - через уравнение Ламберта. Однако, по-моему мнению, это было лишним - код нормально работать отказывался, а определение параметров орбиты вообще стало работать хуже, чем было. Smart chase также работал хуже, чем naive chase. Я попытался вывести hohmann elliptic delay - аналог hohmann delay но для произвольных эллиптических орбит, однако и этот алгоритм нам не очень пригодился. В этот момент - оставалось часа 3 до конца контеста - мы решили, что нужно хотя бы какие-нибудь Score получить на задачах 4001-4004. Murkt сделал простой солвер, который работал также, как 3001-3004(hohmann elliptic transfer+naive chase), однако ему не хватало топлива. Остальные три часа мы пытались подстроить naive chase, так чтобы он экономил топливо. Итог - пойманы три спутника в 4001(третий спутник был пойман мной за 7 минут до окончания, скриншот смотрите ниже) и два спутника в 4002.
Итог контеста - Weighted Total Score 2852.2285 (14 problems solved), 21 место, если последние 4 часа контеста все участники прохлаждались :)

О разном

• Репозиторий с исходниками можно найти здесь
• Orbital mechanics - кодовое название книги Howard Curtis "Orbital mechanics for engineering students" - для нас она стала Библией астрофизики
• Отчёт от Murkt
• Отчёт от xa4a

Организаторам

• Слишком много версий заданий. Последние я даже не читал - надоело
• Математика - это круто, и я не жалею, что участвовал в контесте, но всё же хотелось увидеть programming contest

Выводы

Как ни странно, текущий раздел не последний в этом отчёте. Тех, кто интересуется математикой, могут также прочитать и следующий раздел. Здесь же хотелось отметить, что фана от ICFPC 09 было всё же меньше, чем от Sapka (возможно потому, что Sapka была первым моим подобным контестом), однако море удовольствия от решения математических задачек я всё же получил. Будем надеяться, что в следующем году я тоже смогу поучаствовать.

О математике

За время контеста я получил(вывел сам, подсмотрел в Orbital Mechanics) множество формул. Здесь небольшой список, что было проделано(список не включает достижения остальных участников соревнования):

Кодовое имя	Описание
hohmann delay	Позволял найти время, которое нужно подождать на текущей орбите, чтобы при hohmann transfer на целевую орбиту попасть в нужную точку. Я выводил из равенства конечных углов, где конечные углы - функции времени. Этот hohmann delay не был использован в решении
phasing	Был подсмотрен в Orbital Mechanics и немного подправлен, чтобы была возможность совершать подстройку из любой точки орбиты, а не только из перигея. Вывод можно посмотреть в Orbital Mechanics
orbital equation v.1	Позволял находить уравнение орбиты по двум точкам. Был выведен из системы двух уравнений орбиты в разных точках. Работал идеально на орбитах, apse line которых совпадала с осью абсцисс
orbital equation v.2	К v.1 был добавлен еще один параметр - угол поворота орбиты. Параметры должны были находиться теперь уже по трём точкам. Решение искалось численно, потому что косинусы. Довести до ума так и не получилось, возможно, в моих предположениях была какая-то ошибка
orbital equation v.3	Было использовано уравнение орбиты в векторах. Также должно было определять по трём точкам и находить угловой момент и вектор эксцентриситета. Не был доведен до ума, потому что см. ниже
orbital equation v.4	Был подсмотрен в википедии в статье про кеплеровские орбиты. Вероятно, я где-то ошибся, но и эта формула выдавала неправильные результаты, хотя по этой же статье xa4a смог сделать рабочую версию
hohmann elliptic transfer	Почти то же самое, что и hohmann transfer, только без упрощений, возможных для круговых орбит. Вывод можно посмотреть в Orbital Mechanics. Было использовано для 3001-3004
elliptic phasing	То же самое, что и phasing, но для эллиптических орбит. Работало хуже, чем phasing, но работало для некоторых задач из 3001-3004. Вывод можно посмотреть в Orbital Mechanics
Smart chase	Chasing maneuver по Orbital Mechanics. Работал не очень, использован не был

Django CouchDB backend 0.1

Не так давно стараниями 42cc была выпущена версия 0.1 бэкенда к CouchDB для Django ORM. Доступ к нему можно получитьна github, также есть трак. Так как я принимал в этом проекте весьма деятельное участие, то мне бы хотелось рассказать про него поподробнее.
Я не буду останавливаться на том, нужна или не нужна CouchDB. Вы можете прочитать об этом здесь или в google. Мне бы хотелось отметить один из недостатков CouchDB - он непривычен для людей, привыкших к реляционным базам данных, а следовательно, может показаться неудобным. Это и стало одной из причин разработки django-couchdb.
Основная цель разработки - позволить описывать взаимодействие приложений на Django с CouchDB на знакомом "языке" - на языке Django ORM. Для поверхностного использования не понадобится даже знания о том, что такое CouchDB - достаточно прописать backend в DATABASE_ENGINE и использовать его. Простейшие примеры того, что умеет django-couchdb(в виде теста):

class Boo(models.Model):
    title = models.CharField(max_length=20)
    slug = models.SlugField()
    class Meta:
        unique_together = ('title', 'slug')

class Foo(models.Model):
    boo = models.ForeignKey(Boo)
    boo2 = models.ForeignKey(Boo, related_name="foo2_set")

b1 = Boo(title="1", slug="1")
b1.save()
b11 = Boo(title="11", slug="1")
b11.save()
b2 = Boo(title="2", slug="2")
b2.save()
f1 = Foo(boo=b1)
f1.save()
f2 = Foo(boo=b2)
f2.save()
f3 = Foo(boo=b1,boo2=b2)
f3.save()
assert_equal(Foo.objects.filter(boo__title="1").count(), 2)
assert_equal(Foo.objects.filter(boo__title="11").count(), 0)
assert_equal(Foo.objects.filter(Q(boo__title="1") | Q(boo__slug="2")).count(), 3)

assert_equal(Foo.objects.filter(Q(boo__title="1") & Q(boo2__title="2")).count(), 1)
assert_equal(Foo.objects.filter(Q(boo__title="1") & Q(boo2__title="11")).count(), 0)

А именно: работает генерация "схемы" из моделей, insert, update, delete, select, joins(не все). Не работает - ManyToManyField, aggregates. Поэтому django.contrib(например, admin) работает, но не полностью.

Перспективы развития

Дальнейшее развитие будет вестись в нескольких направлениях:

1. Исправление недостатков, поддержка других возможностей ORM
2. Развитие backend для использования сильных сторон CouchDB
3. Увеличение производительности

Выводы

Получился очень удобный инструмент, скрывающий особенности реализации (JS, HTTP запросы). Спасибо за внимание, ожидайте новые версии и новые возможности :)

Bachelor Thesis in Computer Science. Part 2. Верстка в LaTeX

В предыдущей статье было дано краткое видеоописание программного продукта, который появился в результате написания бакалаврской работы. Во второй части хотелось бы рассказать про вёрстку диплома в LaTeX - ведь именно она заняла большую часть времени, которое я потратил на диплом(в несколько раз больше, чем было затрачено на программу :( ). Для нетерпеливых сразу дам ссылку на конечный вариант (в формате PDF) - скачать(~800kb).
Я уже как-то упоминал про LaTeX. С момента публикации той заметки, я занимался написанием и версткой диплома с использованием этого замечательного инструментария. Я не буду давать подробные описания, но хотелось бы отметить основные пункты. Cкачать исходные тексты можно здесь(~2mb).

Сборка

Для сборки я использовал scons. Рекомендую. Достаточно написать простейший Sconstruct файл:

DEFAULT_TARGET = 'main.dvi'

env=Environment()
env.Alias('dvi', 'main.dvi')
env.Alias('pdf', 'main.pdf')

src=['main.tex','preamble.tex']
main_dvi = env.DVI('main.dvi', src)
main_pdf = env.PDF('main.pdf', src)

Default(DEFAULT_TARGET)

После этого полная сборка выполняется командой scons или scons pdf.

Класс

Для написания диплома был использован видоизменённый rusthesis класс - я назвал его uadiplom. Многие изменения, связанные с требованиями моего ВУЗа были учтены в нём, однако многое было сделано отдельно - с использованием дополнительных пакетов.

Списки TODO

При написании диплома я пользовался замечательным пакетом todonotes, который и вам рекомендую попробовать. Для того, чтобы его использовать, понадобится:

\usepackage[paperwidth=210mm,paperheight=297mm,left=25mm,right=35mm,top=2cm,bottom=2cm]{geometry} % нужно оставить поле справа
\usepackage[colorinlistoftodos, shadow, textwidth=3cm, textsize=tiny]{todonotes} % и установить размер пометок
\usepackage{hyperref} % для ссылок
\hypersetup{colorlinks=true, linkcolor=blue, citecolor=blue, filecolor=blue, urlcolor=blue}

Также для удобства я использовал такие команды:

\newcommand{\toaddtext}[1]{\todo[color=green!40]{#1}}
\newcommand{\toaddref}{\todo[color=red!40]{Добавить ссылку}}
\newcommand{\torewrite}[1]{\todo[color=blue!40]{#1}}

Эти команды можно использовать прямо в тексте. Чтобы сгенерировать список TODO, достаточно вставить команду \listoftodos. Предлагаемые todonotes выглядят красиво и очень удобны.

Настройки заголовков

Одной из норм, которые приняты в моем ВУЗе, являются странноватые подписи к таблицам. А именно - подпись идёт сверху, в две строки, первая из которых - "Таблица ##" курсивом справа, а вторая - название таблицы жирным по центру. Для того, чтобы добиться этого, был использован пакет caption:

\usepackage[labelsep=period,justification=centering]{caption}
\DeclareCaptionLabelFormat{uatablelabelformat}{\hfill\textit{#1~#2}}
\DeclareCaptionFormat{uatableformat}{#1#2\\#3}
\DeclareCaptionTextFormat{uatabletextformat}{\textbf{#1}}
\captionsetup[table]{format=uatableformat,labelformat=uatablelabelformat,textformat=uatabletextformat}

Оформление библиографии

Был использован bibtex. Стиль - модифицированный gost780u (который я назвал uabib). Единственная модификация, которая понадобилась - изменение подхода к аббревиатурам.

Оформление рисунков

Для вставки рисунков были добавлены простенькие шорткаты:

\newcommand{\coolfigure}[3]{\coolwfigure{#1}{#2}{#3}{\textwidth}}
\newcommand{\coolwfigure}[4]{\begin{figure}[!ht]\begin{center}\includegraphics[width=#4]{#1}\end{center}\caption{#2}\label{#3}\end{figure}}

Т.е., для вставки рисунка достаточно указать адрес изображения, название и метку.

Оформление таблиц

Такой же шорткат был создан и для таблиц:

\newcommand{\cooltable}[4]{
\begin{longtable}{#1}
\kill
\caption{#3\label{#2}}\\
\endfirsthead
\kill
\multicolumn{\LT@cols}{c}{\parbox{\textwidth}{\hfill \textit{Продолжение таблицы~\ref{#2}}}}\\
\endhead
#4
\end{longtable}}

Он принял такой вид, чтобы правильно обрабатывать разрывы страниц (с надписью "Продолжение таблицы ##" в правом верхнем углу). Назначение параметров можно понять по представленному коду.

Выводы

LaTeX можно и нужно использовать при написании текстов со сложной версткой. Он очень удобен и обладает неоспоримыми преимуществами, среди которых одним из важнейших является возможность каскадных изменений. Основные неудобства связаны с нежеланием ВУЗов переходить на использование LaTeX. Например, в моем случае пример титулки был выдан в виде .DOC файла(поэтому официальную титулку я делал в OpenOffice, в предложенном архиве - заглушка), а пример рамок для плакатов - вообще в формате Visio. Что уж сетовать на неточность требований и неквалифицированность нормоконтролёра.
Также одним из недостатков LaTeX является его сложность в некоторых вещах по отношению к WYSIWIG редакторам(к примеру, вспомните таблицы). Этот недостаток уравновешивается тем, что квалифицированную помощь всегда можно найти, например, в комнате #latex на freenode. Спасибо за внимание! В следующей части я расскажу про использование beamer для создания презентаций.

Bachelor Thesis in Computer Science. Part 1

Finally, my bachelor thesis has come to an end! And now I am going to publish the most interesting stuff I've done. Let me introduce you CamTrack, a simple OpenCV based tool that can be used to control your desktop using webcam. There is nothing breaking new in there (it is only a bachelor thesis and in Ukraine it is not something difficult). But I think, it can be a strong open source competitor to the CamSpace software.





You can find the source code on bitbucket. Or use direct link to download latest version. Don't hesitate to ask if you have any problems with installation.

If you're interested in this software or if you want to take part in it - please contact me.

Announcement for russian readers: I am also going to publish my thesis papers and give some suggestions about writing thesis using LaTeX. Stay tuned.