From 2d8ad6ddcce3421b3a94805e568c02b644989927 Mon Sep 17 00:00:00 2001 From: Oscar Najera Date: Fri, 15 Dec 2023 19:29:51 +0100 Subject: [AoC2023] day12 part1 lisp --- AoC2023/day12/solver.lisp | 72 ++++++++++++++++++++++++++++++----------------- 1 file changed, 46 insertions(+), 26 deletions(-) diff --git a/AoC2023/day12/solver.lisp b/AoC2023/day12/solver.lisp index ce196c9..c93a351 100644 --- a/AoC2023/day12/solver.lisp +++ b/AoC2023/day12/solver.lisp @@ -11,30 +11,50 @@ ????.######..#####. 1,6,5 ?###???????? 3,2,1") +(defun parse-line (line) + (destructuring-bind (row . damage-list) + (cl-ppcre:split "[\\s,]" line) + (cons row (mapcar #'parse-integer damage-list)))) -(destructuring-bind (row . damage-list) - (cl-ppcre:split "[\\s,]" "???.###. 1,1,3") - (setf damage-list (mapcar #'parse-integer damage-list)) - (labels ((options (row-idx damage-group) - (cond - ;; commited to all options - ((= damage-group (length damage-list)) - ;; If still damaged springs are left, then - ;; it was a wrong arrangement, otherwise counts - (if (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)) - (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))) +(defun solve-row (line) + (destructuring-bind (row . damage-list) (parse-line 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))))))) + (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:test solutions + (fiveam:is (= 7090 + (reduce #'+ + (uiop:read-file-lines "input") + :key #'solve-row)))) -- cgit v1.2.3