Count the number of musically distinct mixes that can be generated in Dropmix without considering tempo or key.

dropmix_mix_count.py

import collections
import functools
import itertools
import operator

"""
Constants that will change over the life of the game
The current values are based off the following google sheet as of 2018/04/08 19:40 UTC
DropMix Card Checklist (Public)
https://docs.google.com/spreadsheets/d/13TjEBCW5Wv4xJgGVXGV7PfVNAuc3D07ADE-694NH1Ig/edit?usp=sharing

The reddit post that inspired this script:
https://www.reddit.com/r/dropmix/comments/8ao2t3/dropmix_combinations_math_that_nobody_asked_for/
"""
TOTAL_YELLOW = 52
TOTAL_RED = 74
TOTAL_BLUE = 73
TOTAL_GREEN = 49
TOTAL_WILD = 21
TOTAL_FX = 40

TOTAL_CARDS = sum([
    TOTAL_YELLOW,
    TOTAL_RED,
    TOTAL_BLUE,
    TOTAL_GREEN,
    TOTAL_WILD,
    TOTAL_FX,
])

TOTAL_CARD_MAP = {
    "Y": TOTAL_YELLOW,
    "R": TOTAL_RED,
    "B": TOTAL_BLUE,
    "G": TOTAL_GREEN,
    "W": TOTAL_WILD,
    "F": TOTAL_FX,
}

GAME_SLOTS = [
    ["Y","R"],
    ["R"],
    ["R","B"],
    ["B"],
    ["B","G"],
]

"""
We define some helper functions.
These functions are written in such a way to keep the calculations
as ints, which in python dynamically extend their capacity.
"""

def memorize(func):
    """
    we use this to speed up a few calculations at the cost of memory
    """
    cashe = dict()

    @functools.wraps(func)
    def wrapper(*args):
        if args not in cashe:
            cashe[args] = func(*args)

        return cashe[args]

    return wrapper

@memorize
def factorial(nn):
    if nn < 0:
        raise ValueError("Implementation does not support negative factorials")
    elif nn == 0:
        return 1
    else:
        return functools.reduce(operator.mul, range(1,nn+1), 1)


@memorize
def choose(nn,kk):
    if kk < 0 or kk > nn:
        return 0
    else:
        numerator = factorial(nn)
        denomminator = factorial(kk) * factorial(nn-kk)

        return numerator // denomminator

@memorize
def permutation(nn,kk):
    if kk < 0 or kk > nn:
        return 0
    else:
        return factorial(nn) // factorial(nn-kk)

"""
The real stuff
"""
def _create_layout_signature(layout):
    """
    We want to convert the layout into a key for a counter dictionary
    this way we can skip equivalent layouts.
    What ever the result, it needs to be hashable so that we can use it as a key for a dictionary.
    """
    counter_dict = collections.Counter(layout)

    """
    we count up different card types in the layout
    create key-value pair tuples and them place in in a frozen set
    so it is hashable
    """
    return frozenset(counter_dict.items())

