Advent of Code '23 - day 12

Table of Contents

Part 1 takes way too long to generate an answer, so I'll really have to rewrite my solution for part 2… I did learn the rx macro with this one though, which is pretty nice. I'll skip part 2 for now, maybe come back to it later.

Input

Example

???.### 1,1,3
.??..??...?##. 1,1,3
?#?#?#?#?#?#?#? 1,3,1,6
????.#...#... 4,1,1
????.######..#####. 1,6,5
?###???????? 3,2,1

Part 1

(defun aoc23/convert-input (line)
  (let* ((segs (string-split line " " t))
         (springs (car segs))
         (checks (cadr segs)))
    (list (cons 'low (aoc23/springs-to-number springs 'low))
          (cons 'high (aoc23/springs-to-number springs 'high))
          (cons 'candidates (aoc23/springs-to-candidates springs))
          (cons 'pattern (aoc23/checks-to-pattern checks)))))

(defun aoc23/springs-to-candidates (springs)
  (let ((i nil)
      (m nil)
      (c nil)
      (b 0)
      (base 0))

  (while (setq i (string-match (rx "?") (reverse springs) (if i (1+ i) 0)))
    (setq m (cons (lsh 1 i) m)))
  (setq i nil)
  (while (setq i (string-match (rx "#") (reverse springs) (if i (1+ i) 0)))
    (setq base (logior base (lsh 1 i))))
  (cons base (build-patterns m base))))

(defun build-patterns (candidates base)
  (let ((m candidates)
        (out '()))
    (while m
      (let ((n (logior base (car m))))
        (setq m (cdr m))
        (setq out (cons n out))
        (when m
          (setq out (append out (build-patterns m n))))
      ))
    out))

(defun aoc23/springs-to-number (in low)
  (let* ((in (string-replace "?" (if (eq low 'low) "#" ".") in))
         (in (string-replace "." "0" in))
         (in (string-replace "#" "1" in)))
    (string-to-number in 2)))

(defun aoc23/checks-to-pattern (check)
  (let ((c (mapcar 'string-to-number (split-string check "," t)))
        (matches '()))
    (apply 'concat `("^0*" 
                     ,(string-join 
                       (mapcar (lambda (n)
                                 (format "1\\{%d\\}" n))
                               c)
                       "0+")
                     "0*$"))))

(defun int-to-binary-string (i)
  "convert an integer into it's binary representation in string format"
  (let ((res ""))
    (while (not (= i 0))
      (setq res (concat (if (= 1 (logand i 1)) "1" "0") res))
      (setq i (lsh i -1)))
    (if (string= res "")
        (setq res "0"))
    res))

(defun aoc23/spring-config-p (number check)
  (let ((s (int-to-binary-string number))
        (p (alist-get 'pattern check)))
    (string-match-p p s)))


(defun aoc23/part-1 (input)
  (let ((in (string-split input "\n" t))
        (sum 0))
    (dolist (line in)
      (let* ((m (aoc23/convert-input line))
             (i (alist-get 'low m))
             (last (alist-get 'high m))
             (c (alist-get 'candidates m)))
        (dolist (s c)
          (when (aoc23/spring-config-p s m)
            (setq sum (1+ sum)))
          (setq i (1+ i)))))
    sum))


(aoc23/part-1 input)

Part 2