commit 55b5b1cbe2d68e849b2fd9eb9db939156e74dbce parent 64be7f4d0436cbe686a8db7b23012a8bb94c031e Author: Lukas Henkel <lh@entf.net> Date: Mon, 11 Dec 2023 06:24:18 +0100 Day 11 task 1 Diffstat:
| A | input/11.txt | | | 140 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | src/day-11.lisp | | | 36 | ++++++++++++++++++++++++++++++++++++ |
| M | src/utils.lisp | | | 7 | +++++++ |
| A | t/day-11.lisp | | | 18 | ++++++++++++++++++ |
4 files changed, 201 insertions(+), 0 deletions(-)
diff --git a/input/11.txt b/input/11.txt @@ -0,0 +1,140 @@ +............#..................#..........................................................#..........................#...................... +.................................................................#...............#..............#...............#......................#.... +...................................#.....................#..................#............................#...................#.............. +#.....................#.....................#............................................................................................... +........................................................................................#............#...................................... +.....#..............................................#....................................................................................... +.......................................#................................#..........#...........#......................................#..... +..................#...........#............................................................................................................. +.............................................#............#................................................................................. +.#............................................................................#..................................#.......................... +............#......................#....................................................................#...................#.............#. +.......#............#....................#........#...................................#......................#.............................. +...................................................................#................................#....................................... +..............................#.................................................................................................#........... +..#...........................................................................................#.......................#..................... +..............................................................................#............................................................. +.......................................#.........#............#...........................#................#..............................#. +........................................................#.............#..................................................................... +.....#..........................#....................................................................#....................#................. +....................#.......................#...................................#...............#...............#......................#.... +...............#..................................................................................................................#......... +..#......................................................................#...................................................#.............. +.................................................#............#.........................................#.............#..................... +....................................#....................................................................................................... +...........#..........................................................................#..................................................... +.................#.......................................................................................................................... +.............................................#............................#....................................................#............ +.........................#.......#..........................#............................................................................... +.......#............#....................................................................................................#..........#....... +...................................................................#................#...........................#........................... +..............#....................................#..........................#..............#.............................................. +..#....................#....................................................................................#........#...................... +.........................................................................#......................................................#........... +......................................#.........#........................................................................................... +..........#................................................................................................................................. +.....................#......................#...............#.................................................#............................. +...............................#...................................................#....................................#.................#. +.............................................................................................#.............................................. +...................................................................#........................................................................ +................#..........#.....................#..................................................................................#....... +...................................#............................................#..................#........................................ +.....#.....................................................................#...............................#.....#.......................... +............#.........................................................................................................#..................... +.....................#.............................#.......................................................................#................ +..............................................................#...............................#..........................................#.. +.....................................#.......#.................................................................#............................ +...............#...................................................................#.....#..............................#................... +...#.....................#.........................................#......#...........................#..................................... +.........#......................................................................................#.............................#............. +..........................................................#................................................................................. +..................................#.......#...........................................#......................#......................#....... +.............................................................................#.............................................................. +.....#...........................................#..................................................#....................#.................. +............................................................................................................................................ +............................................................................................................................................ +.................#...................#........................#......#..................................#................................... +..........................#.........................#.....................................#......#.........................#................ +..............................................#...........................#.....................................#........................... +#.....................#.................#............................................................................................#...... +...............................#..........................#.....................................................................#........... +..........#.........................#.............................#...........#....................................#........................ +.....................................................#...................................................................................... +.............................................................................................#.............................................. +............................................................................................................................................ +...............#...........#..........#.....#..................#.......................#......................#.......#..............#...... +........#...........#.............................#.....#................................................................................... +............................................................................................................................................ +.#................................#.............................................#................................................#.......... +............................................................................................................................................ +..........................................................................#...............................................................#. +..............................#...............#......................................#........#.............#.........#..................... +...#................................................#....................................................................................... +............................................................................................................................................ +.......................#...............#...........................................................#..........................#............. +.................................................#...........#......................................................#....................... +...........#............................................................................#................................................... +.....#..................................................#.....................................#.............#..............................# +..................#..........#..............................................#..........................#..............................#..... +....................................................#....................................................................................... +..#............................................................................................................#................#........... +.............................................................#........#..........#.....#.................................................... +...........#..........#............#.......#...............................................................................#................ +............................................................................................................................................ +......................................................#..............................................#...................................... +.........................#.....#...............................................#................................#................#.......... +...#.......................................................................................................#...........................#.... +........#...........................#....................................#...............#.................................................. +..........................................#.......................#......................................................................... +............................................................#.............................................................#................. +...........................#...................................................................#.....................#...................... +...............#.................#............#............................................................................................. +...#......#..........................................#..................................#...............#................................... +.................................................................#......................................................................#... +.......................#..................#...............#..................#.............................................................. +.................................................#...................................#.............#............................#........... +................#........................................................................................................................... +...................................#.........................................................#........................#.............#....... +.............................................................#..........................#......................#............#..............# +...#..................#.............................#..........................#............................................................ +........#......................................#............................................................................................ +..............#............#...........#............................................................#....................................... +....................................................................#.......................#............................................... +.#....................................................................................#........................................#.......#.... +...........#...................#............................................................................................................ +.........................#..........#.......#.........#..................#..................................#............................... +................................................................#....................................................#...................... +...#.............................................................................................#.....#.................................... +.................................................#....................#..................................................................... +.......................#.........#..................................................#.......#...................#........#.................. +........................................................................................................................................#... +...........#................................................#..............................................#................................ +.....................................#..........................................................#........................................... +....#.......................................#....................................................................................#.......... +...................#..............................................#.........#..........#.............#...................................... +............................................................................................................................................ +............................................................................................................................................ +.............#.......................................#...............#......................#......................#...............#........ +...............................................#............................................................................................ +....#.................................#.......................................................................................#............. +............................#.................................................#......#.....................................................# +...................#..............#.......#...............#.....................................................#.........#................. +..................................................................#.....................................#................................... +...................................................#..............................#......#.......#..............................#........... +.......................................#.....................#..............#......................................#........................ +.................#.......................................................................................................................... +..............................................#.......#.................#.................................#................................. +.........#...............#.............................................................#.................................#.............#.... +..#..............................#..................................#....................................................................... +...............................................................#...........#.......................................................#........ +............................................................................................................................#............... +................#...........#............#.........#........................................................................................ +........#.............#........................................................................................#...........................# +..........................................................#...............................#..............#...........................#...... +...............................#................................................................#........................................... +..................#.............................................#.........#..........................................#...................... +.....#................................................#.........................................................................#........... +............................................#.....................................#.........#............................................... +.......................................................................................................................................#.... +#..........#.............#......#.................................#...................................#..................................... +.....................................#.........#.........................#.....#............................................................ diff --git a/src/day-11.lisp b/src/day-11.lisp @@ -0,0 +1,36 @@ +(defpackage #:aoc/day-11 + (:use #:cl #:aoc/utils) + (:export #:day-11)) +(in-package #:aoc/day-11) + +(defun find-galaxies (map) + (let (galaxies + empty-rows + empty-cols) + (loop for x from 0 below (input-map-width map) + for contains-galaxy? = nil + do (loop for y from 0 below (input-map-height map) + when (char= (map-cell map (cons x y)) #\#) + do (setf contains-galaxy? t) + and do (push (cons x y) galaxies)) + unless contains-galaxy? + do (push x empty-cols)) + (loop for y from 0 below (input-map-height map) + unless (loop for x from 0 below (input-map-width map) + thereis (char= (map-cell map (cons x y)) #\#)) + do (push y empty-rows)) + (loop for galaxy in galaxies + collect (cons (+ (point-x galaxy) + (count-if (curry #'> (point-x galaxy)) empty-cols)) + (+ (point-y galaxy) + (count-if (curry #'> (point-y galaxy)) empty-rows)))))) + +(defun day-11 (input) + (let* ((map (make-map input)) + (galaxies (find-galaxies map)) + (sum 0)) + (map-combinations (lambda (p) + (incf sum (apply #'manhattan-distance p))) + galaxies + :length 2) + (values sum))) diff --git a/src/utils.lisp b/src/utils.lisp @@ -16,6 +16,7 @@ #:point-x #:point-y #:point-neighbours + #:manhattan-distance #:do-map-neighbours #:read-number-list)) (in-package #:aoc/utils) @@ -138,6 +139,12 @@ (mapcar (curry #'point+ point) *map-neighbours*)) +(defun manhattan-distance (from to) + (+ (abs (- (point-x to) + (point-x from))) + (abs (- (point-y to) + (point-y from))))) + (defmacro do-map-neighbours ((neighbour-point map start-point) &body body) (with-gensyms (width height lb? rb? tb? bb?) (once-only ((sp start-point) diff --git a/t/day-11.lisp b/t/day-11.lisp @@ -0,0 +1,18 @@ +(defpackage #:aoc-test/day-11 + (:use #:cl #:lisp-unit2)) +(in-package #:aoc-test/day-11) + +(define-test test-day-11 + () + (multiple-value-bind (task-1) + (aoc:run-day 11 "...#...... +.......#.. +#......... +.......... +......#... +.#........ +.........# +.......... +.......#.. +#...#.....") + (assert= 374 task-1)))