For school i need to make an assignment. We have to find a path between 2 vertices. I have given my code below, i almost got it working, but i am stuck at one part. this is the input:
1->5
1, 2; 2, 3; 3, 4; 4, 5; 5,
this is the correct output:
1->2->3->4->5
My program also gives the correct output when passing this input. However when passing the following input:
1->4000000000
1, 2, 3; 2, 2; 3, 4, 5; 4, 1, 2; 5, 5, 4000000000; 4000000000, 2
This should be the output:
1->3->5->4000000000
but my program gives me this
1-> 2-> 3-> 4-> 5-> 4000000000
How can i optimize this? Thanks for the help in advanve!
import sys
from typing import List
stack: []
def output():
'''
Will print the path stored in the `stack` global variable.
You are free to modify it to be a parameter.
'''
#for id in stack[:-1]:
#print(f'{id}->', end='')
#try:
#print(f'{stack[-1]}')
#except IndexError:
#pass
return "->".join(stack) if stack else ""
def find_path(graph, start, target, path):
#print(start, target)
path = path + [start]
#print(path)
if start == target:
return path
for node in graph:
#print(node)
if node not in path: ##idk what to do here..
new_path = find_path(graph, node, target, path)
if new_path:
return new_path
return path
def add_value(dict_obj, key, value):
if key not in dict_obj:
dict_obj[key] = list()
dict_obj[key].append(value)
if __name__ == '__main__':
'''
Fetch starting and target nodes.
'''
start, target = [x for x in input().split('->')]
#print(start, target)
'''
Fetch `;` separated twitter data. <id-1: u_int>, <following: u_int>, ..<following: u_int>; ...
i.e: 1, 2; 2, 3; 3, 4; 4, 5; 5,
'''
data = input()
data_l: List = data.split(';')
graph = dict()
for d in data_l:
id, followers = d.split(', ', 1)
# print(followers)
following_l: List = followers.split(', ')
for f in following_l:
if f == '':
# node is not following other nodes.
continue
add_value(graph, id, followers)
print(graph)
stack = find_path(graph, start, target, [])
sys.stdout.write(output())
First mistake: you add followers which is string like "1, 2" - you should add following_l which is a list ["1", "2"]
Another mistake: you use for node in graph: but you should use graph[start] in for node in graph[start]:
Another mistake: you shouldn't add start to path because it may not be correct direction - but you should add it when you find new_path - return [start] + new_path.
And when it can't find path then you should return empty list, not path
You should add start to separated list visited and later check if node not in visited - to check every node only once.
def find_path(graph, start, target):
print('find_path:', start, '->', target)
visited.append(start)
if start == target:
return [start]
for node in graph[start]:
#print('node:', node)
if node not in visited:
path = find_path(graph, node, target)
if path:
print('path:', [start] + path)
return [start] + path
return []
My full version:
def find_path(graph, start, target, visited):
print('find_path:', start, '->', target)
visited.append(start)
if start == target:
return [start]
for node in graph[start]:
#print('node:', node)
if node not in visited:
path = find_path(graph, node, target, visited)
if path:
print('path:', [start] + path)
return [start] + path
return []
def main(path, data):
start, target = path.split('->')
print('start, target:', start, target)
data = data.split(';')
graph = dict()
for d in data:
parts = d.split(',')
if len(parts) > 1:
id = parts[0]
id = id.strip()
followers = parts[1:]
followers = [x.strip() for x in followers if x.strip()]
print(id, 'followers:', followers)
if followers:
graph[id] = followers
print('graph:', graph)
visited = list()
stack = find_path(graph, start, target, visited)
output = "->".join(stack)
print('output:', output)
print('------')
if __name__ == '__main__':
#path = input()
#data = input()
#main(path, data)
path = '1->4000000000'
data = '1, 2, 3; 2, 2; 3, 4, 5; 4, 1, 2; 5, 5, 4000000000; 4000000000, 2'
main(path, data)
path = '1->5'
data = '1, 2; 2, 3; 3, 4; 4, 5; 5,'
main(path, data)
Result:
start, target: 1 4000000000
1 followers: ['2', '3']
2 followers: ['2']
3 followers: ['4', '5']
4 followers: ['1', '2']
5 followers: ['5', '4000000000']
4000000000 followers: ['2']
graph: {'1': ['2', '3'], '2': ['2'], '3': ['4', '5'], '4': ['1', '2'], '5': ['5', '4000000000'], '4000000000': ['2']}
find_path: 1 -> 4000000000
find_path: 2 -> 4000000000
find_path: 3 -> 4000000000
find_path: 4 -> 4000000000
find_path: 5 -> 4000000000
find_path: 4000000000 -> 4000000000
path: ['5', '4000000000']
path: ['3', '5', '4000000000']
path: ['1', '3', '5', '4000000000']
output: 1->3->5->4000000000
------
start, target: 1 5
1 followers: ['2']
2 followers: ['3']
3 followers: ['4']
4 followers: ['5']
5 followers: []
graph: {'1': ['2'], '2': ['3'], '3': ['4'], '4': ['5']}
find_path: 1 -> 5
find_path: 2 -> 5
find_path: 3 -> 5
find_path: 4 -> 5
find_path: 5 -> 5
path: ['4', '5']
path: ['3', '4', '5']
path: ['2', '3', '4', '5']
path: ['1', '2', '3', '4', '5']
output: 1->2->3->4->5
------