commit 7cc8e9d818053d66ee14d8f381d953ace100a7f0 parent 18c13061da0c7b642446e64b7dc1a561c3958fc0 Author: Lukas Henkel <lh@entf.net> Date: Sat, 7 Dec 2024 07:37:43 +0100 Much faster recursive solution Diffstat:
| M | src/day-7.lisp | | | 46 | ++++++++++++++++------------------------------ |
1 file changed, 16 insertions(+), 30 deletions(-)
diff --git a/src/day-7.lisp b/src/day-7.lisp @@ -3,18 +3,6 @@ (:export #:day-7)) (in-package #:aoc/day-7) -(defparameter *operators-task-1* '(+ *)) -(defparameter *operators-task-2* '(+ * combine)) - -(defun map-operator-combinations (function length operators) - (labels ((%map (current n) - (if (= n length) - (funcall function current) - (loop with nn = (1+ n) - for operator in operators - do (%map (cons operator current) nn))))) - (%map nil 0))) - (defun number-digits (number) (if (zerop number) 1 @@ -23,29 +11,27 @@ (defun combine (num-1 num-2) (+ (* num-1 (expt 10 (number-digits num-2))) num-2)) -(defun calculate (operators numbers test-value) - (loop with current = (car numbers) - for operator in operators - for next in (cdr numbers) - do (setf current (funcall operator current next)) - when (> current test-value) - do (return current) - finally (return current))) - -(defun test-value-valid-p (test-value numbers operators) - (map-operator-combinations (lambda (operators) - (when (= test-value (calculate operators numbers test-value)) - (return-from test-value-valid-p t))) - (1- (length numbers)) - operators) - nil) +(defun test-value-valid-p (test-value numbers &optional combine-op) + (labels ((%solve (test-value numbers combine-op current) + (if (null numbers) + (= current test-value) + (if (> current test-value) + nil + (or (%solve test-value (cdr numbers) combine-op + (+ current (car numbers))) + (%solve test-value (cdr numbers) combine-op + (* current (car numbers))) + (and combine-op + (%solve test-value (cdr numbers) combine-op + (combine current (car numbers))))))))) + (%solve test-value numbers combine-op 0))) (defun day-7 (input) (loop for line = (read-line input nil) until (null line) for (test-value . numbers) = (read-number-list line) - when (test-value-valid-p test-value numbers *operators-task-1*) + when (test-value-valid-p test-value numbers) sum test-value into task-1 - when (test-value-valid-p test-value numbers *operators-task-2*) + when (test-value-valid-p test-value numbers t) sum test-value into task-2 finally (return (values task-1 task-2))))