Advent of code 2024 day 19

def day19(s, *, part2=False):  # Faster using 2-character prefix buckets.
  p1, p2 = s.split('\n\n')
  towels = p1.split(', ')
  designs = p2.splitlines()

  towels_1ch = {towel for towel in towels if len(towel) == 1}
  towels_2ch_prefix = collections.defaultdict(list)
  for towel in towels:
    if len(towel) >= 2:
      towels_2ch_prefix[towel[:2]].append(towel)

  def is_possible(design):
    if not design:
      return True
    if design[0] in towels_1ch and is_possible(design[1:]):
      return True
    for towel in towels_2ch_prefix[design[:2]]:
      if design.startswith(towel) and is_possible(design[len(towel) :]):
        return True
    return False

  @functools.cache
  def num_possible(design):
    if not design:
      return 1
    count = 0
    if design[0] in towels_1ch:
      count += num_possible(design[1:])
    for towel in towels_2ch_prefix[design[:2]]:
      if design.startswith(towel):
        count += num_possible(design[len(towel) :])
    return count

  total = 0
  for design in designs:
    total += num_possible(design) if part2 else is_possible(design)

  return total