Трое новых русских рассказывают, какую пиротехнику подарили своим чадам на Новый Год:
— Я своему прикупил пять ящиков хлопушек…
— А я пять ящиков петард…
— А я своему ракету прикупил, тока, блин, каких-то космонавтов в нагрузку дали…
Теория
Космическая компания приняла вас на работу на должность “Разработчик кораблей и архитектор космических путей”. Это высокооплачиваемая работа, но и цена всему этому — сложные решения, которые придется вам принят во время работы.
Космос
Начнем с самого простого, как построена космическая карта. Космос будет представлен в виде графа с вершинами-системами и ребрами-космическими-путями.
Граф и ребра
Каждое ребро описывается последовательностью ячеек, каждая ячейка определяет позицию перемещения для корабля. Ячейки различаются на пустые и цветные.
Ребра как таковые не имеют направления, однако перемещение в одну сторону и в другую определяет чтение последовательности ячеек в ребре. Граф не имеет каких либо усложнений или необычных форм.
Перемещение по ребрам
Для перемещения кораблей из точки в точку используются … “кубики”. Кубики с 6-ю сторонами. Каждая сторона определяет количество возможных перемещений. Дополнительно с помощью цветовой маркировки указываются дополнительные “цветовые хода”. Каждый цветовой ход позволяет переместиться по ячейке с указанным цветом без ограничений на количество выпавших ходов, но только 1 ход на 1 цветовой ход. Например, если выпало 4 (3 черных и 1 зеленый), то корабль может переместится на 4 хода вне зависимости от цвета, или на 4 хода и 1 зеленый ход. Для других комбинаций используются аналогичные правила.
Каждый корабль оснащен двумя кубиками для хода. Кубики могут быть случайными и возможно даже не иметь определенного значения или иметь их несколько.
Пример:
Другой пример:
Пример перемещения
Рассмотрим передвижение на первом примере и с первым набором кубиков. Если представить ребро в виде
последовательности, то [2, 2, 3, 0, 1, 0, 0, 0, 2, 2, 0] - путь от белой звезды до красной. Аналогично для кубиков.
Но в данном случае кубики в виде множества граней, где каждая грань представлена в виде последовательности:
[[0], [0, 0], [0, 0, 0], [0, 0, 0, 0], [1, 3, 0, 0, 0], [1, 3, 4, 0, 0, 0]] - для первого кубика и
[[0], [0, 0], [3, 0, 0], [2, 4, 0, 0], [0, 0, 0, 0, 0], [2, 2, 2, 0, 0, 0]] - для второго.
Бросив кубики мы, например, получаем множество ходов: [0, 0, 0, 3, 0, 0], что означает 6 обычных ходов и один зеленый ход.
В случае выпадения другой комбинации: [1, 3, 4, 0, 0, 0, 3, 0, 0] мы получаем 9 обычных ходов, 1 красный, 2 зеленых и 1 синий ход.
Рассмотрим ход на примере [0, 0, 0, 3, 0, 0]. Если мы идем из белой звезды в красную, то выбросив такую комбинацию мы
передвинемся не на 6-ую по счету ячейку, а на 7-ую, так как зеленую клетку мы прошли за счет зеленого хода. Это означает,
что фактически у нас было 6 ходов и один цветной, 2 прошли, после зеленую клетку за счет зеленого хода пропустили и после прошли еще 4.
Точный формат кубиков будет определен позже.
Задача
Теперь о самой задаче. Вам требуется при данном графе и кубиках, определить наиболее выгодный маршрут.
Подготовка
На этапе подготовки ваши идеи, системы оценивания маршрутов, различные метрики и алгоритмы не ограничены входными и выходными данными. Продумайте способ оценки одного маршрута или сразу нескольких, подумайте о способе обхода путей между звездами.
Модели данных для решений
Теперь вам предоставлены модели данных в формате классов. Найти их можно в репозитории данной лабораторной работы.
Для полной работы вам потребуется установить часть модулей, однако если отрисовка для визуального анализа не нужна, то
в lab/__init__ удалите все связанное с draw.
Для простоты работы можно опять воспользоваться repl.it. При создании можно указать Import from GitHub и передав
ссылку на данный репозиторий https://github.com/octo-gone/ifmsh-lab-spaceship.git. Репл сам все установит.
Подготовка решения
Для простоты подготовки решения было решено использовать следующий подход. Решение должно находится в функции main
в файле solution.py (файл требуется создать самостоятельно на том же уровне что и main.py). Можно создавать другие, однако решение не
должно затрагивать файлы: main.py, lab/__init__.py, lab/generators.py, lab/models.py и lab/draw.py.
def main(space, start, end, dice_1, dice_2):
pass