MTA Problem

breadth_first_search.rb

require 'set'

class Subway
  
  attr_reader :stops

  def initialize(lines)
    @stops = {}
    lines.each_pair {|line, stops|
      stops.each do |stop|
        @stops[stop] ||= Stop.new(stop)
        @stops[stop].add_line line
      end
    }
    lines.each_pair {|line, stops|
      stops.each_with_index {|stop_name, i|
        stop = @stops[stop_name]
        if i > 0
          previous_stop = @stops[stops[i-1]]
          stop.add_link(previous_stop)
        end
        if i < stops.size && stops[i+1]
          next_stop = @stops[stops[i+1]]
          stop.add_link(next_stop)
        end
      }
    }
  end
  
  def seek(start, finish)
    start = @stops[start]
    finish = @stops[finish]
    raise ArgumentError('Must have valid start and finish!') unless start && finish
    path = RouteSearch.new(start, finish).seek
    puts RouteDescription.new(path).to_s
  end
  
  class Stop

    attr_accessor :name, :lines
    attr_reader :links

    def initialize(name)
      @name = name
      @lines = Set.new
      @links = Set.new
    end
    
    def add_line(line)
      @lines << line
    end

    def add_link(stop)
      @links << stop
    end
    
    def eql?(stop)
      stop.name == self.name
    end

  end
  
  class RouteSearch
    attr_accessor :start, :finish, :visited, :routes, :queue
    def initialize(start, finish)
      @start, @finish = start, finish
      @visited = {}
      @routes = RouteSet.new
      @queue = []
    end

    def seek
      search(start)
      shortest_route
    end

    def search(stop)
      queue << stop
      set_visited! stop
      visit_stop(queue.shift) while queue.any?
    end
    
    def visit_stop(stop)
      stop.links.each do |next_stop|
        next if already_visited?(next_stop)
        set_visited! next_stop
        routes.add_route from: stop, to: next_stop
        self.queue << next_stop unless next_stop.eql?(finish)
      end
    end
    
    def shortest_route
      routes.to(finish)
    end

    def already_visited?(stop)
      @visited.key?(stop.name)
    end
    
    def set_visited!(stop)
      @visited[stop.name] = true
    end

  end
  
  class RouteSet
    
    attr_accessor :routes
    
    def initialize
      self.routes = []
    end
    
    def add_route(from: nil, to: nil)
      self.routes << Route.new(from) if routes.empty?
      routes_ending_at(from).each do |route|
        self.routes << route.with_added_stop(to)
      end
    end
    
    def routes_ending_at(stop)
      routes.select {|route| route.last_stop.eql?(stop) }
    end
    
    def size
      routes.size
    end
    
    def to_s
      routes.map(&:to_s).join("\n")
    end
    
    def to(stop)
      routes.detect {|route| route.last_stop.eql?(stop) }
    end
  end

  class Route
    
    attr_accessor :stops, :last_stop
    
    def initialize(start=nil)
      @stops = []
      add_stop(start) if start
    end
    
    def add_stop(stop)
      self.stops ||= []
      self.stops << stop
      self.last_stop = stop
    end
    
    def size
      stops.size
    end
    
    def with_added_stop(stop)
      route = Route.new
      route.stops = stops.dup
      route.add_stop(stop)
      route
    end
    
  end
  
  class RouteDescription
    attr_reader :stops
    def initialize(route)
      @route = route
      @stops = route.stops
    end
    
    def first_stop
      @stops.first.name
    end
    
    def last_stop
      @stops.last.name
    end
    
    def num_stops
      @stops.size - 1
    end
    
    def to_s
      summary + line_directions
    end
    
    def summary
      "#{num_stops} stops from #{first_stop} to #{last_stop}."
    end
    
    def line_directions
      msg = ''
      previous_lines = nil
      stops.each_with_index do |stop, i|
        next if i < 1
        previous_stop = stops[i-1]
        current_lines = stop.lines.intersection(previous_stop.lines)
        if previous_lines && previous_lines != current_lines
          msg << " Change to the #{current_lines.first.upcase} line at #{previous_stop.name}."
        end
        previous_lines = current_lines
      end
      msg
    end
    
  end
  
