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