Can You Make the Connection?

In the word game Connections, $16$ words must be sorted into four sets of four, each set sharing some common property. On each turn you select four of the remaining words and submit them. If they form one of the sets, they are removed and you look for the next. The game also gives a hint: whenever your four words include exactly three from one set, it says “One away…”.

Faced with all $16$ words, suppose you pick four at random. What is the probability that you see the “One away…” message?

The Fiddler, Zach Wissner-Gross, December 8, 2023(original post)

The official solution appeared in the post of December 15, 2023 and gives $48/455 \approx 10.55$ percent for the main puzzle and $7$ guesses for the Extra Credit. Both agree with the answers below.

Solution

Every set of four words is equally likely to be picked, so the answer is a count of good picks divided by a count of all picks.

All picks: choosing $4$ of $16$ words can be done in $$\binom{16}{4} = \frac{16 \cdot 15 \cdot 14 \cdot 13}{4 \cdot 3 \cdot 2 \cdot 1} = 1820$$ ways.

Good picks have exactly three words from one set. Build one in three steps: choose the set that supplies the three words ($4$ ways), choose which of its four words to leave out ($4$ ways), and choose the fourth word from the $12$ words of the other three sets ($12$ ways). Each good pick is built exactly once, because the set supplying three words is determined by the pick. So there are $4 \cdot 4 \cdot 12 = 192$ good picks, and $$\boxed{\ P(\text{``One away''}) \;=\; \frac{192}{1820} \;=\; \frac{48}{455} \;\approx\; 10.55\%. \ }$$ That is more than one time in ten, which is more often than most people guess.

The computation

The program labels the $16$ words by set, runs through all $1820$ picks of four, and counts those in which some set supplies exactly three words.

from fractions import Fraction
from itertools import combinations
from collections import Counter

words = [s for s in range(4) for _ in range(4)]  # word -> set
picks = list(combinations(range(16), 4))
hits = sum(1 for p in picks
           if 3 in Counter(words[i] for i in p).values())
print(len(picks), hits, Fraction(hits, len(picks)))

It prints

1820 192 48/455

Extra Credit

You have found two sets in your first two guesses, leaving eight words, and you have no idea how they split into the last two sets. Ignoring the game’s limit on wrong guesses, and using the “One away…” hints cleverly, how many guesses do you need to be certain of solving the puzzle in the worst case?

Solution

First, size up the unknown. Call the eight words $A$ to $H$. The split is settled once we know which three words share a set with $A$, so there are $\binom73 = 35$ possible splits.

A guess of four words has three possible replies. If the four words are one of the sets, the guess is correct. Otherwise the four words meet the two sets either three and one (“One away”) or two and two (no message). Note that a guess tells us the same about its complement, the other four words.

At least seven guesses. Picture any strategy as a tree. Each guess is a node, and the two replies “One away” and “two-two” lead to two further nodes. A “correct” reply ends the search, and it can happen at a given node for only one of the $35$ splits, the split whose set was guessed. Every split must eventually be guessed correctly, so every split needs a node of its own. A tree with the first guess at the top and at most $d$ levels has at most $1 + 2 + 4 + \dots + 2^{d-1} = 2^d - 1$ nodes. Five levels give only $31$ nodes, too few for $35$ splits, so some split is not found until the sixth guess at the earliest. One more guess submits the last four words. So no strategy can promise fewer than $7$ guesses.

Seven guesses suffice. The counting argument leaves little slack ($35$ splits against $63$ nodes in six levels), and it does not by itself produce a strategy. Each guess must split the surviving possibilities almost evenly. The first guess already shows the shape: guessing $ABCD$ leaves $18$ splits behind the two-two reply and $16$ behind “One away”, and both fit in the $31$ nodes of the five remaining levels. Pushing this through by hand level by level is laborious. The exhaustive search below tries every guess at every stage and confirms that a strategy exists that always finds the first set by the sixth guess. Together with the lower bound, $$\boxed{\ 7 \text{ guesses in the worst case}. \ }$$

The computation

The program solves the guessing game exactly. A state is the list of splits still consistent with the replies so far. For a state it tries every possible guess, sorts the surviving splits by the reply each would produce, and takes the worst branch. The best guess is the one whose worst branch is smallest. Once a single split is left, two more guesses finish the game. Caching the states keeps the search to about a second.

from functools import lru_cache

letters = range(8)
# word 0's set fixes the split: 35 possible splits
splits = [frozenset(c) for c in combinations(letters, 4)
          if 0 in c]
guesses = [frozenset(c) for c in combinations(letters, 4)]

def reply(g, s):
    k = len(g & s)
    if k in (0, 4):
        return "correct"          # g is one of the two sets
    return "one away" if k in (1, 3) else "two-two"

@lru_cache(maxsize=None)
def need(S):
    """Worst-case guesses still needed when the split
    is one of those in S."""
    if len(S) == 1:
        return 2                  # submit both sets
    best = float("inf")
    for g in guesses:
        groups = {}
        for s in S:
            groups.setdefault(reply(g, s), []).append(s)
        if len(groups) == 1 and "correct" not in groups:
            continue              # learns nothing
        worst = max(1 if r == "correct"
                    else need(frozenset(v))
                    for r, v in groups.items())
        best = min(best, 1 + worst)
    return best

print("worst-case guesses:", need(frozenset(splits)))

It prints

worst-case guesses: 7