Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
require 'rspec'
require 'forwardable'
require 'pry'
require 'set'
class ListyThing
extend Forwardable
def_delegators :@data, :<<, :empty?, :concat
def initialize
@data = []
end
end
class MyQueue < ListyThing
def get
@data.shift
end
end
class Stack < ListyThing
def get
@data.pop
end
end
class Graph
def initialize(unions)
@unions = unions
end
def shortest_path(start, finish, storage=Stack.new)
visited = Set.new
storage << [start]
visited.add start
until storage.empty?
path = storage.get
node = path.last
visited.add node
paths = @unions[node].reject{|n| visited.include? n}.map{|n| path + [n]}
return p if (p = paths.find {|p| p.last == finish})
storage.concat(paths)
end
end
end
describe Graph do
it "finds the shortest path" do
unions = { 1 => [2,4],
2 => [1,3,5],
3 => [2,11],
4 => [1,5,7],
5 => [2,4,6,8],
6 => [5,9,10],
7 => [4,13],
8 => [5,14],
9 => [6,12],
10 => [6,11],
11 => [3,10],
12 => [9],
13 => [7,13],
14 => [8,13]
}
graph = Graph.new(unions)
expect(graph.shortest_path(1,12, Stack.new)).to eq [1, 2, 5, 6, 9, 12]
expect(graph.shortest_path(1,12, MyQueue.new)).to eq [1, 2, 5, 6, 9, 12]
end
it "" do
unions = { 1 => [2,3],
2 => [1],
3 => [1] }
graph = Graph.new(unions)
expect(graph.shortest_path(1,3)).to eq [1, 3]
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment