Can You Help Dakota Jones Raid The Lost Arc?

Riddler Express

A laser scanner records a three-dimensional “highly symmetric crystal” as a stack of two-dimensional cross-sections taken along one axis. The looping scan shows a cross-section that grows from a small equilateral triangle into a hexagon (a regular hexagon exactly halfway through), then shrinks back to an equilateral triangle. What three-dimensional shape is the crystal?

The Riddler, FiveThirtyEight, September 13, 2019(original post)

Solution

The triangle-to-hexagon-to-triangle signature is the giveaway: it is exactly what you see slicing a cube along its main diagonal. Stand a cube on one corner so its long diagonal is vertical, and sweep a horizontal plane up from the bottom corner. Near the bottom the plane cuts three faces, giving a growing equilateral triangle; once it passes the next three corners it cuts all six faces, giving a hexagon that is regular at the exact midpoint; then it shrinks to a triangle as it nears the top corner. $$\boxed{\text{A cube (sliced along its space diagonal).}}$$ More precisely, the same scan could come from any trigonal trapezohedron, a solid with six rhombic faces, of which the cube is the special case with square faces. But the simplest and intended answer is the cube.

The computation

Encode the slicing: take the unit cube, intersect the plane $x + y + z = t$ (perpendicular to the diagonal) with the cube’s edges, and report the cross-section’s number of sides, its area, and whether it is a regular hexagon. The sequence should be triangle, then hexagon (regular at the centre $t = 1.5$), then triangle.

import numpy as np
from itertools import combinations
verts = [(x, y, z) for x in (0, 1) for y in (0, 1) for z in (0, 1)]
edges = [(a, b) for a, b in combinations(verts, 2)
         if sum(abs(np.subtract(a, b))) == 1]
def section(t):
    pts = []
    for a, b in edges:
        sa, sb = sum(a) - t, sum(b) - t
        if sa * sb < 0:
            u = sa / (sa - sb)
            pts.append(tuple(np.add(a, np.multiply(u, np.subtract(b, a)))))
    uniq = []
    for p in pts:
        if not any(np.allclose(p, q) for q in uniq): uniq.append(p)
    c = np.mean(uniq, axis=0); n = np.array([1, 1, 1]) / np.sqrt(3)
    e1 = np.array([1, -1, 0]) / np.sqrt(2); e2 = np.cross(n, e1)
    ring = sorted(uniq, key=lambda p: np.arctan2(
        np.dot(np.subtract(p, c), e2), np.dot(np.subtract(p, c), e1)))
    sides = [np.linalg.norm(np.subtract(ring[i], ring[(i + 1) % len(ring)]))
             for i in range(len(ring))]
    return len(uniq), max(sides) - min(sides) < 1e-9

for t in (0.5, 1.0, 1.2, 1.5, 1.8, 2.0, 2.5):
    n, reg = section(t)
    print(f"t={t}: {n}-gon", "(regular hexagon)" if n == 6 and reg else "")
# t=0.5/1.0: 3-gon;  t=1.2/1.8: 6-gon
# t=1.5: 6-gon (regular hexagon);  t=2.0/2.5: 3-gon

The cross-section runs triangle $\to$ hexagon $\to$ triangle, regular hexagon at the midpoint, exactly the scanned animation: the crystal is a cube.

Riddler Classic

Find the longest string of letters in which (1) every pair of consecutive letters is a two-letter postal abbreviation for a state, territory, or freely associated state, and (2) no abbreviation is used more than once. For instance, GUTX works (GU, UT, TX); ALAK works (AL, LA, AK); ALAL does not (AL twice).

The Riddler, FiveThirtyEight, September 13, 2019(original post)

Solution

Turn the abbreviations into a graph: each of the $59$ codes is a directed edge from its first letter to its second. A valid string is then a trail, a walk that uses no edge twice, and its length in letters is one more than the number of edges. So the puzzle asks for the longest trail in this $26$-vertex directed graph. There is no tidy formula; a search settles it. $$\boxed{31 \text{ letters (}30 \text{ abbreviations)}}$$ One such string is FMPWVINVASDCTNMNCOHIALAKSCARIDE, running from FM (Federated States of Micronesia) to DE (Delaware). Many different strings reach $31$ (thousands, in fact), but none is longer.

The computation

Encode the abbreviations as directed edges and search exhaustively (depth-first over trails from every starting letter, never reusing an edge) for the longest one. The search confirms the maximum is $31$ letters.

from collections import defaultdict
ABBR = """AL AK AZ AR CA CO CT DE FL GA HI ID IL IN IA KS KY LA ME MD MA MI MN
MS MO MT NE NV NH NJ NM NY NC ND OH OK OR PA RI SC SD TN TX UT VT VA WA WV WI
WY DC AS GU MP PR VI FM MH PW""".split()
out = defaultdict(list)
for ab in ABBR: out[ab[0]].append((ab[1], ab))

best = [0, ""]
def dfs(node, used, path):
    if len(path) > best[0]: best[0], best[1] = len(path), path
    for nxt, ab in out[node]:
        if ab not in used:
            used.add(ab); dfs(nxt, used, path + nxt); used.discard(ab)
for s in sorted({ab[0] for ab in ABBR}):
    dfs(s, set(), s)
print("longest:", best[0], "letters,", best[0] - 1, "abbreviations")
print("example:", best[1])
# longest: 31 letters, 30 abbreviations
# example: FMNVALAKSCARIDCOHINCTNMPWVIASDE

The exhaustive search returns $31$ letters, $30$ abbreviations, confirming the maximum.