day14.scm (5391B)
1 (use-modules (ice-9 popen))
2 (use-modules (ice-9 rdelim))
3 (use-modules (ice-9 format))
4 (use-modules (ice-9 hash-table))
5 (use-modules (ice-9 receive))
6 (use-modules (srfi srfi-1))
7
8 (define (parse-input filename)
9 (let ((file (open-input-file filename))
10 (platform '()))
11 (while #t
12 (let ((line (car (%read-line file))))
13 (if (eof-object? line)
14 (break)
15 (set! platform (cons (string->list line) platform)))))
16 (reverse platform)))
17
18 (define (array-to-dict platform)
19 (let ((platform-dict (make-hash-table))
20 (y-max (1- (length platform)))
21 (x-max (1- (length (car platform)))))
22 (do ((y 0 (1+ y))) ((> y y-max))
23 (do ((x 0 (1+ x))) ((> x x-max))
24 (hash-set! platform-dict
25 (cons x y)
26 (list-ref (list-ref platform y) x))))
27 (values platform-dict x-max y-max)))
28
29 (define (display-platform platform-dict x-max y-max)
30 (do ((y 0 (1+ y))) ((> y y-max))
31 (do ((x 0 (1+ x))) ((> x x-max))
32 (display (hash-ref platform-dict (cons x y))))
33 (newline)))
34
35 (define (between x a b)
36 (and (>= x a) (<= x b)))
37
38 (define (swap-vals dict a b)
39 (let ((val-a (hash-ref dict a))
40 (val-b (hash-ref dict b)))
41 (hash-set! dict a val-b)
42 (hash-set! dict b val-a)))
43
44 (define (move-rock platform-dict x-max y-max dx dy x y)
45 (let ((curr-x x)
46 (curr-y y))
47 ;; (display (cons x y)) (newline)
48 (while #t
49 (let ((next-x (+ curr-x dx))
50 (next-y (+ curr-y dy)))
51 ;; (display (list "checking" (cons next-x next-y) (hash-ref platform-dict (cons next-x next-y)))) (newline)
52 (case (hash-ref platform-dict (cons next-x next-y))
53 ((#f) (break))
54 ((#\#) (break))
55 ((#\O) (break)))
56 ;; (display (list "passed" (cons next-x next-y))) (newline)
57 (set! curr-x next-x)
58 (set! curr-y next-y)))
59 ;; (display (list "moving rock from" (cons x y) "to" (cons curr-x curr-y))) (newline)
60 (swap-vals platform-dict (cons x y) (cons curr-x curr-y))))
61
62 (define (tilt-platform platform-dict x-max y-max dx dy)
63 (if (and (= dx 0) (= dy -1))
64 (do ((y 0 (1+ y))) ((> y y-max))
65 (do ((x 0 (1+ x))) ((> x x-max))
66 (if (equal? (hash-ref platform-dict (cons x y)) #\O)
67 (move-rock platform-dict x-max y-max dx dy x y)))))
68 (if (and (= dx 0) (= dy 1))
69 (do ((y y-max (1- y))) ((< y 0))
70 (do ((x 0 (1+ x))) ((> x x-max))
71 (if (equal? (hash-ref platform-dict (cons x y)) #\O)
72 (move-rock platform-dict x-max y-max dx dy x y)))))
73 (if (and (= dx -1) (= dy 0))
74 (do ((x 0 (1+ x))) ((> x x-max))
75 (do ((y 0 (1+ y))) ((> y y-max))
76 (if (equal? (hash-ref platform-dict (cons x y)) #\O)
77 (move-rock platform-dict x-max y-max dx dy x y)))))
78 (if (and (= dx 1) (= dy 0))
79 (do ((x x-max (1- x))) ((< x 0))
80 (do ((y 0 (1+ y))) ((> y y-max))
81 (if (equal? (hash-ref platform-dict (cons x y)) #\O)
82 (move-rock platform-dict x-max y-max dx dy x y)))))
83 platform-dict)
84
85 (define (compute-load platform-dict x-max y-max)
86 (let ((load 0))
87 (do ((y 0 (1+ y))) ((> y y-max))
88 (do ((x 0 (1+ x))) ((> x x-max))
89 (if (equal? (hash-ref platform-dict (cons x y)) #\O)
90 (set! load (+ load (- (1+ y-max) y))))))
91 load))
92
93 (receive (platform-dict x-max y-max) (array-to-dict (parse-input "input.txt"))
94 (tilt-platform platform-dict x-max y-max 0 -1)
95 ;; 110565
96 (format #t "Part 1: ~d" (compute-load platform-dict x-max y-max))
97 (newline))
98
99 (receive (platform-dict x-max y-max) (array-to-dict (parse-input "input.txt"))
100 ;; Load pattern repeats after 102th cycle (89803) every 42 cycles. However the
101 ;; repeating pattern contains duplicated entries, so can't use tortois-hare to
102 ;; automate this.
103 (let ((hist-load (make-hash-table))
104 (cycle 0)
105 (max-cycle 1000000000)
106 (period #nil)
107 (period-start #nil))
108 ;; I see - here's what you do, for every repeat, check backwards to see if
109 ;; (last-repeat, curr-repeat] is the same as (last-repeat - diff,
110 ;; last-repeat]. If so we have a cycle - this should work as long as there's
111 ;; at least one non-repeating element in the cycle.
112 (while #t
113 (tilt-platform platform-dict x-max y-max 0 -1)
114 (tilt-platform platform-dict x-max y-max -1 0)
115 (tilt-platform platform-dict x-max y-max 0 1)
116 (tilt-platform platform-dict x-max y-max 1 0)
117 (set! cycle (1+ cycle))
118 (let ((curr-load (compute-load platform-dict x-max y-max)))
119 (if (and (hash-ref hist-load curr-load)
120 ;; hack
121 (= curr-load 89803))
122 (begin
123 (set! period-start (hash-ref hist-load curr-load))
124 (set! period (- cycle period-start))
125 (break)))
126 (hash-set! hist-load curr-load cycle))
127 (if (>= cycle max-cycle)
128 (break)))
129 (let ((terminal-cycle (+ period-start (floor-remainder (- max-cycle period-start) period)))
130 (terminal-load #nil))
131 (hash-for-each (lambda (k v) (if (= v terminal-cycle) (set! terminal-load k))) hist-load)
132 ;; 89845
133 (format #t "Part 2: ~d" terminal-load)
134 (newline))))