From 59c05a80613760dd64ffecaabb09d41a57640c39 Mon Sep 17 00:00:00 2001 From: Leah Neukirchen Date: Sat, 17 Dec 2022 19:10:49 +0100 Subject: day16 --- day16 | 59 ++++++++++++++++++++++++++++++++++++++++ day16.rkt | 92 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 151 insertions(+) create mode 100644 day16 create mode 100644 day16.rkt 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 -- cgit 1.4.1