56 lines
1,006 B
Python
56 lines
1,006 B
Python
#!/usr/bin/env python3
|
|
|
|
from functools import cache
|
|
from typing import Optional
|
|
|
|
with open('day19') as f:
|
|
towels = set(f.readline().strip().split(", "))
|
|
f.readline()
|
|
designs = [d.strip() for d in f]
|
|
|
|
# part 1
|
|
|
|
@cache
|
|
def is_possible(design) -> Optional[list[str]]:
|
|
if len(design) == 0:
|
|
return []
|
|
|
|
collector = ""
|
|
for i,c in enumerate(design):
|
|
collector += c
|
|
if collector in towels:
|
|
rest = is_possible(design[i+1:])
|
|
if rest is not None: return [collector] + rest
|
|
|
|
return None
|
|
|
|
|
|
|
|
cnt = 0
|
|
for design in designs:
|
|
if is_possible(design):
|
|
cnt += 1
|
|
|
|
|
|
# part 2
|
|
|
|
@cache
|
|
def count_possible(design) -> int:
|
|
if len(design) == 0:
|
|
return 1
|
|
|
|
collector = ""
|
|
count = 0
|
|
for i,c in enumerate(design):
|
|
collector += c
|
|
if collector in towels:
|
|
rest = count_possible(design[i+1:])
|
|
count += rest
|
|
|
|
return count
|
|
|
|
|
|
|
|
cnt = 0
|
|
for design in designs:
|
|
cnt += count_possible(design)
|