Can You Systematically Solve A Friday Crossword?

Riddler Express

You are on $18$ points and must reach exactly $21$ (going over loses) with four bean-bag tosses. Each toss you choose: aggressive ($0.4$ in the hole for $+3$, $0.3$ on the board for $+1$, $0.3$ miss), conservative ($0.1$, $0.8$, $0.1$), or a deliberate waste ($+0$ for sure). Playing optimally, what is your probability of finishing on exactly $21$?

Solution

You need exactly $3$ more points and must never exceed them. Work backwards over the throws, tracking how many points you still have in hand. Let $P_k(x)$ be your best chance of finishing on $3$ when you have $x$ points and $k$ tosses left. Any score above $3$ is an instant loss ($P = 0$), and with no tosses left you succeed only if $x = 3$. Otherwise you pick the best of the three throws (aggressive, conservative, waste, top to bottom), $$P_k(x) = \max\!\begin{cases} 0.4\,P_{k-1}(x{+}3) + 0.3\,P_{k-1}(x{+}1) + 0.3\,P_{k-1}(x)\\ 0.1\,P_{k-1}(x{+}3) + 0.8\,P_{k-1}(x{+}1) + 0.1\,P_{k-1}(x)\\ P_{k-1}(x). \end{cases}$$ The waste option matters: once you reach $3$ you simply waste the rest and lock in the win. Evaluating $P_4(0)$ gives $$\frac{2137}{2500} = \boxed{85.48\%}.$$ The optimal play opens aggressively while there is room for a $+3$, then turns conservative or wastes throws to protect a reachable exact total.

The computation

Recurse over (tosses left, points), taking the best throw at each state and treating any overshoot as a loss.

from fractions import Fraction as F
from functools import lru_cache
A = (F(4,10), F(3,10), F(3,10)); C = (F(1,10), F(8,10), F(1,10))
@lru_cache(None)
def P(k, x):
    if x > 3: return F(0)
    if k == 0: return F(1) if x == 3 else F(0)
    throw = lambda h, b, m: h*P(k-1, x+3) + b*P(k-1, x+1) + m*P(k-1, x)
    return max(throw(*A), throw(*C), P(k-1, x))
print(P(4, 0), float(P(4, 0)))                 # 2137/2500, 0.8548