Let's go to the Mun!

[thedeemon]

Называются ли разработчики космической программы космическими программистами?

В наше темное время, когда NASA закрылось, а Роскосмос вставляет датчики положения вверх ногами, регулярно бороздя космическими кораблями пашни Казахстана и просторы Тихого океана, вся надежда человечества сосредоточена на небольшой группе людей, знакомых с кроссплатформенной игрушкой Kerbal Space Program, а надежда этих людей лежит сегодня на вас: нужно написать программу, которая бы изобретала ракеты, оптимально приспособленные под параметры миссии. Входных параметров всего два: масса полезного груза и Delta-V бюджет миссии (определяемый планируемым маршрутом корабля), программа должна придумать конфигурацию ракеты минимальной массы, способной подняться в космос и доставить груз по назначению.
Подробное описание задачи здесь. Там же ссылка на онлайн-калькулятор, в котором можно проверить свое решение и посмотреть, как идет расчет.

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



Upd: время вышло, ответы открыты, подводим итоги:

	Mun	Kerbol	Moho	sum	language
Nikita Beloglazov	224.325	113.899	467.7125	805.9365	Clojure
Sanny Sanoff	223.6125	128.975	504.75	857.3375	Java
Alex Pashkov	222.7875	116.1499	552	890.9374	Haskell
kerbal_nut	225.05	115.462499	603.30	943.8125	Python

Похоже, наш победитель - Никита Белоглазов с решением на Clojure!
Если есть вопросы или лучшие идеи по оценке решений, еще не поздно тут обсудить.
Я думаю, окончательные результаты опубликует у себя хозяин конкурса ФП(ФП) _darkus_.

Comments

Re: какое эта задачка имеет отношение к космонавтике?

[alex pashkov (from livejournal.com)]

Дим, а почему, собственно
динамическое программирование тут не работает
?
Моё решение - это как раз динпрог. Правда, где-то явно закрался баг (возможно, косяк с вещественной арифметикой), иначе бы он мне нашёл все оптимальные решения. Но изъяна в логике я пока не вижу.

А логика такая.
Берём все разрешённые спецификацией конфигурации одной ступени - это будет множество S. Это уже почти фазовое пространство для динпрога, только нужно в него перетащить еще совместные ограничения на стартовую массу, дефицит дельта-v и высоту ракеты (они все моноиды, т.ч. с полугрупповым свойством всё будет хорошо). Итак, фазовое пространство X = S x M x V x H. В роли "времени" или "слоя" для динпрога будет, естественно, выступать номер ступени.

Стартуем динпрог со множества всех разрешённых спецификацией конструкций головной части (наличие центральной секции, acc_vac >= 5.0).

Далее на каждом слое динпрога отсекаем:
- все ракеты, не удовлетворяющие динамическим требованиям в вакууме (acc_vac >= 5.0)
- все ракеты, не удовлетворяющие динамическим требованиям в атмосфере (dv <= 5000 => acc_atm >= 15.0)  (Ха! как раз это условие неправильное, вот и нашлась ошибочка...)
- все ракеты, не проходящие по суммарной высоте (h <= 7)
- все ракеты, не проходящие по взлётной массе (начинаем с 700т, потом - масса наилучшего найденного so far претендента на решение)
- все ракеты, которые "хуже" одной из уже имеющихся в текущем слое, т.е. (m1,dv1,h1) <= (m2,dv2,h2)
(на деле тут чуть тоньше, т.к. надо учитывать еще тип ступени и её диаметр - но это несущественно)

Среди оставшихся вариантов ищем претендента на решение, т.е. конфигурацию с наименьшей массой из имеющих отрицательный дефицит (атмосферного) дельта-v. (И вот сюда-то как раз надо проверку dv <= 5000 => acc_atm >= 15.0 добавить)

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

Останавливаем процесс либо после 7 слоёв, либо после опустошения текущего множества разрешённых конфигураций.
Если к этому моменту у нас есть претендент на решение, то он им и является.

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

p.s. Эх, измельчала космонавтика... 700т максимальной стартовой массы. То ли дело Сатурн-5 со своими 2800т (!)
p.p.s. Возможный баг спецификации: нет требования, чтобы высота ступени третьего типа не превосходила высоту ступени первого типа, к которой она крепится; калькулятор это тоже не энфорсит
p.p.p.s. А в чём фишка Laythe? И что такое "РОБОТОТЕХНИКА"?

Re: какое эта задачка имеет отношение к космонавтике?

[thedeemon.livejournal.com]

Возможно, я просто не с той стороны к динпрогу подходил, надо над твоим вариантом подумать еще. Исходники не покажешь, кстати?

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

Про высоты ступеней самое смешное, что такая проверка изначально была, но потом я от нее отказался:

Решил, что и так уже много ограничений, а большие боковые ступени в случае чего можно и друг на друга налепить.

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

РОБОТОТЕХНИКА - это часть программы _darkus_'a в рамках его серии конкурсов. Он в них какие-то слова прячет, которые по идее надо в течении года собирать и потом как-то в очки конвертировать. Сам не знаю подробностей.

Re: какое эта задачка имеет отношение к космонавтике?

[thedeemon.livejournal.com]

>Среди оставшихся вариантов ищем претендента на решение, т.е. конфигурацию с наименьшей массой из имеющих отрицательный дефицит (атмосферного) дельта-v.

А что значит "отрицательный дефицит (атмосферного) дельта-v"?
Из подходящих ступеней на этом уровне выбираем самую легкую что-ли? Я не вижу, почему это должно давать оптимальное решение. Среди лучших найденных решений часто самая верхняя ступень имеет много баков с топливом.

Re: какое эта задачка имеет отношение к космонавтике?

[alex pashkov (from livejournal.com)]

> Из подходящих ступеней на этом уровне выбираем самую легкую что-ли?

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

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

А теперь добавляем в этот алгоритм запоминание текущего лучшего решения ("Среди оставшихся вариантов бла-бла-бла...")

> А что значит "отрицательный дефицит (атмосферного) дельта-v"?

Параметр dv у конфигурации в моём решении - это сколько ей не хватает до заданного в условиях задачи дельта-v.
Т.е. не бюджет, а его дефицит. Так удобнее. Получается вот что:
dv (i) = dv (i+1) - isp_vac * g_ln_m_i

Но когда мы проверяем, является ли некоторая конфигурация решением, то для нижней ступени нужно смотреть на
dv_atm (1) = dv (2) - isp_atm * g_ln_m_i

Ну и там же надо проверять условие, которое я ошибочно поставил в правила отсечения:
dv (i) <= 5000 => acc >= 15.0, i=1..n

p.s. Мои исходники - это крайне неидиоматический хаскель. Показывать их стыдно :-)

Re: какое эта задачка имеет отношение к космонавтике?

[thedeemon.livejournal.com]

А, кажется, начинаю понимать, спасибо.

Re: какое эта задачка имеет отношение к космонавтике?

[thedeemon.livejournal.com]

_darkus_, хозяин этой серии конкурсов, слезно просит посмотреть исходники, пусть и крайне неидиоматичные. Решение-то интересное, и язык расово верный.