def _count_mixes_from_layouts(game_slots,min_played_cards):
    """
    This function will take a game layout that defines the possible choices that can be made
    for card selection.

    Board Options in Frestyle pre v1.5.4
    |-----------|-----------|-----------|-----------|-----------|
    |    Y/R    |     R     |    R/B    |     B     |    B/G    |
    |-----------|-----------|-----------|-----------|-----------|
    | Y/R/B/G/F | Y/R/B/G/F | Y/R/B/G/F | Y/R/B/G/F | Y/R/B/G/F |
    |    Wyr    |     Wr    |    Wrb    |     Wb    |    Wbg    |
    |     N     |     N     |     N     |     N     |     N     |
    |-----------|-----------|-----------|-----------|-----------|
    | 7 choices | 7 choices | 7 choices | 7 choices | 7 choices |
    |-----------|-----------|-----------|-----------|-----------|

    Board Options in Frestyle post v1.5.4
    |-----------|-----------|-----------|-----------|-----------|
    |    Y/R    |     R     |    R/B    |     B     |    B/G    |
    |-----------|-----------|-----------|-----------|-----------|
    | Y/R/B/G/F | Y/R/B/G/F | Y/R/B/G/F | Y/R/B/G/F | Y/R/B/G/F |
    | Wyr/Wy/Wr |     Wr    | Wrb/Wr/Wb |     Wb    | Wbg/Wb/Wg |
    |     N     |     N     |     N     |     N     |     N     |
    |-----------|-----------|-----------|-----------|-----------|
    | 9 choices | 7 choices | 9 choices | 7 choices | 9 choices |
    |-----------|-----------|-----------|-----------|-----------|

    Board Options in Clash
    |-----------|-----------|-----------|-----------|-----------|
    |    Y/R    |     R     |    R/B    |     B     |    B/G    |
    |-----------|-----------|-----------|-----------|-----------|
    |  Y/R/F/N  |   R/F/N   |  R/B/F/N  |   B/F/N   |  B/G/F/N  |
    |    Wyr    |     Wr    |    Wrb    |     Wb    |    Wbg    |
    |-----------|-----------|-----------|-----------|-----------|
    | 5 choices | 4 choices | 5 choices | 4 choices | 5 choices |
    |-----------|-----------|-----------|-----------|-----------|

    We also have to watch out, since the following two layouts will create the same mixes:
    `Y|R|F|B|G`
    `Y|F|R|B|G`
    Though the cards are placed in different ways, the same music will be played.

    But also the following will produce different mixes:
    `Wy|R|B|B|G`
    `Wr|R|B|B|G`
    """
    count_total_layouts = 0
    total_mixes = 0
    used_layouts = dict()

    for layout in itertools.product(*game_slots):
        layout_signature = _create_layout_signature(layout)
        count_total_layouts += 1

        num_cards_played = sum(
            num_cards_in_slot
            for card_type, num_cards_in_slot in layout_signature if card_type != 'N'
        )

        if layout_signature in used_layouts:
            # this layout is equivalent to one we have already done. Skip it.
            continue

        elif num_cards_played < min_played_cards or num_cards_played == 0:
            # there are not enough cards in the layout to concider. Skip it.
            continue

        elif num_cards_played < 0:
            raise Exception("Something wrong happened during calculation, we cannot have negative number of cards")

        else:
            # we got here, so we haven't seen this card layout before and there is at least one card being played
            # set the flag that we used this layout
            used_layouts[layout_signature] = True

            # initalize number of layout specific mix count
            num_layout_specific_mixes = 1
            wild_count = 0

            for card_type, num_cards_in_slot in layout_signature:
                if card_type == "N":
                    # blank card slots
                    continue

                elif isinstance(card_type,str) and card_type.startswith("W"):
                    # defer wild card calcualtion to later
                    wild_count += num_cards_in_slot

                elif card_type in TOTAL_CARD_MAP:
                    num_specific_cards = TOTAL_CARD_MAP[card_type]
                    num_layout_specific_mixes *= choose(num_specific_cards, num_cards_in_slot)

                else:
                    raise Exception("Something wrong happened during calculation. Unexpected card type")

            if wild_count > 0:
                """
                treat the order of selection of wild cards as important
                since the following could occur
                Wyr|Wr|Wrb|Wb|Wbg
                where the wild card selection order will matter
                """
                num_layout_specific_mixes *= permutation(TOTAL_WILD, wild_count)

                # take into account the multi-counting for something like
                # Wr|Wr|Wr|Wb|Wb
                for card_type, num_cards_in_slot in layout_signature:
                    if isinstance(card_type,str) and card_type.startswith("W"):
                        num_layout_specific_mixes //= factorial(num_cards_in_slot)

            # print(layout,num_layout_specific_mixes)

            total_mixes += num_layout_specific_mixes

    return (count_total_layouts, total_mixes, used_layouts)

def num_freestyle_mixes_basic(num_min_cards=3,num_max_cards=5):
    """
    This is a flawed calculation.
    This just tells you the number of card selections you can have.
    No matter what this underestimates the number of mixes since
    placed of wild cards will matter, thus order of selection of wild cards matter.
    """
    total_mixes = 0

    for kk in range(num_min_cards, num_max_cards+1):
        total_mixes += choose(TOTAL_CARDS, kk)

    return total_mixes


