Tengo un hash como se muestra a continuación:

hash = {
  "Hulk" => 25,
  "IronMan" => 75,
  "Groot" => 51,
  "Captain America" =>50,
  "Spider Man" => 40,
  "Thor" => 50,
  "Black Panther" => 49
}

Necesito encontrar un conjunto de superhéroes cuyo valor será 100 cuando sume el valor del otro, por ejemplo, Capitán América + Thor = 100.

Puedo iterar sobre un hash con índice con:

hash.each_with_index { |(key,value),index| ... }

Con un bucle interno que compara cada valor.

¿Hay alguna forma mejor y más sencilla de abordar esto?

0
Prasad 14 sep. 2018 a las 13:02

5 respuestas

La mejor respuesta

Si la entrada no es enorme, uno podría usar Array#combination:

1.upto(input.size).
  flat_map do |i|
    input.to_a.combination(i).select do |arrs|
      arrs.map(&:last).reduce(:+) == 100
    end
  end.
  map(&:to_h)
#⇒ [{"Hulk"=>25, "IronMan"=>75},
#   {"Groot"=>51, "Black Panther"=>49},
#   {"Captain America"=>50, "Thor"=>50}]

Si estás seguro de que solo podría haber 2 héroes cuyo poder sume hasta 100, sustituye el 1.upto(input.size) bucle con 2 codificado en el argumento de combination. En este caso, sería lo suficientemente rápido incluso para grandes entradas.

3
Aleksei Matiushkin 14 sep. 2018 a las 10:17

Tratar

input["Thor"] + input["Captain America"]

El objeto de entrada que ha creado es un hash, y la forma más fácil de obtener el valor de un hash es introducir la clave con la que está asociado:

hash["key"]
-2
Mark 14 sep. 2018 a las 10:05

Puede lograr una complejidad lineal O(N) en cuanto al rendimiento

EDITAR Supuse que está buscando las combinaciones de 2, lo cual es incorrecto, según tengo entendido.

input = { 
  "Hulk" => 25,
  "IronMan" => 75,
  "Groot" => 51,
  "Captain America" => 50,
  "Spider Man" => 40,
  "Thor" => 50,
  "Black Panther" => 49
}

# Create inverse lookup map
inverse_input = input.each.with_object(Hash.new([])){ |(k, v), h| h[v] += [k] }
#=> {25=>["Hulk"], 75=>["IronMan"], 51=>["Groot"], 50=>["Captain America", "Thor"], 40=>["Spider Man"], 49=>["Black Panther"]}

input.flat_map do |hero, power| 
  # Get heroes with needed power only
  other_heroes = inverse_input[100 - power]
  # Remove current hero from the list
  other_but_this = other_heroes.reject{ |name| name == hero }
  # Map over remaining heroes 
  # and sort them for later `uniq` filtering
  other_but_this.map { |h| [hero, h].sort }
end.compact.uniq
# compact will remove nils
# uniq will remove duplicates
#=> [["Hulk", "IronMan"], ["Black Panther", "Groot"], ["Captain America", "Thor"]]

Si la longitud de la entrada es pequeña, puede optar por una solución más corta O(N^2):

input.to_a.
      permutation(2).
      select{|(n1,v1), (n2, v2)| n1 != n2 && v1 + v2 == 100 }.
      map{ |l,r| [l.first, r.first].sort }.
      uniq
#=> [["Hulk", "IronMan"], ["Black Panther", "Groot"], ["Captain America", "Thor"]]
2
fl00r 14 sep. 2018 a las 10:41

Una posible solución sería:

all_options = input.map { |a| input.without(a).map { |b| [a, b] } }.flatten(1).sort.uniq

valid_options = all_options.select { |r| r.sum(&:second) == 100 }

Enmienda, la primera línea se puede lograr usando input.combination(2) (Uy). Todo este problema se puede resolver usando:

input.combination(2).select { |r| r.sum(&:second) == 100 }.map(&:to_h)
0
Ben Toogood 14 sep. 2018 a las 10:17

Supongo que esto es lo que estás buscando.

resultArr = []
input.keys.each do |keyName|
  input.each do |inKey, inValue|
    ((resultArr << [keyName, inKey]) if ((input[keyName] + inValue) == 100)) unless (keyName == inKey)
  end
end

result = []
resultArr.each do |resArr| result << resArr.sort end
result.uniq!
puts result
-1
anjali rai 14 sep. 2018 a las 10:19