From 1b1ee3db6b7cf6746782d9c2fb5f80bfa3f3afb5 Mon Sep 17 00:00:00 2001 From: Thomas Voss Date: Thu, 19 Dec 2024 18:59:37 +0100 Subject: Add 2024 day 19 solutions --- 2024/19/puzzles.lisp | 46 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 46 insertions(+) create mode 100644 2024/19/puzzles.lisp (limited to '2024/19/puzzles.lisp') diff --git a/2024/19/puzzles.lisp b/2024/19/puzzles.lisp new file mode 100644 index 0000000..6d99dc8 --- /dev/null +++ b/2024/19/puzzles.lisp @@ -0,0 +1,46 @@ +#!/usr/bin/sbcl --script + +(defun main (filename) + (multiple-value-bind (towels stream) (parse filename) + (loop for pattern = (read-line stream nil) + while pattern + ;; START PART 1 + count (plusp (nconstructions pattern towels)) + ;; END PART 1 START PART 2 + sum (nconstructions pattern towels) + ;; END PART 2 + finally (close stream)))) + +(defparameter *memo* + (let ((map (make-hash-table :test #'equal))) + (setf (gethash "" map) 1) + map)) + +(defun nconstructions (pattern towels) + (multiple-value-bind (count existsp) (gethash pattern *memo*) + (when existsp + (return-from nconstructions count))) + (let ((count 0)) + (dolist (towel towels) + (when (string-prefix-p towel pattern) + (incf count (nconstructions (subseq pattern (length towel)) towels)))) + (setf (gethash pattern *memo*) count))) + +(defun string-prefix-p (prefix string) + (and (<= (length prefix) (length string)) + (string= prefix (subseq string 0 (length prefix))))) + +(defun parse (filename) + (let* ((stream (open filename)) + (towels (parse-strings (read-line stream)))) + (read-line stream) ; Consume empty line + (values towels stream))) + +(defun parse-strings (string) + (loop for end = (position-if-not #'alpha-char-p string) + collect (subseq string 0 end) into strings + unless end + return strings + do (setq string (subseq string (+ 2 end))))) + +(format t "~d~%" (main "input")) \ No newline at end of file -- cgit v1.2.3