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
|
#advent of code 2024
#day 05
#cool, but seemed harder on first glance
#part1: keep looking up the rules for each page in an update
#if any of the pages in rules are present before the current page
#then the update is incorrect, else add the middle page to part1 score
#part2: keep correcting the order until each rule is satisfied
#popping the incorrectly placed page, then inserting it at the index
#of the page violating the rule
#edit: apparently there's a cycle in the rules which may lead to inifite
#corrections, but in my solution, or at least for my input, that isnt the case
f = open("05.in","r");
r, u = f.read().split("\n\n"); #rules and updates
f.close();
rules, updates = {}, [];
part1 = 0;
part2 = 0;
for l in r.split("\n"):
v1, v2 = [int(x) for x in l.split("|")];
if not v1 in rules: rules[v1] = [];
rules[v1].append(v2);
for l in u.split("\n")[:-1]: #skipping last line because its reading an empty line
updates.append([int(x) for x in l.split(",")]);
def Verify(update):
ok = True;
for x, page in enumerate(update):
if page in rules:
for rule in rules[page]:
if rule in update[0:x]: ok = False;
return ok*update[len(update)//2];
def correction(update):
NewUpdate = update.copy();
ok = False;
while not ok:
ok = True;
for x, page in enumerate(NewUpdate):
if page in rules:
for y in range(x,-1,-1):
if NewUpdate[y] in rules[page]:
ok = False;
NewUpdate.pop(x);
NewUpdate.insert(y, page);
break;
return NewUpdate[len(NewUpdate)//2];
for update in updates:
score = Verify(update);
part1 += score;
if score == 0: part2 += correction(update);
print("part 1 =", part1);
print("part 2 =", part2);
|
