thirteen

(sas) Сумбурное

В этот раз все было куда как лучше. Я горжусь, что смог примазаться к таким людям.
Но я не удовлетворен. Уж очень мало сам сделал полезного. Мне бы поменьше болтать, да побольше кодить.
А вот команде в целом бы наоборот бы. Бы. San хорош. Очень. Может быть слишком. Я за полетом его мысле-рук не успеваю. Остановить и одумать его никак. А порой надо. Обидно иметь давно решенные задачи и не иметь рабочей проги в час Х.
А в целом, и впрочем, это - подробности. Которые враки.
Пошел писать все сначала, на хаскеле. Чего и вам.

ICFPC 2009 THIRTEEN testcase 4001 video

Здесь базу посетили _после_ Луны.

Оригинал 5М

ICFPC 2009 THIRTEEN testcase 4003 video

Здесь мы залетаем на базу перед полетом на луну.

Оригинал

ICFPC 2009 THIRTEEN testcase 4002 video

А это видео 4002 эпизода.

Оригинал 5.6М

ICFPC 2009 THIRTEEN testcase 4004 video

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

Оригинал AVI 5M

В этой версии прикручен залет на базу (в первую очередь). Можно отследить при покадровом просмотре, по топливу.

(brox) Моя ложка дегтя

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

По стилю кодинга san’а - это отдельный разговор. На будущее, к нему необходимо приставлять человека, который только и будет делать, что бить по рукам и заставлять комититься, как только получен какой-либо положительный результат. И тут же делать архив репозитория и класть его на полку с пометкой - здесь мы набрали N очков.

Общие впечатления от конкурса: орги явно делали все второпях. Наверное, это карма всех такого рода конкурсов

Своей работой я доволен, скажем так, процентов на 60. Во-первых, протупил с форматом %g. Можно, конечно, оправдываться сколько угодно - “кто мог знать и т.п.”, но к третьему дню контеста иметь некорректно работающую ВМ?

Во-вторых, “недобил” до конца оптимизацию зависимостей в нашем компиляторе. Там еще много всего можно было проделать.

В-третьих, и это совершенно непростительно, до соревнований ни разу не удосужился поинтересоваться серьезными работами по астронавигации, а ограничивался лишь своими собственными выкладками и прогами типа “посадки на Луну”.

В общем, я пошел учиться

(san) Пользуясь случаем

Пользуясь случаем, хочу сообщить, что наша контора в Харькове набирает Java-программистов. Мы не software house, у нас изначально, и по сей день лишь один проект, который мы все делаем.

Читать полностью (san) Пользуясь случаем…

(san) Новые подробности детектива.

Всплывают в памяти новые подробности.

В самом начале в четвертой задаче мы решали задачу минимизации топлива. Это позволяло нам вертеться не спеша вокруг Земли, вылавливая спутники по очереди, и дало высокий счёт. Но больший счет был бы достигнут при более быстром их облете. Было решено сделать следующий вариант: полностью израсходовать топливо, но очень быстро облететь все спутники. Этот вариант требовал возвращения на базу каждый раз после полета к спутнику, потому что полет был наиболее эффективным и съедал всё топливо (почти, чтобы уложиться суммарно). Но возникли проблемы с возвращением на базу (плохо сходился градиентный алгоритм расчета траектории возврата, то есть он иногда сходился очень, неприемлемо медленно). Чтобы минимизировать это “иногда”, я стал решать более полную задачу - летать за спутниками более эффективно с точки зрения по топливу, чтобы 3-4 спутника облететь за один раз. Эта задача была решена, но возвращения на базу остались проблемными - для нахождения точного импулься требовалось слишком много циклов перебора при градиентном спуске.

