commit f79c9e5b1cb762d0173bc82fe55a91d7782cc789 parent 4118813ce11ef321a27230231c8e4276934215e8 Author: Shimmy Xu <shimmy.xu@shimmy1996.com> Date: Fri, 15 Dec 2023 02:38:24 -0500 Add 2023 day 14 Diffstat:
| A | 2023/day14/day14.scm | | | 134 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 2023/day14/input.txt | | | 100 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
2 files changed, 234 insertions(+), 0 deletions(-) diff --git a/2023/day14/day14.scm b/2023/day14/day14.scm @@ -0,0 +1,134 @@ +(use-modules (ice-9 popen)) +(use-modules (ice-9 rdelim)) +(use-modules (ice-9 format)) +(use-modules (ice-9 hash-table)) +(use-modules (ice-9 receive)) +(use-modules (srfi srfi-1)) + +(define (parse-input filename) + (let ((file (open-input-file filename)) + (platform '())) + (while #t + (let ((line (car (%read-line file)))) + (if (eof-object? line) + (break) + (set! platform (cons (string->list line) platform))))) + (reverse platform))) + +(define (array-to-dict platform) + (let ((platform-dict (make-hash-table)) + (y-max (1- (length platform))) + (x-max (1- (length (car platform))))) + (do ((y 0 (1+ y))) ((> y y-max)) + (do ((x 0 (1+ x))) ((> x x-max)) + (hash-set! platform-dict + (cons x y) + (list-ref (list-ref platform y) x)))) + (values platform-dict x-max y-max))) + +(define (display-platform platform-dict x-max y-max) + (do ((y 0 (1+ y))) ((> y y-max)) + (do ((x 0 (1+ x))) ((> x x-max)) + (display (hash-ref platform-dict (cons x y)))) + (newline))) + +(define (between x a b) + (and (>= x a) (<= x b))) + +(define (swap-vals dict a b) + (let ((val-a (hash-ref dict a)) + (val-b (hash-ref dict b))) + (hash-set! dict a val-b) + (hash-set! dict b val-a))) + +(define (move-rock platform-dict x-max y-max dx dy x y) + (let ((curr-x x) + (curr-y y)) + ;; (display (cons x y)) (newline) + (while #t + (let ((next-x (+ curr-x dx)) + (next-y (+ curr-y dy))) + ;; (display (list "checking" (cons next-x next-y) (hash-ref platform-dict (cons next-x next-y)))) (newline) + (case (hash-ref platform-dict (cons next-x next-y)) + ((#f) (break)) + ((#\#) (break)) + ((#\O) (break))) + ;; (display (list "passed" (cons next-x next-y))) (newline) + (set! curr-x next-x) + (set! curr-y next-y))) + ;; (display (list "moving rock from" (cons x y) "to" (cons curr-x curr-y))) (newline) + (swap-vals platform-dict (cons x y) (cons curr-x curr-y)))) + +(define (tilt-platform platform-dict x-max y-max dx dy) + (if (and (= dx 0) (= dy -1)) + (do ((y 0 (1+ y))) ((> y y-max)) + (do ((x 0 (1+ x))) ((> x x-max)) + (if (equal? (hash-ref platform-dict (cons x y)) #\O) + (move-rock platform-dict x-max y-max dx dy x y))))) + (if (and (= dx 0) (= dy 1)) + (do ((y y-max (1- y))) ((< y 0)) + (do ((x 0 (1+ x))) ((> x x-max)) + (if (equal? (hash-ref platform-dict (cons x y)) #\O) + (move-rock platform-dict x-max y-max dx dy x y))))) + (if (and (= dx -1) (= dy 0)) + (do ((x 0 (1+ x))) ((> x x-max)) + (do ((y 0 (1+ y))) ((> y y-max)) + (if (equal? (hash-ref platform-dict (cons x y)) #\O) + (move-rock platform-dict x-max y-max dx dy x y))))) + (if (and (= dx 1) (= dy 0)) + (do ((x x-max (1- x))) ((< x 0)) + (do ((y 0 (1+ y))) ((> y y-max)) + (if (equal? (hash-ref platform-dict (cons x y)) #\O) + (move-rock platform-dict x-max y-max dx dy x y))))) + platform-dict) + +(define (compute-load platform-dict x-max y-max) + (let ((load 0)) + (do ((y 0 (1+ y))) ((> y y-max)) + (do ((x 0 (1+ x))) ((> x x-max)) + (if (equal? (hash-ref platform-dict (cons x y)) #\O) + (set! load (+ load (- (1+ y-max) y)))))) + load)) + +(receive (platform-dict x-max y-max) (array-to-dict (parse-input "input.txt")) + (tilt-platform platform-dict x-max y-max 0 -1) + ;; 110565 + (format #t "Part 1: ~d" (compute-load platform-dict x-max y-max)) + (newline)) + +(receive (platform-dict x-max y-max) (array-to-dict (parse-input "input.txt")) + ;; Load pattern repeats after 102th cycle (89803) every 42 cycles. However the + ;; repeating pattern contains duplicated entries, so can't use tortois-hare to + ;; automate this. + (let ((hist-load (make-hash-table)) + (cycle 0) + (max-cycle 1000000000) + (period #nil) + (period-start #nil)) + ;; I see - here's what you do, for every repeat, check backwards to see if + ;; (last-repeat, curr-repeat] is the same as (last-repeat - diff, + ;; last-repeat]. If so we have a cycle - this should work as long as there's + ;; at least one non-repeating element in the cycle. + (while #t + (tilt-platform platform-dict x-max y-max 0 -1) + (tilt-platform platform-dict x-max y-max -1 0) + (tilt-platform platform-dict x-max y-max 0 1) + (tilt-platform platform-dict x-max y-max 1 0) + (set! cycle (1+ cycle)) + (let ((curr-load (compute-load platform-dict x-max y-max))) + (if (and (hash-ref hist-load curr-load) + ;; hack + (= curr-load 89803)) + (begin + (set! period-start (hash-ref hist-load curr-load)) + (set! period (- cycle period-start)) + (break))) + (hash-set! hist-load curr-load cycle)) + (if (>= cycle max-cycle) + (break))) + (let ((terminal-cycle (+ period-start (floor-remainder (- max-cycle period-start) period))) + (terminal-load #nil)) + (hash-for-each (lambda (k v) (if (= v terminal-cycle) (set! terminal-load k))) hist-load) + ;; 89845 + (format #t "Part 2: ~d" terminal-load) + (newline)))) diff --git a/2023/day14/input.txt b/2023/day14/input.txt @@ -0,0 +1,100 @@ +.O.....##O.O#..O#....##O#.#.#..##O#..O.....#.OO..O.O.O.O...O....#O...OO....##.O..OO.O......O..O..... +....O..#O....#...#OO..#..#..O.....#O......O.O.#..OO..O....#..#.OO....##O...O..##...#.O...O.#...#.O#. +.O.O#.O...O...O....O...O#....#.#O#...O...#.#..........O#...O#O..O..#.OOO..O.O.....O#.........#O...O. +.O....O.OO.#.....#.#O......##O..O.O.##.#..O##O.O.#OO....O.O..O#.OOO..O..#..##.#...#.O.#O.#.#.....O.. +..O......O..O.O.#.OO.OO...#.O....#...#O..OO.#.O......O....O.O.....O.#.OO..O.OOO.......O.O...##O...O# +.O.O.........#.O#.#OO##..#OO..OOO#....#....O.O..#.O......#.OO..#..O.O..O.O..#....#.O#..OO###.....#.. +.O..#.#.OO.#...........#..O#....O..O.O#.......#.OO.#OO....O.#O.#.....#.OO.#...#..O..O##.O.O##..#.#.O +..O..#...#..OO.#O.#.O.O#O...O.O..O..O#..#..#..O..........O.O#.....O...........O.###..#.#..O#.#.O...# +#..O...#.O..O.O......#O.O##...##...OOO....#.O.O#OO.##...OO.OOO..#.O..##.....O..O.O.#O.O..#.O#O...O.# +OO....#.#...O...O.#...##O..###O.......OO...#.#...O.#..#.O......O....#.O#..#O..O...OO...#..O#..O....O +O#..#O...##O.....#.O.#.O...##......#...#OO#...O.......#.#.OO#.#..#..O#OO...O.......O.#...#.##....O.. +#............O#....##.O.O..#O.#.OO.O...OOOO#.......O#O..O.......O#OO#...O.O....#.....#O.#.#..#.OO.O# +#O.O.....O....#O..OO.#O.#....#.##O.O...........O.##.#O##O...O#..O.O.O#......O...O.#....#OO#.#..O..## +.O..#O.O.#....O.........#.....OOO.......O.#O.....#OOOO#.O##O.#.O...O..#OO...O.....O..#.#......OO.O.# +O..O...O......O.O...#..#...#.OO.#.OO.O..O...#...#...O.###....#O#.O..O..#O..#.O.##.......O#..#O...... +#..O...#...#OOO.#.###.#....#..O.O.#.#......OO.#.#...#....#.OO.O..#.O...#.#.....O.#O.O.#O..O....O.O.. +OOO.#...##.OO.O....#.O.###.#.....O.OO#..#....OO...O#.#.O..#O.#..#.O..O....#O.OO#...O..#.....#O...O.O +.#.#...........#.............O.#..##.#O.#.O......#..O..OO.##O.O##.....#..O.O..O.OO..OO.#O.O.##O.O... +..O......O..##O.O...##......##OO..#O.#..#..OO...#...O.O..O..O.O.O##.#O.O#.#.O#....##.O.....O..#.O... +.#...#O.#.#....O..O..O#.O.....O..O.#.O....O.O...#.O#......O..O.O...#.#...O..##O...#.#...O.##..#..O#. +.O#..O.#....#.OO.#.....#O....O#O.#..#.O.....#......#O....O.........#.#O.OOOO#O.OOOO.#.....O.#.O..#OO +#..#.....O.....#.....##.O....##.O.O#OOO..O....O...#....O.O.....#.O#.O....O.O....#..O....O###.#..O#O. +...O...#..#O.O.O.......O.....O#O....#.#OO#......#..OO.....#.#...#...OO.O#O#O.#.#O....#..O....O...OO. +..#.##.#.#..............#O...#O#..##O.#.....O.#.#......O.....O#..O.O.O.#OOO####O.....O..##.O.OO.#..# +O...O#.O....#.O...........#......##.O.O#.....#.O..OO#...O#.##O..##.....#.O.O.....O#.#O.O..O...OO#... +OO.........##....##.O.O.OO.....O...........O.....O..#..#.OO........#O...OO.....#.O.........#........ +#..#.##O#.O#O..#..O...#.#.O.OO...##O..#..O.O........#.#O#..#..O..#.O.....O...O..O.O....#...O#....#.. +O.#.......O..O#O...OOOO#OO..O..#....#O..#...OO..#....O......#..#....O.O#.#....O.OO..O....O....OO..#. +O.OO..........#..O.#O#.#.#O...##..#..O##..##O#.OO......O..#.O.O.O.OO....#.....OOO#.O.#.O.#O##.#OO.#O +#..O....##...#.O.OO.O.O......#.OO...#......O........OO.#O..#.......OO..O..O...#.O......O.#O#O#...#OO +#...#..#OOOO#.#O#O.O#.O.#.###...O..#.....O..............O.....O.#.O....O.O....#...........O...O#.O.. +.#O.O.OOO.....O...O...#.........#..O..O.#..#.O#....O#O..OO.........OO#.........#..OO.O.......#...O.. +..#...O...#O...O..#.....O..O.#.......O...O.O.O.....O......O...#.....##.O.O#..O.#.O..#.O..O..OO...... +.O.O..O..#O..O#OO#OO.#....O...#.O#.O.#...###........O.....O..O.OOO.O...#....O.O....O..OO.###...O...O +.#.....O..OOOO..#...#.#.O......O..O..#.##.#...O#..O.#.#.O#.....##...##O.......##..O.O.O.......#..OO# +...O...O...O..O...#..O#....O....#......O..OO#...O...#.#O.##.#..O..#.##O..#.#...O.....#.#O.O..O.O##.. +.#OO#.....#O...O.#.OO......OO...O..O..O...#............#.OO##..OO..O.O......O..O...O...O...O...O.... +...O....O..#.O.O###..##.O..O.O.#...#.OO.O..O.O.O.O.#.O..#.O##.......O..#......O.O..O.OOO..##O....#.. +O...O.#..........O..OO.O#...#OO.OO..#O#.......O..#....O.......O.#OO.O.O.O.O##.OO..##...O#..OO#..#.#. +.O....#.#O............OOO.......#.O..#.#...#O......#....#.##..O.#.##OO..OO.#.#......O.O.....#.OO...O +..O...O#...O..O..#..#O..O#..O#..O.OO..O#.#...O####..O...O#..##......O#....O....O..O...O........O..O. +O.O.#..#.#..##..#.#....#..#..#.###.O#.O....OO...#....O#.....#.........#.###..#.#OO..#O...O...O.#.... +..OO.#.O.....O.O..#.......O...O..##.#.#O..#....#OO.O....O......#.OO#....O..#O.O...#.OO#O.#....O..O.# +#...O#.O...O..O..O.O#...O.O.......OO....OO..O#.O..............O..O#.#...O#....OO..OO..O....#.#O.O..# +O.O.##..O#...#O......O...O...OOO.....#....O#...O#.#.#........O..##..##.O..##O.O..O..#............O.# +.....#....O..O.O...####...#.O.#..#.#..#....#...#.OO.#..##...OOO.#..#......O.OOO.....#O#.......OO.... +...#.O#.O...#.OOO#.......OO.#..O..O##.#OO.O.#.O.O.O#.....#.O.........O...O....#.O#....#.#O..O..#..#. +...#..O......O..#.O...#.....#....O.....OOO..O..O##O#...O...O.#...O....#OOO##..........O....#O....... +...O.O.#.#...O.O#O#.#O#O....#....O..O....#.O.O#.....#....O..O..............O...##O.O....O..#....#..O +O.....O..#O....O..O##O..#..#.O.OO..#...##........#.#.#.O..###...#O.##..##..#O..O.OOO...O.O.....O.... +..##.......#...O.O.O#O.#...O..OO#OOO.#..O....#...O..#....#.....OO..OO.#....O.....#.##...O.#..O...#O# +O##....O.O..##OO.#.#.O#..##............OO.O.O.#.....#..OO...#...O..##O..........#.......O..OOO...O.# +#OO.......O.O..O...#...O#.#...O..O.....O..OO.O...#OO...O....O...O.O...O....O......#.#.O.OO.....#.... +...#..#OO..#..O.OO.#..#.....O..#O..#....#..#...O...O...OO..O#..O...O.........#...OO.O.#OO#.#.O..OO.# +..O#.O.O.#.#.....#...O..O#O..#..#..#.#...O..O.#.O.OO..OOO.#..OO.#.#.....OO...OO#O#.#..........O.##O. +...O#..O..O..O..#OO.###..O.........O#...OO.....O..O#....#O.O.O..O#.#...O#OO.O..#..O.O.O...O.OO.....O +.....O.#.O..O...##..#.O#O.#.......#O.OO#...O...##.OO#...OOO....#..#..#O...O.O#O.O..O.#OO...#..#.O#.O +....#...#O.O...##.#...#...##.O....#.#.O.O..##.O...#O...O#OO#..#.O.....#O#O.O.O#O...#.#.O.O..#...O..O +.O...O....O.....#.#O.#.##.##..O#..OO#O..#..O.#..O..O#....O#..#..OOOO.#.O..OO.O.##......#...#......#O +O....O.O...O#.OOO.#..O.......#..#....O#O........###..O..#.O.O.O.......#....O.O.O.##.O..#..O....O..#. +..O..OO...................OO...#........#.#...O..#.O.......#...O.......O..O#...O.#.O#....O#.O...#... +.O..#......O#O#..#......OOO........OOO........O#....O#.OO.#.......O#.OO.......##.....OO.O......O.O.. +.#O..#O#O#..###.............##....#..O...#.O#O..O###.O..##..#..#OOO#.#...O.#.O.....O.#...........#.. +.....O..O..OO.O.......OO.O.....#..##.##OOO#.#O..O.#....OO#OO...#...##...#.O...O....OO.O.##..O#..###. +OOO#.....#..#.O......O...O...#O..#....O.OO.#...O..........O.....O..O.....OO...#..O..O.#OO.O..OO.#... +O.OO.#...#.#...#...OOO.......O#....O....#....O.#...O.#.##.#OO.O..##......O.##OO#.......#.O...O.OOO.. +.....#.........#.............O##.##..O..OOOO....#....O..#..O..#...O...OO.#O....#O.....O#O#......#..# +.#.O#O#.O#OOO.......O.O......O.#.#....#O..O..#..#.......#O.O#.....###..O.#.O......#.#.O#......#O.... +..#O#.#.O.#O.OO.#O.O####.#..##.O.....#...#O#..#O#O#....O....OO#....O#.O...O.........#O##.O.O....#... +.OO..#O..O#.....OO....#O.O.....OO#...O.....OO.......#..O#...OO.#.O..O.O.#O.OO#.#O.....O...O..O.O.O.. +..##OOO.O.....##..O.#.#.##..#...##.O..O....OO...##O..#.OO....#.O#.......O..O..O.#.#.#....O.O.O#O..O. +O#.#..#.##.O..O.O.....OO#....OOO.O.O.OO.....O...###.......#O...#....#.OOO.#O..OO...O..#..O.O.O.....# +OO#.....OO.O.#OO...#O...O.....O..O.#....O............#O.O.O....#.......O.O..OOO...#...#...#......... +......#..O.#.....O....OO..##..##........O.#O..........#OOOO......O......O.O##..O#O#O.O..#.#O.....#.. +..O..OOO.........#.O..O..#..O..O###..O..##...O..#.O.O..#.............O.....##O.OO..#.#..O.##O.##O.O. +..#...#..O........O.O.#..##.O.#O......O.O.#OO..O..#..#O.O.....#.##..##..#......OO..#.O...#..#.O.O#.. +..#...#..O......#......#..O.##.#....OO..#...#.....O.O.O..#.##...##..OO......#.OO....O..O..O.O.#.O... +......O...#O......O.O..OO.O...#O..##..#...#..#....##........##O.O......O.O...#O....OO............... +.....O..#.##....OO.O...O..O..O.O...#....O.#.O....#.#..OO......OO#...#.###..#O...O....O..##O.#..OO.O. +...OO...#...##.##.#..#...#.O..#OOO.....#.#..O...O.##O.#.#..#O.#O.#......O#......OOO.O#.....#......O. +OOO.O.O...###...#...#.#...OOO.O...O..O...#....O.OO...O..##..O........#.O.#....#......##.#O..#.#O#O.. +....OO#.#.....O..O..#......OO.........O....O.....O..O#.#..##O.....#.#.#....#..O#..#OO.O...#.OO##O.OO +O.O..#..O.......O.O....O..OO.O...OO.O.......O###OOO##.O...O...#O#OO......O..O..O...#....##...O..O... +O#.O#.....O...O.O...#.##.#.......###....O.O.##......O....O..#O..#O#.O..##OO..O.###..O.OO#...#....##O +O..O..O............OO.....O.O..O...#............#O..O..O#...O..O.O##........#.#.....#....O#O.......# +............O....O#.OO...##..OO#O...#.....#OO..O#.......##O.O#...OO....#..O.....#..O...O.OO#O.O...O. +.#...#...OO...###.OO.OO....#..O...#...O.O...O....#........O.#..O#.OO..#....#O..O##.......O...#..##.. +#.O.O#.O..#....#...#O#...OO..#...O.O#.OO.##...............O.#......O.....#..O..#..O..#O..O..##.##.O. +O..##.....OO.O##.O..#.O........OOOO...#..##.........#.#..O.O.OO#..O##O#....O.O#.....O.....O#..#...## +O......#.O...#...O#.#...O#........O..#....#..#.O.......O.......#.....#..O......#..O#..O#...#.#O.O... +..........OO###.#.O.O..#...##..##.#.........O#O..O.#O.......O..O#...#..O.O..#.O....#..O..OO.O......O +.OOOO..O....O.....#.....#.#.O.#O.#.O....##...O.O#O.OO.....O.O#.#...#..#.#O.O.##...O...OO..O....OO#O. +O...###O...###O...#...#O...#....#..O#..#O#....O.##..#.....#.#OO#.O...O.##O#...O.....#.......#.O..... +O...#.OO.O##.O.....#.....O..O...#.O...O.#.....#.O....O.#...#OOOO..#.#O...O...##..##..........O....O# +..OOO..O..#...OO....##....O....O...O....#..O..##.O...O.O.....#.#.O.#.#..O#O.#.....#.O.#.#.....O.O#.. +#....O.OO##OO....#...#.....#....###.#..O..O.O...#.....#..O.........#O#...#............OO....#.OO..O. +.O.O#.#O#.O..O........#..O#...O.#..##O....O#O..O#O...#.O...#.....#.#......#......O...#...#..O..#.... +.#..O..O..#O..OO....OO#.#...O.....O....#....O..O#...OOOO#.#...#..##.O.....O.....#..O.O..#...OO#OO..# +....#O.##.O.....#..O..OOO.#.O..#.O.....#O.O.##..#OO.......O..##...O#.#.OO..O..#...#......#...O.O.... +#......#.#.....#O...O..#..#..###..O...##.OOO.O...#.O..#..##.O...#..O..O....O.......#OO.....#....OO..