commit 02ba895db62e5ef212bd779b132e43063548174b parent d6d76c2348e12e43bf9488048af3427a304053dd Author: Lukas Henkel <lh@entf.net> Date: Sat, 9 Dec 2023 08:49:31 +0100 Optimize day 9 - Iterative algorithm - Reduce looping Diffstat:
| M | src/day-9.lisp | | | 44 | +++++++++++++++++++++++++++++++------------- |
1 file changed, 31 insertions(+), 13 deletions(-)
diff --git a/src/day-9.lisp b/src/day-9.lisp @@ -3,20 +3,38 @@ (:export #:day-9)) (in-package #:aoc/day-9) -(defun find-next-value (numbers) - (let ((new-sequence (loop with last = (first numbers) - for number in (rest numbers) - collect (- number last) - do (setf last number)))) - (if (every (curry #'= 0) new-sequence) - (first numbers) - (+ (lastcar numbers) - (find-next-value new-sequence))))) - (defun day-9 (input) - (loop for line = (read-line input nil) + (loop with task-1 fixnum = 0 + with task-2 fixnum = 0 + for line = (read-line input nil) while line for numbers = (read-number-list line) - sum (find-next-value numbers) into task-1 fixnum - sum (find-next-value (nreverse numbers)) into task-2 fixnum + do (loop with sequences = (list (cons (car numbers) + (lastcar numbers))) + with current = numbers + with current-last = 0 + for non-zero? = nil + do (setf current + (loop with last fixnum = (first current) + for number fixnum in (rest current) + for n = (the fixnum (- number last)) + unless (xor non-zero? + (zerop n)) + do (setf non-zero? t) + collect n + do (setf last number) + finally (setf current-last n))) + do (push (cons (car current) + current-last) + sequences) + while non-zero? + finally (progn + (loop with next-1 fixnum = 0 + with next-2 fixnum = 0 + for current in (rest sequences) + do (setf next-1 (+ (the fixnum (cdr current)) next-1) + next-2 (- (the fixnum (car current)) next-2)) + finally (progn + (incf task-1 next-1) + (incf task-2 next-2))))) finally (return (values task-1 task-2))))