И сейчас я понимаю, почему. Потому что при возвращении вниз к земле очень малое изменение направления в начале траектории очень сильно влияет на конечную точку вблизи земли. Вспомните, с какой скоростью спутники вращаются вокруг земли! Там время как бы “идет быстрее”.  Оптимальная “дырка” в плоскости решений становится очень маленькой, на порядки меньше, оттого и время для ее решения. Обратная задача, при взлете, или при переходе с орбиты на орбиту - более простая.

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

Пример его использования: при выборе очередного спутника нам надо было знать, а хватит ли у нас топлива вернуться на базу? Для этого требовалась симуляция полета на спутник (с уточнением, которое сходилось бы быстро - см выше) а затем симуляция возвращения на базу - которая часто не сходилась!. Поэтому вместо этого делалось грубое прикидывание Ламбертом, которое регулярно оказывалось неверным из-за погрешностей, и на базу мы не возвращались. Возможно, уточнение первой половины помогло бы, но я не уверен, и не успел реализовать.

В результате его неиспользования, мы прекрасно облетали 4-5 спутников за один круг (!!! это выглядело великолепно на визуализаторе!!), и залетев однажды на базу (получалось!) набирались топлива, после чего нам надо было поймать следующие спутники, часто на более высоких орбитах (втч вытянутых), таким образом на базу нужно было возвращаться всё чаще (раз 5-6 всего), и на этом месте нас застал финальный свисток.

Далее, баг с посещением всех спутников, но необъявлением нам результатов, о чем Rst написал.  На самом деле баг со счетом состоял в том, что надо было подождать 2 миллиона секунд, пока прийдет счёт. Так что 4-я проблема была таки решена верно, и мы добавили просто ожидание.

В обед третьего дня (см внизу) RST был разбужен решением другой проблемы, а именно:  на сервере организаторов, после сабмита, наши прекрасно решенные проблемы 2000 и 3000 уходили в бесконечность (timeout), что означало, что условие остановки не достигнуто, и спутник улетел мимо, и крутится себе где-то на левой орбите. Нашим возмущениям не было предела: у нас решаются задачи о посложнее, значит VM реализована правильно, а наше решение считается неверным у организаторов. В задачах 4000 мы получали около 260 очков, что означало что мы-таки что-то ловим, но не всё.

Была предпринята попытка проанализировать код VM на предмет ошибок, но буква в букву спецификация сходилась. Была попытка обратить внимание организаторов на вопиющее безобразие. Но они качественно отморозились.

Тогда я понял, что нужна VM сторонних производителей, и пошел на jabber просить милостыню. Там добрая лисперская душа дала мне ссылку на чей-то java интерпретатор (не компилятор), и я его прикрутил, и увидел, что в 4000 задаче нашим решением ловятся только первые 2 спутника, а потом мы гуляем безрезультатно. Это был уже результат: проблема была изолирована. Я стал смотреть код, и он был почти точной копией нашего компилятора. Нет, он был совсем точной!. Ошибок быть не могло. И тут на меня стало снисходить озарение, что ошибки-то в числах! Я внезапно стал уверен, что десятичное представление плавающего числа, каким мы его перенесли в наш симулятор из бинарника (initialization of member variables), в начале работы программы было скомпилено из java кода в другую константу, отличную в битовом представлении от тех, которые в были бинарнике.  Решение было тривиальным, и я пошел будить RST7.

Компилятор бинарных заданий

Вот человек сделал компилятор файлов с формулами в удобочитаемый вид:

http://larubin.livejournal.com/119872.html?thread=650560#t650560 а оттуда http://pastebin.com/f7da69d

Это тот этап, который мы сделать не взялись по недостатку времени, но который бы ускорил перебор еще раз в 3 .. 10. Мы просто компилили в жаву, правда с устранением ненужных вычислений (12 спутников).

Человеку еще надо было сделать некоторые переменные локальными, было бы еще круче.

Update: я тормоз (локальные переменные)

Старый отчет, 2008 год, by san.

В 2008 году мы участвовали неудачно. Вот старый отчет. Под катом копия.

Читать полностью Старый отчет, 2008 год, by san….