Algorithm/Recursion tree challenge

Question

Tengo problemas para tratar de entender cómo usar la recursión con este problema. ¡Estoy usando Ruby para resolverlo porque ese es el único idioma que conozco hasta ahora!

Tienes hachís de las empresas que poseen otras empresas:

@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 } 

Por ejemplo ['A','B'] => 0.5 significa que la empresa 'A' es propietaria de 0,5 (50%) de 'B' La cuestión es definir un método que le permite determinar la cantidad de una empresa que una empresa en particular posee (directa e indirectamente) mediante la propiedad de otras empresas. Lo que he determinado hasta el momento:

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

Esto devuelve una matriz de las firmas que una empresa propietaria directa. Ahora, aquí está lo que estoy pensando en cómo se verá el método de propiedad total.

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

Por el bien de este ejemplo vamos a suponer que estamos buscando total_ownership('A','E')

Obviamente, esto no funciona. Lo que realmente no puedo descifrar es cómo "almacenar" los valores de cada nivel recursivo y cómo establecer correctamente el caso base. Si no puedes ayudarme con eso en Ruby, tampoco me importa el pseudo-código.

Answer 1

Hmm, me parece que debe ser

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 

Answer 2

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