How Fast Can You Type A Million Letters?

Riddler Express

$N$ people need to use a row of $M$ urinals. They obey a fixed rule: the first person picks one of the two ends; each subsequent person picks the unoccupied urinal that maximises the distance to the nearest already-occupied one. Anyone who would be forced into a urinal adjacent to an occupied one simply leaves. What is the minimum $M$ that accommodates all $N$ people at the same time?

The Riddler, FiveThirtyEight, April 27, 2018(original post)

Solution

Why the naive answer is wrong. If the goal were to seat $N$ people non-adjacently, $M = 2N - 1$ urinals always suffice (the alternating pattern XOXOX$\ldots$X). But the rule of play is not "any non-adjacent placement"; it is the strict greedy distance-maximiser. That rule can leave gaps that nobody is willing to use, so the minimum $M$ that the greedy process actually fills is generally larger than $2N - 1$.

What the greedy rule does on a row of $M$ urinals. The first two people take the two ends. After that, every choice splits the longest current empty gap by adding a person in its middle. A gap of length $g$ (the number of empty urinals strictly between two occupied positions) becomes two sub-gaps of lengths $\lfloor (g - 1)/2 \rfloor$ and $\lceil (g - 1)/2 \rceil$ when a person sits at the most central allowed slot. A gap of length $0$ or $1$ is dead (no person will sit there because that would be adjacent to an existing user).

So the question reduces to: starting with one gap of length $M - 2$ between the two end-takers, how many extra people can we seat by repeatedly splitting the largest live gap (length $\ge 2$) into two halves?

Powers-of-two arithmetic. Splitting a gap of length $g \ge 2$ uses one person and produces two sub-gaps of lengths whose sizes are determined by $g$. The cleanest case is when $M - 2 = 2^k$ for some $k \ge 1$: the splitting is binary, every internal vertex of a complete binary tree on $2^k$ leaves seats one person, and the total number of seated people is exactly $1 + 2^k$ end-takers plus the binary-tree count $2^k - 1$, giving $N = 1 + 2^k$ for $M = 2 + 2^k$. So when $N - 1$ is a power of two, the minimum $M$ is exactly $M = N + (N - 1) = 2N - 1$.

For other $N$, the central gap $M - 2$ has to be at least $2^{\lceil \log_2(N - 1) \rceil}$: anything smaller cannot be split into $N - 2$ non-dead pieces by the greedy rule. And taking $M - 2 = 2^{\lceil \log_2(N - 1) \rceil}$ is enough (the splitter never gets stuck in this regime). Therefore $$\boxed{\,M(N) \;=\; N + 2^{\lceil \log_2(N - 1) \rceil} \qquad \text{for } N \ge 2,\,}$$ with $M(1) = 1$.

Reading the formula. For $N = 4$ the formula gives $4 + 4 = 8$, matching the official’s worked example ($N = 4$ does not fit in $7$; it needs $8$). For $N$ at $2^k + 1$ the formula matches the tight $2N - 1$; for $N$ just above such a power of two the bound jumps to $3N - 4$, exactly the loose case where the greedy is most wasteful.

The computation

Encode the greedy rule directly, sweep $M$ upward, and read off the minimum $M$ that seats all $N$ people.

1. Start with the two ends occupied.

2. Repeatedly choose the unoccupied position whose distance to the nearest occupied position is largest, ties broken arbitrarily, and place a person there.

3. Stop when the best achievable distance drops to $1$; that count is the number of people the greedy process seats.

import math

def seated(M):
    if M <= 0: return 0
    if M == 1: return 1
    occ = [False] * M
    occ[0] = occ[-1] = True
    count = 2
    while True:
        best_d, best_i = -1, -1
        for i in range(M):
            if occ[i]: continue
            d = min(abs(i - j) for j in range(M) if occ[j])
            if d > best_d:
                best_d, best_i = d, i
        if best_d <= 1:
            return count
        occ[best_i] = True
        count += 1

def min_M(N):
    M = 1
    while seated(M) < N:
        M += 1
    return M

for N in range(2, 13):
    formula = N + 2 ** math.ceil(math.log2(N - 1)) if N >= 2 else 1
    print(f"N={N:2d}: min M = {min_M(N):2d}, formula = {formula}")

The two columns match for every $N$ in the sweep, confirming the boxed expression.

Riddler Classic

What is the fastest way to fill a text editor with one million $\mathtt{i}$ characters, given these mechanics: tapping a single key produces one character at $5$ per second; holding a key produces one character on the first press, waits a $0.5$ second repeat delay, then repeats at $30$ characters per second; the keystrokes Ctrl-A, Ctrl-C, right-arrow, Ctrl-V take a combined $1$ second from key release to the depress of Ctrl-V and select, copy, and paste the entire buffer; and holding Ctrl-V repeats at the same key rate. How big should the initial buffer be, and how many copy-paste cycles should follow?

