From d0bd893f59a12fd3b58eaf998a2fc48e7b90e975 Mon Sep 17 00:00:00 2001 From: Oscar Najera Date: Thu, 14 Dec 2023 10:31:32 +0100 Subject: [AoC2023] day11 part 1 lisp --- AoC2023/day11/input | 140 ++++++++++++++++++++++++++++++++++++++++++++++ AoC2023/day11/solver.lisp | 66 ++++++++++++++++++++++ 2 files changed, 206 insertions(+) create mode 100644 AoC2023/day11/input create mode 100644 AoC2023/day11/solver.lisp diff --git a/AoC2023/day11/input b/AoC2023/day11/input new file mode 100644 index 0000000..713f54c --- /dev/null +++ b/AoC2023/day11/input @@ -0,0 +1,140 @@ +..........#............................................#..........#.....#...........................................#.......#.........#..... +.....#...................#..............#....................................................#.............................................. +..............................#....................#...................................................#.................................... +.............................................#.....................................................................................#........ +............#................................................................#......#....................................................... +......................................#..................#.........................................#........................................ +.............................................................................................................................#.............. +.................#.....#.................................................................................................................... +.....................................................#...........#..........................................#.............................#. +.....#..........................#...............#.......................................#...........................#....................... +....................#................#...............................#.........................#.....#...................................... +...........#.............................................#.................................................................................. +................................................................................................................................#.....#..... +................#...................................#...........#......................................................#.................... +.........................#.................................................#.................................#.............................# +...#..............................#...................................#................................#.................................... +...............................................................................#............................................................ +..................................................................#...........................#..........................#........#......... +.........#....................#........................................................................................................#.... +..........................................................................#..............#........................#......................... +....................#...............................#........#.............................................................................. +..#..............................#........#...................................#..........................#..................#............... +......................................................................#...........................#............#...................#........ +........#................#..............................#.............................................................#.................#... +......................................#......#....................#........#.....#.........#................................................ +.....................#............................#.............................................................................#........... +....#.........................#.............................................................................#............................... +............#..................................................#................................#...........................#............... +....................................................................................#..................#.............#...................... +..........................................................................................................................................#. +...................................#...............#.....................................#.......................#.......................... +..#................#.......................#................................................................................................ +...........#...............#...........................................#.................................................#.........#........ +......#.....................................................................#............................#.................................. +.........................................................#.................................................................................. +...................................................................#........................................................................ +.........#....................................................#......................................#............#....................#.... +...................................................#....................#...........#......................#...............#................ +..#..............................#......#........................................................#.......................................... +........................................................#...........................................................................#....... +......................................................................................................................#..................... +......#......................................................................#................#............................................. +............................................#..............#............................................#...................#............... +.......................#........#......#........................#..................................................#........................ +....................................................#......................................#.......#.........#.............................. +........#..........................................................................................................................#........ +................#........................................................................................................................... +#..........................#.......#......#.............................#.................................#................................. +......................................................#.............................#............#.......................#.....#............ +...................#.............................................#...........#...........#..............................................#... +...............................#..................#..........................................................#.............................. +..............#..............................................#.......................................#...................................... +..#.....................#.............#........................................................#............................................ +...................................................................#........................................................................ +............................................................................................................................................ +........#.......#.....................................................................#..................................................... +...............................#.....................#..................#.....................................#.........#................... +..............................................#...............................#............#........#....................................... +.#.................#........................................................................................................................ +..................................#................................................#.....................................................#.. +............................................................................................................................................ +...........#..................#....................#....................................#................................................... +....#....................................#.........................#.....#......................#...............#..............#............ +.................................................................................#.......................................................... +...............................................#........................................................#...........#.....................#. +........................#........#.........................#................................................................................ +....................................................................................#..............................................#........ +...#......................................#................................................................................................. +.....................................................#.........................................#......#.........#........................... +..............................#..........................................................#.................#................#............... +..............#....................................................#......#................................................................. +........#............#..........................................................................................................#........... +............................................................................................................................................ +...........................#.....................#..............#..................................#................................#....... +............................................................................#............................................................... +.............................................#..........................................................#.................................#. +.....................................................#..............#....................................................................... +......#................#................#..................#.................................................#...........#.................. +................#.................#......................................#........................................#...........#............. +...........#....................................#................#..........................#......................................#........ +............................................................................................................................................ +...................#..................................#..................................................................................... +...#.......................#..............#.................#..............#..........#...................................................#. +......................................................................................................#................#.............#...... +....................................................................#............................#..............................#........... +...............................#..................#.......................................#...............#................#................ +............................................................................................................................................ +............................................................................................................................................ +......................#...............................#..........#.............................................#...................#........ +........................................#..............................................................#.................#.................. +..........................#........#.......................................#..........#....................................................# +..................#...........................#............................................................................................. +......#....................................................#...............................#................................................ +..............................#............................................................................................................. +................................................................................................#........#.................................. +#.............#.......................................................#........#...............................................#.......#.... +...........................#...................................................................................#............................ +....#...................................#................................................................................................... +................................................#......#..................................................................................#. +.......................................................................................#.............#...................................... +................................#..........................#..................#...........................#................................. +....................#...........................................................................................#...................#....... +...................................................#..............#.......#............................................#.................... +..#......................................................................................................................................... +........#.....#.......................#.......#..............................................................................#.............. +......................#.......#.........................#........................#...........#.......#...................................#.. +...............................................................................................................#............................ +.......................................................................................#..................#................................. +........................................................................#.........................#..................#...................... +..........................................#.....#.........................................................................#................. +..................#..........#...............................#.............................................................................. +......................................#........................................#.........#.................................................. +...#...............................................................................................................#....................#... +........#..............................................#...............#.....................................................#.............. +...................................#........................................#...............#............#..........................#....... +............#.................#............................................................................................................. +....................#.............................#......................................................................................... +....................................................................................#..............#........................................ +...............#......................................#.......................................#.........................................#... +.#........................#........................................#...............................................#......#................. +........................................#.................................................#................................................. +.....#...................................................................#.................................................................. +..................................................................................................#............#............................ +............#.......#.........#.....#...............#.......#...........................................#................................... +..#..........................................#......................#..................#...............................................#.... +............................................................................................................................................ +.........................#.............#.................................................................................................... +..................................................#............................#................................#...................#....... +...................................#..............................................................#......#.................................. +............................................................................................................................................ +........................................................#.....#............................#..........................#.....#............... +......................#.......................#..........................#.............................................................#.... +......#.....#.........................................................................................#..................................... +..................................................................#...............................................................#......... +...................................#.........................................#.................#..........................#...............#. +..#.........................................#.........................#..............#...................................................... +...................................................#......................................#...................#............................. +.........................................................#.................................................................................. +..............#................................................#..................................#......................................... +...................#..........#..........#................................................................#......#............#............# diff --git a/AoC2023/day11/solver.lisp b/AoC2023/day11/solver.lisp new file mode 100644 index 0000000..e7feabf --- /dev/null +++ b/AoC2023/day11/solver.lisp @@ -0,0 +1,66 @@ +;; 9:59 +;; 10:31 part1 +;; +(ql:quickload '(fiveam)) +(defparameter eg-input "...#...... +.......#.. +#......... +.......... +......#... +.#........ +.........# +.......... +.......#.. +#...#.....") + +(defun indexes (array) + (loop for v across array + for i from 0 when v collect i)) + +(defun shift (coord spacers) + (count-if (lambda (idx) (< idx coord)) spacers)) + +(defun expanded (point free-rows free-cols) + (destructuring-bind (y x) point + (list (+ y (shift y free-rows)) + (+ x (shift x free-cols))))) + +(fiveam:test parts + (fiveam:is (= 1 (shift 5 '(3 6)))) + (fiveam:is (equal '(7 4) (expanded '(5 3) '(1 2) '(2))))) + +(defun expanded-galaxies (rows) + (let* ((free-rows (make-array (length rows) :initial-element t)) + (free-cols (make-array (length (car rows)) :initial-element t)) + (galaxies (loop for row in rows + for y from 0 + nconc + (loop for col across row + for x from 0 + when (eq col #\#) + collect (list y x) + and do (setf (aref free-rows y) nil + (aref free-cols x) nil))))) + (map 'vector + (lambda (galaxie) + (expanded galaxie + (indexes free-rows) + (indexes free-cols))) + galaxies))) + + +(defun manhattan-dist (s x) + (destructuring-bind ((sx sy) (bx by)) (list s x) + (+ (abs (- bx sx)) (abs (- by sy))))) + + +(defun solver1 (rows) + (loop with gals = (expanded-galaxies rows) + for g across gals + for i from 0 sum + (loop for j from (1+ i) below (length gals) + sum (manhattan-dist g (aref gals j))))) + +(fiveam:test solutions + (fiveam:is (= 374 (solver1 (uiop:split-string eg-input :separator '(#\Newline))))) + (fiveam:is (= 10154062 (solver1 (uiop:read-file-lines "input"))))) -- cgit v1.2.3