This is a great article. It's pretty fun to play around with this heuristic:

  lambda c: 3*len(matches(c, uncovered)) - len(c)

Here's a trivial way to explore it: say we generalize the heuristic to H(a, b).

  H(a,b) = lambda c: a*len(matches(c, uncovered)) - b*len(c)

The original heuristic is considered H(3,1) by this definition. Then we can play around with a and b to see if we'd get smaller results.

  def findregex_lambda(winners, losers, a, b):
      "Find a regex that matches all winners but no losers (sets of strings)."
      # Make a pool of candidate components, then pick from them to cover winners.
      # On each iteration, add the best component to 'cover'; finally disjoin them together.
      pool = candidate_components(winners, losers)
      cover = []
      while winners:
          best = max(pool, key=lambda c: a*len(matches(c, winners)) - b*len(c))
          cover.append(best)
          pool.remove(best)
          winners = winners - matches(best, winners)
      return '|'.join(cover)

  >>> findregex_lambda(starwars, startrek, 3, 1)
  ' T|E.P| N'
  >>> findregex_lambda(starwars, startrek, 3, 2)
  ' T|B| N| M'

Or, to automate this:

  def best_H_heuristic(winners, losers):
      d = {(a,b) : len(findregex_lambda(winners, losers, a,b)) for a in range(0,4) for b in range(0,4)}
      return min(d, key=d.get)

  >>> best_H_heuristic(starwars, startrek):
  (3,1)

Looks like H(3,1) is pretty good for this case. What about the nfl teams?

  >>> best_H_heuristic(nfl_in, nfl_out)
  (3, 2)
  >>> findregex_lambda(nfl_in, nfl_out, 3, 1)
  'pa|g..s|4|fs|sa|se|lt|os'
  >>> findregex_lambda(nfl_in, nfl_out, 3, 2)
  'pa|ch|4|e.g|sa|se|lt|os'

Not the best heuristic there. H(3,1) wins or ties for the boys/girls set, left/right set and drugs/cities set, which just goes to show you that picking a heuristic off a gut guess isn't such a bad approach.

You could also explore heuristics of different forms:

  M(a,b,d,e) = lambda c: a*len(matches(c, uncovered))^b - d*len(c)^e

Or trying completely different formats:

  L(a,b) = lambda c: a*log(len(matches(c, uncovered))) - b*len(c)