Identificar todos los Nodes abuelos de cada Node en un mapa

Dado en la entrada que tiene relaciones entre una persona y sus hijos, para todas las personas en estos datos, identifique a los abuelos de todas las personas en la entrada.

Input: A map of all the people and their children
Map[String, Set[String]]

Output: A map of all people and their grandparents
Map[String, Set[String]]

Example:
Input 
Map(A -> Set(B,C), B -> Set(D, C), C -> Set(E))

Output:
Map(D -> Set(A), C -> Set(A), E -> Set(A, B)) 

Le recomendamos encarecidamente que minimice su navegador e intente esto usted mismo primero.

Aquí hemos iterado sobre todos y cada uno de los Nodes en Map y descubrimos el abuelo de cada niño.

La idea es usar Recursión. Pero también se puede resolver sin recursividad.

Veamos primero la solución Sin Recursión:

Solución 1 (Sin recursividad):

Aquí tenemos que usar Mutable Scala Map. A continuación se muestra el Código Scala.

val input = Map("A" -> Set("B","C"), "B" -> Set("D", "C"), "C" -> Set("E"))
val output: scala.collection.mutable.Map[String, Set[String]]
  = scala.collection.mutable.Map()

  input.map(node => node._2.map(child =>
    input.get(child).map(grandchildren =>
      grandchildren.map{grandchild =>
        if(output.keys.exists(_ == grandchild)) {
          output.put(grandchild, output.get(grandchild).get ++ Set(node._1))
        } else {
          output.put(grandchild, Set(node._1))
        }
      }
    )
  ))

Aquí estamos iterando sobre cada Node del mapa y descubriendo los nietos de cada hijo en el Node. Esto nos ayudará a crear un mapa con la relación de nietos y abuelos.

Solución 2 (Con recursividad):

Aquí podemos usar Immutable Scala Map ya que estamos usando Recursion.

val input = Map("A" -> Set("B","C"), "B" -> Set("D", "C"), "C" -> Set("E"))
val output = findGrandparents(input)

  def findGrandparents(family: Map[String, Set[String]]): Map[String, Set[String]] = {
    family.foldLeft(Map[String, Set[String]]()){
      case (grandParents, oneFamily) => {
        val grandChildren: Set[String] = oneFamily._2.flatMap(member => family.get(member)).flatten
        val res =  grandChildren.map(child => {
          grandParents.get(child) match {
            case None =>(child -> Set(oneFamily._1))
            case Some(x) => (child -> (x + oneFamily._1))
          }
        }).toMap
        grandParents ++ res
      }

Este artículo es una contribución de Himanshu Gupta . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.