advent-of-code-2024

commit 9320fac455489ef7263b15f3a6336c7ed34a7934
parent 7bd93562fa1827db036c3b25cfe787b809b12669
Author: Lukas Henkel <lh@entf.net>
Date:   Wed, 11 Dec 2024 06:53:40 +0100

Day 11

Diffstat:
A
input/11.txt
 | 
1
+
A
src/day-11.lisp
 | 
42
++++++++++++++++++++++++++++++++++++++++++
A
t/day-11.lisp
 | 
11
+++++++++++

3 files changed, 54 insertions(+), 0 deletions(-)
diff --git a/input/11.txt b/input/11.txt
@@ -0,0 +1 @@
+337 42493 1891760 351136 2 6932 73 0
diff --git a/src/day-11.lisp b/src/day-11.lisp
@@ -0,0 +1,42 @@
+(defpackage #:aoc/day-11
+  (:use #:cl #:aoc/utils)
+  (:export #:day-11))
+(in-package #:aoc/day-11)
+
+(declaim (inline number-of-digits)
+         (ftype (function (fixnum) fixnum) number-of-digits))
+
+(defun number-of-digits (number)
+  (floor (1+ (log number 10))))
+
+(defun blink (stones target-depth)
+  (let ((memo (make-hash-table :test #'equal)))
+    (labels ((%blink (stone depth)
+               (when (= depth target-depth)
+                 (return-from %blink 1))
+               (let ((num-digits (or (zerop stone)
+                                     (number-of-digits stone)))
+                     (new-depth (1+ depth)))
+                 (cond
+                   ((zerop stone)
+                    (%blink-memo 1 new-depth))
+                   ((evenp num-digits)
+                    (let ((divisor (expt 10 (/ num-digits 2))))
+                      (multiple-value-bind (left right)
+                          (floor stone divisor)
+                        (+ (%blink-memo left new-depth)
+                           (%blink-memo right new-depth)))))
+                   ((oddp num-digits)
+                    (%blink-memo (* stone 2024) new-depth)))))
+             (%blink-memo (stone depth)
+               (let ((key (list stone depth)))
+                 (or (gethash key memo)
+                     (setf (gethash key memo)
+                           (%blink stone depth))))))
+      (loop for stone in stones
+            sum (%blink-memo stone 0)))))
+
+(defun day-11 (input)
+  (let ((stones (read-number-list (read-line input))))
+    (values (blink stones 25)
+            (blink stones 75))))
diff --git a/t/day-11.lisp b/t/day-11.lisp
@@ -0,0 +1,11 @@
+(defpackage #:aoc-test/day-11
+  (:use #:cl #:lisp-unit2)
+  (:import-from #:aoc/day-11))
+(in-package #:aoc-test/day-11)
+
+(define-test test-day-11
+    ()
+  (multiple-value-bind (task-1 task-2)
+      (aoc:run-day 11 "125 17")
+    (assert= 55312 task-1)
+    (assert= 65601038650482 task-2)))