def _get_max_rule(search_state, config, examples):
  """Identify a rule to add that maximizes the decrease in codelength."""
  # Dict of rule candidates to the codelenth savings
  # (i.e. negative codelength delta).
  candidates_to_delta = {}
  # Map of rule candidates to the set of rules that they enable removing.
  # (inverse of rules_to_candidates).
  candidates_to_rules = collections.defaultdict(set)

  for rule in search_state.current_rules:
    candidates = search_state.rules_to_candidates[rule]
    for candidate in candidates:
      if candidate not in candidates_to_delta:
        # Subtract cost of new rule if not already accounted for.
        candidates_to_delta[candidate] = -codelength_utils.rule_codelength(
            candidate, config)

      # Add cost of every possible removed rule.
      candidates_to_delta[candidate] += codelength_utils.rule_codelength(
          rule, config)
      candidates_to_rules[candidate].add(rule)

  # Sort candidates by codelength reduction (prior to computing the codelength
  # delta of the dataset encoding, which is relatively more expensive).
  # Use lexical ordering to break ties.
  candidates_to_delta_sorted = sorted(
      candidates_to_delta.items(), key=lambda x: (-x[1], x[0]))

  # For debugging, print up to the top 15 candidates.
  print("Candidate rules:")
  for rule, delta in candidates_to_delta_sorted[:15]:
    print("%s (%s)" % (rule, delta))

  min_delta = config.min_delta
  max_rule_to_add = None
  max_rules_to_remove = None
  for rule, delta in candidates_to_delta_sorted:
    if delta <= min_delta:
      break
    rules_to_remove = candidates_to_rules[rule]
    targets_delta = codelength_utils.get_dataset_encoding_delta(
        sample_size=config.parse_sample,
        examples=examples,
        current_rules=search_state.current_rules,
        candidate_rule_to_add=rule,
        candidate_rules_to_remove=rules_to_remove)

    print("Targets encoding delta for %s: -%s" % (rule, targets_delta))

    # Compute the full deta including both the codelength reduction of encoding
    # the grammar (previously computed) and the codelength delta of encoding
    # the targets with the new grammar.
    delta -= targets_delta
    if delta > min_delta:
      min_delta = delta
      max_rule_to_add = rule
      max_rules_to_remove = rules_to_remove
  return max_rule_to_add, max_rules_to_remove
Identify a rule to add that maximizes the decrease in codelength.
language/compgen/nqg/model/induction/induction_utils.py