From 3aae077b4fd439d5f5ef4778b7efc37e1986ccca Mon Sep 17 00:00:00 2001 From: Leah Neukirchen Date: Sun, 25 Dec 2022 14:02:23 +0100 Subject: day24 --- day24 | 22 ++++++++++++++++++ day24.rkt | 76 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 98 insertions(+) create mode 100644 day24 create mode 100644 day24.rkt diff --git a/day24 b/day24 new file mode 100644 index 0000000..f64ff83 --- /dev/null +++ b/day24 @@ -0,0 +1,22 @@ +#.###################################################################################################################################################### +#^>^^<><^>^^v>vv^v^>>^<>^v^>>v>v><^..>v>>>>^>>.v>.v><<.^>>^^^>v>>^.>vv<<.<^v>^v<>^^.^.<<>^<^>.>vvv><^<^>v.^<># +#<..v<<^^.^^v<<>>v>>.<>>^vv^^v>v^>>>v^vv<<><>>v.>.v>.<..v>^^>^<><>vv>>v>.><.<v^vv<>vvvvv^<^v>.# +#<>>^v^v>v>.^v<>vvv>>^<<^>>v^^^.<<<.>>v.>.v^.>>>^><>v>>v^<.v^<.vv^>^v<><>>v^^<^>..<<^<<<^<^>^<>v>vvv>>^<<>><><<^^.<v># +#>.<<<^..>><>v>^vv>vv^^>>.><^>><^.^<>^v>.<^<>>>^>>^><^><^.^>.><><><^>^>>^>>>^<.>>^<^>vv<^v^>.>^>>vv.^<>>^>>>><>.^.>v<.^<>v^>v>^^>>v<><># +#>>v<^v^<^^><>><>.>v^v>^v.>v^.>>.><><<>^><<>^>^v>v^^^>>^v<<<>vv>>v<^^^<<<<>v<^>>.^v>><.v^<.>>vv>v><><.^^^v><.<^>>><# +#>>vv<^vv<<>^v<^v.>>v<><>.>^.^....<<^<.>^^^<><>.>^<>>^^><>>v^vv^<>v^^^^v.<><^><^v<<.v>>><>>><.v>v>>^.^>^># +#>^v>v^vv^.^<<<^><>v^<.>>^^^<^<^>.>>^<<.^>><<.>^^.vv>.vv><^^.<<v..<^<.vvv<..v>.>>^v<^^<^v^>^.<<^^.^^<>v<<<v>><># +#<^>>^>><<>v.v>.vvv><^>v..<<<>>><^v><^>..<^^v>.<<>.v..^<.^vv.>^><>vv><<>v^>v>><^^>^>><^>.>^^<<><><^.>^v<>v^.>v><>>.v^..v># +#<.<<<^><><^<<^>><..>^<<<>^.<>>v..v^^<<<.><.^.<^>^vvv^^^^>v>^>>>>v<><>v.<>>^.<>v^<.^vv>v^.><<^vv<>><>v><^v>>^^^.v^v>v>^v^>.v<<^>.^v^>vv<# +#<<>^^.^>v.<>>^>^.<<^>^><<>v^.><<<.^^^<<^><<^^>.>vv>^>^^v<.^>.^>^<^>^.<>^v.^^^.v>^.^v^<<<><<>v.>>>>^..v>^^vv^v>># +#<^.<^^><>^^^<<>>^>.^^^<^<^<^^<^v.^^v>^v<>.^v^^<<..v<^<>>^<..<^.>>^>.^v.>>v^.v..v.<^vvv^v<><><<^v^v.^^<<>^vv>^^>v>^v<<^>^<^.^# +#<^^v^v>^<^><>v><.>^>^..v^>^v^>^><>v<^v^<v>^vv<^v.<><>vv>>>>v<>^vv<^v<>^^.v>>^^<<.<^>^>>vv>vv^>^v<<>.>^>^v># +#<<>>>.<<>^>>v>^<^v>><<^v<><<.^<^<>>><^v>>v>^<^vv.<^^^.vv^<<<>^^>v>^v.>^^v>v.<>vvv><v>^v.^>vv<>^>.>.v^v.v^vv^<.<>.>vv>^>v^<.<# +#>^<^<<.<<..>>.>^^v>>v>^^>^^>>>v>v^<>v>>^>vvv>><>>vv>.>^.^<>.>^.v<>^^<^v^>>.>v.v<><<<>^<<^>^>^>^.vv..<>v<^># +#..v<<^v^^>^>^<^v^v^^v>><^><<^v.<.vv^v<<>^v<<^v^v^^.>^>v<^^v...>>vv.<^v>v^<<^v^>v<^>v^<>.>v^^^^.^<>^^.^><.<.>>.><.# +#v^v<<^v^>>^vv.v>>v>.vv^>>vv.>v>>>^.>>><.^.^<><>^vv<^<>><^v^>>.<>v<>v<....^^><.<^^>v^v>v<<>>^<>.v.<.vv<.>^.^v^>.># +#<v>>^>.>^^^<.>>^<><>>.>^v^<.v^^.^<<^>^.^v^^v<>>.>.<>.^.v>.^><^>v>v<>.^v<><.<<.><<^v<><><^>v^...v<<^^<^>v>^^vv^^vvv>^>v>>.>>v^^.vv>^# +#>v<>^v><>^>>><<^.^v<v<>>>.^v><^v<<>v<^^.<.><>^<><.v>><^>^>>.<>vvvv.^^v<<>^<>>><>>^v.<^>.^>><<>v<.<^<^>v^^>v^.><# +#>vv^<^.<^>v^v^<><>v<>>v^<>^>>>^v^>v<<^.^>v^v^<^<^^>^^^vv^.<><>><^v.<^<.<>.>^<^<^<>v<^.^vv><.v<^>># +#>v^.v>^v<>>v^>>>^^^^>.v<<^>^v>.^^>^>v^<^v^^<^^v>v>.v^^v><^^.><^^>>v>v^v><>vv><>^vvv>>v>>^v^^<^>>v^<^vv^<^^^^vv<>^^>v^v<><<<<# +######################################################################################################################################################.# 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 -- cgit 1.4.1