Using `inject`,` except` and `next` to determine the minimum value

Question

I have this code:

def test(vertices, distances) until vertices.empty? nearest_vertex = vertices.inject do |a, b| p "a = #{a}: b = #{b}" p "distances[a] = #{distances[a]}, distances[b] = #{distances[b]}" next b unless distances[a] #next b if distances[a] == true next a unless distances[b] #next a if distances[b] == true next a if distances[a] < distances[b] p "b = #{b}" b end p "nearest_vertex = #{nearest_vertex}" vertices.delete nearest_vertex end end vertices = [1, 2, 3, 4, 5, 6] distances = {1 => 0, 2 => 3, 3 => 2, 4 => 18, 5 => nil, 6 => 7} test(vertices, distances) 

What outputs:

 "a = 1: b = 2" "distances[a] = 0, distances[b] = 3" "a = 1: b = 3" "distances[a] = 0, distances[b] = 2" ... "a = 1: b = 6" "distances[a] = 0, distances[b] = 7" "nearest_vertex = 1" 

Here b = 6 not printed. Is this because next issues an iteration stop command?

 "a = 2: b = 3" "distances[a] = 3, distances[b] = 2" "b = 3" 

Why does the iteration continue to a=2: b=4 here?

 "a = 3: b = 4" "distances[a] = 2, distances[b] = 18" "a = 3: b = 5" "distances[a] = 2, distances[b] = " "a = 3: b = 6" "distances[a] = 2, distances[b] = 7" "nearest_vertex = 3" ... 

Once a set to 3 , everything works as I thought. How does the program know that nearest_vertex is three?

I do not understand the interaction between inject and next in determining how and when to declare a vertex as nearest_vertex . How are distances compared when there is no comparison operator?

Answer 1

Let me explain Enumerable#inject in pure Ruby. Note that the following code is NOT the original implementation of Enumerable#inject . For clarity, I will explain this in the Array class and focus on the main use of ary.inject(&block) :

 class Array def inject(&block) return nil if self.empty? enumerator = self.each accumulator = enumerator.next loop do begin accumulator = block.call(accumulator, enumerator.next) rescue StopIteration break end end accumulator end end 

You can see that in the loop the drive of the previous iteration and the current array element are transferred to the block parameters, and the return value of the block is reassigned to the drive.

Then what is next x in a block?

You can think of the block as an anonymous function, and the next keyword is its return . It ends the current call to the block and returns block x ( nil if the return value is not explicitly specified).

By the way, break x in the block ends the call to the method that takes the block and returns method x . For instance:

 [1, 2, 3, 4].inject do |acc, n| break n if n == 2 acc + n end => 2 

Array#inject ends with break when n is 2 , and n is returned.

return in a block completes a method call that calls a method that takes a block. For instance:

 def foo [1, 2, 3].inject do |acc, n| return n end puts 'You will never see this this sentence.' end foo => 2 

And there is no printed sentence because foo return .

Answer 2

How inject works

The block passed to inject receives two arguments at each iteration. The first argument ( prev_nearest_key here) is a "battery" whose value is any value returned by the previous iteration. (For the first iteration, this will be the argument given by inject or, in the absence, the first element of the collection is vertices[0] here.) The second argument ( key ) is the current element of the collection. When the iteration is complete, the final battery value is returned.

When you call next val in the block passed to the iterator, val immediately returns from the block and the next iteration begins. To demonstrate how this looks with map :

 ["h", "e", "l", "l", "o"].map do |letter| next letter.upcase if "aeoiu".include?(letter) letter end # => ["h", "E", "l", "l", "O"] 

Above, when letter is a vowel, letter.upcase returned from the block, and the next line is never evaluated. When letter not a vowel, it returns from the block unchanged.

Here's a similar injection example:

 ["h", "e", "l", "l", "o"].inject do |accum, letter| next accum + letter.upcase if "aeoiu".include?(letter) accum + letter end # => "hEllO" 

What is the difference here? When letter is a vowel, accum + letter.upcase returned from the block (effectively adding letter.upcase to accum ), and the next line is never evaluated. If letter not a vowel, accum + letter returned from the block. In both cases, the value returned from the block becomes accum in the next iteration.

How your code works

Here is your code, but with more understandable variable names.

 nearest_vertex = vertices.inject do |prev_nearest_vertex, current_vertex| next current_vertex unless distances[prev_nearest_vertex] next prev_nearest_vertex unless distances[current_vertex] next prev_nearest_vertex if distances[prev_nearest_vertex] < distances[current_vertex] current_vertex end 

I renamed a , the battery, to prev_nearest_vertex , as this is the value returned by the previous iteration, and b is current_vertex .

The first two lines inside the block simply check to see if there are distances[prev_nearest_vertex] and distances[current_vertex] nil . They could (and perhaps should) be written like this:

 next current_vertex if distances[prev_nearest_vertex].nil? next prev_nearest_vertex if distances[current_vertex].nil? 

The first line basically says: "If the previous closest distance to the top is nil , then it's not the closest, so set prev_nearest_vertex to current_vertex at the next iteration." The second line says: "If the current distance of the vertex is nil , then it is not the closest, so keep prev_nearest_vertex the same in the next iteration.

And here are the third and fourth lines:

 next prev_nearest_vertex if distances[prev_nearest_vertex] < distances[current_vertex] current_vertex 

They can be rewritten as follows:

 if distances[prev_nearest_vertex] < distances[current_vertex] prev_nearest_vertex else current_vertex end 

He simply says: "Set prev_nearest_vertex in the next iteration to prev_nearest_vertex if its distance is less, otherwise set it to current_vertex .

This is pretty good code, but you should probably ...

Do it instead

There are many really useful methods in the Ruby Enumerable module, including min_by . It evaluates the given block for each element in Enumerable and returns the element for which the lowest value was returned. To demonstrate this, consider map :

 words = ["lorem", "ipsum", "dolor", "sit", "amet"] words.map {|word| word.size } # => [5, 5, 5, 3, 4] 

It just turns an array of words into an array of its size. Now suppose we want the shortest word. This is easy with min_by :

 words = ["lorem", "ipsum", "dolor", "sit", "amet"] words.min_by {|word| word.size } # => "sit" 

Instead of returning the sizes of words, it calculates their sizes and then returns the word whose size is the smallest.

This applies directly to your code. Consider the map operation again:

 vertices = [1, 2, 3, 4, 5, 6] distances = { 1 => 0, 2 => 3, 3 => 2, 4 => 18, 5 => nil, 6 => 7 } vertices.map do |vertex| distances[vertex] || Float::INFINITY end # => [0, 3, 2, 18, Infinity, 7] 

This creates an array of distances corresponding to the elements in vertices , but nil distances are replaced with Float::INFINITY . This is useful because n < Float::INFINITY true for every number n . As before, we can now replace map with min_by to get the vertex corresponding to the smallest distance:

 def test(vertices, distances) vertices.min_by {|vertex| distances[vertex] || Float::INFINITY } end test(vertices, distances) # => 1