Лабораторная работа "Космический корабль"

Трое новых русских рассказывают, какую пиротехнику подарили своим чадам на Новый Год:
— Я своему прикупил пять ящиков хлопушек...
— А я пять ящиков петард...
— А я своему ракету прикупил, тока, блин, каких-то космонавтов в нагрузку дали...

Теория

Космическая компания приняла вас на работу на должность "Разработчик кораблей и архитектор космических путей". Это высокооплачиваемая работа, но и цена всему этому — сложные решения, которые придется вам принят во время работы.

Космос

Начнем с самого простого, как построена космическая карта. Космос будет представлен в виде графа с вершинами-системами и ребрами-космическими-путями.

Граф и ребра

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

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

Перемещение по ребрам

Для перемещения кораблей из точки в точку используются ... "кубики". Кубики с 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

Как использовать модели и что можно с ними сделать

Основной способ создания задачи

from lab import models
from lab import generators
import solution
import random

random.seed(1)  # номер задания

size = random.randint(5, 12)  # генерация количества вершин
space = models.Space(size, generators.barabasi_albert)  # генерация космоса

dice_1 = models.Dice()  # первый кубик
dice_2 = models.Dice()  # второй кубик

points_pool = list(range(size))  # все возможные точки
random.shuffle(points_pool)
start = points_pool.pop()  # начальная точка
end = points_pool.pop()  # конечная точка

result = solution.main(space, start, end, dice_1, dice_2)  # запуск вашей программы

print(result)  # вывод вашей программы

Методы и классы

space - космос
route - маршрут

space.size - количество вершин
len(space) - количество вершин
space.routes - все маршруты
space[i] - маршруты из вершины i (с учетом None-ребер)
space[i, j] - маршрут между i и j вершиной
space[j, i] - маршрут между j и i вершиной

route.length - длина маршрута
len(route) - длина маршрута
list(route) - все ячейки маршрута
route.route - все ячейки маршрута
route[i] - i-ая ячейка маршрута

Вариант прохода маршрутов

for i, j, route in space.routes:
    print(i,  # номер начальной вершины
          j,  # номер конечной вершины
          route)  # маршрут между i и j вершиной