Advent of code 2020 day 19

def num_valid(input, replace_rules=False):
  section1, section2 = input.strip('\n').split('\n\n')
  rules = dict(line.split(': ') for line in section1.splitlines())
  if replace_rules:
    rules.update({'8': '42 | 42 8', '11': '42 31 | 42 11 31'})

  def valid_expansion(symbols, text):
    if not symbols or not text:
      return not symbols and not text
    expansions = rules[symbols[0]]
    if expansions[0] == '"':
      return expansions[1] == text[0] and valid_expansion(symbols[1:], text[1:])
    return any(valid_expansion(expansion.split() + symbols[1:], text)
               for expansion in expansions.split(' | '))

  return sum(valid_expansion(['0'], text) for text in section2.splitlines())