commit df1d03bd1110063b94c895095dd5b9ea889c728a parent adbeaddc3cfb996a88ca94ee3ef197a98be8d173 Author: Lukas Henkel <lh@entf.net> Date: Tue, 5 Dec 2023 19:44:00 +0100 Better algorithm Diffstat:
| M | src/day-5.lisp | | | 54 | ++++++++++++++++++++++++++++++++++++++++++++---------- |
1 file changed, 44 insertions(+), 10 deletions(-)
diff --git a/src/day-5.lisp b/src/day-5.lisp @@ -21,9 +21,11 @@ (defun parse-maps (input) (loop for header = (read-line input nil) while header - collect (loop for line = (read-line input nil) - while (and line (string/= line "")) - collect (read-number-list line)))) + collect (sort (loop for line = (read-line input nil) + while (and line (string/= line "")) + collect (read-number-list line)) + (lambda (a b) + (< (second a) (second b)))))) (declaim (ftype (function (fixnum list) fixnum) map-number)) (defun map-number (number map) @@ -40,14 +42,46 @@ do (setf n (map-number n map)) finally (return n))) +(defun split-range (range map) + (declare (optimize speed)) + (destructuring-bind (start range-length) + range + (declare (type fixnum start range-length)) + (loop with range-end fixnum = (+ start range-length -1) + for (dest source length) (fixnum fixnum fixnum) in map + while (<= source range-end) + for end-map fixnum = (+ source length -1) + when (< start source) + collect (list start (the fixnum (- source start))) into split-ranges + and do (setf start source) + do (decf length (+ (- start source))) + do (decf length (max (- (the fixnum (+ start length -1)) + range-end) + 0)) + when (>= end-map start) + collect (list (the fixnum (+ dest (- start source))) length) into split-ranges + and do (incf start length) + finally (return (if (< start range-end) + (cons (list start (the fixnum (- range-end start -1))) + split-ranges) + split-ranges))))) + +(defun split-ranges (ranges map) + (loop for range in ranges + nconc (split-range range map))) + +(defun task-2 (ranges maps) + (dolist (map maps) + (setf ranges (split-ranges ranges map))) + (loop for range in ranges + minimize (car range) fixnum)) + (defun day-5 (input) - (let ((seeds (parse-seeds input)) - (maps (parse-maps input))) + (let* ((seeds (parse-seeds input)) + (maps (parse-maps input))) (values (loop for seed in seeds minimize (map-seed seed maps) fixnum) - (loop for (seed-start seed-length) on seeds by #'cddr - minimize (loop for seed from seed-start - repeat seed-length - minimize (map-seed seed maps) fixnum) fixnum - do (format t "Seed range ~A ~A done!~%" seed-start seed-length))))) + (task-2 (loop for (seed-start seed-length) on seeds by #'cddr + collect (list seed-start seed-length)) + maps))))