aoc2021 day15

aoc2021-day15.lisp

;;;; +----------------------------------------------------------------+
;;;; | Advent of Code 2021                                            |
;;;; +----------------------------------------------------------------+

(defpackage #:snippets/aoc2021/day15
  (:use #:cl)
  (:import-from
   #:snippets/slhelpers)
  (:export
   #:day15))

(in-package #:snippets/aoc2021/day15)

(defun least-risk (cave scale)
  (let* ((n (length (aref cave 0)))
         (m (length cave))
         (goal-position (complex (1- (* scale n)) (1- (* scale m)))))
    (snippets/slhelpers:a-star
     #C(0 0)
     :goal-state-p
     (lambda (pos)
       (= pos goal-position))
     :heuristic
     (constantly 0)
     :expand
     (lambda (pos)
       (loop for dir in '(#C(-1 0) #C(+1 0) #C(0 -1) #C(0 +1))
             for neighbor = (+ pos dir)
             when (and (<= 0 (realpart neighbor) (realpart goal-position))
                       (<= 0 (imagpart neighbor) (imagpart goal-position)))
             collect (multiple-value-bind (q1 r1) (truncate (realpart neighbor) n)
                       (multiple-value-bind (q2 r2) (truncate (imagpart neighbor) m)
                         (list (1+ (mod (+ (1- (digit-char-p (aref (aref cave r2) r1))) q1 q2) 9))
                               neighbor))))))))

(defun day15 (input)
  (let ((cave (coerce input 'vector)))
    (list (nth-value 1 (least-risk cave 1))
          (nth-value 1 (least-risk cave 5)))))