(ql:quickload '(fiveam str arrows))

(defparameter damaged #\#)
(defparameter operational #\.)
(defparameter unknown #\?)

(defparameter eg-input "???.### 1,1,3
.??..??...?##. 1,1,3
?#?#?#?#?#?#?#? 1,3,1,6
????.#...#... 4,1,1
????.######..#####. 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))))

(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)
               (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))))

(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 (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 (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)))))