end


lines = {
  n: ['ts', '34th', '28th-n', '23rd-n', 'us'],
  l: ['8th', '6th', 'us', '3rd', '1st'],
  s: ['gc', '33rd', '28th-s', '23rd-s', 'us']
}

subway = Subway.new(lines)
puts subway.seek('ts', '23rd-n')
puts subway.seek('23rd-n', '3rd')
puts subway.seek('23rd-n', 'gc')
puts subway.seek('us', '28th-s')

network_traversal.rb

require 'set'

class Subway
  
  attr_reader :stops

  def initialize(lines)
    @stops = {}
    lines.each_pair {|line, stops|
      stops.each do |stop|
        @stops[stop] ||= Stop.new(stop)
        @stops[stop].add_line line
      end
    }
    lines.each_pair {|line, stops|
      stops.each_with_index {|stop_name, i|
        stop = @stops[stop_name]
        if i > 0
          previous_stop = @stops[stops[i-1]]
          stop.add_link(previous_stop)
        end
        if i < stops.size && stops[i+1]
          next_stop = @stops[stops[i+1]]
          stop.add_link(next_stop)
        end
      }
    }
  end
  
  def seek(start, finish)
    start = @stops[start]
    finish = @stops[finish]
    raise ArgumentError('Must have valid start and finish!') unless start && finish
    path = RouteSearch.new(start, finish).seek
    puts RouteDescription.new(path).to_s
  end
  
  class Stop

    attr_accessor :name, :lines
    attr_reader :links

    def initialize(name)
      @name = name
      @lines = Set.new
      @links = Set.new
    end
    
    def add_line(line)
      @lines << line
    end

    def add_link(stop)
      @links << stop
    end
    
    def eql?(stop)
      stop.name == self.name
    end
    
    def visit(search, path)
      return false if search.already_visited?(self)
      Visitation.new(self, search, path.dup).run
    end
    
    class Visitation
      
      attr_accessor :stop, :neighbors, :search, :path
      
      def initialize(stop, search, path)
        @stop, @search, @path = stop, search, path
        @neighbors = stop.links
        set_visited
      end
      
      def run
        report_finished or keep_going
      end
      
      def set_visited
        search.set_visited!(stop)
        self.path << stop
      end
      
      def report_finished
        search.path = path if stop.eql?(search.finish)
      end

      def keep_going
        neighbors.each { |neighbor| neighbor.visit search, path }
      end
    end
    
  end
  
  class RouteSearch
    attr_accessor :start, :finish, :visited, :path
    def initialize(start, finish)
      @start, @finish = start, finish
      @visited = {}
      @path = []
    end

    def seek
      start.visit self, path
      path
    end

    def already_visited?(stop)
      @visited.key?(stop.name)
    end
    
    def set_visited!(stop)
      @visited[stop.name] = true
    end

  end
  
  class RouteDescription
    attr_reader :stops
    def initialize(path)
      @stops = path
    end
    
    def first_stop
      @stops.first.name
    end
    
    def last_stop
      @stops.last.name
    end
    
    def num_stops
      @stops.size - 1
    end
    
    def to_s
      summary + line_directions
    end
    
    def summary
      "#{num_stops} stops from #{first_stop} to #{last_stop}."
    end
    
    def line_directions
      msg = ''
      previous_lines = nil
      stops.each_with_index do |stop, i|
        next if i < 1
        previous_stop = stops[i-1]
        current_lines = stop.lines.intersection(previous_stop.lines)
        if previous_lines && previous_lines != current_lines
          msg << " Change to the #{current_lines.first.upcase} line at #{previous_stop.name}."
        end
        previous_lines = current_lines
      end
      msg
    end
    
  end
  
end


lines = {
  n: ['ts', '34th', '28th-n', '23rd-n', 'us'],
  l: ['8th', '6th', 'us', '3rd', '1st'],
  s: ['gc', '33rd', '28th-s', '23rd-s', 'us']
}

subway = Subway.new(lines)
puts subway.seek('ts', '23rd-n')
puts subway.seek('23rd-n', '3rd')
puts subway.seek('23rd-n', 'gc')
puts subway.seek('us', '28th-s')