CODEWITHSUNDEEP
arraysruby-on-railsrubysortingmerge
Pooja Mokariya
Pooja Mokariya

Reputation: 2120

merge the array of array in ruby on rails

I have one array like below

[["GJ","MP"],["HR","MH"],["MP","KL"],["KL","HR"]]

And I want result like below

"GJ, MP, KL, HR, MH"

First element of array ["GJ","MP"] Added is in the answer_string = "GJ, MP" Now Find MP which is the last element of this array in the other where is should be first element like this ["MP","KL"] after this I have to add KL in to the answer_string = "GJ, MP, KL"

This is What I want as output

Upvotes: 0

Views: 101

Answers (4)

engineersmnky
engineersmnky

Reputation: 29318

Assumptions:

  • a is an Array or a Hash
  • a is in the form provided in the Original Post
  • For each element b in a b[0] is unique

First thing I would do is, if a is an Array, then convert a to Hash for faster easier lookup up (this is not technically necessary but it simplifies implementation and should increase performance)

a = [["GJ","MP"],["HR","MH"],["MP","KL"],["KL","HR"]]
a.to_h 
#=> {"GJ"=>"MP", "HR"=>"MH", "MP"=>"KL", "KL"=>"HR"}

UPDATE If the path will always be from first to end of the chain and the elements are always a complete chain, then borrowing from @KonstantinStrukov's inspiration: (If you prefer this option then please given him the credit ✔️)

a.to_h.then {|edges| edges.reduce { |acc,_| acc << edges[acc.last] }}.join(",")
#=> "GJ,MP,KL,HR,MH"

Caveat: If there are disconnected elements in the original this result will contain nil (represented as trailing commas). This could be solved with the addition of Array#compact but it will also cause unnecessary traversals for each disconnected element.

ORIGINAL We can use a recursive method to lookup the path from a given key to the end of the path. Default key is a[0][0]

def navigate(h,from:h.keys.first)
    return unless h.key?(from)
    [from, *navigate(h,from:h[from]) || h[from]].join(",") 
end

Explanation:

  • navigation(h,from:h.keys.first) - Hash to traverse and the starting point for traversal
  • return unless h.key?(key) if the Hash does not contain the from key return nil (end of the chain)
  • [from, *navigate(h,from:h[from]) || h[from]].join(",") - build a Array of from key and the recursive result of looking up the value for that from key if the recursion returns nil then append the last value. Then simply convert the Array to a String joining the elements with a comma.

Usage:

a = [["GJ","MP"],["HR","MH"],["MP","KL"],["KL","HR"]].to_h
navigate(a) 
#=> "GJ,MP,KL,HR,MH"
navigate(a,from: "KL")
#=> "KL,HR,MH"
navigate(a,from: "X") 
#=> nil

Upvotes: 1

LihnNguyen
LihnNguyen

Reputation: 865

I use arr.size.times to loop

  def check arr
    new_arr = arr.first #new_arr = ["GJ","MP"]
    arr.delete_at(0) # remove the first of arr. arr = [["HR","MH"],["MP","KL"],["KL","HR"]]
    arr.size.times do
      find = arr.find {|e| e.first == new_arr.last}
      new_arr << find.last if find
    end
    new_arr.join(',')
  end

  array = [["GJ","MP"],["HR","MH"],["MP","KL"],["KL","HR"]]

  p check(array)

#=> "GJ,MP,KL,HR,MH"

Upvotes: 1

Konstantin Strukov
Konstantin Strukov

Reputation: 3019

Given

ary = [["GJ","MP"],["HR","MH"],["MP","KL"],["KL","HR"]]

(where each element is in fact an edge in a simple graph that you need to traverse) your task can be solved in a quite straightforward way:

acc = ary.first.dup

ary.size.times do
  # Find an edge whose "from" value is equal to the latest "to" one
  next_edge = ary.find { |a, _| a == acc.last }
  acc << next_edge.last if next_edge
end

acc
#=> ["GJ", "MP", "KL", "HR", "MH"]

Bad thing here is its quadratic time (you search through the whole array on each iteration) that would hit you badly if the initial array is large enough. It would be faster to use some auxiliary data structure with the faster lookup (hash, for instance). Smth. like

head, *tail = ary
edges = tail.to_h

tail.reduce(head.dup) { |acc, (k, v)| acc << edges[acc.last] }
#=> ["GJ", "MP", "KL", "HR", "MH"]

(I'm not joining the resulting array into a string but this is kinda straightforward)

Upvotes: 3

dangarfield
dangarfield

Reputation: 2330

d = [["GJ","MP"],["HR","MH"],["MP","KL"],["KL","HR"]]
o = [] # List for output
c = d[0][0] # Save the current first object
loop do # Keep looping through until there are no matching pairs
 o.push(c) # Push the current first object to the output
 n = d.index { |a| a[0] == c } # Get the index of the first matched pair of the current `c`
 break if n == nil # If there are no found index, we've essentially gotten to the end of the graph
 c = d[n][1] # Update the current first object
end
puts o.join(',') # Join the results

Updated as the question was dramatically changed. Essentially, you navigating a graph.

Upvotes: 1

Related Questions