diff options
Diffstat (limited to 'AoC2022')
| -rw-r--r-- | AoC2022/23/eg-in | 7 | ||||
| -rw-r--r-- | AoC2022/23/input | 72 | ||||
| -rw-r--r-- | AoC2022/23/solver.lisp | 92 |
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))))) |