def num_freestyle_mixes_old_version_1(num_min_cards=3):
    """
    This calculates the number of freestyle mixes pre v1.5.4

    For a given number card count:
    - we first choose how many wilds will be placed
    - choose which slots will be used for wilds
    - select wild cards card to be placed (order matters)
    - choose non-wilds to fill the rest of the slots

    Here wild cards have a distinct behavior based on the slot it is played in.

    For 5 card mixes you sum the following terms:
        (5 choose 0)*(21 permutation 0)*(288 choose 5)
        (5 choose 1)*(21 permutation 1)*(288 choose 4)
        (5 choose 2)*(21 permutation 2)*(288 choose 3)
        (5 choose 3)*(21 permutation 3)*(288 choose 2)
        (5 choose 4)*(21 permutation 4)*(288 choose 1)
        (5 choose 5)*(21 permutation 5)*(288 choose 0)
    """
    total_mixes = 0
    total_non_wilds = TOTAL_CARDS - TOTAL_WILD
    num_card_slots = len(GAME_SLOTS)
    for num_cards in range(num_min_cards, num_card_slots+1):
        for num_wilds_used in range(num_cards+1):
            wild_choices = choose(num_card_slots,num_wilds_used) * permutation(TOTAL_WILD, num_wilds_used)
            non_wild_choices = choose(total_non_wilds, num_cards-num_wilds_used)
            total_mixes += non_wild_choices * wild_choices

    return total_mixes


def num_freestyle_mixes_old_version_2(min_played_cards=3):
    """
    This calculates the number of freestyle mixes pre v1.5.4
    using layout enumeration method
    """
    card_types = ["Y","R","B","G","F","N"]

    game_slots_freestyle = [list(card_types) for _ in GAME_SLOTS]

    # adding special conditions for wild cards
    game_slots_freestyle[0].append("Wyr")
    game_slots_freestyle[1].append("Wr")
    game_slots_freestyle[2].append("Wrb")
    game_slots_freestyle[3].append("Wb")
    game_slots_freestyle[4].append("Wbg")

    count_total_layouts, total_mixes, used_layouts = _count_mixes_from_layouts(
        game_slots_freestyle,
        min_played_cards,
    )

    print("DEBUG: num_freestyle_mixes_old_version_2")
    print("DEBUG: Total enumerated layouts: {}".format(count_total_layouts))
    print("DEBUG: Musically unique layouts with at least {} cards: {}".format(
        min_played_cards,
        sum(used_layouts.values()),
    ))

    return total_mixes

def num_freestyle_mixes_splitvolume(min_played_cards=3):
    """
    we assume you have one of every card only.
    With the introduction of split volume controls for wild cards, this changes.
    For simplicity, depending on the slot, wild cards will either count as one card or three cards.
    """
    card_types = ["Y","R","B","G","F","N"]

    game_slots_freestyle = [list(card_types) for _ in GAME_SLOTS]

    # adding special conditions for wild cards
    game_slots_freestyle[0].extend(["Wy","Wr","Wyr"])
    game_slots_freestyle[1].extend(["Wr"])
    game_slots_freestyle[2].extend(["Wr","Wb","Wrb"])
    game_slots_freestyle[3].extend(["Wb"])
    game_slots_freestyle[4].extend(["Wb","Wg","Wbg"])

    count_total_layouts, total_mixes, used_layouts = _count_mixes_from_layouts(
        game_slots_freestyle,
        min_played_cards,
    )

    print("DEBUG: num_freestyle_mixes_splitvolume")
    print("DEBUG: Total enumerated layouts: {}".format(count_total_layouts))
    print("DEBUG: Musically unique layouts with at least {} cards: {}".format(
        min_played_cards,
        sum(used_layouts.values()),
    ))

    return total_mixes


