I need help with this python computer science DEEP BREADTH SEARCH question. I have the layout of the code but I need help filling in the parts that say "pass" and I want you to take a picture of your output and make sure it matches the sample run below. Find a path (not the best path, but just any path) from A to Z. You see that the green path is not the shortest but it does let us navigate from start to finish. (The picture below) First, we need to know A and Z, our starting and ending points. We'll pass these into our function. I'm going to use a dictionary to represent this graph. Each node (vertex, circle) will have a name, in this case "A" and "Z" were the names of the nodes, but in the generated maps I'm going to use "Node 1", "Node 2", "Node 3", etc. Here is an example web_map web_map = { 'Node 1': ['Node 3', 'Node 2'], 'Node 2': ['Node 1', 'Node 4'], 'Node 3': ['Node 1'], 'Node 4': ['Node 2'] } Node 1 is connected to 2 and 3 for instance, and then also note that Node 3 is connected back to Node 1. Similarly, Node 2 is connected back to Node 1. Then there's a connection between Node 2 and Node 4 that also goes both ways. All connections in our web will be bi-directional. So, in order to find the path from the start to the finish we should check if there's a path recursively through any of the nodes connected to wherever we start. Let's create a new dictionary with the nodes the same as the nodes in the web_map. Then we'll set all of them to False. You can call this visited, seen, been_there, whatever as long as it records when we visit a node. Here's the next hint: Make a recursive helper function that does most of the work that is called by the function you are required to make. ------------------------------YOU CAN'T USE--------------------------------- for instance str.endswith list.index, list.count, etc. Keywords you definitely don't need: await, as, assert, async, class, except, finally, global, lambda, nonlocal, raise, try, yield The is keyword is forbidden, not because it's necessarily bad, but because it doesn't behave as you might expect (it's not the same as ==). built in functions: any, all, breakpoint, callable, classmethod, compile, exec, delattr, divmod, enumerate, filter, map, max, min, isinstance, issubclass, iter, locals, oct, next, memoryview, property, repr, reversed, round, set, setattr, sorted, staticmethod, sum, super, type, vars, zip for instance str.endswith list.index, list.count, etc. Keywords you definitely don't need: await, as, assert, async, class, except, finally, global, lambda, nonlocal, raise, try, yield The is keyword is forbidden, not because it's necessarily bad, but because it doesn't behave as you might expect (it's not the same as ==). built in functions: any, all, breakpoint, callable, classmethod, compile, exec, delattr, divmod, enumerate, filter, map, max, min, isinstance, issubclass, iter, locals, oct, next, memoryview, property, repr, reversed, round, set, setattr, sorted, staticmethod, sum, super, type, vars, zip Starter Code import random def spider_web(web_map, starting_place, destination): pass def spider_web_rec(web_map, starting_place, destination, visited): pass def make_spider_web(num_nodes, seed=0): if seed: random.seed(seed) web_map = {} for i in range(1, num_nodes + 1): web_map[f'Node {i}'] = [] for i in range(1, num_nodes + 1): sample = random.sample(list(range(i, num_nodes + 1)), random.randint(1, num_nodes - i + 1)) print('sample', i, sample) for x in sample: if i != x: web_map[f'Node {i}'].append(f'Node {x}') web_map[f'Node {x}'].append(f'Node {i}') return web_map if __name__ == '__main__': num_nodes, seed = [int(x) for x in input('Input num_nodes, seed: ').split(',')] the_web = make_spider_web(num_nodes, seed) print(spider_web(the_web, 'Node 1', f'Node {num_nodes}')) Sample Output linux5[109]% python3 spider_web.py Input num_nodes, seed: 5, 101 {'Node 1': ['Node 2', 'Node 3', 'Node 5', 'Node 4'], 'Node 2': ['Node 1', 'Node 4', 'Node 3'], 'Node 3': ['Node 1', 'Node 2', 'Node 4', 'Node 5'], 'Node 4': ['Node 1', 'Node 2', 'Node 3', 'Node 5'], 'Node 5': ['Node 1', 'Node 3', 'Node 4']} ['Node 1', 'Node 2', 'Node 4', 'Node 3', 'Node 5'] linux5[110]% python3 spider_web.py Input num_nodes, seed: 8, 2323 {'Node 1': ['Node 8', 'Node 3', 'Node 5', 'Node 6', 'Node 7', 'Node 4'], 'Node 2': ['Node 6', 'Node 8'], 'Node 3': ['Node 1', 'Node 7', 'Node 6', 'Node 4'], 'Node 4': ['Node 1', 'Node 3', 'Node 8', 'Node 5'], 'Node 5': ['Node 1', 'Node 4', 'Node 8', 'Node 6'], 'Node 6': ['Node 1', 'Node 2', 'Node 3', 'Node 5', 'Node 8', 'Node 7'], 'Node 7': ['Node 1', 'Node 3', 'Node 6'], 'Node 8': ['Node 1', 'Node 2', 'Node 4', 'Node 5', 'Node 6']} ['Node 1', 'Node 8'] linux5[111]% python3 spider_web.py Input num_nodes, seed: 5, 6554 {'Node 1': [], 'Node 2': ['Node 4', 'Node 5'], 'Node 3': [], 'Node 4': ['Node 2'], 'Node 5': ['Node 2']} [] ([] means no path)
I need help with this python computer science DEEP BREADTH SEARCH question. I have the layout of the code but I need help filling in the parts that say "pass" and I want you to take a picture of your output and make sure it matches the sample run below.
Find a path (not the best path, but just any path) from A to Z. You see that the green path is not the shortest but it does let us navigate from start to finish. (The picture below)
First, we need to know A and Z, our starting and ending points. We'll pass these into our function.
I'm going to use a dictionary to represent this graph. Each node (vertex, circle) will have a name, in this case "A" and "Z" were the names of the nodes, but in the generated maps I'm going to use "Node 1", "Node 2", "Node 3", etc.
Here is an example web_map
web_map = {
'Node 1': ['Node 3', 'Node 2'],
'Node 2': ['Node 1', 'Node 4'],
'Node 3': ['Node 1'],
'Node 4': ['Node 2']
}
Node 1 is connected to 2 and 3 for instance, and then also note that Node 3 is connected back to Node 1. Similarly, Node 2 is connected back to Node 1.
Then there's a connection between Node 2 and Node 4 that also goes both ways. All connections in our web will be bi-directional.
So, in order to find the path from the start to the finish we should check if there's a path recursively through any of the nodes connected to wherever we start.
Let's create a new dictionary with the nodes the same as the nodes in the web_map. Then we'll set all of them to False. You can call this visited, seen, been_there, whatever as long as it records when we visit a node.
Here's the next hint: Make a recursive helper function that does most of the work that is called by the function you are required to make.
------------------------------YOU CAN'T USE---------------------------------
- for instance str.endswith
- list.index, list.count, etc.
- Keywords you definitely don't need: await, as, assert, async, class, except, finally, global, lambda, nonlocal, raise, try, yield
- The is keyword is forbidden, not because it's necessarily bad, but because it doesn't behave as you might expect (it's not the same as ==).
- built in functions: any, all, breakpoint, callable, classmethod, compile, exec, delattr, divmod, enumerate, filter, map, max, min, isinstance, issubclass, iter, locals, oct, next, memoryview, property, repr, reversed, round, set, setattr, sorted, staticmethod, sum, super, type, vars, zip
- for instance str.endswith
- list.index, list.count, etc.
- Keywords you definitely don't need: await, as, assert, async, class, except, finally, global, lambda, nonlocal, raise, try, yield
- The is keyword is forbidden, not because it's necessarily bad, but because it doesn't behave as you might expect (it's not the same as ==).
- built in functions: any, all, breakpoint, callable, classmethod, compile, exec, delattr, divmod, enumerate, filter, map, max, min, isinstance, issubclass, iter, locals, oct, next, memoryview, property, repr, reversed, round, set, setattr, sorted, staticmethod, sum, super, type, vars, zip
Starter Code
import random
def spider_web(web_map, starting_place, destination):
pass
def spider_web_rec(web_map, starting_place, destination, visited):
pass
def make_spider_web(num_nodes, seed=0):
if seed:
random.seed(seed)
web_map = {}
for i in range(1, num_nodes + 1):
web_map[f'Node {i}'] = []
for i in range(1, num_nodes + 1):
sample = random.sample(list(range(i, num_nodes + 1)), random.randint(1, num_nodes - i + 1))
print('sample', i, sample)
for x in sample:
if i != x:
web_map[f'Node {i}'].append(f'Node {x}')
web_map[f'Node {x}'].append(f'Node {i}')
return web_map
if __name__ == '__main__':
num_nodes, seed = [int(x) for x in input('Input num_nodes, seed: ').split(',')]
the_web = make_spider_web(num_nodes, seed)
print(spider_web(the_web, 'Node 1', f'Node {num_nodes}'))
Sample Output
|
linux5[109]% python3 spider_web.py Input num_nodes, seed: 5, 101 {'Node 1': ['Node 2', 'Node 3', 'Node 5', 'Node 4'], 'Node 2': ['Node 1', 'Node 4', 'Node 3'], 'Node 3': ['Node 1', 'Node 2', 'Node 4', 'Node 5'], 'Node 4': ['Node 1', 'Node 2', 'Node 3', 'Node 5'], 'Node 5': ['Node 1', 'Node 3', 'Node 4']} ['Node 1', 'Node 2', 'Node 4', 'Node 3', 'Node 5'] linux5[110]% python3 spider_web.py Input num_nodes, seed: 8, 2323 {'Node 1': ['Node 8', 'Node 3', 'Node 5', 'Node 6', 'Node 7', 'Node 4'], 'Node 2': ['Node 6', 'Node 8'], 'Node 3': ['Node 1', 'Node 7', 'Node 6', 'Node 4'], 'Node 4': ['Node 1', 'Node 3', 'Node 8', 'Node 5'], 'Node 5': ['Node 1', 'Node 4', 'Node 8', 'Node 6'], 'Node 6': ['Node 1', 'Node 2', 'Node 3', 'Node 5', 'Node 8', 'Node 7'], 'Node 7': ['Node 1', 'Node 3', 'Node 6'], 'Node 8': ['Node 1', 'Node 2', 'Node 4', 'Node 5', 'Node 6']} ['Node 1', 'Node 8'] linux5[111]% python3 spider_web.py Input num_nodes, seed: 5, 6554 {'Node 1': [], 'Node 2': ['Node 4', 'Node 5'], 'Node 3': [], 'Node 4': ['Node 2'], 'Node 5': ['Node 2']} [] ([] means no path) |
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 3 images
