#advent of code 2024
#day 19
#unfortunately I didn't figure it out in time on my own
#I read some tips on the internet and returned to it on later date
#my attempt was kinda close but I didn't manage to correctly 
#control the flow of the program which lead to duplicated paths
#I used the patterns dictionary to split the patterns based on their 
#first letter so I don't need to check all patterns at the same time,
#only those potentially correct
#then, using CalcDesign function, we iterate over the whole string
#the dictionary PatternPaths stores the total amount of possible ways
#to reach a given substring of the function argument
#when we check each character c of the argument, we first look up 
#how many paths there are to reach this substring (if it's the first 
#letter then it is hardcoded as 1). Then we iterate over the list of 
#patterns that begin with given character. 
#if the substring plus pattern are the same as the substring of design
#then it is counted as possible path
#function returns a bool and an int: if there's at least one way to reach
#desired design (part 1), and amount of possible ways to reach it (part 2)

def CalcDesign(design):
	PatternPaths = {};
	for c_ind,c in enumerate(design): #character index, character
		subpath = PatternPaths.get(design[:c_ind],0) + 1*(c_ind==0);
		for pattern in patterns.get(c,[]):
			subdesign = design[:c_ind] + pattern;
			if subdesign == design[:c_ind + len(pattern)]:
				if subdesign not in PatternPaths: 
					PatternPaths[subdesign] = 0;
				PatternPaths[subdesign] += subpath + 0;
	paths = PatternPaths.get(design,0);
	return paths != 0, paths;

part1 = 0;
part2 = 0;
patterns = {};
data1, data2 = open("19.in","r").read().split("\n\n");
for data in data1.strip().split(", "):
	if data[0] not in patterns: patterns[data[0]] = [];
	patterns[data[0]].append(data);

for des in data2.strip().split("\n"):
	ok,TotalPaths = CalcDesign(des);
	part1 += ok*1;
	part2 += TotalPaths;

print("part 1 =", part1);
print("part 2 =", part2);