import re from tracemalloc import start import numpy as np DP = {} def recursive_solve(data, numbers, num_idx, current_num): key = (data, num_idx, current_num) if key in DP: return DP[key] if len(data) == 0: if (len(numbers)-1 == num_idx and numbers[num_idx] == current_num): return 1 elif num_idx == len(numbers) and 0 == current_num: return 1 else: return 0 ret = 0 for ch in ['.', '#']: if data[0] == ch or data[0] == '?': if ch == '.' and current_num == 0: ret += recursive_solve(data[1:], numbers, num_idx, current_num) elif ch == '.' and len(numbers) > num_idx and numbers[num_idx] == current_num: ret += recursive_solve(data[1:], numbers, num_idx+1, 0) elif ch == '#': ret += recursive_solve(data[1:], numbers, num_idx, current_num+1) DP[key] = ret return ret # f = open('test.txt', 'r') f = open('input.txt', 'r') content = f.read() lines = content.splitlines() sum = 0 for line in lines: data, numbers_str = line.split() numbers = [int(x) for x in numbers_str.split(',')]*5 DP.clear() data = data + '?' + data + '?' + data + '?' + data + '?' + data line_sum = recursive_solve(data, numbers, 0, 0) print("ret ", line_sum) sum += line_sum print(sum) f.close()