[WIP] Day16

3 files changed, 157 insertions, 0 deletions

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