advent-of-code-2023

commit c1af0e38b7b56e77082a3f44eaa249842a057535
parent c3dc0bc1b9d10e1cb15b5e7b3de92896523afbb5
Author: Lukas Henkel <lh@entf.net>
Date:   Thu, 14 Dec 2023 07:58:30 +0100

Day 14 task 2

Diffstat:
M
src/day-14.lisp
 | 
29
++++++++++++++++++++++++++---
M
src/utils.lisp
 | 
11
++++++++++-
M
t/day-14.lisp
 | 
8
+++++---

3 files changed, 41 insertions(+), 7 deletions(-)
diff --git a/src/day-14.lisp b/src/day-14.lisp
@@ -1,6 +1,8 @@
 (defpackage #:aoc/day-14
   (:use #:cl #:aoc/utils)
-  (:export #:day-14))
+  (:export
+   #:day-14
+   #:*minimum-pattern-length*))
 (in-package #:aoc/day-14)
 
 (defun point-x-constructor (y)
@@ -90,7 +92,28 @@
                   when (char= (map-cell map (cons x y)) #\O)
                     sum load-multiplier)))
 
+(defun spin-cycle (map &optional (cycle '(:north :west :south :east)))
+  (loop for direction in cycle
+        do (slide-rocks map direction)))
+
+(defparameter *minimum-pattern-length* 100)
+
 (defun day-14 (input)
-  (let ((map (make-map input)))
+  (let ((map (make-map input))
+        task-1 task-2)
     (slide-rocks map :north)
-    (total-load map)))
+    (setf task-1 (total-load map))
+    (spin-cycle map '(:west :south :east))
+    (loop with history = nil
+          for cycles from 1
+          do (spin-cycle map)
+          do (push (total-load map) history)
+          do (let ((pattern-length (find-pattern history *minimum-pattern-length*)))
+               (when pattern-length
+                 (setf task-2
+                       (elt history
+                            (1+ (- pattern-length
+                                   (- (mod 1000000000 pattern-length)
+                                      (- cycles (* pattern-length 2)))))))
+                 (return))))
+    (values task-1 task-2)))
diff --git a/src/utils.lisp b/src/utils.lisp
@@ -20,7 +20,8 @@
    #:point-neighbours
    #:manhattan-distance
    #:do-map-neighbours
-   #:read-number-list))
+   #:read-number-list
+   #:find-pattern))
 (in-package #:aoc/utils)
 
 (defun normalize-type (type)
@@ -196,3 +197,11 @@
                                    :junk-allowed t)
                   (setf i end)
                   number)))
+
+(defun find-pattern (list &optional (minimum-length 5))
+  (loop for length from minimum-length to (floor (/ (length list) 2))
+        when (loop for i below length
+                   for c-1 = (elt list i)
+                   for c-2 = (elt list (+ i length))
+                   always (= c-1 c-2))
+          do (return-from find-pattern length)))
diff --git a/t/day-14.lisp b/t/day-14.lisp
@@ -4,8 +4,9 @@
 
 (define-test test-day-14
     ()
-  (multiple-value-bind (task-1)
-      (aoc:run-day 14 "O....#....
+  (let ((aoc/day-14:*minimum-pattern-length* 5))
+    (multiple-value-bind (task-1 task-2)
+        (aoc:run-day 14 "O....#....
 O.OO#....#
 .....##...
 OO.#O....O
@@ -15,4 +16,5 @@ O.#..O.#.#
 .......O..
 #....###..
 #OO..#....")
-    (assert= 136 task-1)))
+      (assert= 136 task-1)
+      (assert= 64 task-2))))