1 files changed, 49 insertions, 0 deletions
diff --git a/2024/aoc2024-d19.py b/2024/aoc2024-d19.py
new file mode 100644
index 0000000..eb3721a
--- /dev/null
+++ b/2024/aoc2024-d19.py
@@ -0,0 +1,49 @@
+#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);