Jurassic Summer Challenge

jp.rb

# The following adjacency matrix includes a super source `i1` and a super sink `o1`.
# This allows us to implement max-flow where there is one source and sink.
# The edge weights used are the sums of all outgoing edge weights for the original sources
# and the sums for all incoming edge weights for the original sinks.
GRAPH = [
  #i1  A   B   C   D   E   F   G   H   I   J   K    L   M   N   O   P   o1
  [0, 40,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 105,  0,  0,  0,  0,  0],  #i1
  [0,  0,  0,  0,  0, 23, 17,  0,  0,  0,  0,  0,   0,  0,  0,  0,  0,  0],  #A
  [0, 23,  0, 20,  0,  0,  0, 30,  0,  0,  0,  0,   0,  0,  0,  0,  0,  0],  #B
  [0,  0,  0,  0,  4,  0,  0, 18,  7,  0,  0,  0,   0,  0,  0,  0,  0,  0],  #C
  [0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,   0,  0,  0,  0,  0, 37],  #D
  [0,  0,  0,  0,  0,  0, 13,  0,  0,  0, 21, 28,  19,  0,  0,  0,  0,  0],  #E
  [0,  0, 29,  9,  0,  0,  0, 14,  0,  0,  0, 19,   0,  0,  0,  0,  0,  0],  #F
  [0,  0,  0,  0,  5,  0,  0,  0, 10,  0,  0,  0,   0,  0,  0,  0,  0,  0],  #G
  [0,  0,  0,  0, 28,  0,  0,  0,  0,  0,  0,  0,   0,  0,  0,  0,  0,  0],  #H
  [0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,   0,  0, 21,  0,  0,  0],  #I
  [0,  0,  0,  0,  0,  0,  0,  0,  0, 19,  0,  0,   0,  0, 29,  9,  0,  0],  #J
  [0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 25,  0,   0,  0,  0,  7, 18,  0],  #K
  [0,  0,  0,  0,  0,  0, 21, 19,  0,  0,  0, 13,   0, 23,  0,  0, 29,  0],  #L
  [0,  0,  0,  0,  0,  0, 12, 14, 24,  0,  0,  0,   0,  0,  0,  0,  0,  0],  #M
  [0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,   0,  0,  0,  0,  0, 68],  #N
  [0,  0,  0,  0,  0,  0,  0,  0,  0,  9,  0,  0,   0,  0, 18,  0,  0,  0],  #O
  [0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 20,  0,   0,  0,  0, 25,  0,  0],  #P
  [0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,   0,  0,  0,  0,  0,  0],  #o1
]
NODES = %w(i1 a b c d e f g h i j k l m n o p o1)

# Part 1
puts "My favorite dino is: Triceratops"

# Part 2
def dfs(graph, source, sink, visited: nil, path: nil)
  visited ||= Set[]
  path ||= Array.new
  visited << source
  path << source

  return path if source == sink

  graph[source].each_with_index do |weight, neighbor|
    if weight.positive? && !visited.include?(neighbor)
      possible_path = dfs(graph, neighbor, sink, visited: visited, path: path.clone)
      return possible_path if possible_path
    end
  end

  nil
end

def ff(graph, source, sink, show_paths: false)
  max_flow = 0

  path = dfs(graph, source, sink)
  while !path.nil?
    bottleneck_cap = Float::INFINITY
    path.each_cons(2) do |u, v|
      bottleneck_cap = [bottleneck_cap, graph[u][v]].min
    end

    path.each_cons(2) do |u, v|
      graph[u][v] -= bottleneck_cap
      graph[v][u] += bottleneck_cap
    end
    max_flow += bottleneck_cap

    puts "Path: #{path.map{NODES[_1]}.join('->')}, Bottleneck: #{bottleneck_cap}" if show_paths
    path = dfs(graph, source, sink)
  end

  max_flow
end

puts "The total guests that can be evacuated in two hours is #{ff(GRAPH, 0, 17) * 2}"