def _induce_rules_for_examples(examples, seed_rules, config):
  """Iteratively searches for rules to optimize codelength objective."""
  # Initialize the search state.
  search_state = SearchState(
      current_rules=seed_rules,
      rules_to_candidates=collections.defaultdict(set),
      derivable_rules=seed_rules.copy())

  # Update state for all seed rules.
  _update_state(seed_rules, search_state, config)

  # Iteratively update grammar.
  for iteration_num in range(config.max_iterations):
    print("Iteration %s." % iteration_num)
    rule, rules_to_remove = _get_max_rule(search_state, config, examples)

    # Break if there is no candidate that improves codelength objective.
    if rule is None:
      print("Breaking as no candidate exceeds minimum threshold.")
      break

    # Otherwise, update the set of rules.
    print("Adding rule: %s" % str(rule))
    search_state.current_rules.add(rule)
    search_state.derivable_rules.add(rule)
    for rule_to_remove in rules_to_remove:
      print("Removing rule: %s" % str(rule_to_remove))
      search_state.current_rules.remove(rule_to_remove)
      del search_state.rules_to_candidates[rule_to_remove]
    print("Number of current_rules: %s" % len(search_state.current_rules))

    # Update the search state based on any potentially affected rules.
    # The set of affected rules includes any rule that the added rule
    # may potentially be used in a derivation for.
    affected_rules = _find_affected_rules(search_state.current_rules, rule)
    _update_state(affected_rules, search_state, config)

  # Return the set of induced rules.
  return search_state.current_rules
Iteratively searches for rules to optimize codelength objective.
language/compgen/nqg/model/induction/induction_utils.py