MiniCactpotSolver.py

from itertools import chain, permutations
from statistics import mean, median

FIRST_PAYOUT = 6
MIN_UNKNOWN = 1
MAX_UNKNOWN = 9

# Enter the board here. Use 0 for unknown tiles.
BOARD = [
    [ 9, 0, 0 ],
    [ 6, 0, 1 ],
    [ 0, 0, 4 ]
    ]

# Payouts starting with sum = 6
PAYOUTS = [
    10000,
    36,
    720,
    360,
    80,
    252,
    108,
    72,
    54,
    180,
    72,
    180,
    119,
    36,
    306,
    1080,
    144,
    1800,
    3600
    ]

def get_paths(board):
    """ Enumerates all paths across the board

    Returns ('path_name', [#, #, #]) tuples
    """
    # rows
    for i, row in enumerate(board):
        yield ('row {0}'.format(i), row)

    # columns
    board_transpose = map(list, zip(*board))

    for i, col in enumerate(board_transpose):
        yield ('col {0}'.format(i), col)

    # diagonals
    yield ('diag \\', [board[0][0], board[1][1], board[2][2]])
    yield ('diag /',  [board[0][2], board[1][1], board[2][0]])

def get_possible_unknowns(board):
    """ Returns a list of all numbers whose locations aren't known """
    # Flatten board into a list and pick out all nonzero values
    knowns = [val for val in list(chain(*board)) if val != 0]
    # Return all numbers 1-9 that aren't already on the board
    return [val for val in range(MIN_UNKNOWN, MAX_UNKNOWN + 1) if val not in knowns]

def get_possible_sums(path, unknowns):
    """ Enumerates all possible sums for a path """
    base_sum = 0
    num_unknowns = 0

    # Calculate the sum of the known numbers and the number of unknown slots
    for num in path:
        if num == 0:
            num_unknowns += 1
        else:
            base_sum += num

    if num_unknowns == 0:
        # No unknown numbers. Only possible sum is the sum of the numbers we know.
        yield base_sum
    elif num_unknowns == 1:
        # Only one unknown. Possible sums are base + each possible number.
        for num in unknowns:
            yield base_sum + num
    else:
        # Multiple unknowns. Possible sums are base + sum of each permutation of
        # unknowns of length num_unknowns.
        for nums in permutations(unknowns, num_unknowns):
            yield base_sum + sum(nums)
        

def get_possible_payouts(path, unknowns, payouts):
    """ Enumerates all possible payout values for a path

    Returns (sum, payout) tuples
    """
    for s in get_possible_sums(path, unknowns):
        yield (s, payouts[s - FIRST_PAYOUT])

def get_results(board, payouts):
    """ Enumerates tuples describing the statistics of the board

    Returns ('path_name', expected_payout, median_payout, [possible_payouts, ...]) tuples
    """
    unknowns = get_possible_unknowns(board)
    print('Unknowns:', unknowns)

    for name, path in get_paths(board):
        # Sort possible payouts descending by value
        possible_payouts = sorted(get_possible_payouts(path, unknowns, payouts), key=lambda x: x[1], reverse=True)

        # Collect the payout values for statistics
        values = [p[1] for p in possible_payouts]
        res_mean = mean(values)
        res_median = median(values)
        yield (name, res_mean, res_median, possible_payouts)
        
def solve(board, payouts):
    # Sort results descending by expected payout
    results = sorted(get_results(board, payouts), key=lambda x: x[1], reverse=True)

    for name, mean, median, possible_payouts in results:
        print(name)
        print('    mean:   {0}'.format(mean))
        print('    median: {0}'.format(median))
        print('    possible payouts:')

        payout_sums = [val[0] for val in possible_payouts]
        payout_sets = sorted(set(possible_payouts), key=lambda x: x[1], reverse=True)

        for s, payout in payout_sets:
            sum_count = payout_sums.count(s)
            if sum_count == 1:
                print('        {0} ({1})'.format(payout, s))
            else:
                print('        {0} x {1} ({2})'.format(payout, sum_count, s))

if __name__ == '__main__':
    solve(BOARD, PAYOUTS)