Day 5: Print Queue

In today’s task we need to help Elves working in the printer room. They, as per usual, use a very convoluted way to do things and we need to help them figure out which updates are correct. Check out the full back story and problem setup on the official Day 5 of Advent of Code 2024 website.

And here’s the ChatGPT generated graphic to get us started:

Part 1: Determining correct sequences

The first part of the task involves identifying the correct sequence of pages based on a set of given rules. The input consists of two sections:

1. Page Order Instructions: We are provided with a series of strings in the format X|Y, where X represents a page number, and Y is the page number that must follow X (not necessarily directly). These rules define the proper sequence of pages.

2. Page Updates: In this section, a list of page updates is given, each represented as a sequence of page numbers (e.g., X, Z, Y, B). Our objective is to verify whether each update adheres to the rules specified in the first section.

Finally, for all updates that satisfy the rules, we identify the middle page number in each valid sequence and compute the sum of these middle values.

Setting up

from misc.helper import verify_answer

example_input_file = "../inputs/example_day_05.txt"
input_file = "../inputs/day_05.txt"

from pathlib import Path
from typing import Tuple


def parse_input(input) -> Tuple[dict[int: int], list[int]]:
    if Path(input).exists():
        with open(input, "r") as file:
            input = file.read()

    rules = {}
    updates = []

    for line in input.splitlines():
        line = line.strip()
        if line == "":
            continue
        if "|" in line:
            b, a = map(int, line.split("|"))
            rules[b] = rules.get(b, []) + [a]
        else:
            updates.append(list(map(int, line.split(","))))

    return rules, updates

small_example = """
0|1
3|4
0|6

1,2,3
6,1,0
"""
parse_input(small_example)

({0: [1, 6], 3: [4]}, [[1, 2, 3], [6, 1, 0]])

def check_correctness(rules, updates):
    def is_correct(update):
        for i in range(len(update)):
            test_value = rules.get(update[i], [])
            for value in test_value:
                if value in update[:i]:
                    return False
        return True

    return [update for update in updates if is_correct(update)]


check_correctness(*parse_input(small_example))

[[1, 2, 3]]

def get_middle_value(seq) -> int:
    return seq[len(seq) // 2]


def part_one(input):
    rules, updates = parse_input(input)
    correct_updates = check_correctness(rules, updates)
    middle_values = [get_middle_value(update) for update in correct_updates]
    return sum(middle_values)

verify_answer(part_one, example_input_file, 143)

✔️ That's right! The answer is 143.

%time
part_one(input_file)

CPU times: user 2 μs, sys: 1 μs, total: 3 μs
Wall time: 5.96 μs

4281

That’s the right answer! You are one gold star ⭐ closer to finding the Chief Historian.

Part 2: Fixing the weird printer

In this part, we need to fix the sequences according to the rules. I first tried a solution with a graph, but this wasn’t working since the rules are not a DAG (as was also noticed by u/timrprobocom). Instead, I decided to implement a solution that would iteratively fix the sequence by popping the offending value to the right of the tested one.

First, I need to identify the incorrect sequences.

def check_incorrectness(rules, updates):
    def is_incorrect(update):
        for i in range(len(update)):
            test_values = rules.get(update[i], [])
            for value in test_values:
                if value in update[:i]:
                    return True
        return False

    return [update for update in updates if is_incorrect(update)]


check_incorrectness(*parse_input(example_input_file))

[[75, 97, 47, 61, 53], [61, 13, 29], [97, 13, 75, 29, 47]]

And then implement fixing the sequences by moving the offending value to the right of the tested one.

def fix_sequence(rules: dict, sequence):
    while True:
        made_changes = False

        for i in range(len(sequence)):
            checks = rules.get(sequence[i], [])
            for check in checks:
                if check in sequence[:i]:
                    check_index = sequence.index(check)
                    offending_value = sequence.pop(check_index)
                    sequence.insert(i, offending_value)
                    made_changes = True
                    break

            if made_changes:
                break

        if not made_changes:
            break

    return sequence


fix_sequence({1: [0], 2: [1, 0]}, [2, 0, 1])

[2, 1, 0]

def part_two(input):
    rules, updates = parse_input(input)
    incorrect_updates = check_incorrectness(rules, updates)
    fixed_updates = [
        fix_sequence(rules, update) for update in incorrect_updates
    ]

    return sum(get_middle_value(update) for update in fixed_updates)

verify_answer(part_two, example_input_file, 123)

✔️ That's right! The answer is 123.

%time
part_two(input_file)

CPU times: user 3 μs, sys: 1 μs, total: 4 μs
Wall time: 5.96 μs

5466

That’s the right answer! You are one gold star ⭐ closer to finding the Chief Historian.