Advent of Code 2024 - Day 5: Print Queue
Attention!
-
Check Advent of Code for the full challenge details. They created everything we need to know about the challenge - give them your support.
-
My solutions are not ‘the’ solutions - I target one of the possible solutions. They might not be the most efficient, but they are a way to solve the problem. I do not plan to spend too much time doing the challenges.
-
Every challenge = different language - just for fun and learning.
-
I do not include the input data, but you can find it on the Advent of Code website or in the repository of the code.
In today’s challenge, I’ve been tasked with assisting an Elf at the North Pole printing department, where they are facing a problem with the printing order of safety manuals. Each manual requires specific page numbers to be printed in a particular order, and my job is to figure out which updates are already in the correct order and to reorder the ones that are not.
The problem revolves around ensuring the correct sequence of pages during updates. The input consists of page ordering rules and updates, where each update involves several pages, and I need to verify if they are in the correct order according to the rules.
The solution for today’s challenge will be implemented in PHP.
Part One: Checking the Page Order
In Part One, I was given a list of page ordering rules, such as 47|53, which means that if both pages 47 and 53 are part of an update, 47 must be printed somewhere before 53. Additionally, I was given a list of updates, each of which contains several page numbers that need to be printed. I need to determine which updates are already in the correct order based on the given rules.
The task here is simple: for each update, check if the pages are printed in the correct order, considering the rules provided. Then I need to calculate the sum of the middle page numbers for the updates that are in the correct order.
To solve this, I wrote a function that loops through each update and checks whether each pair of pages is in the correct order according to the given rules.
Example input
39|57
31|97
31|75
29|45
78,45,48,38,52,62,29
87,59,38,52,25,55,79,42,34,85,37,26,13,64,65,33,68
57,29,84,48,45,75,11,14,76,73,69,16,38,23,22
Let’s start with a little function that read the input file and returns the rules and updates.
// main.php
function read_rules_and_updates($filename) {
$lines = explode("\n", file_get_contents($filename));
$rules = [];
$updates = [];
foreach ($lines as $line) {
if (str_contains($line, "|")) {
$rule = explode("|", $line);
$rules["$rule[0]|$rule[1]"] = true;
} else if (str_contains($line, ",")) {
$updates[] = explode(",", $line);
}
}
return [$rules, $updates];
}
It could be better of course, but it really does not need to for this challenge.
I included this function to demonstrate what $rules and $updates look like (used later).
Code for Part One
The part_one function calculates the sum of the middle page numbers for the updates that are in the correct order.
This is all we need to solve Part One of the challenge.
// main.php
function part_one($rules, $updates) {
$sum = 0;
$cache = [];
foreach ($updates as $update) {
if (is_update_correct($rules, $update, $cache)) {
$sum += $update[floor(count($update) / 2)];
}
}
return $sum;
}
To know if an update is correct I’ve implemented a function is_update_correct which iterates through each update and verifies whether all the pages are in the right order based on the rules. If any page pair is found to be out of order, it returns false.
// main.php
function is_update_correct($rules, $update, &$cache) {
$update_str = implode(",", $update);
if (isset($cache[$update_str])) return $cache[$update_str];
for ($i = 0; $i < count($update) - 1; $i++) {
for ($j = $i + 1; $j < count($update); $j++) {
$rule = find_rule_for_update($rules, $update, $i, $j);
if ($rule === null || $rule[0] !== $update[$i] || $rule[1] !== $update[$j]) {
$cache[$update_str] = false;
return false;
}
}
}
$cache[$update_str] = true;
return true;
}
There I used another helper function find_rule_for_update to find the rule for a given pair of pages in an update.
function find_rule_for_update($rs, $update, $i, $j) {
if ($j >= count($update) || $i == $j) return null;
if (isset($rs["$update[$i]|$update[$j]"])) {
return [$update[$i], $update[$j]];
} else if (isset($rs["$update[$j]|$update[$i]"])) {
return [$update[$j], $update[$i]];
}
return null;
}
The is_update_correct function is already optimized by using a cache to store the results for each update. This way, I can avoid recalculating the same update multiple times.
Part Two: Reordering the Pages
In Part Two, the task is to reorder the incorrectly ordered updates. Once I find which updates are in the wrong order, I use the rules to sort the pages correctly. After sorting, I need to find the middle page number in each update and calculate the sum of these numbers.
The approach for Part Two is similar to Part One, but I need to implement a reordering function that fixes the order for the updates that aren’t correct.
Code for Part Two
The part_two function works similarly to part_one, but skips the updates that are already in the correct order. For the updates that are out of order, it calls the reorder_update function to reorder the pages and calculate the sum of the middle page numbers.
// main.php
function part_two($rules, $updates) {
$sum = 0;
$cache = [];
foreach ($updates as $update) {
if (is_update_correct($rules, $update, $cache)) continue;
$new_update = reorder_update($rules, $update, $cache);
$sum += $new_update[floor(count($new_update) / 2)];
}
return $sum;
}
Here I needed to implement the reorder_update which was the most challenging part of this solution.
I rewrote this function a few times to make it more efficient and avoid unnecessary swaps.
The reorder_update function iterates over each update and swaps the pages and rechecks the order.
It uses a cache to store the results for each update, which helps avoid recalculating the same update multiple times.
// main.php
function reorder_update($rules, $update, &$cache) {
$update_str = implode(",", $update);
if (isset($cache[$update_str]) && $cache[$update_str]) return $update;
$new_update = $update;
$swapped = true;
while ($swapped) {
$swapped = false;
for ($i = 0; $i < count($new_update) - 1; $i++) {
for ($j = $i + 1; $j < count($new_update); $j++) {
$rule = find_rule_for_update($rules, $new_update, $i, $j);
if ($rule === null) continue;
if ($rule[0] != $new_update[$i] || $rule[1] != $new_update[$j]) {
$temp = $new_update[$i];
$new_update[$i] = $new_update[$j];
$new_update[$j] = $temp;
$swapped = true;
break;
}
}
if ($swapped) break;
}
}
$cache[$update_str] = true;
return $new_update;
}
And that’s it! I have implemented the solution for both parts of the challenge.
Solution Breakdown
After implementing these functions, I ran the program and got the results for both parts:
- Part One: I calculated the sum of the middle page numbers for the correctly ordered updates.
- Part Two: I reordered the incorrectly ordered updates and then calculated the sum of their middle page numbers.
// main.php
[$rules, $updates] = read_rules_and_updates("input.txt");
echo "Part one: " . part_one($rules, $updates) . "\n";
echo "Part two: " . part_two($rules, $updates) . "\n";
Final Solution Code
The final solution code can be found on my GitHub repository.
If you like the content, don’t forget to give it a star ⭐.
part_one:
- Time Complexity: O(U * n^2), where U is the number of updates and n is the average size of an update. This is because, for each update, it checks all pairs within the update (which involves O(n^2) operations), and this process repeats for every update.
- Space Complexity: O(U * n), where U is the number of updates and n is the average size of an update. The cache stores results for each unique update (in worst case, all updates will be stored).
part_two:
- Time Complexity: O(U * n^2), for similar reasons as
part_one, because for each update, I’m checking all pairs and potentially fixing them with additional swaps. - Space Complexity: O(U * n), as in
part_one, because the cache will store each update’s validity and any updates that have been fixed.
Conclusion
This challenge was a fun one, and I enjoyed solving it. The problem was interesting, and I had to think about how to optimize the solution to avoid recalculating the same updates multiple times.
I did not use a PHP before, but I found it quite easy to work with. It will not be my first choice for anything, but I think I could use it when needed.
I hope you enjoyed this solution and learned something new. Stay tuned for the next challenges!
Tomorrow I will be solving the Day 6 challenge using Rust.