def num_clash_mixes(min_played_cards=3):
    """
    We have 5 spots with the following lables:
    Y/R | R | R/B | B | B/G

    In addition to the choices in the slots, FX cards and wilds can be played on all of them.
    Further more any particular slot can be empty.

    So we now have the following options for each slot:
    Y/R/Wyr/F/N | R/Wr/F/N | R/B/Wrb/F/N | B/Wb/F/N | B/G/Wbg/F/N
    """

    total_mixes = 0

    count_total_layouts = 0

    game_slots_clash = [list(slot_options) for slot_options in GAME_SLOTS ]

    # adding special conditions for wild cards
    game_slots_clash[0].extend(["F","N","Wyr"])
    game_slots_clash[1].extend(["F","N","Wr"])
    game_slots_clash[2].extend(["F","N","Wrb"])
    game_slots_clash[3].extend(["F","N","Wb"])
    game_slots_clash[4].extend(["F","N","Wbg"])

    count_total_layouts, total_mixes, used_layouts = _count_mixes_from_layouts(
        game_slots_clash,
        min_played_cards,
    )

    print("DEBUG: num_clash_mixes")
    print("DEBUG: Total enumerated layouts: {}".format(count_total_layouts))
    print("DEBUG: Musically unique layouts with at least {} cards: {}".format(
        min_played_cards,
        sum(used_layouts.values()),
    ))

    return total_mixes




def main():
    freestyle_playable_basic = num_freestyle_mixes_basic(num_min_cards=1)
    freestyle_saveable_basic = num_freestyle_mixes_basic(num_min_cards=3)

    freestyle_playable_old_v1 = num_freestyle_mixes_old_version_1(num_min_cards=1)
    freestyle_saveable_old_v1 = num_freestyle_mixes_old_version_1(num_min_cards=3)
    freestyle_full_old_v1 = num_freestyle_mixes_old_version_1(num_min_cards=5)
    freestyle_playable_old_v2 = num_freestyle_mixes_old_version_2(min_played_cards=1)
    freestyle_saveable_old_v2 = num_freestyle_mixes_old_version_2(min_played_cards=3)
    freestyle_full_old_v2 = num_freestyle_mixes_old_version_2(min_played_cards=5)

    # verification that the old method and the new method agree
    assert(freestyle_playable_old_v1 == freestyle_playable_old_v2)
    assert(freestyle_saveable_old_v1 == freestyle_saveable_old_v2)
    assert(freestyle_full_old_v1 == freestyle_full_old_v2)

    freestyle_playable_splitvolume = num_freestyle_mixes_splitvolume(min_played_cards=1)
    freestyle_saveable_splitvolume = num_freestyle_mixes_splitvolume(min_played_cards=3)
    freestyle_full_splitvolume = num_freestyle_mixes_splitvolume(min_played_cards=5)

    clash_playable = num_clash_mixes(min_played_cards=1)
    clash_saveable = num_clash_mixes(min_played_cards=3)
    clash_full = num_clash_mixes(min_played_cards=5)

    print("Freestyle Mixes (Basic Flawed Calculation)")
    print("Total play-able mixes: {0:d} = {0:e}".format(freestyle_playable_basic))
    print("Total save-able mixes: {0:d} = {0:e}".format(freestyle_saveable_basic))

    print("Freestyle Mixes (Pre v1.5.4)")
    print("Total play-able mixes: {0:d} = {0:e}".format(freestyle_playable_old_v1))
    print("Total save-able mixes: {0:d} = {0:e}".format(freestyle_saveable_old_v1))
    print("Total full mixes: {0:d} = {0:e}".format(freestyle_full_old_v1))

    print("Freestyle Mixes (Split Wild Card Calculation)")
    print("Total play-able mixes: {0:d} = {0:e}".format(freestyle_playable_splitvolume))
    print("Total save-able mixes: {0:d} = {0:e}".format(freestyle_saveable_splitvolume))
    print("Total full mixes: {0:d} = {0:e}".format(freestyle_full_splitvolume))

    print("Clash Mixes")
    print("Total play-able mixes: {0:d} = {0:e}".format(clash_playable))
    print("Total save-able mixes: {0:d} = {0:e}".format(clash_saveable))
    print("Total full mixes: {0:d} = {0:e}".format(clash_full))

if __name__ == "__main__":
    main()