Spaces:
Running
Running
File size: 1,367 Bytes
a4da721 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
def can_make_design(design, patterns, memo=None, start=0):
if memo is None:
memo = {}
if start in memo:
return memo[start]
if start == len(design):
return 1
total = 0
for pattern in patterns:
if start + len(pattern) <= len(design):
if design[start:start+len(pattern)] == pattern:
total += can_make_design(design, patterns, memo, start + len(pattern))
memo[start] = total
return total
def parse_input(filename):
with open(filename, 'r') as f:
lines = f.read().strip().split('\n')
# Find the blank line
separator_index = lines.index('')
# Parse patterns
patterns = [p.strip() for p in lines[0].split(',')]
# Parse designs
designs = lines[separator_index+1:]
return patterns, designs
def solve_part1(patterns, designs):
possible = 0
for design in designs:
if can_make_design(design, patterns) > 0:
possible += 1
return str(possible)
def solve_part2(patterns, designs):
total = 0
for design in designs:
ways = can_make_design(design, patterns)
total += ways
return str(total)
# Read input and solve
patterns, designs = parse_input("input.txt")
# Part 1
print(solve_part1(patterns, designs))
# Part 2
print(solve_part2(patterns, designs)) |