#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);