Chapter 232
I Would Walk 500 Miles And I Would Riddle 500 More
Riddler Express
A long walk passes through parts of nine contiguous states: from the eastern shore of Lake Tahoe (Nevada) southeast into Utah, through Four Corners into New Mexico, east into Oklahoma and on to Tulsa, east to Fayetteville, Arkansas, south to Shreveport, Louisiana, back north into Arkansas, into Missouri near Branson, up through Iowa past Des Moines, ending at the SPAM Museum in Austin, Minnesota. What do these nine states share that none of the other do?
The Riddler, FiveThirtyEight, June 21, 2019(original post)
Solution
Trace the route and the nine states are Nevada, Utah, New Mexico, Oklahoma, Arkansas, Louisiana, Missouri, Iowa, and Minnesota. The property is not geographic but lexical: these are exactly the states whose capital city has a name of more than one word. Their capitals are Carson City, Salt Lake City, Santa Fe, Oklahoma City, Little Rock, Baton Rouge, Jefferson City, Des Moines, and St. Paul. Every other state has a one-word capital (Phoenix, Boston, Denver, and so on).
The computation
Encode all fifty capitals and filter by word count. The states whose capital name splits into more than one word should be exactly the nine on the walk.
caps = {"Alabama":"Montgomery","Alaska":"Juneau","Arizona":"Phoenix",
"Arkansas":"Little Rock","California":"Sacramento","Colorado":"Denver",
"Connecticut":"Hartford","Delaware":"Dover","Florida":"Tallahassee",
"Georgia":"Atlanta","Hawaii":"Honolulu","Idaho":"Boise",
"Illinois":"Springfield","Indiana":"Indianapolis","Iowa":"Des Moines",
"Kansas":"Topeka","Kentucky":"Frankfort","Louisiana":"Baton Rouge",
"Maine":"Augusta","Maryland":"Annapolis","Massachusetts":"Boston",
"Michigan":"Lansing","Minnesota":"Saint Paul","Mississippi":"Jackson",
"Missouri":"Jefferson City","Montana":"Helena","Nebraska":"Lincoln",
"Nevada":"Carson City","New Hampshire":"Concord","New Jersey":"Trenton",
"New Mexico":"Santa Fe","New York":"Albany","North Carolina":"Raleigh",
"North Dakota":"Bismarck","Ohio":"Columbus","Oklahoma":"Oklahoma City",
"Oregon":"Salem","Pennsylvania":"Harrisburg","Rhode Island":"Providence",
"South Carolina":"Columbia","South Dakota":"Pierre","Tennessee":"Nashville",
"Texas":"Austin","Utah":"Salt Lake City","Vermont":"Montpelier",
"Virginia":"Richmond","Washington":"Olympia","West Virginia":"Charleston",
"Wisconsin":"Madison","Wyoming":"Cheyenne"}
multi = sorted(s for s, c in caps.items() if len(c.split()) > 1)
print(len(multi), "states:", multi)
# 9 states: ['Arkansas','Iowa','Louisiana','Minnesota','Missouri','Nevada',
# 'New Mexico','Oklahoma','Utah']Exactly nine states qualify, the nine on the walk.
Riddler Classic
A square table behind a curtain has a quarter on each corner. You want all four heads up; the instant they are, you are told and you win. You may name any set of corners to flip (“flip the top-left and bottom-right”), but after each command the table is spun to a random orientation you cannot see, then you command again. Is there a sequence of moves that guarantees all heads up in finitely many moves?
The Riddler, FiveThirtyEight, June 21, 2019(original post)
Solution
Yes, and in as few as fifteen moves. The random spin is what makes it possible: because you never know the orientation, two arrangements that are rotations of each other are indistinguishable to you, and that collapses the problem to a handful of states.
Six states, five moves. Up to rotation there are only six arrangements of heads and tails: all heads (the win), all tails, one head, one tail, two heads adjacent, and two heads diagonal. Likewise, the moves you can meaningfully make are only five: flip one corner, flip two adjacent, flip two diagonal, flip three, flip all four. Since you cannot tell the orientation, naming specific corners is the same as choosing one of these five move-types and letting the unknown spin decide how it lands.
The flip-four trick. Before any other move, flip all four. If the table happened to be all tails, this wins. Doing it between every move lets you test for “all tails” for free at each step, so you only have to march the remaining states into all-tails-or-all-heads. Interleaving “flip all” with diagonal, adjacent, and single flips drives every possible state through the winning arrangement. One sequence that works (writing the five move-types as , for two diagonal, for two adjacent, for single) is fifteen moves, symmetric about the central single flip.
The computation
Encode the puzzle two ways and check they agree. First, search at the level of belief: track the set of rotation-classes the table might be in (never having been told you won), and breadth-first search for the shortest move-sequence that drives this set empty, meaning every possibility has been forced through all-heads. Second, an independent brute-force adversary check: take the sequence found and, over every starting arrangement, let an adversary choose the worst spin at each step; confirm that no arrangement can avoid all-heads for the whole sequence.
Represent a configuration as four bits; a rotation cycles the bits; a class is the smallest value over the four rotations.
A move applied under an unknown spin sends a class to the set of classes reachable by the move at any orientation.
BFS over belief-sets (subsets of the five non-winning classes) to empty; then verify by a worst-case-adversary replay over all sixteen starting configurations.
from collections import deque
WIN = 0b1111
def rot(c, r): return ((c << r) | (c >> (4 - r))) & 0b1111
def cls(c): return min(rot(c, r) for r in range(4))
NONWIN = [x for x in {cls(c) for c in range(16)} if x != cls(WIN)]
MOVES = {"F4":0b1111, "D":0b0101, "A":0b0011, "S":0b0001, "F3":0b0111}
def step(B, mask): # belief update under unknown spin
nb = set()
for X in B:
nb |= {cls(X ^ rot(mask, r)) for r in range(4)}
nb.discard(cls(WIN))
return frozenset(nb)
start = frozenset(NONWIN); q = deque([(start, [])]); seen = {start}; ans = None
while q:
B, path = q.popleft()
if not B: ans = path; break
for name, mask in MOVES.items():
nb = step(B, mask)
if nb not in seen:
seen.add(nb); q.append((nb, path + [name]))
print("guaranteed win in", len(ans), "moves:", " ".join(ans))
def adversary_survivors(seq): # worst-case spin tries to dodge the win
alive = set(range(16)) - {WIN}
for name in seq:
m = MOVES[name]; nxt = set()
for c in alive:
outs = [c ^ rot(m, r) for r in range(4)]
nxt |= {o for o in outs if o != WIN} # stay alive if some spin dodges
alive = nxt
return len(alive)
print("configs the adversary can keep alive:", adversary_survivors(ans))
# guaranteed win in 15 moves: F4 D F4 A F4 D F4 S F4 D F4 A F4 D F4
# configs the adversary can keep alive: 0The breadth-first search returns a -move sequence (and is minimal, since no shorter belief-path reaches the empty set), and the independent adversary replay confirms that not a single starting arrangement can dodge all-heads through the whole sequence.