AoC 2022 Day16 Part1

edge.rb

class Edge
  attr_reader :start, :to, :dist
  def initialize(start:, to:, dist:)
    @start = start
    @to = to
    @dist = dist
  end
end

flow_runner.rb

require_relative 'requires'
# This solution depends on the fact that the graph is sparse and not directed.
# and on the limited time to open valves which limits the number of functional valves
# that can be part of the optimal path. It is NOT a Traveling Salesman Problem.
# The run time is proportional to x!/(x-n)! where
#     x is the number of functional valves
#     n is the maximum number of valves that can be opened in the time limit
# See: https://en.wikipedia.org/wiki/Twelvefold_way - midpage
class FlowRunner
  Verbose = true
  Test = true
  include Printer if Verbose

  def initialize( parser: Parser, nodes_and_edges: NodesAndEdges,
                  floyd_warshall: FloydWarshall )
    @parser = parser.new(test: Test)
    structured_data = @parser.structured_data
    @nodes_and_edges = nodes_and_edges.new(structured_data)
    @floyd_warshall = floyd_warshall.new(nodes: nodes, edges: edges)
    @max_time = 30
    @valve_time = 1
  end

  def nodes; @nodes_and_edges.nodes; end
  def edges; @nodes_and_edges.edges; end

  def run
    puts "started at: #{Time.now}" if Verbose
      cm = @floyd_warshall.fwa
      compmat = compact_cost_matrix(cm)
      print_optimization_input(compmat) if Verbose
      print_optpaths path_trials(compmat)
    puts "finished at: #{Time.now}" if Verbose
  end

  def compact_cost_matrix(cm)
    slicendx = nodes.index {|n| n.flow == 0 && n.vname != 'AA' }
    cm.map {|row| row[0, slicendx] }[0,slicendx]
  end

  def path_trials(compmat)
    bestpath = [[0], @max_time, 0]
    maxndx = compmat.size-1
    (1..[maxndx,10].min).reduce({ 0 => bestpath }) do |optpaths,i|
      Array(1..maxndx).permutation(i) do |permutation|
        remaining, flow_to_end = cost_benefit(permutation, compmat)
        next if flow_to_end < bestpath[2] or remaining < 0
        bestpath = [permutation, remaining, flow_to_end]
      end
      optpaths[i] = bestpath
      return optpaths if optpaths[i][2] == optpaths[i-1][2]
      optpaths
    end
  end

  def cost_benefit(permutation, costmatrix)
    curnode = flow_to_end = 0
    remaining = @max_time
    permutation.each do |nxtnode|
      step_valve_time = costmatrix[curnode][nxtnode] + @valve_time
      remaining -= step_valve_time
      return [remaining, flow_to_end] if remaining <= 0
      flow_to_end += remaining * nodes[nxtnode].flow
      curnode = nxtnode
    end
    [remaining, flow_to_end]
  end
end

FlowRunner.new.run

floyd_warshall.rb

class FloydWarshall
  attr_reader :nsize, :dist, :nxt

  # node attr: :vname, :flow, :nbrs
  # edge attr: :start, :to, :dist
  attr_reader :nodes, :edges
  def initialize(nodes:, edges:)
    @nodes = nodes
    @edges = edges
  end

  def fwa
    fwa_setup
    edges.each do |e|
      u = nodes.index {|n| n.vname == e.start }
      v = nodes.index {|n| n.vname == e.to }
      dist[u][v] = e.dist
    end
    nsize.times {|v| dist[v][v] = 0}
    nsize.times do |k|  #via
      nsize.times do |i|  #from
        nsize.times do |j|  #to
          if dist[i][j] > dist[i][k] + dist[k][j]
            dist[i][j] = dist[i][k] + dist[k][j]
          end
        end
      end
    end
    dist
  end

  def fwa_with_path_recovery
    fwa_setup(nodes)
    edges.each do |e|
      u = nodes.index {|n| n.vname == e.start }
      v = nodes.index {|n| n.vname == e.to }
      dist[u][v] = e.dist
      nxt[u][v]  = v
    end
    nsize.times do |v|
      dist[v][v] = 0
      nxt[v][v]  = v
    end
    (1..nsize).each do |k|
      (1..nsize).each do |i|
        (1..nsize).each do |j|
          if dist[i][j] > dist[i][k] + dist[k][j]
            dist[i][j] = dist[i][k] + dist[k][j]
            nxt[i][j]  = nxt[i][k]
          end
        end
      end
    end
    dist
  end

  def path(u, v)
    return [] if nxt[u][v] = nil
    path = [u]
    while u != v
      u = nxt[u][v]
      path << u
    end
    path
  end

  def fwa_setup
    @nsize = @nodes.size
    @dist = init_2d_arry(size: nsize, initval: Float::INFINITY)
    @nxt  = init_2d_arry(size: nsize, initval: nil)
  end

  def init_2d_arry(size:,initval:)
    size.times.reduce([]) do |rows,_|
      rows << size.times.reduce([]) do |cols,_|
        cols << initval; cols
      end; rows
    end
  end
end

node.rb

class Node
  attr_reader :vname, :nbrs
  attr_accessor :flow       # Setter required for NodesAndEdges#build_nodes
  def initialize(vname:, flow:, nbrs:)
    @vname = vname
    @flow = flow
    @nbrs = nbrs
  end

  def <=>(other)
    # descending order
    other.flow <=> @flow
  end
end

nodes_and_edges.rb

class NodesAndEdges
  def initialize(structured_data)
    @structured_data = structured_data
  end

  def edges
    @edges ||= nodes.reduce([]) do |edges, n|
      n.nbrs.each {|nbr| edges << Edge.new(start: n.vname, to: nbr[0], dist: nbr[1]) }
      edges
    end
  end

  def nodes
    @nodes ||= build_nodes
  end

  def build_nodes
    nds = @structured_data.reduce([]) do |nodes, (k, v)|
      v[:flow] = Float::INFINITY if k == 'AA' # kludge to put AA first in nodes
      n = Node.new(vname: k, flow: v[:flow], nbrs: v[:nbrs])
      nodes << n; nodes
    end.sort
    nds[0].flow = 0 # Restore 'AA' flow to 0
    nds
  end

  def node_at(ndx)
    nodes[ndx].vname
  end

  def ndx_of(vname)
    nodes.each_index.map {|i| nodes[i].vname == vname ? i : nil }.compact.first
  end
end

parser.rb

class Parser
  def initialize(test: true)
    data_extension = test ? "_test" : ""
    @valve_data = "#{File.dirname(__FILE__)}/../valves#{data_extension}.txt"
  end

  def structured_data
    parse_file.reduce({}) do |valves, (vname, flow, nbrs)|
      nbrs = nbrs.split(', ').map{|vname| [vname, 1] }
      valves[vname] = { flow: flow, nbrs: nbrs }
      valves
    end
  end

  def show_data
    puts "Structured Data:"
    keys = structured_data.keys
    keys.each {|k| puts "node #{k}: #{structured_data[k]}" }
  end

private
  def parse_file
    r = Regexp.new( '\AValve (\w\w) .+rate=(\d+).*valves? (.*)\z' )
    File.foreach(@valve_data).map do |line|
      line.chomp
      .match(r) {|md| [md[1], md[2].to_i, md[3]] }
    end
  end
end

requires.rb

require_relative 'parser'
require_relative 'nodes_and_edges'
require_relative 'node'
require_relative 'edge'
require_relative 'printer'
require_relative '../floyd_warshall'