Advent of Code 2024, Day 5

For part 2, a simple bubble sort is fast enough for the input size and easy to implement on the spot. I think many lost time trying to come up with a more complicated sorting algorithm with parametrized predicate checks.

Part 1 (0.07 seconds)

import sys

def check(xs, rules):
    for (x, y) in rules:
        if x in xs and y in xs and xs.index(x) > xs.index(y):
            return False
    return True

rules = []
s = 0
with open(sys.argv[1]) as f:
    for line in f:
        line = line.strip()
        if "|" in line:
            x, y = line.split("|")
            x, y = int(x), int(y)
            rules.append((x, y))
        elif "," in line:
            xs = line.split(",")
            xs = [int(x) for x in xs]
            if check(xs, rules):
                s += xs[len(xs)//2]
print(s)

Part 2 (0.3 seconds)

import sys

def check(xs, rules):
    for (x, y) in rules:
        if x in xs and y in xs and xs.index(x) > xs.index(y):
            return False
    return True

def bubblesort(xs, rules):
    for j in range(len(xs)):
        for i in range(len(xs)-j-1):
            if (xs[i+1], xs[i]) in rules:
                xs[i], xs[i+1] = xs[i+1], xs[i]
    assert check(xs, rules)

rules = []
s = 0
with open(sys.argv[1]) as f:
    for line in f:
        line = line.strip()
        if "|" in line:
            x, y = line.split("|")
            x, y = int(x), int(y)
            rules.append((x, y))
        elif "," in line:
            xs = line.split(",")
            xs = [int(x) for x in xs]
            if not check(xs, rules):
                bubblesort(xs, rules)
                s += xs[len(xs)//2]
print(s)

2024-12-26