Magic Combat Golf Example

#!/usr/bin/env python3
import itertools


# memoizes function calls, key = repr of input.
class memoized(object):
    def __init__(self, func):
        self.func = func
        self.cache = {}

    def __call__(self, *args):
        args_repr = repr(args)
        if args_repr in self.cache:
            return self.cache[args_repr]
        else:
            value = self.func(*args)
            self.cache[args_repr] = value
            return value


def best_block(attackers, blockers):
    return max(block_sets(len(attackers), len(blockers)),
               key=lambda opt: score(attackers, blockers, opt))


def block_sets(a_len, b_len):
    block_options = []
    for b in range(b_len):
        block_options.append([()])
        for a in range(a_len):
            block_options[-1].append((b, a))
    return (list(list(o) for o in opt if o != ())
            for opt in itertools.product(*block_options))


def score(attackers, blockers, block_pairs):
    blocked_by = {}
    score = sum(sum(blockers, [])) - sum(sum(attackers, []))
    for blocker, attacker in block_pairs:
        if attacker not in blocked_by:
            blocked_by[attacker] = []
        blocked_by[attacker].append(blocker)
    for index, attacker in enumerate(attackers):
        power, toughness = attacker
        if index in blocked_by:
            cur_blockers = [blockers[b_ind] for b_ind in blocked_by[index]]
            def_power = sum(def_pow for def_pow, def_tough in cur_blockers)
            if def_power >= toughness:
                score += power + toughness
            score -= att_score(power, cur_blockers)
        else:
            score -= power/2
    return score


@memoized
def att_score(power, blockers):
    toughnesses = [toughness for _, toughness in blockers]
    if power >= sum(toughnesses):
        return sum(sum(blockers, []))
    elif power < min(toughnesses):
        return 0
    else:
        results = []
        for ind, blocker in enumerate(blockers):
            p, t = blocker
            if power >= t:
                new_blockers = blockers[:ind] + blockers[ind+1:]
                results.append(p+t+att_score(power-t, new_blockers))
        return max(results)

att = eval(input("Attacking creatures: "))
block = eval(input("Defending creatures: "))

best = best_block(att, block)

print("Blocks:", best)
print("Initial score:", sum(sum(block, [])) - sum(sum(att, [])))
print("Final score:", score(att, block, best))