# pyright: strict from functools import cache from sys import stdin @cache def match(arrangement: str, pattern: str) -> bool: if len(arrangement) != len(pattern): return False for a, p in zip(arrangement, pattern): if p == "?": continue if a != p: return False return True @cache def matching( pattern: str, groups: tuple[int, ...], length: int, min_offset: int = 0 ) -> int: if not groups: return 1 if "#" not in pattern else 0 block = "#" * groups[0] total = 0 for offset in range(min_offset, length - sum(groups) - len(groups) + 2): prefix_len = offset + groups[0] if not match("." * offset + block, pattern[:prefix_len]): continue total += matching( pattern[prefix_len:], groups[1:], length - prefix_len, min_offset=1 ) return total inp: list[tuple[str, tuple[int, ...]]] = [] for line in stdin: pattern, rest = line.rstrip().split(maxsplit=1) groups = tuple(map(int, rest.split(","))) inp.append((pattern, groups)) print(sum(matching(pattern, groups, len(pattern)) for pattern, groups in inp)) print( sum( matching("?".join([pattern] * 5), groups * 5, len(pattern) * 5 + 4) for pattern, groups in inp ) )