Skip to content

Instantly share code, notes, and snippets.

@dfurber
Last active August 29, 2015 14:22
Show Gist options
  • Save dfurber/97ae80edb1ec8bb58030 to your computer and use it in GitHub Desktop.
Save dfurber/97ae80edb1ec8bb58030 to your computer and use it in GitHub Desktop.
MTA Problem
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')
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')
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment