diff options
Diffstat (limited to 'AoC2023/day12/solver.lisp')
| -rw-r--r-- | AoC2023/day12/solver.lisp | 82 |
1 files changed, 48 insertions, 34 deletions
diff --git a/AoC2023/day12/solver.lisp b/AoC2023/day12/solver.lisp index c93a351..245a188 100644 --- a/AoC2023/day12/solver.lisp +++ b/AoC2023/day12/solver.lisp @@ -16,45 +16,59 @@ (cl-ppcre:split "[\\s,]" line) (cons row (mapcar #'parse-integer damage-list)))) -(defun solve-row (line) - (destructuring-bind (row . damage-list) (parse-line line) +(defun solve-row (parsed-line) + (let ((cache (make-hash-table :test #'equal)) + (row (first parsed-line)) + (damage-list (rest parsed-line))) (labels ((options (row-idx damage-group) - (cond - ;; commited to all options - ((= damage-group (length damage-list)) - ;; If commited to all slots too, is valid option - ;; If still damaged springs are left, then - ;; it was a wrong arrangement, otherwise counts - (cond ((>= row-idx (length row)) 1) - ((find damaged (subseq row row-idx)) 0) - (1))) - ;; Not enough space to fit the current damaged-group - ((< (length row) (+ row-idx (elt damage-list damage-group))) 0) - ;; Probe options. Either commit to a damage-group at row-idx or skip position - (t - (let* ((damaged-count (elt damage-list damage-group)) - (next-slot (+ row-idx damaged-count))) - (+ (if (not (or (find operational (subseq row row-idx next-slot)) - (and (< next-slot (length row)) - (char-equal damaged (aref row next-slot))))) - ;; commits to the damage group, because in condition it has space - ;; Skips one slot, because it checked that it wasn't damaged - (options (1+ next-slot) (1+ damage-group)) - 0) - (if (not (char-equal damaged (aref row row-idx))) - (options (1+ row-idx) damage-group) - 0))))))) + (or (gethash (cons row-idx damage-group) cache) + (setf (gethash (cons row-idx damage-group) cache) + (cond + ;; commited to all options + ((= damage-group (length damage-list)) + ;; If commited to all slots too, is valid option + ;; If still damaged springs are left, then + ;; it was a wrong arrangement, otherwise counts + (cond ((>= row-idx (length row)) 1) + ((find damaged (subseq row row-idx)) 0) + (1))) + ;; Not enough space to fit the current damaged-group + ((< (length row) (+ row-idx (elt damage-list damage-group))) 0) + ;; Probe options. Either commit to a damage-group at row-idx or skip position + (t + (let* ((damaged-count (elt damage-list damage-group)) + (next-slot (+ row-idx damaged-count))) + (+ (if (not (or (find operational (subseq row row-idx next-slot)) + (and (< next-slot (length row)) + (char-equal damaged (aref row next-slot))))) + ;; commits to the damage group, because in condition it has space + ;; Skips one slot, because it checked that it wasn't damaged + (options (1+ next-slot) (1+ damage-group)) + 0) + (if (not (char-equal damaged (aref row row-idx))) + (options (1+ row-idx) damage-group) + 0))))))))) (options 0 0)))) -(solve-row "???.### 1,1,3") - (fiveam:test partial (loop for line in (cl-ppcre:split "\\n" eg-input) for solution in '(1 4 1 1 4 10) do - (fiveam:is (= solution (solve-row line)))) ) + (fiveam:is (= solution (solve-row (parse-line line)))))) + +(defun solve (lines &optional (unfold #'identity)) + (reduce #'+ lines :key (alexandria:compose #'solve-row unfold #'parse-line))) + +(defun unfold-input (repeats) + (lambda (parsed-line) + (destructuring-bind (row . damage-list) parsed-line + (cons (format nil "~{~a~^?~}" (loop repeat repeats collect row)) + (loop repeat repeats append damage-list))))) (fiveam:test solutions - (fiveam:is (= 7090 - (reduce #'+ - (uiop:read-file-lines "input") - :key #'solve-row)))) + (fiveam:is (= 7090 (solve (uiop:read-file-lines "input")))) + (fiveam:is (= 525152 + (solve (cl-ppcre:split "\\n" eg-input) + (unfold-input 5)))) + (fiveam:is (= 6792010726878 + (solve (uiop:read-file-lines "input") + (unfold-input 5))))) |