from copy import deepcopy
with open('data-2024-05.txt', 'r') as f:
inp = f.read().splitlines()
splitter = inp.index('')
orders = inp[:splitter]
updates = inp[splitter+1:]
orders = [x.split('|') for x in orders]
updates = [x.split(',') for x in updates]
# orders
# updatesAdvent of Code 2024 Day 5
— Day 5: Print Queue —
Follow the rules for the printing order.
Determine which updates are already in the correct order. What do you get if you add up the middle page number from those correctly-ordered updates?
Loop through each of the updates and check that the orders are OK.
summer = 0
for u in updates:
good = True
for o in orders:
if o[0] in u and o[1] in u:
if u.index(o[0]) < u.index(o[1]):
# print(o)
# print('good')
pass
else:
# print('bad')
good = False
break
# print(good)
# if we get through ok the order of printing ok
if good:
summer += int(u[int(len(u)/2)])
summer
# 52085208— Part Two —
For the incorrectly ordered updates maybe we can re-order them.
Find the updates which are not in the correct order. What do you get if you add up the middle page numbers after correctly ordering just those updates?
summer = 0
for u in updates:
good = True
for o in orders:
if o[0] in u and o[1] in u:
if u.index(o[0]) > u.index(o[1]):
good = False
# print(u)
# print(o)
# create a new list
u = (u[:u.index(o[1])]
+ [o[0]]
+ u[u.index(o[1])+1:u.index(o[0])]
+ [o[1]]
+ u[u.index(o[0])+1:])
if not good:
# get the middle value after making adjustments
summer += int(u[int(len(u)/2)])
summer
# 6463 too low6463So, I don’t want to go through and swap the items, I need to do an ordering algorithm comparing sequential values according to the order list. The alternative is creating a sort order and then looping more simply through each list. As below, the sets are the same, so we can go either way.
all_u = set([v for u in updates for v in u])
all_u
all_o = set([p for o in orders for p in o])
all_o
all_o == all_uTrueAttempt 1: create an ‘ordered’ list from the orders and use that as a key for sorting the updates.
list_o = list(all_o)
printer = False
for i in range(0, len(list_o)-1):
if [list_o[i], list_o[i+1]] not in orders:
# swap the order
list_o[i], list_o[i+1] = list_o[i+1], list_o[i]
# check backwards
for j in range(i-1,-1,-1):
if [list_o[j], list_o[j+1]] not in orders:
list_o[j], list_o[j+1] = list_o[j+1], list_o[j]
list_o['37',
'88',
'18',
'85',
'97',
'35',
'55',
'71',
'65',
'69',
'12',
'83',
'76',
'49',
'92',
'39',
'89',
'62',
'22',
'74',
'99',
'96',
'25',
'33',
'95',
'84',
'42',
'17',
'61',
'19',
'43',
'16',
'11',
'82',
'59',
'31',
'68',
'91',
'79',
'75',
'32',
'77',
'45',
'41',
'81',
'67',
'63',
'44',
'73']Let’s check the inputs. Something is not right here.
left = {}
right = {}
for o in orders:
if o[0] in left.keys():
left[o[0]] += 1
else:
left[o[0]] = 1
if o[1] in right.keys():
right[o[1]] += 1
else:
right[o[1]] = 1
left
right{'62': 24,
'17': 24,
'83': 24,
'68': 24,
'22': 24,
'16': 24,
'12': 24,
'74': 24,
'18': 24,
'37': 24,
'25': 24,
'95': 24,
'76': 24,
'77': 24,
'44': 24,
'41': 24,
'42': 24,
'92': 24,
'32': 24,
'91': 24,
'88': 24,
'67': 24,
'31': 24,
'81': 24,
'63': 24,
'19': 24,
'89': 24,
'11': 24,
'73': 24,
'97': 24,
'79': 24,
'65': 24,
'82': 24,
'96': 24,
'49': 24,
'85': 24,
'75': 24,
'35': 24,
'69': 24,
'33': 24,
'55': 24,
'99': 24,
'43': 24,
'45': 24,
'84': 24,
'71': 24,
'59': 24,
'39': 24,
'61': 24}Oh. The orders are symmetric, or something? They all appear an equal amount of times on the left and right. I can’t create a nice thing from the orders that covers all the updates.
Some other statistics
counters = {}
for u in updates:
u_len = len(u)
if u_len in counters.keys():
counters[u_len] += 1
else:
counters[u_len] = 1
counters{23: 20, 21: 24, 15: 20, 17: 17, 11: 22, 9: 22, 7: 21, 5: 7, 13: 25, 19: 25}This is good, and maybe something I should have confirmed before, but all of them are odd lengths, which means they have a middle value. They are also 23 or fewer, which means we have less than half the numbers and no cycles of dependencies. Let’s get the bad update lists
bad_u = []
for u in updates:
for o in orders:
if o[0] in u and o[1] in u:
if u.index(o[0]) < u.index(o[1]):
pass
else:
bad_u.append(u)
break
# bad_u
len(bad_u)
len(updates)203111/203 are bad updates.
I like the idea of looping through each of the bad update lists, and constructing a new list from scratch, starting with the first found order, and inserting the numbers in the correct place in the list. I think. This really assumes that these lists will be internally consistent.
summer = 0
for u in bad_u:
# we are now operating on a single list u
# construct a good update page list
good_u = []
for x in u:
# find the correct place for each element to go
# this feels like a recursive function, almost
if len(good_u) == 0:
good_u.append(x)
# print('start')
else:
found = False
for i in range(len(good_u)):
# go through the current good list
# try to place the next piece, x
if [x, good_u[i]] in orders:
good_u = good_u[:i] + [x] + good_u[i:]
found = True
break
# good_u
if not found:
good_u = good_u + [x]
# get the middle value after placing the pieces
summer += int(good_u[int(len(good_u)/2)])
summer
# 67326732