Can You Shut the Box?

This Week's Fiddler

Dynamic programming!

from fractions import Fraction
from functools import cache


@cache
def calc_partitions(
    target: int, nums: frozenset[int], largest=float("inf")
) -> list[frozenset[int]]:
    if target == 0:
        return []
    partitions = []
    for num in nums:
        if num > target or num > largest:
            continue
        if num == target:
            partitions.append(frozenset((num,)))
            continue
        for partition in calc_partitions(target - num, nums - {num}, num - 1):
            partitions.append(frozenset((num, *partition)))
    return partitions


@cache
def calc_win_prob(tiles: frozenset[int] = frozenset(range(1, 7))):
    if not tiles:
        return Fraction(1)
    prob = Fraction(0)
    for roll in range(1, 7):
        best = Fraction(0)
        for partition in calc_partitions(roll, tiles):
            best = max(best, calc_win_prob(tiles - partition))
        prob += best / 6
    return prob


print(calc_win_prob(), float(calc_win_prob()))

Output:

145/1944 0.07458847736625514

Answer: 145/1944 (about 7.46%)

Extra Credit

More dynamic programming!

from fractions import Fraction
from functools import cache


@cache
def calc_partitions(
    target: int, nums: frozenset[int], largest=float("inf")
) -> list[frozenset[int]]:
    if target == 0:
        return []
    partitions = []
    for num in nums:
        if num > target or num > largest:
            continue
        if num == target:
            partitions.append(frozenset((num,)))
            continue
        for partition in calc_partitions(target - num, nums - {num}, num - 1):
            partitions.append(frozenset((num, *partition)))
    return partitions


@cache
def calc_win_prob2(tiles: frozenset[int] = frozenset(range(1, 10))):
    if not tiles:
        return Fraction(1)
    prob = Fraction(0)
    for roll in range(2, 13):
        p = Fraction(min(roll - 1, 13 - roll), 36)
        best = Fraction(0)
        for partition in calc_partitions(roll, tiles):
            best = max(best, calc_win_prob2(tiles - partition))
        prob += p * best
    return prob


print(calc_win_prob2(), float(calc_win_prob2()))

Output:

466473281/6530347008 0.07143162230560597

Answer: 466473281/6530347008 (about 7.14%)