This community-built FAQ covers the “Search It Again, Sam” exercise from the lesson “Graph Search: Python”.
Paths and Courses
This exercise can be found in the following Codecademy content:
FAQs on the exercise Search It Again, Sam
There are currently no frequently asked questions associated with this exercise – that’s where you come in! You can contribute to this section by offering your own questions, answers, or clarifications on this exercise. Ask or answer a question by clicking reply () below.
If you’ve had an “aha” moment about the concepts, formatting, syntax, or anything else with this exercise, consider sharing those insights! Teaching others and answering their questions is one of the best ways to learn and stay sharp.
Join the Discussion. Help a fellow learner on their journey.
Ask or answer a question about this exercise by clicking reply () below!
Agree with a comment or answer? Like () to up-vote the contribution!
I programmed DFS algorithm following the instructions, got all checks. And with graph provided to test the DFS function I get suspicious result.
Graph provided to test the function:
the_most_dangerous_graph = {
‘lava’: set([‘sharks’, ‘piranhas’]),
‘sharks’: set([‘lava’, ‘bees’, ‘lasers’]),
‘piranhas’: set([‘lava’, ‘crocodiles’]),
‘bees’: set([‘sharks’]),
‘lasers’: set([‘sharks’, ‘crocodiles’]),
‘crocodiles’: set([‘piranhas’, ‘lasers’])
}
and function call with “print(dfs(the_most_dangerous_graph, “crocodiles”, “bees”))” got one of the results: [‘crocodiles’, ‘lasers’, ‘sharks’, ‘lava’, ‘piranhas’, ‘bees’]
Is there a bug in algorithm, how come one can get from “piranhas” to “bees” if “piranhas” is not directly connected to “bees”
Let’s start from the 3rd -> 4th vertex, sharks -> lava (1st choice from sharks), then the 1st vertex choice from lava is sharks. But it’s already visited so skip it.
The 2nd vertex choice from lava is piranhas, it’s not visited yet so pass it as the neighbor argument into the next recursive call.
Inside of recursive call, add the piranhas into the visited list. Then check the vertex choices from it. However, both lava and crocodiles vertices inside piranhas have already been visited. It means it won’t call the next-next recursive call nor return anything.
Consider the path is already “ended”. Back to the beginning of where we started, 3rd vertex, shark. This time choose the 2nd choice -> bees. It hasn’t been visited and it’s the target value, so add it into the list and return.
I’m guess the set is like the dictionary, which is un-ordered. So it may pick the vertex randomly instead of following any pattern of either index or alphabet.
It makes sense that the program would return back to shark since its the only key in the dictionary that has a neighbor that hasn’t been added to visited. I just don’t understand how the program “knows” to go back to the beginning. Does it re run all of the previous recursive calls until it finds bees?
Also an “aha” moment for me during this lesson was reading that “A Set is an unordered collection data type that is iterable, mutable, and has no duplicate elements”. That’s why the neighbors are picked at random.
Yes. It randomly picks one neighbor, then runs down all of its neighbors, etc.
for neighbor in graph[current_vertex]: # one neighbor is selected
if neighbor not in visited: # has this neighbor been searched?
# if not, recursively search this neighbor
# once this neighbor's tree is exhausted, back to "for", for the next neighbor
… that’s how recursion works: each top branch is completed before the next one is attacked, and so on, all the way down.
I noticed the same, and I understand all explanations given. However, given that one of the possible paths returned by the function is “[‘crocodiles’, ‘piranhas’, ‘lava’, ‘sharks’, ‘lasers’, ‘bees’]”, and given that the problem description stated that “…We’ll go with the third option here (i.e. Return the path itself), which gives us the other information as well”, the proposed solution does not seem to be right, since this outcome is not really a path…
Traceback (most recent call last):
File "script.py", line 28, in <module>
print(dfs(the_most_dangerous_graph,'crocodiles','bees'))
File "script.py", line 13, in dfs
path=dfs(graph,neighbor,target_value,visited)
File "script.py", line 13, in dfs
path=dfs(graph,neighbor,target_value,visited)
File "script.py", line 13, in dfs
path=dfs(graph,neighbor,target_value,visited)
File "script.py", line 14, in dfs
if target_value in path:
TypeError: argument of type 'NoneType' is not iterable
just why?
def dfs(graph, current_vertex, target_value, visited=None):
if visited is None:
visited = []
visited.append(current_vertex)
if current_vertex == target_value:
return visited
# Add your recursive case here:
for neighbor in graph[current_vertex]:
if neighbor not in visited:
path=dfs(graph,neighbor,target_value,visited)
if target_value in path:
return path
I think the problem is that they never added a .pop() command for path vertices that had proven to be dead ends. So the “path” provided by this program is actually just the visited list.
We are recursively calling the function. Path is the result of the recursive call of the function (which will return ‘visited’ when the base case is satisfied) so we return it so that our function returns the value we are looking for
I just did this lesson and came here to see if anyone else had noticed the problem with their solution. It looks like quite a few people have, but I don’t see an explanation here.
The reason the algorithm sometimes returns vertices that aren’t part of the solution is that the ‘visited’ variable is passed by reference. So, every instance of the ‘dfs’ function is sharing the same ‘visited’ list. Wrong paths are still adding their vertex to the shared list.
The solution is to make a deep copy or to make sure that ever instance of ‘dfs’ is overwriting the contents of ‘visited’.
One way to do this would be to replace ‘visited.append(current_vertex)’ with ‘visited = visited + [current_vertex]’. If you make that change, you won’t get results like:
The problem with their solution, which hopefully has been fixed by now, is that it is returning nodes that aren’t part of the solution. In the example given, start at ‘crocodiles’ and find ‘bees’, the two solutions would be, “crocodiles - lasers - sharks - bees” or “crocodiles - piranhas - lava - sharks - bees”. To get to the first solution it’s fine that our algorithm looked at ‘lava’ and ‘piranhas’, but when we get to ‘piranhas’ and both of its neighbors have been visited we return None, so they should not end up in the path variable that gets returned when we find ‘bees’.
It is a lot easier to see that the solutions returned by the example code aren’t valid paths if you draw out or make a visualization of the graph.
It fails test case if spelling of neighbour is not as expected
# Add your recursive case here:
for neighbour in graph[current_vertex]:
if neighbour not in visited:
path = dfs(graph, neighbour, target_value, visited)
if path:
return path
) below.
) to up-vote the contribution!