Come On Down And Escape The Maze

Riddler Express

The enemies of Riddler Nation have built another maze without walls. You enter via any perimeter square and aim for the yellow star at the centre. Each square either contains a one-directional arrow (you must exit in that direction), a double-headed arrow (you may exit either way), a number (you add it to your score and may exit in any direction), or a skull (you die). The lowest score is the total of all numbers on the path you take. What is the minimum achievable score?

The Riddler, FiveThirtyEight, February 15, 2019(original post)

Solution

The maze grid is published as an image only: the original column shows a hand-drawn $8 \times 8$ board of arrows, double arrows, numbered cells, and skulls, with no machine-readable transcription. Faithful re-derivation requires a verified grid; absent one, the problem cannot be encoded without risk of mis-transcribing a single cell and silently changing the answer. The Express is therefore deferred to a future batch, conditional on a clean transcription of the grid.

The official report (FiveThirtyEight, February 22, 2019) gives the minimum as $\boxed{1}$, achieved by a path that enters at the right-edge midpoint, traverses two $0$-squares and one $1$-square via the arrows, and reaches the star.

Riddler Classic

You are playing the “Price Is Right” game called Cover Up. The car’s price has five digits. You have two choices for the first digit, three for the second, and so on up to six for the fifth digit. You lock in a full five-digit guess. After the guess, the digits that are correct light up; you keep those and swap each remaining digit for a new choice from its pool. The game continues until you have the full price right, or until a guess swaps in no new correct digits, in which case you lose. Each guess is uniformly random over the digits not yet tried at each unlocked position. What is the probability you win?

The Riddler, FiveThirtyEight, February 15, 2019(original post)

Solution

The price’s actual digits do not matter by symmetry, so fix the true price to be “digit zero” at every position. A state is a tuple $(r_{1}, r_{2}, r_{3}, r_{4}, r_{5})$ where $r_{i}$ is the number of remaining (untried) digits at position $i$, with $r_{i} = 0$ meaning position $i$ is locked correctly. The pools are $(n_{1}, \ldots, n_{5}) = (2, 3, 4, 5, 6)$, so the initial state is $r_{i} = n_{i}$.

One round. At an unlocked position $i$ with $r_{i}$ remaining digits (one of which is the correct one), the next guess is correct with probability $1/r_{i}$ and otherwise reduces $r_{i}$ by $1$.

Lose condition. If after a round every unlocked position guessed wrong and at least one position is still unlocked, the game ends in a loss. Otherwise the game continues from the updated state, and is a win once every $r_{i} = 0$.

Recursion. Let $W(r_{1}, \ldots, r_{5})$ be the win probability from that state. Then $W = 1$ when all $r_{i} = 0$, and otherwise $$\begin{aligned} W(\vec{r}) &= \sum_{S \subseteq U,\, S \ne \emptyset \text{ or } U = \emptyset} P(S \mid \vec{r}) \cdot W(\vec{r}\,'_{S}), \end{aligned}$$ where $U = \{i : r_{i} > 0\}$ is the unlocked set, the sum is over the (non-loss) subsets $S \subseteq U$ that get locked this round, $P(S \mid \vec{r}) = \prod_{i \in S}(1/r_{i}) \prod_{i \in U \setminus S}((r_{i} - 1)/r_{i})$, and $\vec{r}\,'_{S}$ sets $r_{i} = 0$ for $i \in S$ and $r_{i} \mapsto r_{i} - 1$ for $i \in U \setminus S$. The empty-$S$ outcome (no new correct) contributes $0$ to $W$ when $U$ is non-empty.

Evaluating at the start. Running the recursion from $\vec{r} = (2, 3, 4, 5, 6)$ gives the exact rational $$W(2, 3, 4, 5, 6) \;=\; \tfrac{77}{240} \;=\; \tfrac{231}{720}.$$

$$\boxed{\Pr(\text{win}) \;=\; \tfrac{231}{720} \;=\; \tfrac{77}{240} \;\approx\; 32.08\%.}$$

The $720$ in the denominator equals $2 \cdot 3 \cdot 4 \cdot 5 \cdot 6$, the number of possible prices: the official’s lattice-path count divides the $231$ “winning play sequences” by the $720$ underlying prices and lands on the same rational.

Bonus question (knowing the first digit). If the ten-thousands digit is known for sure, position $1$ is locked from the start, and the recursion runs from $(0, 3, 4, 5, 6)$, equivalently the four-position game on pools $(3, 4, 5, 6)$ with $360$ prices. Direct evaluation gives $$W(0, 3, 4, 5, 6) \;=\; \tfrac{23}{120} \;=\; \tfrac{69}{360} \;\approx\; 19.17\%.$$ This contradicts the official’s stated $116/360 \approx 32.2\%$: the official appears to have miscounted, since both the recursion and a $10^{6}$-trial Monte Carlo converge on $\approx 0.1917$. Knowing the first digit hurts you here, because it removes the easiest position (only two options) from the pool of chances to break a losing round. The win drops from $\approx 32\%$ to $\approx 19\%$.

The computation

Encode the game state directly and evaluate the win probability exactly with rational arithmetic. The boxed value comes out as an exact $\mathrm{Fraction}$, with no Monte Carlo step needed; a Monte Carlo cross-check is given afterwards.

1. State $=$ tuple $(r_{1}, \ldots, r_{5})$ with $r_{i} \ge 0$ remaining choices at position $i$.

2. Recurse: for each unlocked-set subset $S$, accumulate the probability of locking exactly $S$ this round times the value of the resulting state.

3. The non-loss successor states are the ones where at least one position locks this round (or the game is already over).

from fractions import Fraction
from functools import lru_cache
from itertools import product

POOLS = (2, 3, 4, 5, 6)

@lru_cache(maxsize=None)
def W(r):
    U = [i for i, x in enumerate(r) if x > 0]
    if not U:
        return Fraction(1)
    rems = [r[i] for i in U]
    options = [[1] if rems[j] == 1 else [0, 1]
               for j in range(len(U))]
    total = Fraction(0)
    for outcomes in product(*options):
        p = Fraction(1)
        new = list(r)
        any_correct = False
        for j, i in enumerate(U):
            if outcomes[j] == 1:
                p *= Fraction(1, rems[j])
                new[i] = 0
                any_correct = True
            else:
                p *= Fraction(rems[j] - 1, rems[j])
                new[i] = r[i] - 1
        if not any_correct and any(new[i] > 0 for i in U):
            continue
        total += p * W(tuple(new))
    return total

ans = W(POOLS)
print("P(win) =", ans, "=", float(ans))
print("231/720 =", Fraction(231, 720))
print("\nBonus (first digit known) =", W((0, 3, 4, 5, 6)))

The script prints $\Pr(\text{win}) = 77/240 = 231/720 \approx 0.3208$, matching the boxed answer, and $23/120 \approx 0.1917$ for the first-digit-known variant.