adventofcode2024/day5.py at main · juneguo257/adventofcode2024 · GitHub

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
import copy

d1 = {} # in-degree
d2 = {} # out-degree
l2 = []
readL1 = True
with open("d5.txt", "r") as fin:
    lines = fin.readlines()
    for x in lines:
        if (x.strip() == ""):
            readL1 = False
        elif (readL1):
            y, z = x.strip().split("|")
            y = int(y)
            z = int(z)
            if (z in d1):
                d1[z].append(y)
            else:
                d1[z] = [y]

            if (y in d2):
                d2[y].append(z)
            else:
                d2[y] = [z]
        else:
            l2.append(list(map(int, x.strip().split(","))))

# part 1

curVisited = set()
midSum = 0
part2 = []
for i in range(len(l2)):
    verified = True
    for j in range(len(l2[i])):
        if (l2[i][j] in curVisited):
            verified = False
            break

        if (l2[i][j] in d1):
            for x in d1[l2[i][j]]:
                curVisited.add(x)

    if (verified):
        midSum += l2[i][len(l2[i]) // 2]
    else:
        part2.append(l2[i])
    curVisited = set()

# print(midSum)
print(part2)

# part 2

visited = set()
midSum2 = 0

def topoSort(visited, curNodes, curNode):
    visited.add(curNode)

    if (curNode not in d2):
        return [curNode]

    res = []
    for node in d2[curNode]:
        if (node in curNodes and node not in visited):
            res = topoSort(visited, curNodes, node) + res

    res.insert(0, curNode)
    return res

midSum2 = 0
for i in range(len(part2)):
    res2 = []
    visited = set()
    nodes = set()
    for j in range(len(part2[i])):
        nodes.add(part2[i][j])

    for j in range(len(part2[i])):
        if (part2[i][j] not in visited):
            res2 = topoSort(visited, nodes, part2[i][j]) + res2

    midSum2 += res2[len(res2) // 2]

print(midSum2)