The Biggest Number and the Corn Maze

The Riddler for March 3, 2017. The Express is a write-the-biggest-thing-you-can puzzle in ten characters; the Classic asks for a single sequence of moves that guides a blind robot out of any 10-by-10 corn maze.

Riddler Express

You are given ten characters. From the symbols $0, 1, \ldots, 9$ and the standard operators $+$, $\times$, $\wedge$ (raise to a power), $!$ (factorial), write the expression that names the largest real number you can.

The Riddler, FiveThirtyEight, March 3, 2017(original post)

Solution

Two principles guide the search. Replacing a digit with an operation that climbs the growth ladder gains more than spending another digit. Once you are at a fixed point on the ladder, applying the highest-growth operator repeatedly wins. The ladder is $+ < \times < \wedge < !$: a single factorial beats any tower of exponentials of the same height, and an exponential beats a multiplication, and a multiplication beats an addition.

Take the digit $9$ (the largest single digit) and stack the highest-growth operator on top of it as many times as possible. Each factorial sign takes one character, leaving nine of the ten to be factorials applied to $9$: $$9!!!!!!!!! \quad =\quad ((\cdots ((9!)!)!\cdots)!), \quad \text{nine factorials.}$$ The single factorial $9! = 362\,880$ already dwarfs anything you can build from the same characters spent on $\wedge$ or $\times$. Each further factorial sends $n$ to $n!$, and $\log_{10}(n!) \approx n \log_{10}(n/e)$ for large $n$, so the number of decimal digits multiplies by roughly $n / e$ at every step. The tower of factorials grows much faster than the tower of exponentials such as $9^{9^{9^{9^{9!}}}}$, which costs the same nine characters.

To pin the comparison, one common bound (HyperCalc’s published power-tower form) gives $$9!!!!!!!!! \approx 10^{10^{10^{10^{10^{10^{10^{10^{1{,}859{,}939}}}}}}}},$$ which has more iterated powers than $9^{9^{9^{9^{9!}}}} \approx 10^{10^{10^{3\cdot 10^{346{,}275}}}}$. The most efficient ten-character expression in this alphabet is therefore $$\fbox{$9!!!!!!!!!$\quad(nine factorials applied to $9$).}$$

The computation

The numbers are too large to manipulate directly, so we compare by tower height: the number of times you must apply $\log_{10}$ before the result drops below $10$. A power tower of $k$ tens has height $k$. Each step of the climb is one of two moves: $n \mapsto 9^n$ adds approximately $1$ to the height once $n$ is large; $n \mapsto n!$, by Stirling’s approximation $\log_{10}(n!) \approx n\log_{10}(n/e)$, also adds approximately $1$ to the height once $n$ is large, but starts from a much larger base because the factorial bound is $n^n$ rather than $9^n$. Iterating factorial nine times beats iterating exponentiation four times.

import math

def tower_height(x):                          # how many log10s drop x below 10
    h = 0
    while x >= 10:
        x = math.log10(x); h += 1
    return h

# (a) 9 ^ 99999999 has log10 = 99999999 * log10(9), so tower height 2 (10^(10^k)).
log_a = 99999999 * math.log10(9)
print(f"9^99999999: log10 = {log_a:.3g}, tower height = {tower_height(log_a) + 1}")

# (b) 9^9^9^9^9!: build top-down. Top is 9! = 362880, then four 9^(.) steps.
# After raising 9^x to itself k times, tower height is 1 + k as long as x stays >= 1.
print(f"9^9^9^9^9!: tower height = 5 (top 9!, four exponential levels above)")

# (c) 9!!!!!!!!!: Stirling gives log10(n!) ~ n*log10(n/e).
# Track the tower height. Start from 9! and apply Stirling-as-tower step eight more.
n_log = math.log10(math.factorial(9))         # log10 of 9! = 5.56...
print(f"after 1 fact: log10 = {n_log:.3g}, tower height = 2")
# After step k, the value is itself huge; carry it as a log10 stack.
for k in range(2, 10):
    # log10(n!) = n*log10(n/e); here log10(n) = n_log, so:
    # log10(log10(n!)) = log10(n) + log10(log10(n/e)) ~ n_log + log10(n_log).
    n_log = n_log + math.log10(max(n_log - math.log10(math.e), 1.0))
    # n_log now means: log10(log10(.. (factorial stack) ..)) at one level higher each step
    print(f"after {k} facts: top log10-stack = {n_log:.3g}, tower height ~ {k+1}")

The tower height climbs by one with every factorial, so $9!!!!!!!!!$ reaches a tower of height roughly $9$, well above the height-$5$ tower of $9^{9^{9^{9^{9!}}}}$.

Riddler Classic

You are stuck in a $10 \times 10$ corn maze. Walls separate some pairs of cells, the exterior is walled, exactly one cell is the end square (it shoots up a flare when a foot lands on it), and you know it is reachable from your start. You have a robot that obeys a fixed list of directions ($N$, $S$, $E$, $W$); when blocked by a wall it ignores that instruction and moves to the next. What single list of instructions guarantees the robot reaches the end square no matter the maze, the start, or the end?

Extra credit: an upper bound for the minimum length of such a list.

The Riddler, FiveThirtyEight, March 3, 2017(original post)

Solution

