OPiMedia

Advent of Code 2020 - Day 19: Monster Messages

Dec 19th, 2020
839
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #!/usr/bin/env python3
  2. # -*- coding: utf-8 -*-
  3.  
  4. """
  5. Advent of Code 2020 - Day 19: Monster Messages
  6. https://adventofcode.com/2020/day/19
  7.  
  8. :license: GPLv3 --- Copyright (C) 2020 Olivier Pirson
  9. :author: Olivier Pirson --- http://www.opimedia.be/
  10. :version: December 19, 2020
  11. """
  12.  
  13. import sys
  14.  
  15. from typing import List, Optional, Tuple, Union
  16.  
  17. import regex as re  # type: ignore
  18.  
  19.  
  20. RULES: List[Union['RuleChar', 'RuleEmpty', 'RuleSeq', 'RuleUnion']] = []
  21.  
  22.  
  23. class RuleChar:
  24.     def __init__(self, rule_id: int, char: str) -> None:
  25.         assert len(char) == 1
  26.  
  27.         self._char = char
  28.         self._id = rule_id
  29.  
  30.     def __repr__(self) -> str:
  31.         return 'RuleChar({})'.format(self._char)
  32.  
  33.     def __str__(self) -> str:
  34.         return self._char
  35.  
  36.     def regex(self) -> str:
  37.         return self._char
  38.  
  39.     def reset(self) -> None:
  40.         pass
  41.  
  42.  
  43. class RuleEmpty:
  44.     def __init__(self, rule_id: int) -> None:
  45.         self._id = rule_id
  46.  
  47.     def __repr__(self) -> str:
  48.         return 'RuleEmpty'
  49.  
  50.     def __str__(self) -> str:
  51.         return 'RuleEmpty'
  52.  
  53.     def regex(self) -> str:  # pylint: disable=no-self-use
  54.         assert False
  55.  
  56.     def reset(self) -> None:
  57.         pass
  58.  
  59.  
  60. class RuleSeq:
  61.     def __init__(self, rule_id: int, indices_str: str) -> None:
  62.         assert indices_str
  63.  
  64.         self._indices = tuple(map(int, indices_str.split()))
  65.         self._id = rule_id
  66.         self._regex: Optional[str] = None
  67.  
  68.     def __repr__(self) -> str:
  69.         return 'RuleSeq({})'.format(' '.join(map(str, self._indices)))
  70.  
  71.     def __str__(self) -> str:
  72.         return ' '.join(map(str, self._indices))
  73.  
  74.     def regex(self) -> str:
  75.         if self._regex is None:
  76.             self._regex = '(?:{})'.format(
  77.                 ''.join(map(lambda i: RULES[i].regex(), self._indices)))
  78.  
  79.         return self._regex
  80.  
  81.     def reset(self) -> None:
  82.         self._regex = None
  83.  
  84.  
  85. class RuleUnion:
  86.     def __init__(self, rule_id: int, indices_str: str) -> None:
  87.         assert indices_str
  88.  
  89.         seq = []
  90.         for sub in indices_str.split(' | '):
  91.             seq.append(RuleSeq(rule_id, sub))
  92.  
  93.         self._subrules = tuple(seq)
  94.         self._id = rule_id
  95.         self._regex: Optional[str] = None
  96.  
  97.     def __repr__(self) -> str:
  98.         return ' | '.join(map(repr, self._subrules))
  99.  
  100.     def __str__(self) -> str:
  101.         return ' | '.join(map(str, self._subrules))
  102.  
  103.     def regex(self) -> str:
  104.         if self._regex is None:
  105.             if self._id == 8:  # ad hoc for the problem
  106.                 self._regex = '(?:{})+'.format(RULES[42].regex())
  107.             elif self._id == 11:  # ad hoc for the problem
  108.                 self._regex = '(?P<r11>{}(?P&r11)?{})'.format(
  109.                     RULES[42].regex(), RULES[31].regex())
  110.             else:
  111.                 self._regex = '(?:{})'.format(
  112.                     '|'.join(map(lambda subrule: subrule.regex(),
  113.                                  self._subrules)))
  114.  
  115.         return self._regex
  116.  
  117.     def reset(self) -> None:
  118.         self._regex = None
  119.  
  120.  
  121. class Rule:
  122.     def __init__(self, line: str) -> None:
  123.         assert line
  124.  
  125.         rule_id_str, rule_str = line.split(': ')
  126.         rule_id = int(rule_id_str)
  127.  
  128.         self._rule: Union[RuleChar, RuleSeq, RuleUnion]
  129.         if rule_str[0] == '"':
  130.             self._rule = RuleChar(rule_id, rule_str[1:-1])
  131.         elif '|' not in rule_str:
  132.             self._rule = RuleSeq(rule_id, rule_str)
  133.         else:
  134.             self._rule = RuleUnion(rule_id, rule_str)
  135.  
  136.         self._id = rule_id
  137.         if rule_id >= len(RULES):
  138.             RULES.extend([RuleEmpty(rule_id)] * (rule_id + 1 - len(RULES)))
  139.  
  140.         RULES[rule_id] = self  # type: ignore
  141.  
  142.     def __repr__(self) -> str:
  143.         return 'Rule {}: {}'.format(self._id, repr(self._rule))
  144.  
  145.     def __str__(self) -> str:
  146.         return 'Rule {}: {}'.format(self._id, str(self._rule))
  147.  
  148.     def regex(self) -> str:
  149.         return self._rule.regex()
  150.  
  151.     def reset(self) -> None:
  152.         self._rule.reset()
  153.  
  154.  
  155. def check(messages: Tuple[str, ...]) -> int:
  156.     regex_str = RULES[0].regex()
  157.     regex = re.compile(regex_str)
  158.  
  159.     nb = 0
  160.     for message in messages:
  161.         if regex.fullmatch(message):
  162.             nb += 1
  163.  
  164.     return nb
  165.  
  166.  
  167. def log(*params) -> None:
  168.     sys.stdout.flush()
  169.     print(*params, file=sys.stderr)
  170.     sys.stderr.flush()
  171.  
  172.  
  173. def main() -> None:
  174.     for line in sys.stdin:
  175.         line = line.rstrip()
  176.         if not line:
  177.             break
  178.  
  179.         Rule(line)
  180.  
  181.     messages = tuple(map(str.rstrip, sys.stdin.readlines()))
  182.  
  183.     # Part 1
  184.     nb = check(messages)
  185.     print(nb)
  186.     sys.stdout.flush()
  187.  
  188.     # Part 2
  189.     if len(RULES) >= 11:
  190.         log('Old rule', RULES[8])
  191.         log('Old rule', RULES[11])
  192.         RULES[8] = Rule('8: 42 | 42 8')  # type: ignore
  193.         RULES[11] = Rule('11: 42 31 | 42 11 31')  # type: ignore
  194.         log('New rule', RULES[8])
  195.         log('New rule', RULES[11])
  196.  
  197.     for rule in RULES:
  198.         rule.reset()
  199.  
  200.     nb = check(messages)
  201.     print(nb)
  202.  
  203.  
  204. if __name__ == '__main__':
  205.     main()
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×