CODEWITHSUNDEEP
rubyarrays
user419017
user419017

Reputation:

Seriously stuck on Ruby array reordering

I need to reorder an array based on dependent elements. If an element is an array (has dependency), the second element of that array is the dependency, and will be required to come before that array. All dependency information is then removed as we don't need any more, and we return an array with corrected order.

# array1 = [['a'], ['b','c'], ['c','a']]
# ordered = ['a', 'c', 'b']
# logic: c comes before b, a comes before c

Here is my approach which I think is over-engineered:

array1.each_with_index do |ar, i|
  # ignore elements without dependencies
  if ar.count > 1
    # get dependency
    dep = ar[1]

    # get index for element where this dependency is first
    dep_index = array1.index { |a| a.first == dep }

    # remove found dependency and store
    dep_element = array1.delete_at(dep_index)

    # insert found dependency to before current element
    array1.insert(i, dep_element)

    # delete processed dependency
    ar.delete(dep)
  end
end

The obvious problem with the above is that as I iterate through the array, elements which have dependencies I haven't processed will be shifted back, yet the loop will only be performed once. So, I introduced a while:

while array1.flatten.count > array1.count

However, my result is ['c', 'a', 'b'].

I have also been tasked to test for self-referential and circular (infinite) dependency loops. Should I have used an Enumerator? Should have I converted array to different structure (objects) to enable easier management of order?

Upvotes: 2

Views: 203

Answers (2)

Kevin
Kevin

Reputation: 671

Check out TSort, which comes with the Ruby standard library.

It performs a topological sort, which sounds like what you need. Using your example above:

require 'tsort'

class Hash
  include TSort
  alias tsort_each_node each_key
  def tsort_each_child(node, &block)
    fetch(node).each(&block)
  end
end

def deps arr
  arr.map { |head, *tail| {head => tail} }.reduce(&:merge).tsort
end

deps [['a'], ['b','c'], ['c','a']]
#=> ['a', 'c', 'b']

Upvotes: 5

Boris Stitnicky
Boris Stitnicky

Reputation: 12578

No need to reinvent the wheel, use Rake:

require 'rake'

ary = [[:a], [:b, :c], [:c, :a]]

ordered = []
ary.each { |head, *tail| task head => tail do ordered << head end }
task( main: ary.map( &:first ) ).invoke

ordered
#=> [:a, :c, :b]

Otherwise, there is an algo for this, but I forgot its name.

Upvotes: 2

Related Questions