diff options
Diffstat (limited to 'day24.rkt')
-rw-r--r-- | day24.rkt | 76 |
1 files changed, 76 insertions, 0 deletions
diff --git a/day24.rkt b/day24.rkt new file mode 100644 index 0000000..6b56406 --- /dev/null +++ b/day24.rkt @@ -0,0 +1,76 @@ +#lang racket + +(require data/heap) + +(define field + (for/list ([line (file->lines "day24")]) + (for/list ([char line]) + char))) + +(define width (length (first field))) +(define height (length field)) + +(define period (lcm (- width 2) (- height 2))) + +(define pos (mutable-set)) + +(for ([(line y) (in-indexed field)]) + (for ([(c x) (in-indexed line)]) + (match c + [#\# (for ([z (in-range 0 period)]) + (set-add! pos (vector x y z)))] + [#\< (for ([z (in-range 0 period)]) + (set-add! pos (vector (+ 1 (modulo (- x 1 z) (- width 2))) y z)))] + [#\> (for ([z (in-range 0 period)]) + (set-add! pos (vector (+ 1 (modulo (- x 1 (- z)) (- width 2))) y z)))] + + [#\^ (for ([z (in-range 0 period)]) + (set-add! pos (vector x (+ 1 (modulo (- y 1 z) (- height 2))) z)))] + [#\v (for ([z (in-range 0 period)]) + (set-add! pos (vector x (+ 1 (modulo (- y 1 (- z)) (- height 2))) z)))] + [#\. (void)]))) + +(define source (index-of (first field) #\.)) +(define target (index-of (last field) #\.)) + +;; close behind source and target +(for ([z (in-range 0 period)]) + (set-add! pos (vector source -1 z)) + (set-add! pos (vector target (length field) z))) + +(define (first<=? a b) + (<= (first a) (first b))) + +(define (distance pos source target period) + (define distances (make-hash)) + (define queue (make-heap first<=?)) + + (hash-set! distances source 0) + (heap-add! queue (list 0 source)) + + (let loop () + (if (zero? (heap-count queue)) + #f + (let ([item (heap-min queue)]) + (heap-remove-min! queue) + (if (equal? (vector-take (second item) 2) target) + (first item) + (let ([ndist (+ 1 (first item))] + [z (modulo (+ (vector-ref (second item) 2) 1) period)]) + (for ([x (list -1 1 0 0 0)] + [y (list 0 0 -1 1 0)]) + (let ([neighbor (vector (+ x (vector-ref (second item) 0)) + (+ y (vector-ref (second item) 1)) + z)]) + (unless (set-member? pos neighbor) + (let [(dist (hash-ref distances neighbor 999999))] + (when (> dist ndist) + (hash-set! distances neighbor ndist) + (heap-add! queue (list ndist neighbor))))))) + (loop))))))) + +(let* ([a (distance pos (vector source 0 0) (vector target (- height 1)) period)] + [b (distance pos (vector target (- height 1) a) (vector source 0) period)] + [c (distance pos (vector source 0 (+ a b)) (vector target (- height 1)) period)]) + (values a ;; 332 + (+ a b c))) ;; 942 |