Ruby Discord Jurassic Challenge

Push–Relabel Maximum Flow.rb

# frozen_string_literal: true

# Goldberg–Tarjan Push–Relabel Algorithm
# with FIFO active set and BFS pre-labeling
# * https://www.adrian-haarbach.de/idp-graph-algorithms/implementation/maxflow-push-relabel/index_en.html
# * https://en.wikipedia.org/wiki/Push%E2%80%93relabel_maximum_flow_algorithm?oldid=1230043247
# variable names are in dummies’ terminologies
class PushRelabel
  
  class Node
    # `{ neighbour => flow capacity remaining }`
    # Residual Graph: tracks both forwards and backwards
    attr_reader :edges
    # technically known as *excess*
    attr_reader :pressure
    protected attr_writer :pressure
    # technically known as ***label*** or less-commonly *height*
    attr_accessor :rank
    def initialize(id)
      @id = id
      @edges = Hash.new
      @pressure = 0
      @rank = -1
    end
    def hash = @id.hash
    
    # Note: does _not_ assert {#rank}
    # @return `amount`
    def push(to, amount = [pressure, edges.fetch(to)].min ||raise)
      @pressure -= amount
      to.pressure += amount
      edges[to] -= amount
      to.edges[self] += amount
      amount
    end
    # Note: does _not_ assert {#pressure}
    # @return new {#rank}
    def relabel
      # Target: one rank higher than that of the lowest-rank neighbour with capacity to push
      @rank = edges.filter_map do|neighbour, capacity|
        neighbour.rank if capacity.positive?
      end.min&.succ || (
        warn "[#{self.class}:#{@id}] unexpected lack of capacity to depressurize"
        0
      )
    end
  end
  
  def initialize(map, source:, sink:)
    nodes = Hash.new {|it, id| it[id] = Node.new id }
    # Initialize
    map.each do|from_key, edges| edges.each do|to_key, capacity|
      from = nodes[from_key]
      to   = nodes[  to_key]
      from.edges[to] = capacity
      to.edges[from] = 0
    end end
    @source = nodes.fetch source
    @source.rank = nodes.size
    @sink   = nodes.fetch sink
    # Optional: optimize non-`source` {Node#rank}s with BFS
    # if skip: set them to `0` in {Node#initialize}
    @sink.rank = 0
    (1..).inject [@sink] do|queue, neighbour_rank|
      break if queue.empty?
      queue.flat_map do|this|
        this.edges.each_key.filter_map do|neighbour|
          if neighbour.rank.negative? # `rank` not specialized
            neighbour.rank = neighbour_rank
            neighbour
          end
        end
      end
    end
  end
  
  def call
    # Preparation: force-{Node#push} maximum amounts from `source`
    @source.edges.each do|neighbour, capacity|
      @source.push neighbour, capacity
    end
    # Using {Hash} over {Set} because {Hash} is insertion-ordered
    # while {Set} is so only because it’s implemented using {Hash}.
    # The algorithm still works in arbitrary order, just not as optimal.
    fifo = @source.edges.except @sink # shallow clone
    terminals = [@source, @sink]
    # Main Loop
    while (active_node, = fifo.shift) do catch :while do
      neighbour_rank = active_node.rank.pred # the target {Node#rank} to be suitable for {Node#push}ing to
      
      active_node.edges.each do|neighbour, capacity|
        if neighbour.rank == neighbour_rank and capacity.nonzero? # check if neighbour is suitable
          # **Push** any pressure away – may be a forward pump or a backward surge
          active_node.push neighbour
          # We now queue up this neighbour – now an active node
          # (has pressure buildup) – unless it’s the `source` or `sink`.
          # Since we’re just using the key set, the value list doesn’t matter.
          fifo[neighbour] = 0 unless terminals.include? neighbour
          # Optional: short-circuit to the next-in-queue if `active_node`’s outta steam
          throw :while if active_node.pressure.zero?
        end
      end
      
      if active_node.pressure.nonzero? # still under pressure?
        # **Relabel** for re-queue
        active_node.relabel
        fifo[active_node] = 0 # queue, ditto
      end
    end end
  end
  
  def flow = @sink.pressure
  def self.call(...)= self.new(...).tap(&:call).flow
