day-19.lisp (1516B)
1 (defpackage #:aoc/day-19 2 (:use #:cl #:aoc/utils) 3 (:export #:day-19)) 4 (in-package #:aoc/day-19) 5 6 (defun parse-comma-list (line) 7 (loop with pos = 0 8 for comma-pos = (position #\, line :start pos) 9 collect (subseq line pos comma-pos) 10 do (setf pos (+ (or comma-pos 0) 2)) 11 until (null comma-pos))) 12 13 (defun parse-input (input) 14 (loop with towels = (parse-comma-list (read-line input)) 15 initially (read-line input) 16 for line = (read-line input nil) 17 until (null line) 18 collect line into lines 19 finally (return (values towels lines)))) 20 21 (defun possible-arrangements (line towels) 22 (let ((cache (make-hash-table))) 23 (labels ((%solve (i) 24 (when (= i (length line)) 25 (return-from %solve 1)) 26 (loop for towel in towels 27 for has-prefix = (string-prefix-p towel line :start2 i) 28 sum (or (and has-prefix (%solve-cached (+ i (length towel)))) 0))) 29 (%solve-cached (i) 30 (or (gethash i cache) 31 (setf (gethash i cache) 32 (%solve i))))) 33 (%solve 0)))) 34 35 (defun all-possible-arrangements (towels lines) 36 (loop for line in lines 37 collect (possible-arrangements line towels))) 38 39 (defun day-19 (input) 40 (multiple-value-bind (towels lines) 41 (parse-input input) 42 (let ((a (all-possible-arrangements towels lines))) 43 (values (count 0 a :test-not #'eq) 44 (sum (remove nil a))))))