Solution for the Rubylearning Challenge #3 (http://tinyurl.com/yzjh4x9)

find_redundant_resistors.rb

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