Forked from jbgutierrez/find_redundant_resistors.rb
Created
November 12, 2009 13:58
-
-
Save RLGGHC/232911 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
require "test/unit" | |
class TestFindRedundantResistors < Test::Unit::TestCase | |
def test_find_redundant_resistors | |
actual = find_redundant_resistors [ | |
[ 'A', 'B', 50], | |
[ 'A', 'D', 150], | |
[ 'B', 'C', 250], | |
[ 'B', 'E', 250], | |
[ 'C', 'E', 350], | |
[ 'C', 'D', 50], | |
[ 'C', 'F', 100], | |
[ 'D', 'F', 400], | |
[ 'E', 'G', 200], | |
[ 'F', 'G', 100], | |
] | |
expected = [ | |
[ 'A', 'B', 50], | |
[ 'B', 'C', 250], | |
[ 'B', 'E', 250], | |
[ 'C', 'E', 350], | |
[ 'D', 'F', 400], | |
[ 'E', 'G', 200], | |
] | |
assert_equal(expected, actual) | |
end | |
end | |
def find_redundant_resistors(resistors) | |
circuit = Graph.new(resistors) | |
least_resistance_path = circuit.shortest_path('A', 'G') | |
redundant_resistors = resistors.dup | |
(least_resistance_path.size - 1).times do |i| | |
from, to = least_resistance_path[i], least_resistance_path[i + 1] | |
redundant_resistors.reject! do |r| # remove this resistence from the circuit | |
to.name == r[0] && from.name == r[1] or | |
to.name == r[1] && from.name == r[0] | |
end | |
end | |
redundant_resistors | |
end | |
## | |
# Graph class | |
class Graph | |
attr_reader :vertices | |
def initialize(distances) | |
@vertices = {} | |
distances.each {|distance| add(*distance) } | |
end | |
def shortest_path(from, to) | |
origen, destiny = self.vertices[from], self.vertices[to] | |
origen.find_shortest_path_to(destiny) | |
end | |
private | |
## | |
# Adds distance info between two vertices in the graph | |
def add(source_name, target_name, distance) | |
target = @vertices[target_name] ||= Vertex.new(target_name) | |
source = @vertices[source_name] ||= Vertex.new(source_name) | |
source.connections[target] = distance | |
target.connections[source] = distance | |
end | |
end | |
## | |
# Vertex class | |
class Vertex | |
attr_reader :name | |
# Hash containing the the distances to the vertices connected to the current vertex | |
attr_reader :connections | |
## | |
# Constructor | |
def initialize(name) | |
@name = name | |
@connections = {} | |
end | |
## | |
# Dijkstra's terms | |
attr_reader :shortest_connections_to_origin | |
attr_reader :shortest_distance_to_origin | |
## | |
# Dijkstra's algorithm | |
def find_shortest_path_to(destiny) | |
@shortest_distance_to_origin = 0 | |
temporary_vertices, checked_vertices = [ self ], [] | |
while !temporary_vertices.empty? | |
# pick next vertex among the temporary vertices who offers the shortest distance to origin | |
min_shortest_distance_to_origin = temporary_vertices.map { |t| t.shortest_distance_to_origin }.compact.min | |
current_vertex = temporary_vertices.find { |t| t.shortest_distance_to_origin == min_shortest_distance_to_origin } | |
# if current vertex offers his connections a shortest path to origin they will update shortest path info | |
current_vertex.connections.keys.each do |v| | |
v.check_distance_through(current_vertex) | |
temporary_vertices << v | |
end | |
checked_vertices << current_vertex | |
temporary_vertices -= checked_vertices | |
end | |
# although each vertix can contain multiple min paths to origin i will pick just one | |
shortest_path = [ destiny ] | |
current_vertex = destiny | |
while !shortest_path.include?(self) | |
current_vertex = current_vertex.shortest_connections_to_origin.first | |
shortest_path.push current_vertex | |
end | |
shortest_path | |
end | |
protected | |
## | |
# Checks whether the distance to the origin through this vertex is shortest than the ones visited earlier | |
def check_distance_through(vertex) | |
shortest_distance_to_origin_through_vertex = (vertex.shortest_distance_to_origin || 0) + @connections[vertex] | |
if @shortest_distance_to_origin.nil? || shortest_distance_to_origin_through_vertex < @shortest_distance_to_origin | |
@shortest_distance_to_origin = shortest_distance_to_origin_through_vertex | |
@shortest_connections_to_origin = [ vertex ] | |
end | |
end | |
end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment