From d7c6cfc828feda16797f9fdeddcf4317e092457b Mon Sep 17 00:00:00 2001
From: Jordan Doyle <jordan@doyle.la>
Date: Sat, 07 Dec 2024 19:22:46 +0000
Subject: [PATCH] Add 2024 day 5

---
 README      |  4 ++--
 2024/05.php | 73 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 75 insertions(+), 2 deletions(-)

diff --git a/README b/README
index 17ee834..05114d6 100644
--- a/README
+++ a/README
@@ -18,8 +18,8 @@
 |        2 | OCaml    | |        2 | Haskell  | |        2 | Nix      |
 |        3 | Perl     | |        3 | Haskell  | |        3 | Clojure  |
 |        4 | Rust     | |        4 | Haskell  | |        4 | Jsonnet  |
-+---------------------+ |        5 | Rust     | |        5 | HCL/TF   |
-                        |        6 | Haskell  | |        6 | Apache2  |
+|        5 | PHP      | |        5 | Rust     | |        5 | HCL/TF   |
++---------------------+ |        6 | Haskell  | |        6 | Apache2  |
                         |        7 | Haskell  | +---------------------+
                         |        8 | Haskell  |
                         |        9 | Haskell  |
diff --git a/2024/05.php b/2024/05.php
new file mode 100755
index 0000000..5e30c4f 100755
--- /dev/null
+++ a/2024/05.php
@@ -1,0 +1,73 @@
+#!/usr/bin/env nix-shell
+<?php
+#!nix-shell -i php -p php
+$i = stream_get_contents(STDIN);
+[$rules, $prints] = explode("\n\n", trim($i));
+
+$dependencies = [];
+$dependents = [];
+$parsedPrints = [];
+
+foreach (explode("\n", $rules) as $rule) {
+    [$dependency, $dependent] = explode("|", $rule);
+    $dependencies[$dependent][] = $dependency;
+    $dependents[$dependency][] = $dependent;
+}
+
+foreach (explode("\n", $prints) as $print) {
+    $print = explode(',', $print);
+
+    foreach ($print as $item) {
+        if (!isset($dependencies[$item])) $dependencies[$item] = [];
+    }
+    
+    $parsedPrints[] = $print;
+}
+
+$part1 = 0;
+$incorrectlySorted = [];
+
+foreach ($parsedPrints as $printItems) {
+    for ($i = 0; $i < count($printItems); $i++) {
+        $ourDependencies = $dependencies[$printItems[$i]] ?? [];
+        $matchedDependencies = array_intersect($ourDependencies, $printItems);
+
+        $beforeMe = array_slice($printItems, 0, $i);
+        $dependenciesBeforeMe = array_intersect($matchedDependencies, $beforeMe);
+
+        if ($matchedDependencies != $dependenciesBeforeMe) {
+            $incorrectlySorted[] = $printItems;
+            continue 2;
+        }
+    }
+
+    $part1 += $printItems[(count($printItems) - 1) / 2];
+}
+
+var_dump($part1);
+
+$part2 = 0;
+
+foreach ($incorrectlySorted as $printItems) {
+    $remainingDependencies = array_map(fn ($v) => count(array_intersect($v, $printItems)), $dependencies);
+    $queue = array_keys(array_filter($remainingDependencies, fn ($c) => $c == 0));
+    $sortedPages = [];
+
+    while (!empty($queue)) {
+        $current = array_shift($queue);
+        $sortedPages[] = $current;
+
+        foreach ($dependents[$current] ?? [] as $dependent) {
+            $remainingDependencies[$dependent]--;
+            if ($remainingDependencies[$dependent] == 0) {
+                $queue[] = $dependent;
+            }
+        }
+    }
+
+    $sortedPrintItems = array_values(array_filter($sortedPages, fn($item) => in_array($item, $printItems)));
+    $part2 += $sortedPrintItems[(count($sortedPrintItems) - 1) / 2];
+}
+
+var_dump($part2);
+
--
rgit 0.1.5