Need help with this python recursive basic pathfinding question. I have the layout of the code but I need help filling in the parts that say "pass" and I need the output of the code to match the sample run below. Our goal is to 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.
Need help with this python recursive basic pathfinding question. I have the layout of the code but I need help filling in the parts that say "pass" and I need the output of the code to match the sample run below.
Our goal is to 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.
You can't use break, str.endswith, list.index, keywords like: await, as, assert, class, except, lambda, and built in functions like: any, all, breakpoint, callable.
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 3 steps with 2 images
