From 8749296d846741d2da035c0df79faf766d172a10 Mon Sep 17 00:00:00 2001 From: Nat Lasseter Date: Fri, 16 Dec 2022 16:51:43 +0000 Subject: [WIP] Day16 --- day16/input | 52 ++++++++++++++++++++++++++++++++ day16/part1.rb | 95 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ day16/test | 10 +++++++ 3 files changed, 157 insertions(+) create mode 100644 day16/input create mode 100644 day16/part1.rb create mode 100644 day16/test diff --git a/day16/input b/day16/input new file mode 100644 index 0000000..c4760e8 --- /dev/null +++ b/day16/input @@ -0,0 +1,52 @@ +Valve AP has flow rate=0; tunnels lead to valves AA, ON +Valve QN has flow rate=21; tunnels lead to valves RI, CG +Valve LK has flow rate=0; tunnels lead to valves XM, AA +Valve HA has flow rate=0; tunnels lead to valves WH, KF +Valve DS has flow rate=16; tunnel leads to valve II +Valve KD has flow rate=0; tunnels lead to valves KG, QB +Valve JW has flow rate=0; tunnels lead to valves AD, KF +Valve HU has flow rate=0; tunnels lead to valves UK, CO +Valve AE has flow rate=10; tunnels lead to valves IR, PT, UV +Valve XA has flow rate=0; tunnels lead to valves CG, EU +Valve SE has flow rate=17; tunnels lead to valves YR, AD +Valve TR has flow rate=0; tunnels lead to valves AL, CS +Valve BS has flow rate=0; tunnels lead to valves YH, XM +Valve IJ has flow rate=24; tunnels lead to valves XN, WE +Valve AA has flow rate=0; tunnels lead to valves LK, AP, IZ, PC, QD +Valve KG has flow rate=0; tunnels lead to valves KD, CS +Valve QV has flow rate=0; tunnels lead to valves XM, II +Valve PC has flow rate=0; tunnels lead to valves AA, YF +Valve GJ has flow rate=20; tunnel leads to valve RI +Valve UV has flow rate=0; tunnels lead to valves UK, AE +Valve IR has flow rate=0; tunnels lead to valves EU, AE +Valve EU has flow rate=13; tunnels lead to valves IR, DT, XA, ON +Valve ED has flow rate=0; tunnels lead to valves XN, CO +Valve DT has flow rate=0; tunnels lead to valves EU, UK +Valve YE has flow rate=0; tunnels lead to valves XM, WS +Valve AD has flow rate=0; tunnels lead to valves JW, SE +Valve WE has flow rate=0; tunnels lead to valves IJ, NA +Valve UK has flow rate=5; tunnels lead to valves UV, DT, QD, HU +Valve YR has flow rate=0; tunnels lead to valves OS, SE +Valve II has flow rate=0; tunnels lead to valves QV, DS +Valve GT has flow rate=0; tunnels lead to valves CS, MN +Valve YH has flow rate=0; tunnels lead to valves BS, QB +Valve BQ has flow rate=0; tunnels lead to valves XM, KF +Valve OS has flow rate=0; tunnels lead to valves YR, NA +Valve WH has flow rate=0; tunnels lead to valves QB, HA +Valve QB has flow rate=4; tunnels lead to valves WH, KD, YH, IZ +Valve ON has flow rate=0; tunnels lead to valves AP, EU +Valve IZ has flow rate=0; tunnels lead to valves AA, QB +Valve MN has flow rate=25; tunnel leads to valve GT +Valve CG has flow rate=0; tunnels lead to valves XA, QN +Valve QD has flow rate=0; tunnels lead to valves UK, AA +Valve AL has flow rate=0; tunnels lead to valves KF, TR +Valve XN has flow rate=0; tunnels lead to valves ED, IJ +Valve WS has flow rate=0; tunnels lead to valves YE, CS +Valve CO has flow rate=18; tunnels lead to valves ED, PT, HU +Valve PT has flow rate=0; tunnels lead to valves CO, AE +Valve RI has flow rate=0; tunnels lead to valves QN, GJ +Valve CS has flow rate=9; tunnels lead to valves YF, GT, WS, TR, KG +Valve YF has flow rate=0; tunnels lead to valves PC, CS +Valve NA has flow rate=23; tunnels lead to valves OS, WE +Valve KF has flow rate=12; tunnels lead to valves HA, AL, JW, BQ +Valve XM has flow rate=3; tunnels lead to valves LK, QV, YE, BS, BQ diff --git a/day16/part1.rb b/day16/part1.rb new file mode 100644 index 0000000..5209fdd --- /dev/null +++ b/day16/part1.rb @@ -0,0 +1,95 @@ +class Valve + def initialize(flow_rate, tunnels) + @flow_rate = flow_rate + @tunnels = tunnels + @distance = {} + @open = false + end + + attr_reader :flow_rate, :tunnels, :distance + + def open? + @open + end + + def open! + @open = true + end +end + +valves = {} +$stdin.readlines.each do |line| + fr = line.scan(/\d+/)[0].to_i + name, *tunnels = line.scan(/[A-Z]{2}/) + valves[name] = Valve.new(fr, tunnels) +end + +valves.each do |k, v| + seen = [k] + v.distance[k] = 0 + q = v.tunnels.map{|nv|[nv, 1]} + until q.empty? + nv, d = q.shift + seen << nv + v.distance[nv] = d if v.distance[nv].nil? + q += valves[nv].tunnels.reject{ |t| seen.include?(t) }.map{ |nv| [nv, d+1] } + end +end + +pointful_valves = valves.select { |k, v| v.flow_rate != 0 }.keys + +at = "AA" +time_rem = 30 +relief = 0 + +loop do + nv = nil + pointful_valves.each do |this| + next if valves[this].open? + nv = this if pointful_valves.map { |that| + ( + valves[that].open? ? + 0 : + (valves[at].distance[this] - valves[at].distance[that] + 1) * + valves[that].flow_rate - valves[this].flow_rate + ) <= 0 + }.all? + end + + break if nv.nil? + time_rem -= valves[at].distance[nv] + time_rem -= 1 + break if time_rem < 0 + puts nv + puts time_rem + valves[nv].open! + relief += (time_rem * valves[nv].flow_rate) + at = nv +end + +pp relief + +exit + + +num_valves = pointful_valves.count + +max_relief = 0 + +pointful_valves.permutation.each do |order| + at = "AA" + num_open = 0 + time_rem = 30 + relief = 0 + until time_rem < 0 || num_open == num_valves + nv = order.shift + time_rem -= valves[at].distance[nv] + time_rem -= 1 + relief += time_rem * valves[nv].flow_rate + at = nv + num_open += 1 + end + max_relief = relief if relief > max_relief +end + +puts max_relief diff --git a/day16/test b/day16/test new file mode 100644 index 0000000..9f30acc --- /dev/null +++ b/day16/test @@ -0,0 +1,10 @@ +Valve AA has flow rate=0; tunnels lead to valves DD, II, BB +Valve BB has flow rate=13; tunnels lead to valves CC, AA +Valve CC has flow rate=2; tunnels lead to valves DD, BB +Valve DD has flow rate=20; tunnels lead to valves CC, AA, EE +Valve EE has flow rate=3; tunnels lead to valves FF, DD +Valve FF has flow rate=0; tunnels lead to valves EE, GG +Valve GG has flow rate=0; tunnels lead to valves FF, HH +Valve HH has flow rate=22; tunnel leads to valve GG +Valve II has flow rate=0; tunnels lead to valves AA, JJ +Valve JJ has flow rate=21; tunnel leads to valve II -- cgit v1.2.1