Skip to content

Instantly share code, notes, and snippets.

@RafaelBroseghini
Created November 26, 2018 02:00
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save RafaelBroseghini/32627cac4b20ccf4d5c712d7108921dc to your computer and use it in GitHub Desktop.
Save RafaelBroseghini/32627cac4b20ccf4d5c712d7108921dc to your computer and use it in GitHub Desktop.
Find the path between an employee to its highest manager
"""
Given a source and a destination, let us
find the path (if existing) between the two.
"""
company = {
"Bill":"Ada",
"Monty":"Alan",
"Ada":"Bob",
"John":"Linus",
"Bob":"Steve",
"Steve":"Linus"
}
def find_path(source: str, dest: str, data: dict) -> list:
done, current, path = False, source, []
while not done:
path.append(current)
if current == dest:
done = True
elif current in data:
current = data[current]
else:
done = True
path.append(None)
return path
def find_path_recursively(source: str, dest: str, data: dict, path = []) -> list:
if source == dest:
path.append(source)
return path
if source not in data:
path.append(None)
return path
path.append(source)
return find_path_recursively(data[source], dest, data)
if __name__ == "__main__":
res = find_path("Bill", "Linus", company)
if res[-1] == None:
print("No path between given arguments")
print(res)
else:
print("Path found!")
print(res)
res_two = find_path_recursively("Bill", "Linus", company)
if res_two[-1] == None:
print("No path between given arguments")
print(res_two)
else:
print("Path found!")
print(res_two)
@RafaelBroseghini
Copy link
Author

Careful when reusing the recursive function, since the path (list) parameter passed to the function would mutate when calling the function again.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment