Regex Golf

regex_golf.rb

# http://norvig.com/ipython/xkcd1313.ipynb
# http://nbviewer.jupyter.org/url/norvig.com/ipython/xkcd1313.ipynb
#
# http://norvig.com/ipython/xkcd1313-part2.ipynb
# http://nbviewer.jupyter.org/url/norvig.com/ipython/xkcd1313-part2.ipynb
#
# Only implemented the 'covers' optimisation in part 2
# no branch and bound.
# no repetition characters or pairs

require 'set'

def mistakes(regex, winners, losers)
  {
    false_positives: losers.select { |l| regex =~ l },
    false_negatives: winners.select { |w| regex !~ w },
  }.reject { |k, v| v.empty? }
end

def verify(regex, winners, losers)
  unless (res = mistakes(regex, winners, losers)).empty?
    raise "#{regex}: #{res}"
  end
end

def golf(winners, losers)
  pool = regex_parts(winners, losers)
  covers = pool.map { |s, r|
    [s, Set.new(winners.select { |w| r =~ w })]
  }.to_h
  solution = []
  unmatched = winners.dup
  until unmatched.empty?
    best_str, _ = pool.max_by { |str, _|
      matches = (unmatched & covers[str]).size
      # Max matches per character. Add 1 if we will have to add an |.
      matches / (str.size.to_f + (matches == unmatched.size ? 0.0 : 1.0))
    }
    solution << best_str
    unmatched -= covers[best_str]
    pool.reject! { |s, r| unmatched.disjoint?(covers[s]) }
  end
  solution.join(?|)
end

def regex_parts(winners, losers)
  wholes = winners.map { |w| "^#{w}$" }
  parts = wholes.flat_map { |w| subparts(w).flat_map { |sp| dotify(sp) } }
  (wholes + parts).map { |p| [p, Regexp.new(p)] }.reject { |_, r| losers.any? { |l| r =~ l } }
end

def subparts(word, max_size: 4)
  Set.new((1..max_size).flat_map { |size|
    word.each_char.each_cons(size).map(&:join)
  })
end

def dotify(n)
  choices = n.each_char.map { |c| '^$'.include?(c) ? [c] : [c, ?.] }
  choices[0].product(*choices[1..-1]).map(&:join)
end

def report(winners, losers)
  soln = golf(winners, losers)
  verify(Regexp.new(soln), winners, losers)
  trivial = "^(#{winners.to_a.join(?|)})$"
  puts "Chars: #{soln.size}, Parts: #{soln.count(?|) + 1}, Competitive ratio: #{trivial.size.to_f / soln.size}, Winners: #{winners.size}, Losers: #{losers.size}"
  puts soln
end

winners = Set.new(%w(
washington adams jefferson jefferson madison madison monroe
monroe adams jackson jackson van-buren harrison polk taylor pierce buchanan
lincoln lincoln grant grapartnt hayes garfield cleveland harrison cleveland mckinley
mckinley roosevelt taft wilson wilson harding coolidge hoover roosevelt
roosevelt roosevelt roosevelt truman eisenhower eisenhower kennedy johnson nixon
nixon carter reagan reagan bush clinton clinton bush bush obama obama))

losers = Set.new(%w(
clinton jefferson adams pinckney pinckney clinton king adams
jackson adams clay van-buren van-buren clay cass scott fremont breckinridge
mcclellan seymour greeley tilden hancock blaine cleveland harrison bryan bryan
parker bryan roosevelt hughes cox davis smith hoover landon willkie dewey dewey
stevenson stevenson nixon goldwater humphrey mcgovern ford carter mondale
dukakis bush dole gore kerry mccain romney)) - winners

report(winners, losers)

nouns = Set.new(%w(time year people way day man thing woman life child world school
state family student group country problem hand part place case week company
system program question work government number night point home water room
mother area money story fact month lot right study book eye job word business
issue side kind head house service friend father power hour game line end member
law car city community name president team minute idea kid body information
back parent face others level office door health person art war history party result
change morning reason research girl guy moment air teacher force education))

adverbs = Set.new(%w(all particularly just less indeed over soon course still yet before
certainly how actually better to finally pretty then around very early nearly now
always either where right often hard back home best out even away enough probably
ever recently never however here quite alone both about ok ahead of usually already
suddenly down simply long directly little fast there only least quickly much forward
today more on exactly else up sometimes eventually almost thus tonight as in close
clearly again no perhaps that when also instead really most why ago off
especially maybe later well together rather so far once)) - nouns

report(adverbs, nouns)