Meeting in the Middle Like a Cryptic Clue

Here is the thing about a cryptic clue that took me an embarrassing number of empty grids to understand: it is two clues welded together. A plain definition sits at one edge — never the middle — and a piece of wordplay reaches the same answer from the other direction. You know you are right when the two paths collide on one word. Setters call that the penny-drop. You are not solving one puzzle; you are running two searches and waiting for them to meet.

Which is Ira Pohl’s 1971 idea almost exactly. Ordinary breadth-first search fans out from the start and hopes to stumble onto the goal, exploring a balloon of nodes that grows like b^d. Pohl’s move: search forward from the start and backward from the goal at the same time, and stop the instant the two frontiers touch. Two balloons of radius d/2 are dramatically smaller than one of radius d — roughly 2·b^(d/2) instead of b^d. The whole win lives in that halved exponent.

function biBFS(adj: Map<string, string[]>, start: string, goal: string): boolean {
  if (start === goal) return true;
  let front = new Set([start]), back = new Set([goal]);
  const seen = new Set([start, goal]);
  while (front.size && back.size) {
    if (front.size > back.size) [front, back] = [back, front]; // grow the smaller side
    const next = new Set<string>();
    for (const node of front)
      for (const nbr of adj.get(node) ?? []) {
        if (back.has(nbr)) return true; // frontiers touch — the penny drops
        if (!seen.has(nbr)) { seen.add(nbr); next.add(nbr); }
      }
    front = next;
  }
  return false;
}

The same alternation in OCaml, swapping which frontier we expand each step:

let bi_bfs adj start goal =
  let expand f = List.sort_uniq compare (List.concat_map adj f) in
  let rec loop front back =
    if List.exists (fun n -> List.mem n back) front then true
    else match front with
      | [] -> false
      | _  -> loop back (expand front)   (* swap sides, grow the other end *)
  in
  loop [ start ] [ goal ]

The catch is the same one the crossword teaches. Meeting in the middle only works when you can walk backward from the goal — a cryptic gives you the answer’s edge (definition) and its interior (wordplay) so both walks are legal. In a graph you need reversible edges, and you need to actually check the intersection every step, or the two frontiers sail past each other and you have paid for two searches that never shake hands. My down-clues resisted all afternoon for want of exactly that: I kept expanding one frontier and forgot to test it against the other.