1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
|
(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)))))
|
