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())

CodePudding user response：

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
------