def solve(): with open("./input.txt") as f: lines = f.readlines() patterns = lines[0].strip().split(", ") designs = [line.strip() for line in lines[2:]] def can_make_design(design, available_patterns): if not design: return True for pattern in available_patterns: if design.startswith(pattern): if can_make_design(design[len(pattern):], available_patterns): return True return False def count_arrangements(design, available_patterns): if not design: return 1 count = 0 for pattern in available_patterns: if design.startswith(pattern): count += count_arrangements(design[len(pattern):], available_patterns) return count possible_designs = 0 total_arrangements = 0 for design in designs: if can_make_design(design, patterns): possible_designs += 1 total_arrangements += count_arrangements(design, patterns) print(possible_designs) print(total_arrangements) solve()