The Riddler, FiveThirtyEight, April 27, 2018(original post)

Solution

The two primitives. Let $L$ denote the current buffer length. The two actions are:

• Holding the $\mathtt{i}$ key for $t$ seconds (with $t \ge 0.5$) appends $30 t - 14$ characters to the buffer: one character on the press, then $30(t - 0.5)$ more after the half-second delay.

• Doing a select-copy-paste cycle followed by holding Ctrl-V for $p$ seconds (with $p \ge 0.5$) multiplies the buffer by $30 p - 13$: a $1$-second fixed overhead from key release to the first paste, the first paste adds one copy, and then $30(p - 0.5)$ more held pastes add that many further copies. So the buffer goes from $L$ to $L \cdot (30 p - 13)$ in time $1 + p$.

The optimisation. A clean policy holds the $\mathtt{i}$ key once for $t_0$ seconds (producing $L_0 = 30 t_0 - 14$), then performs $k$ identical copy-paste rounds each multiplying the buffer by $m = 30 p - 13$ in time $1 + p$. The final length is $L_0 \cdot m^{k}$ and the total time is $t_0 + k(1 + p)$. Set $L_0 \cdot m^{k} = 10^{6}$.

The per-round log growth rate is $\ln(30 p - 13) / (1 + p)$. Maximising over $p$ by differentiating, $$\frac{30}{30 p - 13} \;=\; \frac{\ln(30 p - 13)}{1 + p},$$ which has a unique solution at $p^* \approx 1.134$ seconds, where $m^* = 30 p^* - 13 \approx 21.02$ and the log-rate is $\approx 1.427$ per second. For an integer number of paste rounds, minimising $t_0 + k(1 + p)$ subject to the length constraint gives the optimum $$k = 4, \quad p \approx 0.962 \text{ s}, \quad t_0 \approx 1.00 \text{ s}, \quad L_0 \approx 16,$$ $$\text{total time} \approx 8.84 \text{ seconds}.$$ Allowing continuous $k$ shaves the bound to $\approx 8.71$ seconds; the discrete-round optimum sits a sixth of a second above it. The published winning Riddler entry (Joseph Lombardo) lands on $8.86$ seconds, matching the four-round optimum to the second decimal.

The structure. Both pieces (hold-then-paste-then-paste) obey the same arithmetic. Each copy-paste round costs $\ln(30 p - 13) / (1 + p)$ characters per second in log terms, so the policy is "hold long enough to bootstrap, then paste in identical optimised rounds". The optimum is insensitive to small changes in $p$ near $p^*$; the curve is flat enough that any human-execution rate near one second per round gets within tenths of a second of the bound.

(The published column notes that solvers using tools outside the stated mechanics, such as Emacs’s prefix argument or Vim macros, did the task in five seconds or fewer. The numbers above answer the puzzle as posed, with the named keystroke primitives.)

The computation

Solve the optimisation directly. For each integer round count $k$, find the paste duration $p$ that minimises total time subject to $L_0 \cdot (30 p - 13)^{k} = 10^{6}$.

1. For each $k$ in a small sweep, define total time $t_0 + k(1 + p)$ where $t_0 = (L_0 + 14)/30$ and $L_0 = 10^{6} / (30 p - 13)^{k}$.

2. Minimise over $p \in [0.5, 5]$ by a one-dimensional search.

3. Return the best $(k, p, t_0)$ triple.

import numpy as np

def time_for(k, p):
    m = 30 * p - 13
    if m <= 1: return float("inf")
    L0 = 1e6 / m ** k
    if L0 < 1: return float("inf")
    t0 = max(0.5, (L0 + 14) / 30)
    return t0 + k * (1 + p)

ps = np.linspace(0.5, 3, 2501)
best = (float("inf"), None, None, None)
for k in range(1, 12):
    vals = [time_for(k, p) for p in ps]
    i = int(np.argmin(vals))
    if vals[i] < best[0]:
        m = 30 * ps[i] - 13
        L0 = 1e6 / m ** k
        best = (vals[i], k, ps[i], L0)

print(
    f"optimum: total = {best[0]:.3f} s, "
    f"k = {best[1]}, p = {best[2]:.3f} s, L0 = {best[3]:.1f}"
)

The script prints total $\approx 8.841$ seconds at $k = 4$, $p \approx 0.961$ seconds, $L_0 \approx 15.6$, reproducing the boxed policy.