day16

2 files changed, 151 insertions, 0 deletions

diff --git a/day16 b/day16
new file mode 100644
index 0000000..22e6091
--- /dev/null
+++ b/day16
@@ -0,0 +1,59 @@
+Valve TZ has flow rate=0; tunnels lead to valves ZJ, DM
+Valve LH has flow rate=0; tunnels lead to valves FP, IS
+Valve AA has flow rate=0; tunnels lead to valves XU, JH, CD, WY, HK
+Valve GP has flow rate=0; tunnels lead to valves BO, KL
+Valve GN has flow rate=0; tunnels lead to valves QO, FP
+Valve QO has flow rate=0; tunnels lead to valves CA, GN
+Valve JT has flow rate=22; tunnel leads to valve BL
+Valve DF has flow rate=0; tunnels lead to valves BO, HK
+Valve UM has flow rate=0; tunnels lead to valves OS, LE
+Valve KJ has flow rate=0; tunnels lead to valves YF, UK
+Valve UX has flow rate=23; tunnels lead to valves WM, ZI
+Valve ZI has flow rate=0; tunnels lead to valves UX, AR
+Valve YF has flow rate=0; tunnels lead to valves KJ, EK
+Valve SX has flow rate=0; tunnels lead to valves DM, CD
+Valve KZ has flow rate=0; tunnels lead to valves FR, LE
+Valve IH has flow rate=0; tunnels lead to valves DM, IE
+Valve EL has flow rate=0; tunnels lead to valves WQ, BO
+Valve CD has flow rate=0; tunnels lead to valves AA, SX
+Valve OR has flow rate=0; tunnels lead to valves FP, IR
+Valve EK has flow rate=19; tunnels lead to valves YF, LK
+Valve UE has flow rate=0; tunnels lead to valves FP, LG
+Valve WQ has flow rate=0; tunnels lead to valves EL, DM
+Valve XI has flow rate=0; tunnels lead to valves YH, DM
+Valve GO has flow rate=0; tunnels lead to valves BO, CQ
+Valve IR has flow rate=0; tunnels lead to valves ZJ, OR
+Valve WY has flow rate=0; tunnels lead to valves UI, AA
+Valve JH has flow rate=0; tunnels lead to valves AA, CA
+Valve WM has flow rate=0; tunnels lead to valves UX, YH
+Valve OS has flow rate=0; tunnels lead to valves UM, CA
+Valve AE has flow rate=0; tunnels lead to valves FP, YH
+Valve LG has flow rate=0; tunnels lead to valves UE, LE
+Valve IS has flow rate=0; tunnels lead to valves LH, AR
+Valve XU has flow rate=0; tunnels lead to valves AA, TU
+Valve KL has flow rate=0; tunnels lead to valves GP, TU
+Valve LV has flow rate=0; tunnels lead to valves UK, TU
+Valve UI has flow rate=0; tunnels lead to valves ZJ, WY
+Valve IL has flow rate=0; tunnels lead to valves GW, LK
+Valve XY has flow rate=0; tunnels lead to valves AZ, CA
+Valve JF has flow rate=15; tunnels lead to valves FR, BK
+Valve UK has flow rate=18; tunnels lead to valves LV, KJ
+Valve CA has flow rate=13; tunnels lead to valves JH, XY, QO, BK, OS
+Valve BL has flow rate=0; tunnels lead to valves JT, GW
+Valve GW has flow rate=16; tunnels lead to valves IL, BL
+Valve CQ has flow rate=0; tunnels lead to valves ZJ, GO
+Valve HK has flow rate=0; tunnels lead to valves DF, AA
+Valve BO has flow rate=4; tunnels lead to valves GO, GP, EL, DF
+Valve TU has flow rate=11; tunnels lead to valves XU, IE, KL, LV
+Valve AZ has flow rate=0; tunnels lead to valves ZJ, XY
+Valve FP has flow rate=5; tunnels lead to valves GN, AE, UE, LH, OR
+Valve LE has flow rate=14; tunnels lead to valves KZ, LG, UM
+Valve IE has flow rate=0; tunnels lead to valves IH, TU
+Valve NZ has flow rate=0; tunnels lead to valves YH, AR
+Valve DM has flow rate=3; tunnels lead to valves WQ, IH, TZ, SX, XI
+Valve YH has flow rate=21; tunnels lead to valves WM, NZ, AE, XI
+Valve BK has flow rate=0; tunnels lead to valves JF, CA
+Valve LK has flow rate=0; tunnels lead to valves EK, IL
+Valve AR has flow rate=20; tunnels lead to valves IS, NZ, ZI
+Valve ZJ has flow rate=9; tunnels lead to valves IR, AZ, TZ, UI, CQ
+Valve FR has flow rate=0; tunnels lead to valves JF, KZ
diff --git a/day16.rkt b/day16.rkt
new file mode 100644
index 0000000..5d96756
--- /dev/null
+++ b/day16.rkt
@@ -0,0 +1,92 @@
+#lang racket
+
+;; https://www.reddit.com/r/adventofcode/comments/zn6k1l/2022_day_16_solutions/j0g5nlk/
+
+(define flow-rates (make-hash))
+(define tunnels (make-hash))
+
+(for ([line (file->lines "day16")])
+  (let* ([valves (regexp-match* #rx"[A-Z][A-Z]" line)]
+         [valve (first valves)]
+         [flow-rate (string->number (first (regexp-match #rx"[0-9]+" line)))])
+    (hash-set! flow-rates valve flow-rate)
+    (hash-set! tunnels valve (rest valves))))
+
+(define key-rooms (for/set ([(room flow-rate) flow-rates]
+                            #:when (or (equal? room "AA") (positive? flow-rate)))
+                    room))
+
+(set-count key-rooms)
+
+(define distance (make-hash))
+(for ([start-room (hash-keys tunnels)])
+  (let ([cur (mutable-set start-room)]
+        [next (mutable-set)]
+        [dist 0])
+    (hash-set! distance (list start-room start-room) 0)
+    (let loop ()
+      (set! dist (+ 1 dist))
+      (for ([pos cur])
+        (for ([newpos (hash-ref tunnels pos)])
+          (unless (hash-has-key? distance (list start-room newpos))
+            (hash-set! distance (list start-room newpos) dist)
+            (set-add! next newpos))))
+      (set! cur next)
+      (set! next (mutable-set))
+      (unless (set-empty? cur)
+        (loop)))))
+
+;distance
+
+(define (part1 cur time seen targets)
+  (let* ([seen (set-add seen cur)]
+         [targets (set-subtract targets seen)])
+    (for/fold ([best-flow 0])
+              ([target targets])
+      (let ([time-left (- time (hash-ref distance (list cur target)) 1)])
+        (if (positive? time-left)
+          (let ([flow (+ (* (hash-ref flow-rates target) time-left)
+                         (part1 target time-left seen targets))])
+            (max best-flow flow))
+          best-flow)))))
+
+(part1 "AA" 30 (set) key-rooms)
+;; 1720
+
+
+(define endpoints (make-hash))
+
+(define (find-and-record cur curflow time seen)
+  (let* ([seen (set-add seen cur)]
+         [targets (set-subtract key-rooms seen)]
+         [torecord (set-remove seen "AA")])
+    (hash-update! endpoints torecord (lambda (v) (max v curflow)) 0)
+    (for/fold ([best-flow 0])
+              ([target targets])
+      (let ([time-left (- time (hash-ref distance (list cur target)) 1)])
+        (if (positive? time-left)
+          (let* ([flow (* (hash-ref flow-rates target) time-left)]
+                 [flow (+ flow (find-and-record
+                                target
+                                (+ curflow flow) time-left seen))])
+            (max best-flow flow))
+          best-flow)))))
+
+(void (find-and-record "AA" 0 26 (set)))
+
+(define (fill-in-endpoints cur)
+  (unless (hash-has-key? endpoints cur)
+    (hash-set! endpoints cur (for/fold ([best-flow 0])
+                                       ([e cur])
+                               (max best-flow (fill-in-endpoints
+                                               (set-remove cur e))))))
+  (hash-ref endpoints cur))
+
+(void (fill-in-endpoints (set-remove key-rooms "AA")))
+
+(for/fold ([best-flow 0])
+          ([human (hash-keys endpoints)])
+  (let ([elephant (set-subtract key-rooms (set "AA") human)])
+    (max best-flow (+ (hash-ref endpoints human)
+                      (hash-ref endpoints elephant)))))
+;; 2582