aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--AoC2023/day11/input140
-rw-r--r--AoC2023/day11/solver.lisp66
2 files changed, 206 insertions, 0 deletions
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")))))