Day 19: Monster Messages

Classes:

Rule()	Represent a rule that valid messages should obey.
RuleOr(rules)	Represent an union composition of rules (at least one rule matches).
RuleSequence(rules)	Represent a chain of rules where all rules need to match in sequence.
RuleLiteral(literal)	Represent a rule where a literal is exactly matched.
Node()	Represent a node in the abstract syntax tree.
NodeLiteral(literal)	Represent a literal in the rule syntax.
NodeReference(identifier)	Represent a reference to a rule.
NodeSequence(references)	Represent a parsed sequence of node references.
NodeOr(sequences)	Represent a parsed union of node sequences.

Functions:

parse_rule(line)	Parse the rule from the line into (rule identifier, abstract syntax tree).
parse_rules(lines)	Parse the rules from lines into a dictionary of identifier 🠒 AST.
iterate(rule_tree)	Yield the rule_tree and all its descendants.
repr_rule_tree(rule_tree)	Represent the abstract syntax tree rule_tree as a string for inspection.
interpret_rule_0(rule_trees)	Interpret the rule trees and construct the rule 0.
count_matching_messages(rule_0, messages)	Count the messages that match the rules starting from rule_0.

class Rule

Represent a rule that valid messages should obey.

Methods:

match(text)

Match the text and return the remaining unmatched text.

abstract match(text: str) → Optional[str]

Match the text and return the remaining unmatched text.

If the beginning of the text does not match, return None.

Ensures

• result is not None ⇒ text.endswith(result)

• not (result is not None)
  or (len(text) > len(result))
  

class RuleOr(rules: List[Rule])

Represent an union composition of rules (at least one rule matches).

Methods:

__init__(rules)	Initialize with the given values.
match(text)	Check whether at least one rule from rules matches.

Attributes:

rules

Union of rules

__init__(rules: List[Rule]) → None

Initialize with the given values.

rules: Final[List[Rule]]

Union of rules

match(text: str) → Optional[str]

Check whether at least one rule from rules matches.

Ensures

• result is not None ⇒ text.endswith(result)

• not (result is not None)
  or (len(text) > len(result))
  

class RuleSequence(rules: List[Rule])

Represent a chain of rules where all rules need to match in sequence.

Methods:

__init__(rules)	Initialize with the given values.
match(text)	Check whether text matches the whole sequence of rules.

Attributes:

rules

Rule chain

__init__(rules: List[Rule]) → None

Initialize with the given values.

rules: Final[List[Rule]]

Rule chain

match(text: str) → Optional[str]

Check whether text matches the whole sequence of rules.

Ensures

• result is not None ⇒ text.endswith(result)

• not (result is not None)
  or (len(text) > len(result))
  

class RuleLiteral(literal: str)

Represent a rule where a literal is exactly matched.

Methods:

__init__(literal)	Initialize with the given values.
match(text)	Check whether text matches exactly the literal.

Attributes:

literal

Literal to be matched

__init__(literal: str) → None

Initialize with the given values.

literal: Final[str]

Literal to be matched

match(text: str) → Optional[str]

Check whether text matches exactly the literal.

Ensures

• result is not None ⇒ text.endswith(result)

• not (result is not None)
  or (len(text) > len(result))
  

• result is not None ⇒ self.literal + result == text

class Node

Represent a node in the abstract syntax tree.

class NodeLiteral(literal: str)

Represent a literal in the rule syntax.

Methods:

__init__(literal)

Initialize with the given values.

Attributes:

literal

Parsed literal

__init__(literal: str) → None

Initialize with the given values.

literal: Final[str]

Parsed literal

class NodeReference(identifier: int)

Represent a reference to a rule.

Methods:

__init__(identifier)

Initialize with the given values.

Attributes:

identifier

Identifier of the referenced rule

__init__(identifier: int) → None

Initialize with the given values.

identifier: Final[int]

Identifier of the referenced rule

class NodeSequence(references: List[NodeReference])

Represent a parsed sequence of node references.

Methods:

__init__(references)

Initialize with the given values.

Attributes:

references

Parsed references

__init__(references: List[NodeReference]) → None

Initialize with the given values.

references: Final[List[NodeReference]]

Parsed references

class NodeOr(sequences: List[NodeSequence])

Represent a parsed union of node sequences.

Methods:

__init__(sequences)

Initialize with the given values.

Attributes:

sequences

Union

__init__(sequences: List[NodeSequence]) → None

Initialize with the given values.

sequences: Final[List[NodeSequence]]

Union

parse_rule(line: str) → Tuple[int, Node]

Parse the rule from the line into (rule identifier, abstract syntax tree).

Requires

• RULE_RE.match(line)

parse_rules(lines: Lines) → MutableMapping[int, Node]

Parse the rules from lines into a dictionary of identifier 🠒 AST.

Requires

• all(RULE_RE.match(line) for line in lines)

iterate(rule_tree: Node) → Iterator[Node]

Yield the rule_tree and all its descendants.

repr_rule_tree(rule_tree: Node) → str

Represent the abstract syntax tree rule_tree as a string for inspection.

interpret_rule_0(rule_trees: Mapping[int, Node]) → Rule

Interpret the rule trees and construct the rule 0.

Requires

• all(
      all(
          node.identifier in rule_trees
          for node in iterate(rule_tree)
          if isinstance(node, NodeReference)
      )
      for rule_tree in rule_trees.values()
  )
  

  (No dangling references)

• 0 in rule_trees

  (The initial rule is present.)

count_matching_messages(rule_0: Rule, messages: List[str]) → int

Count the messages that match the rules starting from rule_0.

Ensures

• 0 <= result <= len(messages)