Algorithm/Recursion tree challenge

Question

I'm having trouble trying to understand how to use recursion with this problem. I'm using Ruby to solve it because that's the only language I know so far!

You have some hash of firms that own other firms:

@hsh = { ['A','B'] => 0.5, ['B','E'] => 0.2, ['A','E'] => 0.2, 
         ['A','C'] => 0.3, ['C','D'] => 0.4, ['D','E'] => 0.2 }

For example ['A','B'] => 0.5 means that firm 'A' owns 0.5 (50%) of 'B' The question is to define a method that allows you to determine how much of a firm a particular firm owns (directly and indirectly) through owning other firms. What I have determined so far:

def portfolio(entity)
  portfolio = []
  @hsh.keys.each do |relationship|
    portfolio << relationship.last if relationship.first == entity
  end
  portfolio
end

This returns an array of the firms that a firm directly owns. Now, here is what I'm thinking what the total_ownership method will look like.

def total_ownership(entity, security)
  portfolio(entity).inject() do |sum, company|
    sum *= @hsh[[entity,company]]
    total_ownership(company,security)
  end
end

For the sake of this example let's assume we are looking for total_ownership('A','E')

Obviously, this doesn't work. What I can't really figure out is how to "store" the values of each recursive level and how to set the base case correctly. If you can't help me with it in Ruby, I don't mind pseudo-code as well.

+1 Interesting question. If it is homework, it should be labelled as such. — steenslag
– steenslag, Commented Apr 15, 2012 at 22:38
Just to confirm, the solution for total_ownership('A', 'E') is (0.5 * 0.2) + 0.2 + (0.3 * 0.4 * 0.2)? — sunnyrjuneja
– sunnyrjuneja, Commented Apr 15, 2012 at 22:45
Nope! Just a problem I was wondering on how to solve while thinking about recursion. Thanks for the tip though — Alexander Lucic
– Alexander Lucic, Commented Apr 15, 2012 at 22:47

Paweł Obrok · Accepted Answer · 2012-04-15 23:00:03Z

2

Hmm, seems to me it should be

def total_ownership(entity, security)
  indirect = portfolio(entity).inject(0) do |sum, company|
    share = @hsh[[entity, company]]
    sum + (share || 0) * total_ownership(company,security)
  end
  direct = @hsh[[entity, security]] || 0

  indirect + direct
end

answered Apr 15, 2012 at 23:00

Paweł Obrok

23.3k8 gold badges77 silver badges70 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Alexander Lucic Over a year ago

Thanks a lot for the help; it makes much more sense now

btilly Over a year ago

Now for the bonus challenge. What if company A owns company B which owns a portfolio of stocks which includes some of company A? Your code breaks...

Leventix · Accepted Answer · 2012-04-15 23:04:42Z

1

def total_ownership(a, b)
  direct_ownership(a, b) + indirect_ownership(a, b)
end

def direct_ownership(a, b)
  @hsh[[a, b]] || 0
end

def indirect_ownership(a, b)
  portfolio(a).map do |portfolio_item|
    @hsh[[a, portfolio_item]] * total_ownership(portfolio_item, b)
  end.inject(&:+) || 0
end

answered Apr 15, 2012 at 23:04

Leventix

3,8691 gold badge34 silver badges41 bronze badges

1 Comment

Alexander Lucic Over a year ago

Thanks for the alternative method as well!

Collectives™ on Stack Overflow

Algorithm/Recursion tree challenge

2 Answers 2

2 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related