end

Push–Relabel Maximum Flow.rbs

class PushRelabel
  type amount = Integer # contextual alias
  
  class Node
    @id: Symbol
    attr_reader edges: Hash[instance, amount]
    attr_reader pressure: amount
    private attr_writer pressure: amount
    attr_accessor rank: Integer
    
    def push: (instance to, ?amount amount) -> amount
    def relabel: () -> Integer
  end
  
  @source: Node
  @sink  : Node
  
  type map = Hash[Symbol, Hash[Symbol, amount]]
  def self.call: (map map, source: Symbol, sink: Symbol) -> amount
  def initialize: (map map, source: Symbol, sink: Symbol) -> void
  def call: () -> void
  def flow: () -> amount
end

Ruby Discord Jurassic Challenge.rb

# frozen_string_literal: true
require_relative 'Push–Relabel Maximum Flow'

puts <<~"MD"
  ## What is your favorite dinosaur and why?
  My favorite “dinosaurs” are normally the pterodactyls, but everyöne knows they’re not actually dinosaurs.
  
  After a while, I choose **the Triceratops** as my favorite dinosaur kind.
  I find them and their close relatives the most identifiable dinosaur with their tri-horns and rugged build.
  In comparison, the other big names all look like either ostriches or monster reptiles.
  Heck, ‘dinosaur’ is literally “large and terrible reptile” in Greek.
  
  Our favorite pack hunters are actually primal chickens and our favorite apex predators may’ve eaten carrion.
  My selection is rather a reflection on how unfortunately limited our understanding of these majestic giants are.
  
  ## What is the total number of guests that can be safely evacuated in 2 hours?
  As it is not given how long guests take to travel on each path,
  I’ll assume the question as sampling from a continuous stream of people.
  In which case, my answer is:
MD

MAP = {
  A: {E: 23, F: 17},
  B: {A: 23, C: 20, G: 30},
  C: {D:  4, G: 18, H:  7, },
  E: {F: 13, J: 21, K: 28, L: 19},
  F: {B: 29, C:  9, G: 14, K: 19}, #B:29
  G: {D:  5, H: 10},
  H: {D: 28},
  I: {N: 21},
  J: {I: 19, N: 29, O:  9},
  K: {J: 25, O:  7, P: 18},
  L: {F: 21, G: 19, K: 13, M: 23, P: 29},
  M: {F: 12, G: 14, H: 24},
  O: {I:  9, N: 18},
  P: {J: 20, O: 25},
}
capacity_sum = MAP.each_value.sum { _1.each_value.sum }
MAP[:supersource] = {A: capacity_sum, L: capacity_sum}
MAP[:D] = MAP[:N] = {supersink: capacity_sum}
puts PushRelabel.(MAP, source: :supersource, sink: :supersink) * 2

Ruby Discord Jurassic Challenge.txt

A:  9
B:  0
C:  9
D: 37
E:  7
F: 28
G: 15
H: 28
I: 21
J: 50
K: 32
L: 96
M: 23
N: 68
O: 27
P: 29

A->E:  7/23
A->F:  2/17
C->D:  4/ 4
C->G:  5/18
E->J:  7/21
F->C:  9/ 9
F->K: 19/19
G->D:  5/ 5
G->H: 10/10
H->D: 28/28
I->N: 21/21
J->I: 12/19
J->N: 29/29
J->O:  9/ 9
K->J: 25/25
K->O:  7/ 7
L->F: 21/21
L->G: 10/19
L->K: 13/13
L->M: 23/23
L->P: 29/29
M->F:  5/12
M->H: 18/24
O->I:  9/ 9
O->N: 18/18
P->J: 18/20
P->O: 11/25

Wikipedia example.rb

# frozen_string_literal: true
require_relative 'Push–Relabel Maximum Flow'

puts PushRelabel.({
  s: {a: 15, c: 4},
  a: {b: 12},
  b: {c: 3, t: 7},
  c: {d: 10},
  d: {a: 5, t: 10}
}, source: :s, sink: :t)