commit 90579a511a64f2a6c89db48afc90203ec110d028 parent dae046eb5523b5e39bd17661f61fb520cb638fb2 Author: Lukas Henkel <lh@entf.net> Date: Sat, 24 Dec 2022 12:12:34 +0100 Day 24 task 2 Diffstat:
| M | src/day24.lisp | | | 69 | +++++++++++++++++++++++++++++++++++++++++---------------------------- |
| M | t/day24.lisp | | | 6 | ++++++ |
2 files changed, 47 insertions(+), 28 deletions(-)
diff --git a/src/day24.lisp b/src/day24.lisp @@ -100,38 +100,51 @@ do (setf current-blizzards (get-next-blizzard-state current-blizzards min-pos max-pos)) do (print-map min-pos max-pos (list 0 0) current-blizzards)))) +(defun walk-through-storm (blizzards min-pos max-pos start-pos end-pos &optional (start-minute 0)) + (loop named outer + with visited = (make-hash-table :test 'equal) + with blizzard-states = (make-hash-table) + with queue = (make-queue :simple-queue) + initially (qpush queue (list start-minute start-pos)) + (setf (gethash start-minute blizzard-states) blizzards) + for (minute current-pos) = (qpop queue) + while current-pos + for next-minute = (1+ minute) + for current-blizzards = (gethash minute blizzard-states) + for next-blizzards = (or (gethash next-minute blizzard-states) + (setf (gethash next-minute blizzard-states) + (get-next-blizzard-state current-blizzards min-pos max-pos))) + do (loop for neighbor-delta in *neighbor-deltas* + for next-pos = (coord+ current-pos neighbor-delta) + when (equal next-pos end-pos) + do (return-from outer (values next-minute next-blizzards)) + when (and (>= (car next-pos) (car min-pos)) + (>= (cadr next-pos) (cadr min-pos)) + (<= (car next-pos) (car max-pos)) + (<= (cadr next-pos) (cadr max-pos)) + (null (gethash next-pos next-blizzards)) + (null (gethash (list next-pos next-minute) visited))) + do (qpush queue (list next-minute next-pos)) + and do (setf (gethash (list next-pos next-minute) visited) t)) + when (not (gethash current-pos next-blizzards)) + do (qpush queue (list next-minute current-pos)))) + (defun task1 (inputs) (multiple-value-bind (blizzards min-pos max-pos start-pos end-pos) (analyze-inputs inputs) - (loop named outer - with visited = (make-hash-table :test 'equal) - with blizzard-states = (make-hash-table) - with queue = (make-queue :simple-queue) - initially (qpush queue (list 0 start-pos)) - (setf (gethash 0 blizzard-states) blizzards) - for (minute current-pos) = (qpop queue) - while current-pos - for next-minute = (1+ minute) - for current-blizzards = (gethash minute blizzard-states) - for next-blizzards = (or (gethash next-minute blizzard-states) - (setf (gethash next-minute blizzard-states) - (get-next-blizzard-state current-blizzards min-pos max-pos))) - do (loop for neighbor-delta in *neighbor-deltas* - for next-pos = (coord+ current-pos neighbor-delta) - when (equal next-pos end-pos) - do (return-from outer next-minute) - when (and (>= (car next-pos) (car min-pos)) - (>= (cadr next-pos) (cadr min-pos)) - (<= (car next-pos) (car max-pos)) - (<= (cadr next-pos) (cadr max-pos)) - (null (gethash next-pos next-blizzards)) - (null (gethash (list next-pos next-minute) visited))) - do (qpush queue (list next-minute next-pos)) - and do (setf (gethash (list next-pos next-minute) visited) t)) - when (not (gethash current-pos next-blizzards)) - do (qpush queue (list next-minute current-pos))))) + (nth-value 0 (walk-through-storm blizzards min-pos max-pos start-pos end-pos)))) + +(defun task2 (inputs) + (multiple-value-bind (blizzards min-pos max-pos start-pos end-pos) + (analyze-inputs inputs) + (let ((current-minute)) + (multiple-value-setq (current-minute blizzards) + (walk-through-storm blizzards min-pos max-pos start-pos end-pos)) + (multiple-value-setq (current-minute blizzards) + (walk-through-storm blizzards min-pos max-pos end-pos start-pos current-minute)) + (nth-value 0 (walk-through-storm blizzards min-pos max-pos start-pos end-pos current-minute))))) (define-day 24 () #'task1 - nil) + #'task2) diff --git a/t/day24.lisp b/t/day24.lisp @@ -22,3 +22,9 @@ (= 18 (run-task 24 1 (make-string-input-stream +testdata-day24+))))) + +(def-test day24-task2 () + (is-true + (= 54 + (run-task 24 2 + (make-string-input-stream +testdata-day24+)))))