«Билет для езды» логика игровой логики для серых маршрутов

Question

Мне нравится играть Ticket to Ride, поэтому я решил поиграть с реализацией частей игровой логики в Python в качестве побочного проекта программирования. Игровая доска - это, по сути, взвешенный мультиграф, поэтому репликация базовой структуры игры с NetworkX была сундуком.

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

Для тех, кто не знает игры: в любой момент каждый игрок имеет несколько карт поезда в одном из восьми цветов, а также специальную категорию «локомотив», которая служит в качестве дикой карты. Эти цвета соответствуют цвету линий поезда на игровой доске (shown here), за исключением серых линий, где вы можете использовать любой цвет, если все автомобили в сегменте одного цвета. (Есть крайние случаи, связанные с туннелями и паромами, но мы оставим их в стороне на данный момент.)

С кодом, который сейчас находится, я могу найти все пути между двумя городами и получить обратно, сколько карт поезда каждый цвет необходим, чтобы принять этот конкретный путь, если только пути не связаны с серыми сегментами. Сначала я делаю несезонные сегменты, так как они более понятны - либо у вас достаточно красных/зеленых/синих карт для каждого красного/зеленого/синего сегмента на пути, иначе вы этого не сделаете. С серой, потому что вы можете выбрать любой цвет, который будет использоваться для каждого сегмента, он становится немного более привлекательным.

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

В качестве примера предположим, что инвентарь карты игрока 4 красных, 2 зеленых, 3 синих, и мы пытаемся выяснить, может ли он добраться из Парижа в Вену. Глядя на доску, довольно легко увидеть, что единственный возможный маршрут для этой комбинации карт - поездка в Париж - (3 серый) -> Цюрих - (2 зеленый) -> Венеция - (2 серый) - > Заград - (2 серый) -> Вена. Мой алгоритм для определения этого начинается с зеленого сегмента и выделяет две зеленые карты. Затем необходимо решить, как использовать оставшиеся 4 красные и 3 синие карты для покрытия серых сегментов длин 3, 2 и 2.

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

Мой код это прямо сейчас выглядит следующим образом:

def can_afford(path, cards): 
    grays = list() 
    for segment in path: 
     if segment.color == 'Gray': 
      grays.append(segment) 
     else: 
      if cards.get(segment.color, 0) >= segment.weight: 
       cards[segment.color] -= segment.weight 
      else: 
       return False 
    for gray in grays: 
     # Halp! 
     pass 
    return True 

(. «Вес» длина сегмента в вагонах)

Я чувствую, что есть на самом деле тривиальное решение скрываясь в здесь, на который я просто не могу положиться. Есть идеи?

Answer 1

Как говорит Даниэль Брюкнер, проблема поиска способа присвоения цветов карточек серому сегменту соответствует bin packing problem, с наборами цветных карточек, соответствующих ячейкам, и серыми сегментами, соответствующими упаковываемым объектам ,

Теперь проблема бен упаковка NP-hard, но это не катастрофа, в этом случае, так как проблема может быть решена в pseudo-polynomial time (то есть, во время, что это многочлен от размера бункеров), используя dynamic programming, и что должен быть достаточно хорош для вашего приложения, где размер бункеров ограничен количеством карт в игре. Вот пример реализации бен упаковки, используя @functools.lru_cache decorator для memoize его:

из functools импорта lru_cache

@lru_cache(maxsize=None) 
def packing(bins, objects): 
    """Return a packing of objects into bins, or None if impossible. Both 
    arguments are tuples of numbers, and the packing is returned in 
    the form of a list giving the bin number for each object. 

    >>> packing((4,5,6), (6,5,4)) 
    [2, 1, 0] 
    >>> packing((4,5,6), (1,1,2,4,5)) 
    [0, 0, 0, 1, 2] 

    """ 
    if not objects: 
     return [] 
    o = objects[0] 
    rest = objects[1:] 
    for i, b in enumerate(bins): 
     if o <= b: 
      p = packing(bins[:i] + (b - o,) + bins[i+1:], rest) 
      if p is not None: 
       return [i] + p 
    return None 

И это может быть использовано для определения, если путь может следовать в билете ездить:

def can_afford(path, cards): 
    """Return True if path can be followed using cards, False if not. 
    cards might be updated, so pass a copy if you don't want that to 
    happen. 

    """ 
    grays = [] 
    for segment in path: 
     c, w = segment.color, segment.weight 
     if c == 'Gray': 
      grays.append(w) 
     elif cards.get(c, 0) >= w: 
      cards[c] -= w 
     else: 
      return False 
    return packing(tuple(cards.values()), tuple(grays)) is not None 

Обратите внимание, что если вы сделали cardscollection.Counter, то вы могли бы просто написать cards[c] вместо cards.get(c, 0).

Answer 2

Эта проблема имеет некоторые сходства с такими проблемами, как bin packing, subset sum и другими аналогичными проблемами. Указанные и многие связанные с этим проблемы являются NP-полными, и поэтому может оказаться, что нет (известного) эффективного алгоритма для этой проблемы, но я не могу доказать это на данный момент - это просто интуиция. Я подумаю об этом еще, а затем обновить этот ответ.

Answer 3

Другой способ приблизиться это построить дерево поиска следующим образом:

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

• Каждый ребенок узла соответствует городу, который вы можете достать от родителя, вместе с картами и кусками поезда, которые остаются в вашей руке после завершения маршрута от родителя к узлу.

Например, корень дерева может соответствовать Монреалю с 4 синими, 1 белыми и 1 дикой картой и 45 кусками поезда. Дети корня будут:

• Торонто (1 синих, 1 белых, 1 диких), 42 # Используйте 3 синих карточки
• Торонто (2 синих, 1 белых), 42 # Используйте- синий и дикая карта
• Нью-Йорк, (1 синий, 1 белый, 1 дикий), 42 # Используйте 3 синих карты
• Нью-Йорк, (2 синий, 1 белый), 43 # Используйте 2 синих и диких карта
• Бостон, (3 синий, 1 белый), 43 # Используйте 1 синий и дикую карту
• Бостон, (2 синий, 1 белый, 1 дикий), 43 # Используйте 2 blu электронные карты
• Бостона (4-синее), 43 # Использование 1 белого и джокер

Теперь вам просто нужно выполнить поиск в глубине в этом дереве, чтобы увидеть, если вы можете добраться до места назначения город. Края, которые вы добавляете в дерево поиска, ограничены картами в руке (т. Е. Вы не можете перейти непосредственно из Монреаля в Sault St.Мари, потому что у вас нет в общей сложности 6 черных/диких карт в руке) и количество оставшихся поездов (вы не могли отправиться из Калгари в Сиэтл, если остались только 3 карты).