I recently played the Categories Game with a group of friends. You know the one: each person in the circle says a word in the category, starting with the last letter of the previous word. cat leads to tarantula, then to anteater, and so on. And of course, if you repeat a word then you lose. Here, every category is a hypernym: a category a word belongs to. A dog is an animal, alongside pigeons and leopards. With fungi and plants, an animal is likewise a living being. Pretending for a moment that a word belongs to only one category, we can build a hierarchical tree of all words.
Well, almost all words. Here I restrict myself to nouns from the WordNet dataset. They have a single root at entity, which splits into 45,905 physical entities and 36,200 abstractions. These count meanings, which WordNet calls synsets. Keeping only the single words in everyday use that name them leaves 40,117 words to play.
Playing to Win
If you’re allergic to fun and you want to kill the vibes as quickly as possible, how can you be sure to win? Many categories have dead-end words that force an end to the game immediately. Take plantain in the vegetables category. No vegetables start with an n1, so playing it forces the next person to lose. That’ll show them.
The widget above finds the longest chain in a category and, after each word, how many more words perfect play can still reach. Most words leave the next player a reply, so a sure win means looking ahead through every reply and every reply to those. Imagine we treat each word as a node in a graph, with an edge to every word that can follow it. Players take turns moving along an edge to an unvisited node, and whoever cannot move loses. This game is generalised geography, proven PSPACE-complete in 1978 by Thomas Schaefer2. PSPACE (polynomial space) is a class considered to be harder than NP (nondeterministic polynomial time), so I gave up on winning.
A Graph of Letters
Suppose instead you’re a more cooperative sort of group, and you want to keep the game going for as long as possible. The longest game is the longest path through the word graph. In a perfect world, that path would pass through every word once, creating a Hamiltonian path. But this is extremely unlikely, as the connections between words are usually too limited to allow it. So we want to solve the longest path problem instead, a generalisation of the Hamiltonian path problem. This turns out to be NP-hard, so the best known algorithms take exponential time in the worst case. With 40,117 words in play, this is not tractable.
We can reframe the problem. Instead of a node for each word, why don’t we use the fact that there are only 26 letters in the Latin alphabet? Consider a multi-graph with 26 nodes, one for each letter, and an edge for each word. For example, octopus creates a directed edge from o to s. Two words that open and close on the same letters are interchangeable, since either can stand in for the other anywhere in a chain. So between two letters, all we care about is the number of edges.
It also changes the question. A chain plays each word once, so on the letter graph it is a trail: a route that uses each directed edge at most once. A trail that uses every edge is an Eulerian trail. Euler’s condition for such a trail has two parts. First, every letter must have as many words coming in as going out, bar the two ends of the trail. Second, the words must all be joined up. The first part can be solved in polynomial time, and takes up most of this article. The second comes at the end, where it turns a few of the answers into upper bounds.
In the widget below, each letter sits on the rim. The more words run between two letters, the wider the edge between them is. Selecting a letter shows how many words start and end on it.
Balancing with Flow
The word graph falls well short of the first part of Euler’s condition. Many letters have far more words in than out, or the reverse — consider that many more words end with y than begin with it. Letters with more outgoing words have a surplus, and letters with more incoming have a deficit. Resolving these discrepancies means discarding words. To keep the most words in the chain, we must discard the fewest to leave every letter balanced. This is a question about flow.
If every letter is balanced then the chain must be a loop, ending on the letter it begins with. Our strategy is to solve for the longest loop first, then relax it to let the ends differ. To find it, we build a network. Every pair of letters with words running from one to the other gets one word edge, whose capacity is the number of words running from the first letter to the second and whose cost is 1. Two more nodes complete the network, a super-source that feeds every letter in surplus and a super-sink that drains every letter in deficit. Each of their edges has a capacity equal to the letter’s surplus or deficit, and a cost of 0.
Discarding a word from to lowers ’s surplus by one and ’s deficit by one. So pushing one unit of flow from a surplus letter to a deficit letter discards exactly the words on its path. Every letter in the middle of the path stays as balanced as it was. The cheapest way to push all of the surplus from to is therefore the set of discards that keeps the most words. This makes the whole thing a minimum-cost transshipment, a special case of min-cost flow. The figure below shows it on four words from the plant category, aloe, erica, vine and almond, with the surplus letters (a and v) drawn on the left and the deficit letters (e and d) on the right.
We solve it by successive shortest paths. Each round searches the residual graph, the network as it stands after the flow pushed so far, for the cheapest path from to . It then pushes as much surplus along that path as the path allows, and the rounds repeat until no surplus is left. Pushing a unit of flow along an edge takes one unit from its capacity and adds one to an edge running the other way, at the opposite cost. So a letter pair has up to two edges in the residual graph: a +1 edge means another word of that pair can still be discarded, and a −1 edge running the other way means a discard can be taken back. Because of the negative edges, each round searches with the shortest path faster algorithm (SPFA), a queue-based variant of Bellman–Ford.
Those negative edges matter because the first path the solve picks can be the wrong one. All three paths open to the first round cost 1. If it balances a and e by dropping aloe, aloe becomes a −1 edge from e back to a, and v is stranded with a unit still to send to d. On +1 edges alone, the cheapest way there is v → e → a → d, which discards three more words, vine, erica and almond, and leaves nothing to play. Round 2 instead takes the hop from e to a backwards along aloe’s −1 edge. The path discards vine and almond, leaving −1 edges in their place, and restores aloe, for a net cost of one. Every edge out of and into is then full, so no surplus is left and the solve stops. The figure below draws the graph after round 1, with the path that round 2 takes.
The same solve scales to a full category. Over the 40,117 words of entity it takes 220 paths, and 37 of them carry −1 edges. The letters start 15,883 words out of balance, and closing the loop costs 19,919 discards. The two numbers differ because a unit routed through intermediate letters pays a discard on every +1 edge it crosses.
The widget below plays that solve. Surplus letters bank down the left column and deficit letters down the right, and each path crosses between them as a band as wide as the surplus it moves. A −1 edge is drawn as a line segment running backwards.
Chains with Two Ends
A chain whose first and last letters differ needs one more step. A phantom word from the ending letter back to the opening letter would close the chain into a loop, adding one unit of surplus at the ending letter and one of deficit at the opening letter. The cheapest way to move that unit is a shortest path from the ending letter to the opening one, through the residual graph the balanced solve left behind. A chain’s cost is therefore the balanced cost plus the cost of that path. Because the residual graph carries −1 edges, that cost can be negative; in this case the chain keeps more words than the loop.
Four letters give twelve ordered pairs. No word in the example opens on d or ends on v, so five have no chain, leaving seven combinations as well as the balanced loop at a → a. The chain a → d keeps three words where the loop keeps two, because its path from d back to a runs along almond’s −1 edge and takes that discard back.
Dijkstra’s algorithm is the usual tool for those shortest paths, but cannot run directly on a residual graph with negative edges. The solver uses Johnson’s algorithm, which reprices the graph so that Dijkstra can run. It gives each letter a potential , the cost of the cheapest residual path ending at that letter from any starting letter. A potential only exists if the residual has no negative-cost cycle, since going round one more time would always make a path cheaper. One run of Bellman–Ford over the 26 letters computes all of the potentials.
We then reprice every edge from to as the original price plus the difference in potential . Think of a letter’s potential as its height (hence the name, after potential energy). Repricing charges each edge extra for the height it drops. Every path from to drops by the same in total, so the cheapest path stays the cheapest. No repriced edge is negative either. The cheapest path to costs no more than the cheapest path to plus the edge between them, so . Rearranging gives . In the four-letter example, almond’s −1 edge leads into a and vine’s leads into v. So , while . The repriced edges are shown below.
With every edge non-negative, we can run Dijkstra 26 times, once from each letter. This prices all 26 × 25 = 650 pairs of distinct letters off the single balanced solve, and the loop that the solve already priced makes the 651st.
Joining Up the Chain
Flow settles the first part of Euler’s condition, but we must also pay attention to the second, connectivity. The flow can balance every letter and still leave the kept words as two separate loops, with no words joining them. Swap vine and almond in the earlier example for tulip and peanut. Aloe and erica run between a and e, and tulip and peanut between t and p. Every letter has one word in and one out, so the flow keeps all four. But no single chain can play both loops. The flow’s answer is therefore only an upper bound on the chain length.
We check for this with union-find, a data structure that sorts letters into groups. Every letter starts in a group of its own, and each kept word merges the groups of its first and last letter. The direction of a word does not matter here. In a balanced graph every word lies on a loop, so if a reaches e then e also reaches a. In the figure, the two loops leave two groups. If every letter that a kept word touches ends up in a single group, then the real chain meets the flow’s upper bound.
With more than one group, a quick heuristic first finds a good chain, and a search then checks whether a longer one exists. The search picks one group and sorts every possible chain into cases. A chain either stays inside the group, stays outside it, or plays a word that crosses between the two. Each case is one more flow solve with an extra rule: the letters on the far side are removed, or one crossing word is forced into the chain. A case whose upper bound is no better than the best chain so far is dropped. This is called branch and bound. With only 26 letters the search stays small. No opening word in any category needs more than 135 flow solves, and none takes more than 8.1 ms.
The bound can be too high. In the fabric category the flow keeps 63 words, but the longest chain plays only 62. Ten of its words end on a, such as organza, and only one leaves it for another letter, acetate. To balance a, the flow can keep at most one of the ten, paired with acetate. Keeping that pair costs three words elsewhere, one more than it gains, so the flow discards all eleven. Two more words, aba and alpaca, start and end on a. A loop like this cannot unbalance its letter, so the flow keeps both for free. But a loop joins a only to itself, so union-find leaves a in a group of its own, out of a chain’s reach. To reach the loops, a real chain has to pay for that pair, as the figure below shows. It comes in on one of the ten and leaves on acetate, giving up three words to gain four, for 62.
How Long a Game Can Last
The animal category holds 1,582 words, and its longest chain plays 640 of them. Plant keeps 456 of its 1,020 words, and toy just 3 of 29. The solver handles all 40,117 words of entity in 2.6 ms on an M1 MacBook Pro. Cooperation is this cheap because a chain only cares about each word’s first and last letter. Tens of thousands of words collapse onto 26 letters, and Euler’s condition turns the longest chain into a flow problem. Winning collapses onto the same letters too. On the letter graph it becomes edge geography, where each word is an edge used at most once. Schaefer’s paper also proves edge geography PSPACE-complete on a general graph, but the letter graph is not general since it has only 26 nodes. While a full search takes polynomial time in the number of words, the degree of that polynomial is the number of letter pairs in use, which can reach 676. Slightly infeasible in practice.
Before your next game, try the solver in the widget under Playing to Win. For some problems, competition is much harder than cooperation.