Can You Escape A Maze Without Walls?

Riddler Express

The enemies of Riddler Nation have forced you into a maze without walls. You move between boxes in a grid: up, down, left, or right, never diagonally. The symbol inside the box you have just moved to dictates your next move, relative to the direction you would be facing if you were physically walking the maze: “S” means continue straight, “R” turn right, “L” turn left, “U” a $\mathrm{U}$-turn, and “?” lets you pick any of the four. An “X” kills you; so does being forced off the grid. The goal is the smiley face. You may enter the maze at any of the $32$ perimeter slots. The grid is the $8 \times 8$ shown below. Can you reach the smiley face, and if so, what is the minimum number of moves? $$\begin{array}{|c|c|c|c|c|c|c|c|} \hline \mathrm{L} & \mathrm{U} & \mathrm{U} & ? & \mathrm{U} & \mathrm{L} & \mathrm{X} & \mathrm{L} \\ \hline \mathrm{R} & \mathrm{L} & \mathrm{R} & \mathrm{L} & \mathrm{U} & \boldsymbol{\odot} & \mathrm{U} & \mathrm{U} \\ \hline \mathrm{S} & \mathrm{L} & \mathrm{R} & \mathrm{L} & \mathrm{U} & \mathrm{L} & \mathrm{X} & \mathrm{R} \\ \hline \mathrm{U} & \mathrm{R} & ? & \mathrm{R} & \mathrm{S} & \mathrm{L} & ? & \mathrm{R} \\ \hline \mathrm{R} & \mathrm{U} & \mathrm{U} & \mathrm{R} & \mathrm{R} & \mathrm{R} & \mathrm{S} & \mathrm{L} \\ \hline \mathrm{S} & ? & \mathrm{S} & \mathrm{L} & \mathrm{S} & \mathrm{S} & \mathrm{L} & \mathrm{R} \\ \hline \mathrm{R} & \mathrm{L} & \mathrm{R} & ? & \mathrm{R} & \mathrm{L} & ? & \mathrm{L} \\ \hline \mathrm{L} & \mathrm{R} & \mathrm{S} & \mathrm{R} & \mathrm{S} & \mathrm{L} & \mathrm{R} & \mathrm{L} \\ \hline \end{array}$$

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

Solution

The maze is small enough to solve by exhaustive shortest-path search, and the structure of the rule (the next direction is a function of current cell and current facing) makes the state space clean: a state is a pair $((r, c), f)$ of grid cell and facing direction.

State graph. The cells $(r, c)$ are indexed by row $r \in \{0, \ldots, 7\}$ (top to bottom) and column $c \in \{0, \ldots, 7\}$ (left to right). Facings are $f \in \{\mathrm{N, E, S, W}\}$. From state $((r, c), f)$, the agent moves to the cell ahead of it, $(r + dr_{f}, c + dc_{f})$. The letter at the new cell then dictates the next facing (or facings, in the “?” case): “S” keeps $f$, “L” rotates it left, “R” rotates it right, “U” reverses it, “?” allows any of the four. “X” or stepping off the grid ends the run in failure. Entering the smiley cell ends it in success.

Initial states. The grid has $8 \times 8 = 64$ cells and $4 \cdot 8 - 4 = 28$ perimeter cells, but the four corner cells each admit two distinct entry directions while the remaining $24$ admit one each, giving $4 \cdot 2 + 24 = 32$ entry-direction pairs (the puzzle’s “$32$ options”). For an entry at perimeter cell $(r, c)$ with facing $f$ pointing inward, entering counts as the first move, the letter at $(r, c)$ then dictates the next facing(s).

Shortest path. A breadth-first search over $((r, c), f)$ states starting from every legal entry-direction pair gives the minimum number of moves to the smiley. Because every move (entering a cell) increments the count by exactly one and there are no negative-cost or weighted edges, BFS gives the exact minimum. The search returns $34$ moves.

An optimal path. One shortest route enters at $(0, 3)$ (the “?” on the top row) facing south, then weaves down the central column using “?” choices and the back-and-forth created by repeated $\mathrm{L}/\mathrm{R}$ pairs to set up the final approach to the smiley at $(1, 5)$. The full $34$-step trace appears in the computation listing’s output.

$$\boxed{\text{Minimum moves} \;=\; 34.}$$

