commit dae046eb5523b5e39bd17661f61fb520cb638fb2
parent 65dd74b013d4e656f3d4efb67eb3ae8e71d9d588
Author: Lukas Henkel <lh@entf.net>
Date: Sat, 24 Dec 2022 12:02:12 +0100
Day 24 task 1
Diffstat:
4 files changed, 194 insertions(+), 2 deletions(-)
diff --git a/adventofcode2022.asd b/adventofcode2022.asd
@@ -33,7 +33,9 @@
(:file "day19")
(:file "day20")
(:file "day21")
- (:file "day22")))
+ (:file "day22")
+ (:file "day23")
+ (:file "day24")))
(defsystem "adventofcode2022/test"
:description "My solutions to the advent of code 2022"
@@ -65,4 +67,6 @@
(:file "day19")
(:file "day20")
(:file "day21")
- (:file "day22")))
+ (:file "day22")
+ (:file "day23")
+ (:file "day24")))
diff --git a/input/day24.txt b/input/day24.txt
@@ -0,0 +1,27 @@
+#.########################################################################################################################
+#<>v^<vv<v<><.^v><<.>v><<^^<v..<>.v^>^v<^><vv>.>^v>^>>v^v>><^><><<^><^>.^>^<vv>v>^>>^<^v.^<^v<.><.v><<.^v^.^<v^v<<vv><<v>#
+#<>.vv^^vv<^v.^><^v<>>.<<<.^<^<>v<v<<>v>^vv..<<.^>^>>>.<>>^.^<^<<<^<>vv>.<<><^>.^>.vv^^v..v^<v^<vv.^.>v<^<^.<>^^v>^>v^<^>#
+#<<>v>v>v.^<><^><>^>.v<<>.^v.v<<v<^^v>v<^^<<>^>vv<vvv>^v^.<>>^^^^<><vvv<v^>^<vv.><..><^>^<<^><^.v>>^>>>v>v>>vv^v<<.<v^<^>#
+#<^.vv><^>^^>v<.>^vvv>v^v>><v>><v<><^.>v^v<v<<<>v.^>>^>v>^.>><<<v.^^^v^.v>^^vv^<<.v^<^v.v<<>><><vv.vv<^..<vv^.^<>>>.<<^^>#
+#<^<v<.>vvvvvv^>>.^v>.<<v^^^><^<^^<^>v><>>><>>vv^v><^>v>>v.^>>>v^v^^^.^^>^v<.v^>^^v<vv.<.<^v>vv^v>^v>>v<^^>>^^<><^>v<v>.>#
+#<vvvv<<^<v^vvv<.^<vv>.>v<v><<^v>^^<^v<^>vv^.<^vvv<^>^^vv^.v.^^..><<>^.>...^<<^>^^<^vvv>.^<>>^.v^v.^<>v^<vvvv>^.<>v>><v<>#
+#>.^>.vv^<^^<v><><<>>>vv>.<><^^<>>v><<>>v^vv.>^.>v^^<^<^.>>v<<<vv<<>>.<^<><.<<^v^><>.<>^<<.^>^v<>^^>><<>vv.v<>v^^>>>>>v><#
+#<.^<>.>.^>v><.^<>>>^^<^v^>^<^.>^^^v.<>vv><>v^v^v^^<^>^<<.v^>^v.<>.<^.>v><>>.<<v<^>>v>>>.^<><v<vv.<^^>^v<<<^^.<v<^>v>v^<<#
+#><^>.<<<^..>>>^>.>^<vv.<.v^><>>>^<.v<^^^><>v.>.v^v<^^v><^.^.><^^<>^^v<>><^<.v>><>>>>.>^v<^v^<<^v>>.v<^<>vv<>v>vv.^<<<v.<#
+#>.^^<<><v.>^^>>.^>^v>^>..>>>^v^<v^^^>v>>v>>v.^<>vv><>.<>vvvvv.vvv..><>v.vv<^v^v>^>^vv^<v<.^>>.>v^><<v>^v^>>.>^v><<^^^<v<#
+#.^<>>.v<>vv<vvv^^>vv><<.^>><^.v>>^v<.v^<^v^.<vvv^^>^^>^>>>.^.>vvv>>^^^^<^^v>^>v^<v><v^<><><<^v<<<><><<v^.vv><^vv^v<<vv<>#
+#<..vvv>><.v<^><v.v^^^v>^^v<<^v<>^><^v>^vvv^<^v>>^>>^<v>^<<^v^v.^vv>^><^v<^v^v>vv>^<^^^v>^^^<.>^v.v^<^>>^>^^^^^^vv<.v^^><#
+#<v><<v>>^v<>>v^^v<^v<<><<^><^<<^^>.<.^v>^>>v<>^><.^<<<.>^^v^vvv><<^>>^^<^^<><v.^v<<^..v^.<v>>^v.>^<^^v<<vvv^v<^<<<<<v>^>#
+#<v<<v^<^<^^v^vv<<<.>v<<><<^v^.^>><.v<^<v<^<<<<.<v^^vvv^>^^^>.><<><><<<^>v.>>>vv<.<v.><>^v^>^^^^.>v^<>.v>^.<v>v<^.v>vv<>>#
+#>v<v..<^v^<<<>><>>^<^v>>v>v^>vv^v<^.vv^vv>v<<<vv.v^.>^v><<v<vv>>^<.>vvv...v<^><>>.^v>v<^^>v^v<<>v>.^>><<<><<v^<v^.^v^>v>#
+#<<>^v>v>v<<<vvvv^^>v^..>..>^<>^>>><><<><v><^vv.>^v>v^v<<<vv><<.>><<<<<.<<<>^><v><vv^^v>^>>>><.^.^^>v<^<^>>.^>>^v.<>^>v>>#
+#>v<<<>^^>..^>>v.v^<><^>^^<<vv<<>>^<<>v^.<^><.v>>vv^v<v<^^v..>>^^^>^v>^v^^v^>^.<^>>>v^<><v>^.<>>^^<vv>>>^><^>>.<<>>v>vv<>#
+#<^^^..>>><>v>v>.>^.<.vv.vv<>v^vv<<^^>>v<^^<vv><^>><v>>>^^^><^^<.<^^>v>^^><v<vv^>vvv<^<..^>>>^v^v^^v>^^^.<.>v<^v><><>^^.>#
+#>^^>^^^^.<<.v^.><v<^^.<<<.><<><>.<<<^^><.>>..<>v^^^>^v<^>>.>v><^^vvv^>>^<v>v><^<>^<>>^^v>^.v>v<<>>>^v^vv<<<^..<>^><>>^>.#
+#.^<<<^^vv<.>v<.<>.>v.^..^^.>.vv.v>^>v.^.v<>v>>^^<^<^^^>>^>vvv.<^>><^>><^^>^>..^><.<v>.<^>^^v^v.>v<v^^><<>>vv^vv><v<>v^<>#
+#<vvv><<>v<^<^.>..^<.<v^v^v>.^<^vv^v>v<vvv<>><>vv.vvv<^><^^>><>vv>^^^><>^<^^><^>.>v<>^.vv<v<<v^^>v<v.^^^><>^<v^<>.>.^^v^>#
+#>v.^>..^>v>v>^^<^v>..>..^<.^..>>v<>.<>.<v>>>vv^<<>>>v<v^v^^vv<^vvvv<^v<^v<^^>>v>v><v><<v><v><^v<v>^>^^<>v.v<<^<.<><<<>.>#
+#>>v><..^^^.<v<^^<v<><<<<<^^^<>^^v^.>vv<v><<>>^^^<v^vv^v^<>...>^.<v><<^^v^..><>vv>v^>^v>.vv<v<^.<<<v^<^v^<<v^.<.^<.>v^<><#
+#>^v<..<>>v^v>v>v^v^<^<^^<..><v>^^>><<><>.^v.v<^>^<v><.^vv^.>v^>^v>^^v^>v<v^...><<<>><>>>^<vv<<^^^.<^vv^^^.v<vv<<<>>^><^<#
+#>><<v<>>>vv>>^^^v^^^>^>><v<>><^vv><>>>^.v^>^>^vv<>>..^v.^^^vvvv<><^><^v>vv<<^vv>^>v..<><.>^^^v.v>vvvv>>>><<vv<>.<v^<vv>>#
+########################################################################################################################.#
diff --git a/src/day24.lisp b/src/day24.lisp
@@ -0,0 +1,137 @@
+(defpackage #:adventofcode2022/day24
+ (:use #:cl #:adventofcode2022)
+ (:import-from #:queues
+ #:make-queue
+ #:qpush
+ #:qpop))
+(in-package #:adventofcode2022/day24)
+
+(defparameter *neighbor-deltas* (list '(-1 0)
+ '(0 -1)
+ '(1 0)
+ '(0 1)))
+
+(defun coord+ (a b)
+ (list (+ (car a) (car b))
+ (+ (cadr a) (cadr b))))
+
+(defun analyze-inputs (inputs)
+ (loop with blizzards = (make-hash-table :test 'equal)
+ with min-pos = (list 1 1)
+ with max-pos = (list 0 0)
+ with start-pos = (list 1 0)
+ with end-pos = (list 0 0)
+ for row in inputs
+ for y from 0
+ when (= y 0)
+ do (setf (car max-pos) (- (length row) 2)
+ (car end-pos) (- (length row) 2))
+
+ do (loop for column across row
+ for x from 0
+ for blizzard-direction = (case column
+ (#\^ :up)
+ (#\< :left)
+ (#\> :right)
+ (#\v :down))
+ when blizzard-direction
+ do (setf (gethash (list x y) blizzards)
+ (append (gethash (list x y) blizzards)
+ (list blizzard-direction))))
+ finally (progn
+ (setf (cadr max-pos) (1- y)
+ (cadr end-pos) y)
+ (return (values
+ blizzards
+ min-pos
+ max-pos
+ start-pos
+ end-pos)))))
+
+(defun get-next-blizzard-state (blizzards min-pos max-pos)
+ (loop with next-blizzards = (make-hash-table :test 'equal)
+ with width = (1+ (- (car max-pos) (car min-pos)))
+ with height = (1+ (- (cadr max-pos) (cadr min-pos)))
+ for pos being the hash-key of blizzards using (hash-value dirs)
+ do (loop for dir in dirs
+ for next-pos = (copy-seq pos)
+ do (case dir
+ (:up (decf (cadr next-pos)))
+ (:left (decf (car next-pos)))
+ (:right (incf (car next-pos)))
+ (:down (incf (cadr next-pos))))
+ do (setf next-pos (list
+ (+ (mod (- (car next-pos) (car min-pos))
+ width)
+ (car min-pos))
+ (+ (mod (- (cadr next-pos) (cadr min-pos))
+ height)
+ (cadr min-pos))))
+ do (setf (gethash next-pos next-blizzards)
+ (append (gethash next-pos next-blizzards)
+ (list dir))))
+ finally (return next-blizzards)))
+
+(defun print-map (min-pos max-pos current-pos blizzards)
+ (loop for y from (cadr min-pos) to (cadr max-pos)
+ do (loop for x from (car min-pos) to (car max-pos)
+ for pos = (list x y)
+ for bs = (gethash pos blizzards)
+ do (format t "~A" (cond
+ ((equal pos current-pos) "E")
+ ((> (length bs) 9) "*")
+ ((> (length bs) 1) (length bs))
+ (bs (case (car bs)
+ (:up "^")
+ (:left "<")
+ (:right ">")
+ (:down "v")))
+ (t "."))))
+ do (format t "~%"))
+ (format t "~%"))
+
+(defun test-blizzards (inputs rounds)
+ (multiple-value-bind (blizzards min-pos max-pos start-pos end-pos)
+ (analyze-inputs inputs)
+ (declare (ignore start-pos end-pos))
+ (loop with current-blizzards = blizzards
+ initially (print-map min-pos max-pos (list 0 0) current-blizzards)
+ repeat rounds
+ 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 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)))))
+
+(define-day 24
+ ()
+ #'task1
+ nil)
diff --git a/t/day24.lisp b/t/day24.lisp
@@ -0,0 +1,24 @@
+(in-package #:adventofcode2022/test)
+
+(define-constant +testdata-day24+ "#.######
+#>>.<^<#
+#.<..<<#
+#>v.><>#
+#<^v^^>#
+######.#"
+ :test 'equal)
+
+(define-constant +testdata-day24-simple+ "#.#####
+#.....#
+#>....#
+#.....#
+#...v.#
+#.....#
+#####.#"
+ :test 'equal)
+
+(def-test day24-task1 ()
+ (is-true
+ (= 18
+ (run-task 24 1
+ (make-string-input-stream +testdata-day24+)))))
