Let's go to the Mun!
Oct. 11th, 2013 01:00 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
thedeemonНазываются ли разработчики космической программы космическими программистами?
В наше темное время, когда NASA закрылось, а Роскосмос вставляет датчики положения вверх ногами, регулярно бороздя космическими кораблями пашни Казахстана и просторы Тихого океана, вся надежда человечества сосредоточена на небольшой группе людей, знакомых с кроссплатформенной игрушкой Kerbal Space Program, а надежда этих людей лежит сегодня на вас: нужно написать программу, которая бы изобретала ракеты, оптимально приспособленные под параметры миссии. Входных параметров всего два: масса полезного груза и Delta-V бюджет миссии (определяемый планируемым маршрутом корабля), программа должна придумать конфигурацию ракеты минимальной массы, способной подняться в космос и доставить груз по назначению.
Подробное описание задачи здесь. Там же ссылка на онлайн-калькулятор, в котором можно проверить свое решение и посмотреть, как идет расчет.
Задача проходит в рамках октябрьского конкурса по функциональному программированию, но с измененными правилами. Побеждает не тот, кто пришлет решение раньше, а тот, чьи ракеты для предложенных миссий окажутся легче, а поиск конфигураций - быстрее. Ответы с найденными конфигурациями, ссылками на исходники и указанием времени работы оставляйте здесь. Комментарии будут скрыты в течении 72 часов. Открытое обсуждение условий на страничке конкурса, ну и тут тоже можно, только могут быть некоторые задержки с открытием таких комментов.
Upd: время вышло, ответы открыты, подводим итоги:
Похоже, наш победитель - Никита Белоглазов с решением на Clojure!
Если есть вопросы или лучшие идеи по оценке решений, еще не поздно тут обсудить.
Я думаю, окончательные результаты опубликует у себя хозяин конкурса ФП(ФП)![[livejournal.com profile]](https://www.dreamwidth.org/img/external/lj-userinfo.gif)
_darkus_.
В наше темное время, когда 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_.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
Октябрьский конкурс по ФП запущен
Date: 2013-10-11 06:13 am (UTC)no subject
Date: 2013-10-11 06:33 am (UTC)Про ихнее очень много наслышан и читал много...
какое эта задачка имеет отношение к космонавтике?
Date: 2013-10-11 05:18 pm (UTC)Это весьма упрощенная игрушечная постановка.
Re: какое эта задачка имеет отношение к космонавтике?
Date: 2013-10-12 03:10 am (UTC)Re: какое эта задачка имеет отношение к космонавтике?
Date: 2013-10-12 05:32 am (UTC)Re: какое эта задачка имеет отношение к космонавтике?
Date: 2013-10-12 08:18 am (UTC)http://wiki.kerbalspaceprogram.com/wiki/PB-ION_Electric_Propulsion_System
Но это больше для мелкого маневрирования, в данной задаче его не используем. Из используемых ближе всего к ионному
http://wiki.kerbalspaceprogram.com/wiki/LV-N_Atomic_Rocket_Engine
Он очень эффективен в вакууме, но слабоват по тяге. Если их взять несколько штук в одной ступени, то больше 5 м/с^2 получить несложно.
Re: какое эта задачка имеет отношение к космонавтике?
Date: 2013-10-14 09:30 pm (UTC)?
Моё решение - это как раз динпрог. Правда, где-то явно закрался баг (возможно, косяк с вещественной арифметикой), иначе бы он мне нашёл все оптимальные решения. Но изъяна в логике я пока не вижу.
А логика такая.
Берём все разрешённые спецификацией конфигурации одной ступени - это будет множество 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: какое эта задачка имеет отношение к космонавтике?
Date: 2013-10-15 03:31 am (UTC)700 тонн это следствие наложенных мной тут в задаче ограничений, в самой игре можно намного больше ракеты строить, плюс еще твердотопливные бустеры есть, которые мы тут не использовали.
Про высоты ступеней самое смешное, что такая проверка изначально была, но потом я от нее отказался:
Решил, что и так уже много ограничений, а большие боковые ступени в случае чего можно и друг на друга налепить.
Laythe - далекая планета, и в рамках ограничений этой задачи туда можно было отправить лишь тонны 3 груза, для более тяжелого груза нужна ракета побольше. Это я выяснил уже после начала контеста, но менять не стал, ибо вдруг решение все же есть и просто я не нашел, а также интересно было проверить, как программы участников будут обрабатывать случай отсутствия решения.
РОБОТОТЕХНИКА - это часть программы _darkus_'a в рамках его серии конкурсов. Он в них какие-то слова прячет, которые по идее надо в течении года собирать и потом как-то в очки конвертировать. Сам не знаю подробностей.
Re: какое эта задачка имеет отношение к космонавтике?
Date: 2013-10-15 04:33 am (UTC)А что значит "отрицательный дефицит (атмосферного) дельта-v"?
Из подходящих ступеней на этом уровне выбираем самую легкую что-ли? Я не вижу, почему это должно давать оптимальное решение. Среди лучших найденных решений часто самая верхняя ступень имеет много баков с топливом.
Re: какое эта задачка имеет отношение к космонавтике?
Date: 2013-10-15 06:48 am (UTC)Нет, конечно. Видимо, я непонятно изложил.
Попробуй прочитать алгоритм, пропустив абзац, начинающийся со слов "Среди оставшихся вариантов...".
Это и будет схема для динпрога. Вся её соль заключается в возможности на каждом слое отсеять (львиную) часть конфигураций, которые "хуже", чем какие-то из уже известных. Под словом конфигурация я понимаю не одну ступень, а всю построенную ракету.
А теперь добавляем в этот алгоритм запоминание текущего лучшего решения ("Среди оставшихся вариантов бла-бла-бла...")
> А что значит "отрицательный дефицит (атмосферного) дельта-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: какое эта задачка имеет отношение к космонавтике?
Date: 2013-10-15 09:48 am (UTC)Re: какое эта задачка имеет отношение к космонавтике?
Date: 2013-10-20 05:25 am (UTC)no subject
Date: 2013-10-11 04:43 pm (UTC)no subject
Date: 2013-10-12 03:10 am (UTC)Начальный сабмишен
Date: 2013-10-11 08:46 pm (UTC)Кстати, я ещё в процессе экспериментирования с калькулятором получил зелёную строчку "РОБОТОТЕХНИКА" под листингом расчётов, правда соответствующую ракету для Mun не сохранил. Повторный запуск строчки не дал, поэтому я предполагаю что она служит индикатором рекорда.
https://github.com/Vlad-Shcherbina/kerbal/blob/b71541f5b4218cfad342bb3e288184ad752946bc/production/monte_carlo_solver.py
Mun 330.5625 7011.15932633 [ { "fuel": "FL-T100 Fuel Tank", "engine": "LV-T45 Liquid Fuel Engine", "central": true, "numSideParts": 2, "numEngines": 1, "height": 3 }, { "fuel": "Rockomax X200-16 Fuel Tank", "engine": "LV-T45 Liquid Fuel Engine", "central": true, "numSideParts": 6, "numEngines": 7, "height": 1 }, { "fuel": "Rockomax X200-32 Fuel Tank", "engine": "Rockomax \"Mainsail\" Liquid Engine", "central": true, "numSideParts": 3, "numEngines": 4, "height": 3 } ] Kerbol 220.95 12074.873437 [ { "fuel": "FL-T400 Fuel Tank", "engine": "LV-N Atomic Rocket Engine", "central": true, "numSideParts": 2, "numEngines": 1, "height": 1 }, { "fuel": "Rockomax X200-8 Fuel Tank", "engine": "Rockomax \"Mainsail\" Liquid Engine", "central": true, "numSideParts": 3, "numEngines": 1, "height": 2 }, { "fuel": "Rockomax Jumbo-64 Fuel Tank", "engine": "Rockomax \"Mainsail\" Liquid Engine", "central": true, "numSideParts": 3, "numEngines": 4, "height": 1 } ]Условие
Date: 2013-10-11 11:07 pm (UTC)Re: Условие
Date: 2013-10-12 03:12 am (UTC)http://wiki.kerbalspaceprogram.com/wiki/Cheat_Sheet
no subject
Date: 2013-10-12 03:22 am (UTC)no subject
Date: 2013-10-12 03:28 pm (UTC)Также избыточным кажется бак "Rockomax X200-8 Fuel Tank".
no subject
Date: 2013-10-12 04:52 pm (UTC)Бак Х200-8 отличается от аналога того же объема своим диаметром. Если под ним большой двигатель и сверху тоже что-то большое, ставить узкий бак может быть плохо, т.к. крепкость и устойчивость конструкции падает, в этом месте велик шанс разлома.
Но все эти тонкости уже за пределами данной задачи.
точность
Date: 2013-10-12 05:13 pm (UTC)log (13.5 / 11.5) * 370 * 9.816 = 582.3517051814985
у меня в JS/Haskell/Java:
Prelude> log (13.5 / 11.5) * 370 * 9.816
582.3516776610459
Чото не так, есть мизерный шанс, что это будет влиять, но всё равно непонятно. ELM сам считает логарифм?
Re: точность
Date: 2013-10-12 05:51 pm (UTC)dV = logBase 2.718281828 (m_start / m_end) * isp * 9.816
Завтра могу сделать поточнее.
Re: точность
Date: 2013-10-12 10:58 pm (UTC)Re: точность
Date: 2013-10-13 04:22 am (UTC)Re: точность
Date: 2013-10-12 11:59 pm (UTC)Re: точность
Date: 2013-10-13 04:06 am (UTC)атмосфера
Date: 2013-10-13 04:20 pm (UTC)Re: атмосфера
Date: 2013-10-13 05:01 pm (UTC)Решение
Date: 2013-10-13 03:42 pm (UTC)Масса: 224.32500000000002
Время: 40сек
Конфигурация: https://github.com/nbeloglazov/fpcontests/blob/master/rocketscience-october-2013/mun.json
https://github.com/nbeloglazov/fpcontests/blob/master/rocketscience-october-2013/mun.json
2. m = 1.5, ∆V = 12000 (codename: Kerbol)
Масса: 113.89999999999999
Время: 115 сек
Конфигурация: https://github.com/nbeloglazov/fpcontests/blob/master/rocketscience-october-2013/kerbol.json
3.m = 11.0, ∆V = 10500 (codename: Moho)
Масса: 467.71250000000003
Время: 74 сек
Конфигурация: https://github.com/nbeloglazov/fpcontests/blob/master/rocketscience-october-2013/moho.json
4. m = 12.0, ∆V = 14800 (codename: Laythe)
Решение не найдено.
Вообще программа ищет решение, пока не истечёт время, попутно сохраняя лучшие решения. Таймаут настраивается, по умолчанию - 2 минуты.
Исходник и описание алгоритма: https://github.com/nbeloglazov/fpcontests/tree/master/rocketscience-october-2013
Язык: clojure
Время написания: часов 10-12.
Re: Решение
Date: 2013-10-15 09:54 pm (UTC)Re: Решение
Date: 2013-10-22 11:22 am (UTC)Финальный сабмишен
Date: 2013-10-13 07:02 pm (UTC)Mun 225.05 7001.99753996 [ { "fuel": "FL-T200 Fuel Tank", "engine": "LV-T30 Liquid Fuel Engine", "central": true, "numSideParts": 2, "numEngines": 1, "height": 3 }, { "fuel": "FL-T800 Fuel Tank", "engine": "LV-T30 Liquid Fuel Engine", "central": true, "numSideParts": 6, "numEngines": 7, "height": 2 }, { "fuel": "Rockomax X200-32 Fuel Tank", "engine": "Rockomax \"Skipper\" Liquid Engine", "central": true, "numSideParts": 4, "numEngines": 5, "height": 1 }, { "fuel": "FL-T200 Fuel Tank", "engine": "Rockomax \"Mainsail\" Liquid Engine", "central": true, "numSideParts": 2, "numEngines": 3, "height": 1 } ] Kerbol 115.4625 12015.2296636 [ { "fuel": "FL-T400 Fuel Tank", "engine": "LV-N Atomic Rocket Engine", "central": true, "numSideParts": 0, "numEngines": 1, "height": 3 }, { "fuel": "FL-T400 Fuel Tank", "engine": "LV-T30 Liquid Fuel Engine", "central": false, "numSideParts": 2, "numEngines": 2, "height": 3 }, { "fuel": "Rockomax X200-16 Fuel Tank", "engine": "LV-T30 Liquid Fuel Engine", "central": true, "numSideParts": 6, "numEngines": 7, "height": 1 }, { "fuel": "FL-T100 Fuel Tank", "engine": "Rockomax \"Skipper\" Liquid Engine", "central": true, "numSideParts": 2, "numEngines": 3, "height": 3 } ] Moho 603.3 10504.0617543 [ { "fuel": "FL-T800 Fuel Tank", "engine": "LV-N Atomic Rocket Engine", "central": true, "numSideParts": 2, "numEngines": 3, "height": 1 }, { "fuel": "FL-T400 Fuel Tank", "engine": "LV-N Atomic Rocket Engine", "central": true, "numSideParts": 4, "numEngines": 5, "height": 1 }, { "fuel": "Rockomax Jumbo-64 Fuel Tank", "engine": "Rockomax \"Mainsail\" Liquid Engine", "central": true, "numSideParts": 2, "numEngines": 3, "height": 2 }, { "fuel": "Rockomax Jumbo-64 Fuel Tank", "engine": "Rockomax \"Mainsail\" Liquid Engine", "central": true, "numSideParts": 4, "numEngines": 5, "height": 1 }, { "fuel": "FL-T800 Fuel Tank", "engine": "Rockomax \"Mainsail\" Liquid Engine", "central": true, "numSideParts": 6, "numEngines": 7, "height": 2 } ]В предположении что тороидалный двигатель в центральной части действительно не нужен и что моя программа правильна, Laythe решений не имеет.
https://github.com/Vlad-Shcherbina/kerbal/blob/23fa93a496b05c4f1f54b59be87c69c572389e03/production/solve_all.sh
Для получения данных конструкций солвер запускался в два процесса с ограничением в 110с.
Первые три миссии я ещё попробую ради интереса запустить ночью в большое число процессов и с большим таймлимитом.
Re: Финальный сабмишен
Date: 2013-10-14 08:33 am (UTC)Но вот зато решение для Mun:
222.725 7001.34188801 [ { "fuel": "FL-T200 Fuel Tank", "engine": "LV-T30 Liquid Fuel Engine", "central": true, "numSideParts": 6, "numEngines": 1, "height": 1 }, { "fuel": "FL-T400 Fuel Tank", "engine": "LV-T30 Liquid Fuel Engine", "central": true, "numSideParts": 3, "numEngines": 4, "height": 3 }, { "fuel": "Rockomax Jumbo-64 Fuel Tank", "engine": "Rockomax \"Mainsail\" Liquid Engine", "central": true, "numSideParts": 0, "numEngines": 1, "height": 1 }, { "fuel": "Rockomax Jumbo-64 Fuel Tank", "engine": "Rockomax \"Mainsail\" Liquid Engine", "central": false, "numSideParts": 2, "numEngines": 2, "height": 1 }, { "fuel": "FL-T800 Fuel Tank", "engine": "Rockomax \"Mainsail\" Liquid Engine", "central": true, "numSideParts": 2, "numEngines": 3, "height": 2 } ] it took 14797.9sRe: Финальный сабмишен
Date: 2013-10-14 08:51 am (UTC)IKS
Date: 2013-10-13 08:49 pm (UTC)Mun 10.4 7000 ; m=222.78750000000002 ; dv=7027.3617714100865 ; t=0m9.444s [ { "height": 1, "central": true, "numSideParts": 3, "engine": "LV-T30 Liquid Fuel Engine", "numEngines": 1, "fuel": "FL-T400 Fuel Tank" }, { "height": 3, "central": true, "numSideParts": 3, "engine": "LV-T30 Liquid Fuel Engine", "numEngines": 4, "fuel": "FL-T400 Fuel Tank" }, { "height": 1, "central": true, "numSideParts": 6, "engine": "LV-T30 Liquid Fuel Engine", "numEngines": 7, "fuel": "FL-T800 Fuel Tank" }, { "height": 1, "central": true, "numSideParts": 4, "engine": "Rockomax \"Skipper\" Liquid Engine", "numEngines": 5, "fuel": "Rockomax X200-32 Fuel Tank" }, { "height": 1, "central": true, "numSideParts": 2, "engine": "Rockomax \"Mainsail\" Liquid Engine", "numEngines": 3, "fuel": "FL-T100 Fuel Tank" } ] Kerbol 1.5 12000 ; m=116.14999999999999 ; dv=12020.901040814302 ; t=0m5.611s [ { "height": 1, "central": true, "numSideParts": 2, "engine": "LV-N Atomic Rocket Engine", "numEngines": 1, "fuel": "FL-T400 Fuel Tank" }, { "height": 1, "central": true, "numSideParts": 2, "engine": "LV-T30 Liquid Fuel Engine", "numEngines": 3, "fuel": "Rockomax X200-16 Fuel Tank" }, { "height": 3, "central": true, "numSideParts": 6, "engine": "LV-T30 Liquid Fuel Engine", "numEngines": 7, "fuel": "FL-T400 Fuel Tank" }, { "height": 1, "central": true, "numSideParts": 2, "engine": "Rockomax \"Skipper\" Liquid Engine", "numEngines": 3, "fuel": "FL-T400 Fuel Tank" } ] Moho 11.0 10500 ; m= 552 ; dv=10524.816027767874 ; t=1m45.269s [ { "height": 1, "central": true, "numSideParts": 2, "engine": "LV-N Atomic Rocket Engine", "numEngines": 3, "fuel": "FL-T800 Fuel Tank" }, { "height": 1, "central": true, "numSideParts": 4, "engine": "LV-N Atomic Rocket Engine", "numEngines": 5, "fuel": "FL-T400 Fuel Tank" }, { "height": 1, "central": true, "numSideParts": 0, "engine": "Rockomax \"Mainsail\" Liquid Engine", "numEngines": 1, "fuel": "Rockomax Jumbo-64 Fuel Tank" }, { "height": 3, "central": false, "numSideParts": 3, "engine": "Rockomax \"Mainsail\" Liquid Engine", "numEngines": 3, "fuel": "Rockomax X200-32 Fuel Tank" }, { "height": 1, "central": true, "numSideParts": 4, "engine": "Rockomax \"Mainsail\" Liquid Engine", "numEngines": 5, "fuel": "Rockomax Jumbo-64 Fuel Tank" }, { "height": 3, "central": true, "numSideParts": 6, "engine": "Rockomax \"Mainsail\" Liquid Engine", "numEngines": 7, "fuel": "FL-T200 Fuel Tank" } ] Laythe 12.0 14800 решения не существует ; t=1m16.377s SHA1: 34c7e93f56ccfcf34b83a089e9780a11d40c6735 haskellp.s. добавил конфигурации ракет
no subject
Date: 2013-10-14 02:35 am (UTC)Просьба Алексу и тем, кто еще будет постить: приводите не только массу ракеты, но и саму конфигурацию. Здесь или в виде ссылки.
no subject
Date: 2013-10-14 03:23 am (UTC)no subject
Date: 2013-10-14 04:09 am (UTC)Это ЖЖ так на посты со ссылками от незнакомых людей реагирует, но они не теряются все равно.
submission
Date: 2013-10-14 03:20 am (UTC)Программа считает около 3 минут на моей тачке, стало быть может и за 2 минуты на более продвинутой (работает в 8 тредов).
Вначале генерятся все возможные типы ступеней (включая ступени высот 1 2 и 3) получается около 2183 штук.
Потом они комбинируются в цепочки из 1, 2 и 3 - считается верхняя часть (голова) для полета начиная с 5000 км до финиша. Выбирается самый легкий вариант. Потом к нему подбирается "земная", нижняя часть, ведь мы уже знаем вес головы. Выбирается снова самая легкая нижняя часть, которая может этот вес вынести на высоту 5000 км с учетом ограничений.
Писал несколько вариантов, самый тупой и неоптимизированный из вариантов - самый рабочий в последнем коммите. Его можно оптимизировать, да.
Не нашел случаев, когда голова длиной 3 была бы оптимальнее головы длиной 2. Может на длине 4?
Решения:
I) mass= 223.6125
[ { "fuel": "FL-T200 Fuel Tank",
"engine":"LV-909 Liquid Fuel Engine",
"central": true,
"numSideParts": 2,
"numEngines": 3,
"height": 3}
, { "fuel": "FL-T800 Fuel Tank",
"engine":"LV-T30 Liquid Fuel Engine",
"central": true,
"numSideParts": 6,
"numEngines": 7,
"height": 2}
, { "fuel": "Rockomax X200-32 Fuel Tank",
"engine":"Rockomax \"Skipper\" Liquid Engine",
"central": true,
"numSideParts": 4,
"numEngines": 5,
"height": 1}
, { "fuel": "FL-T100 Fuel Tank",
"engine":"Rockomax \"Mainsail\" Liquid Engine",
"central": true,
"numSideParts": 2,
"numEngines": 3,
"height": 1}
]
II) mass = 128.975
[ { "fuel": "FL-T200 Fuel Tank",
"engine":"LV-N Atomic Rocket Engine",
"central": true,
"numSideParts": 6,
"numEngines": 1,
"height": 1}
, { "fuel": "FL-T800 Fuel Tank",
"engine":"LV-T30 Liquid Fuel Engine",
"central": true,
"numSideParts": 4,
"numEngines": 5,
"height": 2}
, { "fuel": "Rockomax X200-16 Fuel Tank",
"engine":"Rockomax \"Skipper\" Liquid Engine",
"central": true,
"numSideParts": 2,
"numEngines": 3,
"height": 2}
]
III) mass = 504.75
[ { "fuel": "FL-T400 Fuel Tank",
"engine":"LV-N Atomic Rocket Engine",
"central": true,
"numSideParts": 3,
"numEngines": 4,
"height": 3},
{ "fuel": "FL-T800 Fuel Tank",
"engine":"LV-T30 Liquid Fuel Engine",
"central": true,
"numSideParts": 6,
"numEngines": 7,
"height": 1}
, { "fuel": "Rockomax Jumbo-64 Fuel Tank",
"engine":"Rockomax \"Mainsail\" Liquid Engine",
"central": true,
"numSideParts": 3,
"numEngines": 4,
"height": 2}
, { "fuel": "Rockomax X200-16 Fuel Tank",
"engine":"Rockomax \"Mainsail\" Liquid Engine",
"central": true,
"numSideParts": 6,
"numEngines": 7,
"height": 1}
]
IV = нет решения.
Maximum dV succeeded: 10767.024886966658 (not enough to reach 14000)
[ { "fuel": "FL-T800 Fuel Tank",
"engine":"LV-N Atomic Rocket Engine",
"central": true,
"numSideParts": 2,
"numEngines": 3,
"height": 1}
, { "fuel": "FL-T800 Fuel Tank",
"engine":"LV-909 Liquid Fuel Engine",
"central": true,
"numSideParts": 6,
"numEngines": 7,
"height": 1}
,
{ "fuel": "Rockomax X200-32 Fuel Tank",
"engine":"Rockomax \"Skipper\" Liquid Engine",
"central": true,
"numSideParts": 3,
"numEngines": 4,
"height": 1}
, { "fuel": "Rockomax X200-32 Fuel Tank",
"engine":"Rockomax \"Mainsail\" Liquid Engine",
"central": true,
"numSideParts": 3,
"numEngines": 4,
"height": 3}
, { "fuel": "Rockomax Jumbo-64 Fuel Tank",
"engine":"Rockomax \"Mainsail\" Liquid Engine",
"central": true,
"numSideParts": 6,
"numEngines": 7,
"height": 1}
]
no subject
Date: 2013-10-14 07:34 am (UTC)[{"central":true,"height":1,"engine":"LV-N Atomic","numSideParts":6,"numEngines":1,"fuel":"FL-T200"},
{"central":true,"height":1,"engine":"LV-T30","numSideParts":2,"numEngines":3,"fuel":"X200-16"},
{"central":true,"height":3,"engine":"LV-T30","numSideParts":6,"numEngines":7,"fuel":"FL-T400"},
{"central":true,"height":1,"engine":"Skipper","numSideParts":2,"numEngines":3,"fuel":"FL-T100"}]
no subject
Date: 2013-10-16 02:24 pm (UTC)Дмитрий, выражаю крайнюю и категорическую благодарность за помощь.
no subject
Date: 2013-10-19 08:58 pm (UTC)no subject
Date: 2013-10-20 05:13 am (UTC)Вот мое на хаскеле, в полторы сотни строк:
http://stuff.thedeemon.com/lj/ksp2.hs
Оно бы заняло третье место из пяти, если бы участвовало. Для одной из планет нашло решение лучше, чем у всех конкурсантов. Работает в среднем около минуты.
Не учитывает вес разделителей ступеней, что на качество ответов мало влияет, но истинную массу полученных ей ракет следует проверять в онлайн-калькуляторе.
no subject
Date: 2013-10-20 07:24 pm (UTC)no subject
Date: 2013-10-21 12:29 pm (UTC)https://github.com/nbeloglazov/fpcontests/blob/master/rocketscience-october-2013/src/rocketscience/core.clj
Описание решения:
https://github.com/nbeloglazov/fpcontests/tree/master/rocketscience-october-2013
https://bitbucket.org/sannysanoff/rock/src/54a69891c9726f71932dd7f6e806c0999e6aa5cd/src/main/Generator.java?at=master
no subject
Date: 2013-10-21 12:51 pm (UTC)