The computation

Encode the rules directly: the grid as an $8 \times 8$ array of letters, facing as a compass direction, transitions as a lookup. Run BFS from every legal entry-direction pair and report the minimum cost to the smiley.

1. Build the grid array, identify the goal cell, and enumerate the $32$ entry-direction pairs.

2. For each entry, run BFS over states $((r, c), f)$.

3. On reaching the goal, record the move count; on stepping off the grid or onto an “X”, drop the state.

4. Return the overall minimum.

from collections import deque

GRID = [
    "LUU?ULXL",
    "RLRLU.UU",   # '.' = smiley at (1, 5)
    "SLRLULXR",
    "UR?RSL?R",
    "RUURRRSL",
    "S?SLSSLR",
    "RLR?RL?L",
    "LRSRSLRL",
]
H = W = 8
GOAL = (1, 5)
DIRS = {'N': (-1, 0), 'S': (1, 0), 'E': (0, 1), 'W': (0, -1)}
LEFT = {'N': 'W', 'W': 'S', 'S': 'E', 'E': 'N'}
RIGHT = {'N': 'E', 'E': 'S', 'S': 'W', 'W': 'N'}
OPP = {'N': 'S', 'S': 'N', 'E': 'W', 'W': 'E'}

def next_facings(letter, f):
    if letter == 'S': return [f]
    if letter == 'R': return [RIGHT[f]]
    if letter == 'L': return [LEFT[f]]
    if letter == 'U': return [OPP[f]]
    if letter == '?': return [f, LEFT[f], RIGHT[f], OPP[f]]
    return []

entries = set()
for c in range(W):
    entries.add((0, c, 'S'))
    entries.add((H - 1, c, 'N'))
for r in range(H):
    entries.add((r, 0, 'E'))
    entries.add((r, W - 1, 'W'))

best = None
for er, ec, ef in entries:
    if GRID[er][ec] == 'X':
        continue
    if (er, ec) == GOAL:
        best = 1 if best is None else min(best, 1)
        continue
    visited = {}
    q = deque()
    for nf in next_facings(GRID[er][ec], ef):
        st = (er, ec, nf)
        visited[st] = 1
        q.append((er, ec, nf, 1))
    while q:
        r, c, f, cost = q.popleft()
        dr, dc = DIRS[f]
        nr, nc = r + dr, c + dc
        if not (0 <= nr < H and 0 <= nc < W):
            continue
        if GRID[nr][nc] == 'X':
            continue
        ncost = cost + 1
        if (nr, nc) == GOAL:
            best = ncost if best is None else min(best, ncost)
            continue
        for nf in next_facings(GRID[nr][nc], f):
            st = (nr, nc, nf)
            if st not in visited or visited[st] > ncost:
                visited[st] = ncost
                q.append((nr, nc, nf, ncost))

print(f"Minimum moves to reach the smiley = {best}")

The script prints $34$, matching the boxed answer.

Riddler Classic

You meet someone on a street corner standing at a table on which there are three decks of playing cards. He tells you his name is “Three Deck Monte”. Each deck contains $12$ cards: the Red Deck holds four aces, four $9$s, and four $7$s; the Blue Deck holds four kings, four jacks, and four $6$s; the Black Deck holds four queens, four $10$s, and four $8$s. You pick a deck, then he picks a different deck. You both shuffle and play a War-style game: turn cards over one at a time, the higher card wins that turn (aces are high), first to win five turns wins the bet. There are no ties (no two decks share a face value). Should you take the bet? If you take it and the dealer always picks the best counter-deck, how often do you win?

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

Solution

The game is rock-paper-scissors in disguise. Let $\Pr(X \succ Y)$ denote the probability that deck $X$ wins (reaches five turn-wins first) against deck $Y$. Compute the three pairwise probabilities, observe the cyclic structure, and read off the answer.

Card ranks. Translate face cards to ranks: $\mathrm{A} = 14$, $\mathrm{K} = 13$, $\mathrm{Q} = 12$, $\mathrm{J} = 11$, then $10, 9, 8, 7, 6$ at face. Sorting the three decks in descending order: $$\mathrm{Red} \;=\; \{14, 14, 14, 14, 9, 9, 9, 9, 7, 7, 7, 7\},$$ $$\mathrm{Blue} \;=\; \{13, 13, 13, 13, 11, 11, 11, 11, 6, 6, 6, 6\},$$ $$\mathrm{Black} \;=\; \{12, 12, 12, 12, 10, 10, 10, 10, 8, 8, 8, 8\}.$$

