From 6b733982f9f240c1c97f1fa705bfbe4cd93c640e Mon Sep 17 00:00:00 2001 From: mhsn Date: Fri, 12 Sep 2025 20:20:58 +0100 Subject: simplify python file structure --- 2024/19/python.py | 42 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 42 insertions(+) create mode 100755 2024/19/python.py (limited to '2024/19/python.py') diff --git a/2024/19/python.py b/2024/19/python.py new file mode 100755 index 0000000..efd3272 --- /dev/null +++ b/2024/19/python.py @@ -0,0 +1,42 @@ +#!/usr/bin/env python3 + +from fileinput import input +from functools import cache +from itertools import takewhile + +inp = map(str.strip, input()) +towels = [t.strip() for t in next(takewhile(bool, inp)).split(",")] +designs = [d for d in inp if d] + +# Construct trie +trie = {} +for towel in towels: + prev = None + curr = trie + for t in towel: + term, succ = curr.setdefault(t, (False, {})) + prev = curr + curr = succ + prev[towel[-1]] = (True, curr) + + +@cache +def steps(design, n=0): + if n == len(design): + return 1 + ways = 0 + curr = trie + for d, s in enumerate(design[n:], start=1): + if s not in curr: + return ways + term, curr = curr[s] + if term: + ways += steps(design, n + d) + return ways + + +silver = sum(map(bool, map(steps, designs))) +gold = sum(map(steps, designs)) + +print("silver:", silver) +print("gold:", gold) -- cgit v1.2.3