day12.lisp (3402B)
1 (defpackage #:adventofcode2022/day12 2 (:use #:cl #:adventofcode2022) 3 (:import-from #:queues 4 #:qpush 5 #:qpop 6 #:qsize 7 #:make-queue)) 8 (in-package #:adventofcode2022/day12) 9 10 (defun get-passable-neighbors (map pos) 11 (loop with width = (array-dimension map 0) 12 with height = (array-dimension map 1) 13 with pos-height = (aref map (first pos) (second pos)) 14 for dir in '((-1 0) 15 (1 0) 16 (0 -1) 17 (0 1)) 18 for x = (+ (first pos) (first dir)) 19 for y = (+ (second pos) (second dir)) 20 unless (or (< x 0) (< y 0) 21 (>= x width) (>= y height) 22 (< (1+ pos-height) (aref map x y))) 23 collect (list x y))) 24 25 (defun find-shortest-route (map start-pos end-pos) 26 (loop with queue = (make-queue :simple-queue) 27 with steps = (make-hash-table :test 'equal) 28 initially (setf (gethash start-pos steps) 0) 29 (qpush queue start-pos) 30 while (> (qsize queue) 0) 31 for pos = (qpop queue) 32 for current-steps = (gethash pos steps) 33 when (equal pos end-pos) 34 return current-steps 35 do (loop for next in (get-passable-neighbors map pos) 36 unless (gethash next steps) 37 do (setf (gethash next steps) (1+ current-steps)) 38 and do (qpush queue next)))) 39 40 (defun find-position (map char) 41 (loop named outer 42 for y from 0 below (length map) 43 for row = (aref map y) 44 do (loop for x from 0 below (length row) 45 when (char= (aref row x) char) 46 do (return-from outer (list x y))))) 47 48 (defun convert-map (map) 49 (loop with height = (length map) 50 with width = (length (aref map 0)) 51 with new-map = (make-array (list width height)) 52 for y from 0 below height 53 for row = (aref map y) 54 do (loop for x from 0 below width 55 for cell = (aref row x) 56 do (setf (aref new-map x y) 57 (cond 58 ((char= cell #\S) 0) 59 ((char= cell #\E) 25) 60 (t (- (char-code cell) 97))))) 61 finally (return new-map))) 62 63 (defun task1 (inputs) 64 (let* ((map (coerce inputs 'vector)) 65 (start-pos (find-position map #\S)) 66 (end-pos (find-position map #\E)) 67 (map (convert-map map))) 68 (find-shortest-route map start-pos end-pos))) 69 70 (defun task2 (inputs) 71 (loop with map = (coerce inputs 'vector) 72 with end-pos = (find-position map #\E) 73 with shortest-distance = nil 74 with current-distance = nil 75 initially (setf map (convert-map map)) 76 for x from 0 below (array-dimension map 0) 77 do (loop for y from 0 below (array-dimension map 1) 78 when (= 0 (aref map x y)) 79 do (setf current-distance 80 (find-shortest-route map (list x y) end-pos)) 81 and when (or (null shortest-distance) 82 (and (not (null current-distance)) 83 (< current-distance shortest-distance))) 84 do (setf shortest-distance current-distance)) 85 finally (return shortest-distance))) 86 87 (define-day 12 88 () 89 #'task1 90 #'task2)