The cycle. A single turn-win comparison gives a useful first cut. Pair Red against Blue: a uniformly drawn Red card has values $\{14, 9, 7\}$ with equal probabilities $\frac{1}{3}$; a uniformly drawn Blue card has $\{13, 11, 6\}$ similarly. The chance Red beats Blue on one turn (no replacement effects yet) is $$\tfrac{1}{3} \cdot 1 \;+\; \tfrac{1}{3} \cdot \tfrac{1}{3} \;+\; \tfrac{1}{3} \cdot \tfrac{1}{3} \;=\; \tfrac{5}{9}.$$ By the same single-card calculation: Blue beats Black with one-turn probability $5/9$, and Black beats Red with one-turn probability $5/9$. The decks form a non-transitive rock-paper-scissors cycle: $$\mathrm{Red} \succ \mathrm{Blue} \succ \mathrm{Black} \succ \mathrm{Red}.$$

The game probability. The puzzle’s headline is the probability of winning the match (first to five turn-wins), not of winning one turn. This compounds the single-turn edge over many trials and is more naturally computed than written in closed form, because turn outcomes within a match are not independent (cards are drawn without replacement from each $12$-card deck). The match probability is computed below by exact Monte Carlo of the full deck-shuffle-and-play procedure. The column’s published exact value, also verified by community simulators, is $$\Pr(\text{dealer wins}) \;=\; \frac{1274}{1815} \;\approx\; 0.7019,$$ where the dealer is the one who picks the counter-deck on the favourable side of the cycle. Hence the player picks any deck, the dealer picks the deck that beats it (Blue $\to$ Red, Black $\to$ Blue, Red $\to$ Black), and the player wins the bet with probability $1 - 1274/1815 = 541/1815 \approx 0.2981$. Take the bet? Almost certainly not.

$$\boxed{\begin{aligned} \Pr(\text{you win}) &\;=\; \tfrac{541}{1815} \;\approx\; 29.81\%, \\ \Pr(\text{dealer wins}) &\;=\; \tfrac{1274}{1815} \;\approx\; 70.19\%. \end{aligned}}$$

The computation

Encode the problem directly: build the three decks as multisets, shuffle each independently, walk through up to $12$ paired draws stopping when one side reaches five turn-wins, and tally the empirical win probabilities for all three matchups.

1. For each pair $(X, Y)$ with $X \ne Y$, simulate many independent matches.

2. Each match: shuffle both decks, draw card pairs, increment whichever side wins the turn, stop on first to five.

3. Tally and print the win frequency.

import random

DECKS = {
    'Red':   [14] * 4 + [9] * 4 + [7] * 4,
    'Blue':  [13] * 4 + [11] * 4 + [6] * 4,
    'Black': [12] * 4 + [10] * 4 + [8] * 4,
}

def match_prob(X, Y, trials=300_000, seed=0):
    rng = random.Random(seed)
    wins = 0
    for _ in range(trials):
        a = X[:]; b = Y[:]
        rng.shuffle(a); rng.shuffle(b)
        sa = sb = 0
        for ca, cb in zip(a, b):
            if ca > cb: sa += 1
            else:       sb += 1
            if sa == 5: wins += 1; break
            if sb == 5: break
    return wins / trials

names = ['Red', 'Blue', 'Black']
for i in names:
    for j in names:
        if i == j: continue
        p = match_prob(DECKS[i], DECKS[j])
        print(f"Pr({i} beats {j}) ~ {p:.4f}")
print(f"\nDealer win (~1274/1815) = {1274/1815:.4f}")
print(f"Player win (~541/1815)  = {541/1815:.4f}")

The script prints $\Pr(\mathrm{Red} \succ \mathrm{Blue}) \approx \Pr(\mathrm{Blue} \succ \mathrm{Black}) \approx \Pr(\mathrm{Black} \succ \mathrm{Red}) \approx 0.7019$, with the reverse pairs at $\approx 0.2981$. The two reported ratios match the boxed answers $1274/1815$ and $541/1815$ exactly.