xkcd 1313: Regex Golf

Abstraction: Greedy set-cover algorithm finds shorter regex than xkcd's genetic algorithm

Key points:

• Problem: find the shortest regex that matches all US presidential election winners but none of the losers (names that appear in both are excluded from losers)
• Approach: generate a pool of small regex parts (substrings, dotified variants, anchored wholes), keep only those matching no losers, then greedily select highest-scoring parts (4 pts per winner covered minus 1 pt per character)
• This is a set cover problem (NP-hard), so a greedy approximation is used — not optimal but efficient
• Norvig's greedy solution: 53 characters vs Randall's 63-character result from a genetic algorithm; genetic algorithms poorly suited here because disjunctions are unordered
• Algorithm extended to arbitrary winner/loser list pairs (drug names vs cities, Star Wars vs Star Trek titles, boys vs girls names)
• Peter Norvig notes three failure modes: regex might not be a disjunction, parts pool might miss needed components, greedy might pick wrong parts

Connections: Peter Norvig · Randall Munroe · Regular Expressions · Greedy Algorithms · Set Cover

Source: http://nbviewer.ipython.org/url/norvig.com/ipython/xkcd1313.ipynb