commit a8fde4e01fa1684be6df30394d399d9921049f10 parent 61329b780f3e4c31a9f4fd93c4242a861e1abc21 Author: Shimmy Xu <shimmy.xu@shimmy1996.com> Date: Tue, 12 Dec 2023 00:24:17 -0500 Add 2023 day 11 Diffstat:
| A | 2023/day11/day11.scm | | | 97 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 2023/day11/input.txt | | | 140 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
2 files changed, 237 insertions(+), 0 deletions(-) diff --git a/2023/day11/day11.scm b/2023/day11/day11.scm @@ -0,0 +1,97 @@ +(use-modules (ice-9 popen)) +(use-modules (ice-9 rdelim)) +(use-modules (ice-9 format)) +(use-modules (ice-9 receive)) +(use-modules (ice-9 hash-table)) +(use-modules (ice-9 match)) +(use-modules (srfi srfi-1)) + +(define (parse-input filename) + (let ((file (open-input-file filename)) + (image '())) + (while #t + (let ((line (car (%read-line file)))) + (if (eof-object? line) + (break) + (set! image (cons (string->list line) image))))) + (reverse image))) + +(define (find-galaxies image) + (let ((galaxies '()) + (y-max (length image)) + (x-max (length (car image)))) + (do ((y 0 (1+ y))) ((>= y y-max)) + (do ((x 0 (1+ x))) ((>= x x-max)) + (case (list-ref (list-ref image y) x) + ((#\#) (set! galaxies (cons (cons x y) galaxies)))))) + (reverse galaxies))) + +(define (get-column image x) + (let ((y-max (length image)) + (x-max (length (car image))) + (column '())) + (do ((y 0 (1+ y))) ((>= y y-max)) + (set! column (cons (list-ref (list-ref image y) x) column))) + (reverse column))) + +(define (no-galaxy line) + (if (null? line) + #t + (and (equal? (car line) #\.) (no-galaxy (cdr line))))) + +(define (find-expansion image) + (let ((y-max (length image)) + (x-max (length (car image))) + (expand-x '()) + (expand-y '())) + (do ((y 0 (1+ y))) ((>= y y-max)) + (if (no-galaxy (list-ref image y)) + (set! expand-y (cons y expand-y)))) + (do ((x 0 (1+ x))) ((>= x x-max)) + (if (no-galaxy (get-column image x)) + (set! expand-x (cons x expand-x)))) + (list (reverse expand-x) (reverse expand-y)))) + +(define (between a b c) + (if (> b c) + (between a c b) + (and (>= a b) (<= a c)))) + +(define (calc-dist expansion curr next mult) + (let* ((x-a (car curr)) + (y-a (cdr curr)) + (x-b (car next)) + (y-b (cdr next)) + (x-expand (car expansion)) + (y-expand (car (cdr expansion))) + (dist (+ (abs (- y-b y-a)) (abs (- x-b x-a))))) + (do ((i 0 (1+ i))) ((>= i (length x-expand))) + (if (between (list-ref x-expand i) x-a x-b) + (set! dist (+ dist (1- mult))))) + (do ((i 0 (1+ i))) ((>= i (length y-expand))) + (if (between (list-ref y-expand i) y-a y-b) + (set! dist (+ dist (1- mult))))) + dist)) + +(define (calc-dist-all expansion curr other-galaxies mult) + (if (null? other-galaxies) + 0 + (let ((dist-sum 0)) + (do ((i 0 (1+ i))) ((>= i (length other-galaxies))) + (set! dist-sum + (+ dist-sum + (calc-dist expansion curr (list-ref other-galaxies i) mult)))) + (+ dist-sum + (calc-dist-all expansion (car other-galaxies) (cdr other-galaxies) mult))))) + +(let* ((image (parse-input "input.txt")) + (galaxies (find-galaxies image)) + (expansion (find-expansion image)) + (total-dist-1 (calc-dist-all expansion (car galaxies) (cdr galaxies) 2)) + (total-dist-2 (calc-dist-all expansion (car galaxies) (cdr galaxies) 1000000))) + ;; 10289334 + (format #t "Part 1: ~d" total-dist-1) + (newline) + ;; 649862989626 + (format #t "Part 2: ~d" total-dist-2) + (newline)) diff --git a/2023/day11/input.txt b/2023/day11/input.txt @@ -0,0 +1,140 @@ +...........#...............................................#...................#.....#.............#........................................ +..................#..................................#..................#.....................#................#...................#.......# +....#........................................................................................................................#.............. +..............................#........#..................................................#................................................. +.............#........#...........................#..........................#..............................#............................... +......................................................................................................#.............#....................... +...........................................................#......................#........................................#................ +.........#.....................................#.......................#..................................................................#. +..................#.......#....................................................................#...................................#........ +#..........................................#...............................................................#......#......................... +..................................................#......................................................................................... +..............................................................#.....#....................#.................................................. +......#..............................#...................................................................................................... +...............................................#......#.................#..........#................................#....................... +..............................................................................#........................#.................................#.. +.............#....................................................................................#............................#............ +.......................#.............................................#...................................................................... +...............................#....................#.........................................#.....................................#....... +..........#.................................................................................................#............................... +..........................................................................#.......#..........................................#.............. +...#..............................#............................#....................................#..................#.................... +..................#..........................#....................................................................................#......... +.........................#.........................#.......#..........#...................#................................................. +........#.....#.............................................................#...................#........#.................................. +..............................#.........#......................................................................................#......#..... +......................................................#......................................................#.............................. +....................................................................................................#....................................... +.............................................................#.......#.....................#.......................#...............#........ +..#...................#......................................................................................................#.............. +......................................#..........................#.....................#.................................................... +.............#.............................................................................................................................. +...............................#.................#.........................#...................#..............#............................. +........................#...........................................................#................................................#...... +........................................#................................................#..........#......................................# +......................................................................#............................................#......#................. +............................................................................................................................................ +...........#................................................#.................................#............................................. +.....................................#......#............................................................................................... +....#............#..................................................#.............#....................#..........................#......... +............................................................................................................................................ +.......................#.....#...........#............................................................................#..................#.. +.......#................................................#...............................#......#............................................ +...................................#...........................#...........#....................................#........................... +#.............................................................................................................................#............. +...............................#...........................#......................#.......................#................................. +............#.............#..................#.............................................................................................. +....................................................#...............#........#.........#...........................................#........ +...............................................................................................................#......#...................#. +.......#.............#..............#....................................................................................................... +.............................................................................................................................#.............. +............................................................................................................................................ +.................#............#...............................#.......#......................#..........#...............#................... +........................#..........................................................#................................................#....... +.#.................................................#........................................................................................ +...........#.................................#.....................................................#........................................ +......................................#.....................................................................#......#........................ +.......#............#...................................................#.............................................................#..... +...............#.....................................#........#...............#............................................#...............# +...................................................................#....................#................................................... +.................................................#.......................................................................................... +..................#........................#..................................................#.......#...............#..................... +............................................................................................................................................ +......#...........................#..............................#..........................................................#............... +...........................................................#.....................................................#.......................... +...........................#........................#..............................................................................#......#. +...........#..............................................................#..................................#.............................. +..........................................#................................................................................................. +...#..........................................................#.........................#.......................................#........... +........................................................#......................#..........................#..........................#...... +.......................#.............................................#.............................#........................................ +.......................................................................................................................#.................... +......#......#....................#......................................................................................................... +...............................................................#............#......#.....#..............#..........#..........#............. +.#...............#.....................#......#.....#....................................................................................... +...................................................................#.........................#...........................................#.. +............................................................................................................................................ +...........................................#...........................#..............................#..................................... +......#....................................................#....................#..............................#....................#....... +......................#.......#....................#........................................................................................ +............#.................................#................#...............................#....................#....................... +.......................................#.................................................................................................#.. +............................................................................................................................................ +...#.....................#.........................................#...................#....................#....................#.......... +.................#..............#.....................................................................................................#..... +...........................................................................#....................#.................#......................... +.......#...................................................................................#................................................ +............#..........#.................................................................................................................... +......................................................................#.......#.............................................#............... +........................................................................................................#................................... +....#.........................................................#............................................................................. +..........#....................#....................#......................#..................#......................#...................... +#...............#...................#.........#..........#...................................................#.............................. +...................................................................................................................................#........ +............................#.........................................................#..................................................... +..........................................#...................................#............................................................. +...#.................................................#.................................................................#.....#.............# +......................#............#................................#...............................#.............#..................#...... +.........................................................................................................#.................................. +............#.....................................#.......................#...............#...................#............................. +.#....................................#.....#....................................................................................#.......... +........#........................................................#.......................................................................... +...................#........#............................#.............................#..............................#..................... +..............................................................................................................................#............. +....................................................#..........................#............................................................ +........................#.......................................................................#............#............................#. +..........................................#................................................................................#................ +..................#..........................................#.........................................#..............................#..... +.............#...................................#..................#........................#.............................................. +.............................#...........................#......................#..................#........................................ +...................................#................................................................................#........#.............. +......#.................................................................#..............#.................................................... +.................#.........................................................................................#................................ +............................................................................................................................................ +...........................#...........#.........................................#...................#................#............#.....#.. +.#..........................................................................................#............................................... +.....................#............................#.....#...................#....................................#.......................... +.............................................#.................#......................#..................................................... +...................................#................................#....................................................................... +......................................................................................................#..................................... +......#.....#....................................................................................#.............................#.....#...... +.......................#...................#........#......................................#................................................ +.............................................................................................................#.............................. +#................#..........#........#..........#.......#......#........................................................................#... +.....................................................................#.........#........#.....#......#.................#.................... +................................#........................................................................................................... +.........................#..............#....................................................................................#.............. +..........#................................................................................................................................. +..........................................................................................#........#........................................ +.................#...................#..........#.......#......#...................................................#...............#........ +............................................................................................................................................ +.............................#................................................................#............................................. +...#.......#................................................................#........#...................#............#.........#..........# +........................#.................#................#................................................................................ +.....................................................................#.....................................................#................ +....................................................#............................#......................................................#... +.#..........................................................................................#......#...............#..............#......... +............................................................................................................................................ +..........#........#............#.........................................................................#................................. +........................................................#..........#........................................................................ +.....#.............................................#.........#....................#.............................#.........#.................