diff options
| -rw-r--r-- | day24 | 22 | ||||
| -rw-r--r-- | day24.rkt | 76 |
2 files changed, 98 insertions, 0 deletions
diff --git a/day24 b/day24 new file mode 100644 index 0000000..f64ff83 --- /dev/null +++ b/day24 @@ -0,0 +1,22 @@ +#.###################################################################################################################################################### +#<v^>^>^^<><^>^^v>vv^v^>>^<>^<v<>v^>>v>v><^..><v<^v<<^v>v>>>>^<v^>>>.v>.v><<v><.^>>^^^>v>>^.<v>>vv<<.<<v<<vv^<^>^v>^v<>^^.^.<<<v^>>^<^>.>vvv><^<^>v.^<># +#<..v<<^^.^^v<<>>v<vv.><v<<<>>>.<>>^vv^^v>v^>><v<.<<v.v^^>>v^vv<<><>>v.>.v>.<..v>^^>^<<vv>><>vv>>v>.><.<<vv<v^..v<v<v^v>v^vv<v<v^.^<v<.<<><>vvvvv^<^v>.# +#<>>^<v>v^v>v>.^v<>v<v^<<<.^^<.>vv>>^<<^>>v<v.>^^^.<<<.>>v.>.v^<v><v>.>>>^><>v>>v^<.v^<.vv^>^v<><>>v^^<^>..<v><<^<<<^<v><^>^<>v>vvv>>^<<>><><<^^.<<v>v># +#>.<<<^..>><>v>^vv>vv<v..^>^^>>.><^<v.>>><^.^<>^v>.<^<>>>^>>^><^><^.^>.><><><^>^>>^>>>^<.>>^<^>vv<^v^><vv^v>.>^>>vv.^<>>^>>>><>.^.>v<.^<>v^>v>^^>>v<><># +#>>v<^v^<^^><>><>.>v^v>^v.>v^.>>.><><<>^><<>^>^v>v^^^>>^v<<<>v<vv>v>>v<^^^<<<<v^vv><>v<^>>.<v.^^>^v<v<v.v..v<^^>>><.v^<.>>vv>v><><.^^^v><.<<v^>^>>><v><# +#>>vv<^vv<<v<^v^.><>^<v<>v<^v.>>v<><>.>^.^....<<^<.<v>><v>^^^<><>.>^<<v^<>>>^^><v><>>v^v<v<v^<.^<v>v^<>v^<vv^.<^v>^^^v.<><^><^v<<.v>>><>>><.v>v>>^.^>^># +#<v<>>^v>v^vv^.^<<<^><>v^<.>>^^^<^<^>.>>^<<.^>><<<v^v>.>^^.vv>.v<v^>v><^^.<<<v^>v..<^<.vvv<.<v..<.>.v>.>>^v<^^<^v^>^.<<^^.^^<><v^^v<^^^v>v<<<<v<<>v>><># +#<^>>^>><<>v.v>.vvv><^><v<^v<>v..<<<>>><<vv>^v><^>..<^^v>.<<<v><v^^vv^^>>.v..^<.^v<v>v.><vv>^><>vv><<>v^>v>><^^>^>><^>.>^^<<><><^.>^v<>v^.>v><>>.v^..v># +#<.<<<^><><^<<^>><..>^<<<>^.<>>v..v^^<<<.><.^.<^>^vvv^^^^>v>^<v>>>>>v<><>v.<>>^.<>v^<.^vv>v^<v>.><v<^.><<^vv<>><>v><^v>>^^^.v^v>v>^v^>.v<<^>.^v<v>^>vv<# +#<<>^^.^>v<vvvv<<^v<v<<<v>.<>>^>^.<<^>^><<>v^.><<<.^^^<<^><<^^>.>vv<v<>>^>^^v<.^>.<v<>^>^<^>^.<>^v.^^^.v><v>^.^v^<<<><<>v.>>>>^<v>..v>^^v<v<^>v<v.>^v>># +#<^.<^^><>^^^<<>>^>.^^^<^<^<^^<^v.^^v>^v<>.^v^^<<..v<^<>>^<..<^.>><v<>^>.^v.>>v^.v..v.<<vv^>^vvv^v<vv<^.^><><><<^v^v.^^<<>^vv>^^>v>^v<<^>^<vvv.><^.^<v># +#<^^v^v>^<^><>v><.><v>^>^<vv<>..v^>^v^>^><>v<^v^<<v<<<<v<v..^^^<><v>v>^vv<^v.<><>vv>>>>v<>^vv<^v<>^^.v>>^^<<.<^<v<>>^>>vv>vv^<v^^>>^<v<.v<v>v<<>.>^>^v># +#<<>>>.<<>^>>v>^<^v>><<^v<><<.^<^<>>><^v>>v>^<^vv.<^^^.vv^<<<>^^>v>^v.>^^v>v.<>vvv><<v>v>^v.<v^<>^>vv<><vv<v^<><vv.>^>.>.v^v.v^vv^<.<>.>vv>^>v<v<v>^<.<# +#>^<^<v<^^<^^v><<.<<..>>.>^^v>>v>^^>^^>>>v>v^<v^><>v>><v^<v>^>vvv>><>>vv>.>^.^<>.><v.>^.v<><v<^v><v.v<v<..^>^^<^v^>>.>v.v<><<<v><>^<<^>^>^>^.vv..<>v<^># +#..v<<^v^^>^>^<^<vvv>v<v^^v^.<<vvv.v.v^v>^v^^v>><^><<^v.<vv<><.vv^v<<>^v<<^v^v^^.>^>v<^^v...>>vv.<^v>v^<<^<vv>v^>v<^>v<vv>^<>.>v^^^^.^<>^^.^><.<.>>.><.# +#<vv>v^<v^.vv<<.>v<<^v^>>^vv.v>>v>.vv^>>vv.>v>>>^.>>><.^.^<><>^vv<^<>><<vv<<v>^v^>>.<v^<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>^^vv^^vvv>^>v>>.>>v^^.vv>^<v<># +#>v<>^v><>^>>><<^.^v<<v^>v<>>>.^v><^v<<>v<^^.<.><><v>^<><.v<v<<^^^>>><^>^>>.<>vvvv.^^v<<>^<>>><<v^v><v>>>^v.<^>.^>><v><<><vv.v<vv<v^^>v<.<^<^>v^^>v^.><# +#><v>vv^<^.<^>v^v^<><><vvv^v>v<>>v^<>^>>>^v^<v>>v<<^.^<v^vvv^^<><vvv.<vv^.>>v^<v.^vv><vv<>v^<^<^^>^^^vv^.<><>><^v.<^<.<>.>^<^<^<>v<^.<v<v<v>^vv><.v<^>># +#>v^.v>^v<>>v^>>>^^^^>.v<<^>^v>.^^>^>v^<^v^^<^^v>v>.v^<v>^v><^^.><^^>>v>v^v<v.<^>><>vv><v^v^><>^vvv>>v>>^v^^<^>>v^<^vv^<^^^^vv<><vv<.v^><v>^^>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 |