1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
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);
|
