parent = {'Amy':'Ben', 'May':'Tom', 'Tom':'Ben',
 'Ben':'Howard', 'Howard':'George', 'Frank':'Amy',
 'Joe':'Bill', 'Bill':'Mary', 'Mary':'Philip', 'Simon':'Bill',
 'Zoe':'Mary'}

Este es el diccionario principal mencionado en la pregunta. Mi tarea es:

Averigüe si los 2 nombres ingresados son ancestros. Por ejemplo, el padre de Amy es Ben, el padre de Ben es Howard, por lo que Howard y Amy están relacionados como antepasados.

A continuación se muestra mi código:

    def is_ancestor(name1,name2,pdict):
        for name in pdict:
            parent = pdict.get(name2)
            parent2 = pdict.get(parent)
            if(name1 == parent2):
                return True
            else:
                return False

Esto funcionará para el caso de ejemplo que mencioné anteriormente. Pero, ¿y si la pregunta es 'Amy' y 'Howard'? Debería devolver True ya que el padre de 'Amy' es 'Tom', el padre de Tom es Ben y el padre de Ben es Howard. Así que Amy y Howard son ancestros. Pero mi código se detendrá después de recibir a Tom y Ben. ¿Cómo mantenerlo en bucle hasta que encuentre una respuesta correcta?

A continuación se muestra la pregunta exacta:

La persona A es un antepasado (indirecto) de la persona B si se considera que la persona B es uno de los muchos descendientes de la persona A.

En el árbol de ascendencia del ejemplo dado arriba, Howard es un antepasado de Amy, pero Amy no es un antepasado de Tom.

Y esa persona misma NO es su propio antepasado. Su tarea es escribir una función,
is_ancestor(name1,name2,pdict), que abarca tres argumentos.

Los primeros dos argumentos son los nombres de personas (cadenas), mientras que el tercer argumento es
El diccionario principal mencionado anteriormente.

La función debe devolver el valor booleano ‘Verdadero 'si la primera persona en la lista de argumentos es un antepasado de la segunda persona,

y "Falso" si la primera persona en la lista de argumentos no es un
antepasado de la segunda persona.

3
Balaji Hariharan 8 oct. 2019 a las 14:45

4 respuestas

La mejor respuesta

Puede usar la recursión en lugar de un bucle.

def is_ancestor(name1, name2, pdict):
    parent = pdict.get(name2, None)
    if not parent:
        return False
    elif parent == name1:
        return True
    else:
        return is_ancestor(name1, parent, pdict)

parents = {'Amy':'Ben', 'May':'Tom', 'Tom':'Ben',
 'Ben':'Howard', 'Howard':'George', 'Frank':'Amy',
 'Joe':'Bill', 'Bill':'Mary', 'Mary':'Philip', 'Simon':'Bill',
 'Zoe':'Mary'}

print(is_ancestor("Amy", "Ben", parents))
print(is_ancestor("Ben", "Amy", parents))
print(is_ancestor("Howard", "Amy", parents))

La función obtiene el padre de name2. Si no se encuentra ningún padre, hemos alcanzado el caso base y devolvemos False. De lo contrario, verificamos si el padre encontrado es el que estamos buscando. Si es así, devolvemos True. Si no, buscamos si el padre de esa persona es el antepasado que estamos buscando. Esto seguirá recurriendo hasta que lleguemos al antepasado que estamos buscando o golpeemos a una persona sin padre en el diccionario.

1
Bill the Lizard 8 oct. 2019 a las 12:18

Que te equivocaste

Lo que sucede en su código es que solo está verificando a los padres, y no más. Debes seguir atravesando la cadena, hasta que encuentres un antepasado o te quedes sin nombres

La solución

Aquí hay un enfoque simple para el problema:

def is_ancestor(name1,name2,pdict):
    child = name1
    while True:
        if child not in pdict:
            return False
        if pdict[child] == name2:
            return True
        child = pdict[child]

Explicación

Aquí verifica si el niño que está revisando tiene un padre. Si no, devuelve False si es así, luego verifica si ese padre es la persona que estás buscando. Si no es así, establezca ese hijo como padre y repita el proceso.

1
tituszban 8 oct. 2019 a las 11:57

Puedes hacer algo como esto:

parent = {
    'Amy':'Ben', 
    'May':'Tom', 
    'Tom':'Ben', 
    'Ben':'Howard', 
    'Howard':'George', 
    'Frank':'Amy', 
    'Joe':'Bill', 
    'Bill':'Mary', 
    'Mary':'Philip', 
    'Simon':'Bill', 
    'Zoe':'Mary',
}


def is_ancestor(name1, name2, pdict):
    while name1 in pdict:
        name1 = pdict[name1]

        if name1 == name2:
            return True

    return False


assert is_ancestor('Amy', 'Amy',parent) == False
assert is_ancestor('Amy', 'Ben',parent) == True
assert is_ancestor('Ben', 'Amy',parent) == False
assert is_ancestor('Amy', 'Howard',parent) == True
assert is_ancestor('Howard', 'Amy', parent) == False
assert is_ancestor('Amy', 'George', parent) == True
assert is_ancestor('George', 'Amy', parent) == False
1
Dipen Dadhaniya 8 oct. 2019 a las 11:56

Aquí está tu respuesta usando la recursividad:

def is_ancestor(name1, name2, pdict):

    try:
        if pdict[name1] == name2:
            return True
        else:
            return is_ancestor(pdict[name1], name2, pdict)
    except KeyError:
        return False

Primero, verifica si ha encontrado un antepasado directo; de lo contrario, verifica la próxima generación recurriendo a la misma función. La excepción KeyError se activa si no se encuentra el ancestro, lo que indica que name2 no es un ancestro de name1.

3
wgb22 8 oct. 2019 a las 11:56
58285723