Advent of Code 2024 Day 5 - Shaurya's website

Once again, I am using Python.

Setup

I read the input file into a string, parse that string, then pass the parsed string into my part 1 and part 2 functions and display their outputs.

inp = open("input.txt", "r").read()
parsed = parse_input(inp)
print(f"Part 1: {part1(parsed)}")
print(f"Part 2: {part2(parsed)}")

Parsing

The input has two parts: a set of rules to determine the order of page numbers, and a set of lists of page numbers (called updates in the text).

I split the input into two parts, then use nested list comprehensions to convert both parts into lists of collections of numbers.

def parse_input(inp):
    rules_s, updates_s = inp.split("\n\n", maxsplit=1)
    rules = [
        tuple([int(num) for num in line.split("|")]) for line in rules_s.splitlines()
    ]
    updates = [
        [int(num) for num in line.split(',')] for line in updates_s.splitlines()
    ]
    return rules, updates

Part One

We need to find the all the updates that are sorted according to the rules, then add up all the middle page numbers of those updates.

My code makes the (luckily correct) assumption that the list of ordering rules will include all the possible pairs of page numbers found in the updates. The problem would be much harder to solve if the rules weren’t complete like that and I would have had to consider how to transitively apply the rules.

def part1(parsed):
    rules, updates = parsed
    ans = 0
    for update in updates:
        valid = True
        for i in range(len(update)-1):
            if (update[i], update[i+1]) not in rules:
                valid = False
                break
        if valid:
            ans += update[len(update)//2]
    return ans

Part Two

Now, we need to sort all the unsorted updates and then add up their post-sorting middle page numbers. My code is very similar to part 1, with the addition of a sort function that I translated into Python from the pseudocode on Wikipedia’s insertion sort page.

def part2(parsed):
    rules, updates = parsed
    ans = 0
    for update in updates:
        valid = True
        for i in range(len(update)-1):
            if (update[i], update[i+1]) not in rules:
                valid = False
                break
        if not valid:
            insertion_sort(update, rules)
            ans += update[len(update)//2]
    return ans
    pass

def insertion_sort(l, rules):
    for i in range(1, len(l)):
        j = i
        while j > 0 and (l[j], l[j-1]) in rules:
            l[j], l[j-1] = l[j-1], l[j]
            j -= 1