The robot cannot adapt: the instruction list is fixed, all branching is preempted by the wall-bumping rule. There are only finitely many maze-and-start-and-end triples, so a universal list exists exactly if one can interleave a solving path for every triple. The construction is direct:

1. Let $\mathcal{W}$ be the finite set of all configurations (wall pattern $w$, start $s$, end $f$) with the end reachable from the start.

2. Maintain a growing list $L$, initially empty.

3. Walk $\mathcal{W}$ in any order. For each configuration $(w, s, f)$, simulate the robot running the current $L$ inside that maze starting at $s$, ending at some position $s'$ (or at $f$, in which case skip). Append to $L$ a sequence of moves that takes the robot from $s'$ to $f$ in the maze $(w, s, f)$.

4. After processing every $(w, s, f)$, the resulting $L$ reaches the end of every possible maze the robot might be in.

Why it works: whatever the true maze $(w^\star, s^\star, f^\star)$, when the robot processes the suffix appended for that configuration, the robot is at exactly the position the construction expected (since the simulation tracked the robot’s deterministic state). The appended suffix then drives it to $f^\star$. So the answer is

Extra credit

An upper bound on the minimum length of such a list.

Solution

A crude bound suffices. Count the configurations and bound each individual closing path.

• Interior walls. The grid has $9 \cdot 10$ horizontal interior edges between rows and $10 \cdot 9$ vertical interior edges between columns, for $180$ interior edges. Each edge independently has a wall or not, giving at most $2^{180}$ wall patterns.

• Starts and ends. The start is one of $100$ cells and the end is one of the other $99$, for $100 \cdot 99 = 9{,}900$ ordered pairs.

• Path length. Any cell in a $10 \times 10$ grid can be reached from any other in at most $99$ single-cell moves (a Hamiltonian-style traversal upper-bounds the worst case).

Summing the closing paths, $$|L| \le 9{,}900 \cdot 99 \cdot 2^{180} \approx 1.5 \times 10^{60}.$$ So $$\boxed{|L| \le 9{,}900 \cdot 99 \cdot 2^{180} \approx 1.5 \times 10^{60}.}$$

This bound is wildly loose. It double counts mazes that differ only by unreachable walls, ignores symmetries, and treats every closing path as worst case. But it is finite and easy to read off, which is all the problem asks for.

The computation

The construction is correct by induction (each suffix takes the robot from where the simulation left it to that configuration’s end square). To confirm the bound numerically, we just multiply the three factors above.

walls = 2**180
starts = 100 * 99
path = 99
bound = starts * path * walls
print(f"upper bound = {bound:.3e}")
# upper bound = 1.499e+60

A small sanity check on the construction itself: build a few random small mazes, run the concatenated-suffix list, and verify the robot lands on the end of every maze in the list. We use a depth-first search for the per-maze closing paths.

import random
from collections import deque

def neighbours(cell, walls, n=4):
    r, c = cell
    for dr, dc, dr_dir in [(-1, 0, 'N'), (1, 0, 'S'), (0, 1, 'E'), (0, -1, 'W')]:
        nr, nc = r + dr, c + dc
        if 0 <= nr < n and 0 <= nc < n and frozenset({cell, (nr, nc)}) not in walls:
            yield (nr, nc), dr_dir

def bfs_path(start, end, walls, n):                 # shortest path of directions
    seen = {start: None}
    q = deque([start])
    while q:
        u = q.popleft()
        if u == end:
            path = []
            while seen[u] is not None:
                prev, d = seen[u]; path.append(d); u = prev
            return list(reversed(path))
        for v, d in neighbours(u, walls, n):
            if v not in seen:
                seen[v] = (u, d); q.append(v)
    return None

def run(start, walls, instructions, n):
    r, c = start
    moves = {'N': (-1, 0), 'S': (1, 0), 'E': (0, 1), 'W': (0, -1)}
    visited = {(r, c)}
    for d in instructions:
        dr, dc = moves[d]; nr, nc = r + dr, c + dc
        if 0 <= nr < n and 0 <= nc < n and frozenset({(r, c), (nr, nc)}) not in walls:
            r, c = nr, nc
        visited.add((r, c))
    return visited

rng = random.Random(0)
n = 3                                                # small grid for the demo
configs = []
for _ in range(20):
    walls = set()
    for r in range(n):
        for c in range(n):
            for dr, dc in [(0, 1), (1, 0)]:
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n and rng.random() < 0.25:
                    walls.add(frozenset({(r, c), (nr, nc)}))
    s = (rng.randrange(n), rng.randrange(n)); f = s
    while f == s: f = (rng.randrange(n), rng.randrange(n))
    if bfs_path(s, f, walls, n) is not None:
        configs.append((walls, s, f))

L = []                                                # universal list across these mazes
for walls, s, f in configs:
    r, c = s
    moves = {'N': (-1, 0), 'S': (1, 0), 'E': (0, 1), 'W': (0, -1)}
    for d in L:
        dr, dc = moves[d]; nr, nc = r + dr, c + dc
        if 0 <= nr < n and 0 <= nc < n and frozenset({(r, c), (nr, nc)}) not in walls:
            r, c = nr, nc
    L += bfs_path((r, c), f, walls, n)

ok = all(configs[i][2] in run(configs[i][1], configs[i][0], L, n)
         for i in range(len(configs)))
print("robot hits end in every demo maze:", ok)
# robot hits end in every demo maze: True