Solve optimal path from Narita to Tokyo with inject

nrt2tokyo.rb

class OptimalPath
  def initialize(road_system)
    @road_system = road_system
  end

  def solve
    bestA, bestB =
      @road_system.inject([Path.new, Path.new]) do |(pathA, pathB), section|
        road_step(pathA, pathB, section)
      end
    [bestA, bestB].min_by(&:length)
  end

  def road_step(pathA, pathB, section)
    a, b, c = section.values
    candidatesA = [ pathA + [ Segment[:A, a] ], 
                    pathB + [ Segment[:B, b], Segment[:C, c] ]]
    candidatesB = [ pathB + [ Segment[:B, b] ],
                    pathA + [ Segment[:A, a], Segment[:C, c] ]]
    
    pathA = candidatesA.min_by { |path| path.length }
    pathB = candidatesB.min_by { |path| path.length }
    [pathA, pathB]
  end

  class Segment
    def self.[](label, length)
      new(label, length)
    end

    attr_reader :label, :length
    def initialize(label, length)
      @label, @length = label, length
    end

    def to_s
      "(#{label}, #{length})"
    end
  end

  class Path
    def initialize(segment=nil)
      @path = segment ? segment : []
    end

    def +(segment)
      self.class.new(@path + segment)
    end

    def length
      @path.map(&:length).inject(0, :+)
    end

    def to_s
      "#{@path}"
    end
  end
end

Section = Struct.new(:a, :b, :c)

nrt_to_tokyo = 
  [ [50,10,30],
    [ 5,90,20],
    [40, 2,25],
    [10, 8, 0]
   ].map { |a,b,c| Section[a,b,c] }
   
nrt_to_tokyo # => [#<struct Section a=50, b=10, c=30>, #<struct Section a=5, b=90, c=20>, #<struct Section a=40, b=2, c=25>, #<struct Section a=10, b=8, c=0>]

op = OptimalPath.new(nrt_to_tokyo)
op.solve # => [(B, 10), (C, 30), (A, 5), (C, 20), (B, 2), (B, 8), (C, 0)]

road_graph.rb

require "graphaz"

routes = [
  ':A0 => :A1 => :A2 => :A3 => :A4',
  ':B0 => :B1 => :B2 => :B3 => :B4',
  ':A0 => :B0',
  ':A1 => :B1',
  ':A2 => :B2',
  ':A3 => :B3',
  ':A4 => :B4'  
  ]

edge_labels = {
  'A0_A1' => 50,
  'A1_A2' => 5,
  'A2_A3' => 40,
  'A3_A4' => 10,
  'B0_B1' => 10,
  'B1_B2' => 90,
  'B2_B3' => 2,
  'B3_B4' => 8,
  'A0_B0' => :NRT,
  'A1_B1' => 30,
  'A2_B2' => 20,
  'A3_B3' => 25,
  'A4_B4' => :Tokyo,
}

ga = GraphAz.new(:Path, :type => 'graph')
ga[:label] = "Road to Tokyo"
ga[:rankdir] = 'LR'
ga.gnode[:style] = 'filled'
ga.gnode[:fillcolor] = 'lightskyblue'

routes.each { |r| ga.add r }
edge_labels.each { |edge, label| ga.edge(edge, :label => label.to_s) }
3.times { ga.lap }

sequence = [
  [nil    , 'B0'],
  ['B0_B1', 'B1'],
  ['A1_B1', 'A1'],
  ['A1_A2', 'A2'],
  ['A2_B2', 'B2'],
  ['B2_B3', 'B3'],
  ['B3_B4', 'B4']
  ]

sequence.each do |edge, node|
  ga.edge(edge, :style => 'bold', :color => color) if edge
  ga.node(node, :style => 'filled', :fillcolor => 'navyblue', :fontcolor => 'white') if node
  ga.lap
end
3.times { ga.lap }

ga.write