From 403e334db290adfa7a64c617c83c4b69e7fc12b6 Mon Sep 17 00:00:00 2001 From: Tomasz Kramkowski Date: Tue, 12 Dec 2023 15:59:26 +0000 Subject: day 12 optimisations --- 12.py | 20 ++++++++++++++++---- 1 file changed, 16 insertions(+), 4 deletions(-) diff --git a/12.py b/12.py index 2c2810c..065a566 100644 --- a/12.py +++ b/12.py @@ -1,22 +1,34 @@ # pyright: strict -import fnmatch 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): - base = "." * offset + "#" * groups[0] - if not fnmatch.fnmatch(base, pattern[: len(base)]): + prefix_len = offset + groups[0] + if not match("." * offset + block, pattern[:prefix_len]): continue total += matching( - pattern[len(base) :], groups[1:], length - len(base), min_offset=1 + pattern[prefix_len:], groups[1:], length - prefix_len, min_offset=1 ) return total -- cgit v1.2.3-54-g00ecf