aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorOscar Najera <hi@oscarnajera.com>2023-01-23 21:10:26 +0100
committerOscar Najera <hi@oscarnajera.com>2023-01-23 22:24:30 +0100
commitae050f4d81d01af2401c09db8a9a6db251c20a37 (patch)
treefd87208cf7790af4de0033b1f40d5690d080f34d
parent6922fd9364d409c00822e897ad59706a1797c82a (diff)
downloadscratch-ae050f4d81d01af2401c09db8a9a6db251c20a37.tar.gz
scratch-ae050f4d81d01af2401c09db8a9a6db251c20a37.tar.bz2
scratch-ae050f4d81d01af2401c09db8a9a6db251c20a37.zip
Day 23
-rw-r--r--AoC2022/23/eg-in7
-rw-r--r--AoC2022/23/input72
-rw-r--r--AoC2022/23/solver.lisp92
3 files changed, 171 insertions, 0 deletions
diff --git a/AoC2022/23/eg-in b/AoC2022/23/eg-in
new file mode 100644
index 0000000..14005cf
--- /dev/null
+++ b/AoC2022/23/eg-in
@@ -0,0 +1,7 @@
+....#..
+..###.#
+#...#.#
+.#...##
+#.###..
+##.#.##
+.#..#..
diff --git a/AoC2022/23/input b/AoC2022/23/input
new file mode 100644
index 0000000..c930006
--- /dev/null
+++ b/AoC2022/23/input
@@ -0,0 +1,72 @@
+####.##.#..#..#...#..#.#..#..#.##.##.####.#..#.#....###.....####..#.#..#
+.##.#..#...#...#....#...#..#.##....#.#..#.#..#.####.........#.#....####.
+#.#..#.#..#....###..#.#.#.....####.##....#.##...#.##..#..#..#..######.##
+.#.##......#.#..#...###..###.#....####..##..####.#..##.###..#..##.##.#.#
+#####.####.####.###.###.###..###...#.##......##...###.####.....##.#.##..
+.....####.#..###.##.###.###.....###.#.##.#..##..##.#...#.#..#.##.#...#.#
+###..#..#..#..#.#..#...#..#.##..#..#.....#....##.########..##.###.#....#
+..#....###..##.####.#..#......##.#..####...#.....#..###..###......#.#...
+####.....#..##....##...#..##..#.#####..####.####....##.####.#...###...#.
+######.....##..#..#...#..###.#.#..#.##..#..#.....########..#....#.#.###.
+##...####.###.####.##.###.#..###.#####....##..###......#....###...##...#
+....#...#.#.##...#.#.###...##.#.#.#.##.#.##.###.#####.#.####.##.#####.#.
+.#.##.####.#.....#.##.##.#......#.#.#.##..#.##.####...#.#..#.#######.#.#
+#..#.#..##......#....#..##.#...####.#.#...#....#..####...#.#.##..#.###.#
+#.##..#.###..###..##.###..#..###.#....#.#.########..##..#.##.###.##..#.#
+.######.#.......#.##....#.###....##.##.#..##.#....#..##...#..#..#.##...#
+...#.###..###.######...####.##..###.#...####.######.#.#.##..###.#.#..##.
+....##....#...###..#...#.#.#.##.#..###.###...#..#..#.#.#..####...##...##
+.##.##.##..#.##......###....#.###.#...#..##.#.#####...############......
+.#..#.#..###.####.#..#.##..###.###.##.#.#.#.##.###......#.##..###.#.#.##
+#..#....#.##..#.#.##.##.##....##..###.###..####..#.#.....#..#......##.##
+#...####...##..#....#.#.#.##.....#.......##...#....#.##....##..##...##.#
+####.#.#..#.##.#######.###....###..#....#.##.####..##.#...#.####.#.#.#..
+............##..#..#.###...#.#.##....#######..#....#..###.....#.###...#.
+##.##..##....####..#######.##.#..#....####....#.###.#.#...###....#.##.#.
+.##.#..#.##.###..##.#.#.#..#...##.#...#.##.#...#.###.#...#.##....##.#...
+.#.########.##.####.#.#...#....#.###..##.##.#.##.#..#.###......###..#..#
+..#.#....#.#.#..##.#..###.#.###.##.##.##..#.#.#..##....#.##.#.....#.###.
+..#...#.###..##..###.##..##.#..#....#.###...###...#..#.#.#.#..###.####..
+###...#.#..###...##.##.###....#.#......##..............#..##.#####.##.##
+###..#.##.#.########.##.####..####...##.#.#.###...##.###.#.####.#.##.###
+..##.###.#.#.#.##.#.####....#.####.#.##....###.###.##.##....#..##..##...
+##..##.#.#......##..#.######...##..#...#.###..#.#.##...#....#.###.##.#.#
+..####...##..#..#.#...#.#.###.##..#.#.#..##.##..#..##.#######...##...##.
+....#..#..#.#...##.#.##.####..#..#..#..#...###..#.####.#.##.###.###..#..
+.##...#.#.##.##..###.#.#..#.#.#.....##......##.#........#####.#......##.
+###.####.#...##...#.#......####.#..#......##.....#..#####...#.###.##.#.#
+...##.#..#.#.###....#####..#..###.#..#..#.#..#.#.#.#####.#..####..#..###
+.##.##....#.#.#.#..#######..#..#.#..#....#.####...#...#..##..#..#...#.##
+#.##.#.....#...#...###.##.##.##.#..#..#.###....##.#.#..##.##.###.##..##.
+#.##..#....########.#.#.....##.###.#..##.####.#.##..###.##...#.....#.#.#
+#..#..##.#....##...#.....#######.###########.#...####.#...####.#.#...##.
+####.#..#..#...##..##.###.#.#.##..##.##.###.####..#.##.#.#....#..#.#.#..
+#..#########...##..####..###..##.#..##....#..#.#.#..##.#..#.##.#.###.#.#
+#....#..#.##.##.....#####.#.......###..#.#.#...###..#...##.#..##.#..#.##
+#...####..#.#...#......#....#.#.#.#.##.....#.#.##..#...#.##........#....
+###........#.###..#....##.##......#..##..##...##.#.####...#.#..##..##.#.
+.#.#.##.#....##.#.#.#.#.#...##.#...##..#####.##.##.###..##..#.#...##...#
+###.####...#......######.###..##..##.....###...#.......#..##.#..#.#.##..
+####.#..#.#.##.#####.#.#..#..####..##...#.###.##.##.##..#.###..#.#..###.
+#..###..#.#.###.#.#.##.#.##....#..#.#.###.##.#.##..###..#.##.....#..##..
+.#..#.##.#####..#.....#....##......#.##.##.##....##.#...#.#.##.#..#..#.#
+..#...##...#..####.##..#.##.#.##..#.##.#..####.#.#####......########..##
+.##.....##.##.######..#.##..#....#..#####.#.##..##..#.#.#.#..#...##..##.
+##.#...###.##..##..#.#....#..#.#.#.#.##.#..#..#.#####.##.#####..##.#.#..
+#.####.#..##..##...##..##.#.#......#.#####.#..####..#..########.##.###..
+#.##.##.#.##...#..#..#.#...#.##.##..##......##.#####..##.#.#.#.##.##.#.#
+..#....##....#..###.#####....##.#######..##..#####...#...#####.###.....#
+#.#.##..####.##.#......###..##.####.#...####.#..#.#.##.#..#.###.##.#####
+.##..####...###...#.##.#..#.##.######.#.##...#.##...##..##.##########...
+#.##.####..######...###.##.###.####.#.#..#..#.#.#..##....#......##....#.
+.###......##.##.####.#...##...#..#.#..####..#.#.##.###.#.....#.#....#.#.
+#..#..#.####.#.#.#..##..#..##.##..#.#..##.#########.###.######......#.##
+..#.#.#.#..#######...#.#.....######.#.#.##.#..#...#..#####..##.###.#.##.
+..#.#.#..##...####.#.###.##..#.#.##.#.#....##.#####.####...##..####....#
+....#.##.....##...#.##.#.###..#.#...#####....##.###..#..########.....#..
+#.#.#..#.#...###...##...#..#.##..#.#..#.....###.#####.##...#.#.#...##.#.
+..#.#####..##....##...##.#.##.#..#..##.#...#.##..###..#.##...#..##..##..
+#.###..##.#...####....###........#...###.#..##.#......###..####.#......#
+#..#.#.#....#...##.##.....#..##..#.####.##.....##.#.....#.#.#....##....#
+########.#.##.#..##..#...####.#.###.#.#.#.##.#.######.##.#.##....####..#
+###.#...##.###.##....#..##.##..#######..###.###...#..###.##...#...#..##.
diff --git a/AoC2022/23/solver.lisp b/AoC2022/23/solver.lisp
new file mode 100644
index 0000000..f3291ae
--- /dev/null
+++ b/AoC2022/23/solver.lisp
@@ -0,0 +1,92 @@
+(ql:quickload '(fiveam uiop arrows))
+
+(defun elf-coordinates (filename)
+ (let ((coord (make-hash-table :test #'equal)))
+ (with-open-file (input filename)
+ (loop for line = (read-line input nil nil)
+ and y from 0
+ while line
+ do (loop for point across line
+ and x from 0
+ when (eq point #\#)
+ do (setf (gethash (cons x y) coord) t))))
+ coord))
+
+(defun bounding-box (elf-coordinates)
+ (loop for k being the hash-key of elf-coordinates
+ minimize (car k) into minx
+ minimize (cdr k) into miny
+ maximize (car k) into maxx
+ maximize (cdr k) into maxy
+ finally (return (list minx miny maxx maxy))))
+
+(defparameter *moves*
+ (vector (vector (cons -1 -1) (cons 0 -1) (cons 1 -1)) ;; North
+ (vector (cons -1 1) (cons 0 1) (cons 1 1)) ;; South
+ (vector (cons -1 -1) (cons -1 0) (cons -1 1)) ;; West
+ (vector (cons 1 -1) (cons 1 0) (cons 1 1)))) ;; East
+
+(defun draw (elves)
+ (with-output-to-string (out)
+ (destructuring-bind (minx miny maxx maxy) (bounding-box elves)
+ (loop for y from miny to maxy
+ do (princ #\Newline out)
+ (loop for x from minx to maxx
+ do (princ (if (gethash (cons x y) elves)
+ #\# #\.) out))))))
+
+(defun pair-add (a b)
+ (cons (+ (car a) (car b))
+ (+ (cdr a) (cdr b))))
+
+(defun test-move (dir elf others)
+ (loop for next-dir across dir
+ never (gethash (pair-add elf next-dir) others)))
+
+(defun all-moves (step elves)
+ (let ((next-places (make-hash-table :test #'equal)))
+ (loop for elf being the hash-key of elves
+ do
+ (let ((options (loop for dirs below 4
+ collect (arrows:-> (aref *moves* (mod (+ dirs step) 4))
+ (test-move elf elves)))))
+ (unless (or (notany #'null options) ;; all free don't move
+ (every #'null options)) ;; all blocked don't move
+ (let ((prop
+ (arrows:->
+ (aref *moves* (mod (+ (position t options) step) 4))
+ (aref 1)
+ (pair-add elf))))
+ (setf (gethash prop next-places)
+ (cons elf (gethash prop next-places)))))))
+ next-places))
+
+(defun move-elves! (next-places elves)
+ (loop for target being the hash-key of next-places using (hash-value source)
+ when (null (cdr source)) ;; no conflicts on target
+ do (remhash (car source) elves)
+ (setf (gethash target elves) t)))
+
+(defun empty-ground (elves)
+ (destructuring-bind (minx miny maxx maxy) (bounding-box elves)
+ (- (* (1+ (- maxx minx))
+ (1+ (- maxy miny)))
+ (hash-table-count elves))))
+
+(defun solver (elves limit)
+ (loop for step from 0 below limit
+ for moves = (all-moves step elves)
+ while (plusp (hash-table-count moves))
+ do (move-elves! moves elves)
+ finally (return step)))
+
+(defun part1 (filename)
+ (let ((elves (elf-coordinates filename)))
+ (solver elves 10)
+ (empty-ground elves)))
+
+(fiveam:test solutions
+ (fiveam:is (= 110 (part1 "eg-in")))
+ (fiveam:is (= 4052 (part1 "input")))
+ (fiveam:is (= 20 (1+ (solver (elf-coordinates "eg-in") 1000))))
+ (fiveam:is (= 978 (1+ (solver (elf-coordinates "input") 1000)))))