xkcd regex golf: the puzzle behind comic 1313

Regex golf, the puzzle from xkcd comic 1313, is the game of writing the shortest regular expression that matches every word in one list and none in another. Like real golf, fewer strokes win. Here's the whole idea in one board — try it:

That's the entire game. The fun is in how quickly it stops being easy.

01The comic that named it

In January 2014, xkcd #1313, "Regex Golf" introduced a lot of programmers to the game. Its first panel shows a regex that matches Star Wars subtitles but not Star Trek ones:

And the comic's hover text raises the stakes: a 63-character pattern that matches the last names of every elected US president but none of the candidates they beat.

It looks like line noise, but read it as a list: each fragment between the | bars catches a few presidents. j alone catches Jefferson, Jackson and Johnson.

02The bug in the punchline

That same month, Peter Norvig — then Director of Research at Google, and co-author of the standard AI textbook — wrote a notebook to solve regex golf automatically. The first thing his test did was check the comic's answer. It failed:

[rn]t catches fremont — John C. Frémont, who lost the 1856 election to James Buchanan. Norvig worked out that Randall had used Millard Fillmore, the third-party candidate that year, as Buchanan's opponent instead. A regex-golf answer is only as good as its word lists.

03How a computer plays regex golf

Norvig's solver is a lovely piece of reasoning, and it's worth knowing because it's how good human golfers think, too:

1. Collect candidate parts. Take every short fragment of the winners' names — one to four characters, with some letters swapped for . — like bu, a.a or r.e$.
2. Keep only the safe ones. A part is useful only if it matches at least one winner and no losers.
3. Cover the winners. Now pick parts until every winner is matched. That's the classic set cover problem, which is NP-hard — so the solver picks greedily, each time taking the part with the best trade-off between winners covered and characters spent.
4. Join them with |.

The result beat the comic by 9 characters:

It shaved the Star Wars panel too — from 10 characters to 9:

04From puzzle to daily ritual

Browser games like regex.alf.nu turned the idea into level packs you could grind through. Regex Hunter takes the other road — the Wordle road:

05One from Norvig's notebook

Norvig also pitted the most popular baby names against each other. Here are five boys and five girls — par is his answer's length. Can you tie it, or beat it?

06Play regex golf today

Play today's hunt → A new regex golf puzzle every day: catch the monsters, spare the innocents, beat par. Free, in your browser, no sign-up.

If you want technique rather than history, read Regex golf strategies: how to beat par.