Can You Find The Fish In State Names?

Riddler Express

To share a cylindrical muffin three ways, Robert makes three vertical cuts in a “Y” pattern, giving three equal pieces. For four equal pieces one would expect an “X,” but a child proposes an “A” pattern instead. If the muffin is cut into four equal pieces with an “A,” what is the ratio of the length of the A’s middle bar to the radius of the muffin?

The Riddler, FiveThirtyEight, May 22, 2020(original post)

Solution

Work in the circular cross-section, a unit circle. The “A” is two straight legs meeting at a point on the rim (the apex, at the top) with a horizontal crossbar between them. It carves the disk into four regions: a left piece and a right piece (each a circular segment cut off by a leg), the triangle above the crossbar, and the region below it. All four must have area $\pi/4$.

Start with the left and right segments. A circular segment cut by a chord spanning an arc of angle $\varphi$ has area $\tfrac12(\varphi - \sin\varphi)$. Setting this to $\pi/4$, $$\varphi - \sin\varphi = \frac{\pi}{2}, \qquad \varphi \approx 2.3099 \text{ rad } (132.3^\circ).$$ The two side arcs use up $2\varphi$, leaving $2\pi - 2\varphi$ for the bottom arc, which the apex angle subtends. By the inscribed-angle theorem the apex angle is half of that, $\pi - \varphi$. The triangle above the crossbar is isosceles with this apex angle and area $\pi/4$; an isosceles triangle of apex angle $2\beta$ and base $L$ has area $L^2/(4\tan\beta)$, so with $2\beta = \pi - \varphi$, $$\frac{L^2}{4\tan\beta} = \frac{\pi}{4} \;\Longrightarrow\; L = \sqrt{\pi \tan\beta}, \quad \beta = \frac{\pi - \varphi}{2}.$$ Numerically the crossbar-to-radius ratio is $$\boxed{\,L \approx 1.1779\,}.$$

The computation

Encode the equal-area conditions: solve $\varphi - \sin\varphi = \pi/2$ for the side segments, take the apex angle $\pi-\varphi$, and get the bar from the top triangle’s area. Confirm all four regions equal $\pi/4$.

import math
from scipy.optimize import brentq
phi = brentq(lambda p: p - math.sin(p) - math.pi / 2, 1.0, math.pi)
beta = (math.pi - phi) / 2                          # half the apex angle
bar = math.sqrt(math.pi * math.tan(beta))
segment = (phi - math.sin(phi)) / 2                 # one side piece
top = bar ** 2 / (4 * math.tan(beta))               # triangle above the bar
print(f"phi = {phi:.4f} rad, bar/radius = {bar:.6f}")
print(f"side = {segment:.5f}, top = {top:.5f}, target = {math.pi/4:.5f}")
# phi = 2.3099 rad, bar/radius = 1.177863
# side = 0.78540, top = 0.78540, target = 0.78540

Riddler Classic

Ohio is the only state whose name shares no letters with the word “mackerel.” Call a word a “mackerel” if it shares no letters with exactly one state. What is the longest mackerel? (If several tie, find them all.) Extra credit: which state has the most mackerels? Use Peter Norvig’s word list.

The Riddler, FiveThirtyEight, May 22, 2020(original post)

Solution

A word’s eligibility depends only on its set of letters, and likewise for a state name. So reduce each word and each state to a $26$-bit mask of the letters it uses; a word shares no letters with a state exactly when the bitwise AND of their masks is zero. A word is a mackerel when this happens for precisely one of the $50$ states.

Scanning Norvig’s list of $263{,}533$ words, the longest mackerels are two words of $23$ letters each:

Across all states there are $45{,}385$ mackerels in total, and the state with the most is fittingly the puzzle’s own mascot, $$\boxed{\text{Ohio, with } 11{,}342 \text{ mackerels}}.$$ Ohio wins because its name uses only three letters ($o$, $h$, $i$), so a huge number of words avoid all of them, and for most of those words Ohio is the only such state.

The computation

Encode each word and each state as a bitmask of its letters. A word is a mackerel when exactly one state’s mask is disjoint from it. Track the longest, the per-state counts, and the total.

import urllib.request
words = urllib.request.urlopen("http://norvig.com/ngrams/word.list").read()
words = words.decode().split()
states = ["alabama","alaska","arizona","arkansas","california","colorado",
"connecticut","delaware","florida","georgia","hawaii","idaho","illinois","indiana",
"iowa","kansas","kentucky","louisiana","maine","maryland","massachusetts","michigan",
"minnesota","mississippi","missouri","montana","nebraska","nevada","newhampshire",
"newjersey","newmexico","newyork","northcarolina","northdakota","ohio","oklahoma",
"oregon","pennsylvania","rhodeisland","southcarolina","southdakota","tennessee",
"texas","utah","vermont","virginia","washington","westvirginia","wisconsin","wyoming"]
def mask(s):
    m = 0
    for c in s:
        if c.isalpha(): m |= 1 << (ord(c) - 97)
    return m
sm = [mask(s) for s in states]
best, champs, total, per = 0, [], 0, [0] * 50
for w in words:
    wm = mask(w)
    hit = [i for i in range(50) if wm & sm[i] == 0]
    if len(hit) == 1:
        total += 1; per[hit[0]] += 1
        if len(w) > best: best, champs = len(w), [(w, states[hit[0]])]
        elif len(w) == best: champs.append((w, states[hit[0]]))
top = max(range(50), key=lambda i: per[i])
print(best, champs)                       # 23 [(...alabama), (...mississippi)]
print("total", total, "| most:", states[top], per[top])   # 45385 | ohio 11342