import re

with open('test.text', 'r') as file:
    data: list[str] = file.readlines()

# Parse Input

seen = {}
records = []
groups = []
for line in data:

    record, group = line.split(' ')

    group = [int(n) for n in group.split(',')]
    records.append(record)
    groups.append(group)

# Part 1

# Checks if a group of springs is valid based on the group info
def valid_group(record: str, groups: list[int]) -> bool:

    damaged_groups = re.findall('#+', record)

    if len(damaged_groups) != len(groups):
        return False

    for i, group in enumerate(damaged_groups):
        if len(group) != groups[i]:
            return False

    return True

def check_combinations(record: str, group: list[int]) -> int:
    if record in seen:
        return seen[record]

    if '?' in record:
        new_record1 = record.replace('?', '.', 1)
        new_record2 = record.replace('?', '#', 1)

        ans = check_combinations(new_record1, group) + check_combinations(new_record2, group)
        seen[record] = ans
        return ans
    else:
        return int(valid_group(record, group))

total = 0
for record, group in zip(records, groups):
    total += check_combinations(record, group)

print(total)

# Part 2
total = 0
for record, group in zip(records, groups):
    record = ((record + '?')* 5)[:-1]
    group = group * 5

    total += check_combinations(record, group)

print(f'Part 2: {total}')