samedi 27 juin 2015

Efficiently calculate multiple object groupings

The situation I'm working on is I'm having to group cards into groups based power and card properties. Each group needs a certain combined power level from its cards and each card in a group need to have a required property or require a lack of a property in order for the group to report that it is ok. For example:

group1:
    required_property = prop1
    required_power_level = 4

group2:
    required_property = prop2
    required_power_level = 3

group3:
    required_property = not prop1
    required_power_level = 5

Some groups can define wild as their required property and will take any card not in any other group; these groups still have a power level that must be met.

Each card has a single, integer power level but can have zero, one or more properties. Obviously if a card is in one group it can not also be in another group.

card1:
    power = 2
    properties = prop1

card2:
    power = 2
    properties = prop1, prop2

card3:
    power = 5
    properties = None

card4:
    power = 3
    properties = prop1, prop2

Ultimately I need to distribute the cards to try get all groups satisfied, this includes any wild groups included. There can be an arbitrary number of groups (usually no more than 2 at a given time) and cards, and card's powers are unbounded positive integers (typically 9 or smaller though) and can have a max of 6 properties, or have no property at all.

The only thing I'm looking for at the end of the algorithm is if all groups can be satisfied or not, given a set of cards; the actual grouping of cards is irrelevant in the end.

Any ideas? I'm just looking for an algorithm, but if it helps, the implementation will be in ironpython.

Aucun commentaire:

Enregistrer un commentaire