Как реализовать функцию, которая выстраивает маршрут между городами

Question

Задание такое: Реализуйте функцию build_itinerary(), которая выстраивает маршрут между городами. Есть список:`

tree = ['Moscow', [
    ['Smolensk'],
    ['Yaroslavl'],
    ['Voronezh', [
        ['Liski'],
        ['Boguchar'],
        ['Kursk', [
            ['Belgorod', [
                ['Borisovka'],
            ]],
            ['Kurchatov'],
        ]],
    ]],
    ['Ivanovo', [
        ['Kostroma'], ['Kineshma'],
    ]],
    ['Vladimir'],
    ['Tver', [
        ['Klin'], ['Dubna'], ['Rzhev'],
    ]],
]]

Мне удалось преобразовать список в надлежащий вид:

>>>def make_flat(tree, dictionary, parent=None):
    (node, branches) = tree
    children = []
    dictionary[node] = (parent, children)
    for branch in branches:
        if len(branch) == 1:
            children += branch
            dictionary[branch[0]] = (node, [])
        elif len(branch) > 1:
            name = make_flat(branch, dictionary, parent=node)
            children.append(name)
    return node

>>>flat = {}
>>>make_flat(tree, flat)
>>>flat

{'Moscow': (None,
  ['Smolensk', 'Yaroslavl', 'Voronezh', 'Ivanovo', 'Vladimir', 'Tver']),
 'Smolensk': ('Moscow', []),
 'Yaroslavl': ('Moscow', []),
 'Voronezh': ('Moscow', ['Liski', 'Boguchar', 'Kursk']),
 'Liski': ('Voronezh', []),
 'Boguchar': ('Voronezh', []),
 'Kursk': ('Voronezh', ['Belgorod', 'Kurchatov']),
 'Belgorod': ('Kursk', ['Borisovka']),
 'Borisovka': ('Belgorod', []),
 'Kurchatov': ('Kursk', []),
 'Ivanovo': ('Moscow', ['Kostroma', 'Kineshma']),
 'Kostroma': ('Ivanovo', []),
 'Kineshma': ('Ivanovo', []),
 'Vladimir': ('Moscow', []),
 'Tver': ('Moscow', ['Klin', 'Dubna', 'Rzhev']),
 'Klin': ('Tver', []),
 'Dubna': ('Tver', []),
 'Rzhev': ('Tver', [])}

Можете подсказать как мне обойти этот словарь и при этом сохранить маршрут? Должно получиться так:

build_itinerary(tree, 'Dubna', 'Kostroma')
['Dubna', 'Tver', 'Moscow', 'Ivanovo', 'Kostroma']

build_itinerary(tree,'Borisovka', 'Kurchatov')
['Borisovka', 'Belgorod', 'Kursk', 'Kurchatov']

build_itinerary(tree, 'Tver', 'Dubna')
['Tver', 'Dubna']

Answer 1

Задача на графы. Для решения строим список смежностей (в нашем случае словарь), используя его ищем маршрут с помощью dfs.

def build_adj_dct(root, adj_dct):
    if len(root) == 1:
        return

    src_name, dest_lst = root
    src_to_dest_set = adj_dct.setdefault(src_name, set())
    for dest in dest_lst:
        src_to_dest_set.add(dest[0])
        dest_to_src_set = adj_dct.setdefault(dest[0], set())
        dest_to_src_set.add(src_name)
        build_adj_dct(dest, adj_dct)

def find_routes(adj_dct, src, dest):
    visited = set()
    def dfs(city, route=()):
        if city in visited:
            return

        if city == dest:
            yield route + (city,)
            return 

        visited.add(city)

        for dst in adj_dct[city]:
            yield from dfs(dst, route + (city,))

    return list(dfs(src))

tree = ['Moscow', [
    ['Smolensk'],
    ['Yaroslavl'],
    ['Voronezh', [
        ['Liski'],
        ['Boguchar'],
        ['Kursk', [
            ['Belgorod', [
                ['Borisovka'],
            ]],
            ['Kurchatov'],
        ]],
    ]],
    ['Ivanovo', [
        ['Kostroma'], ['Kineshma'],
    ]],
    ['Vladimir'],
    ['Tver', [
        ['Klin'], ['Dubna'], ['Rzhev'],
    ]],
]]    

adj_dct = {} 
build_adj_dct(tree, adj_dct)

tests = [
    ('Dubna', 'Kostroma', ('Dubna', 'Tver', 'Moscow', 'Ivanovo', 'Kostroma')),      
    ('Borisovka', 'Kurchatov', ('Borisovka', 'Belgorod', 'Kursk', 'Kurchatov')), 
    ('Tver', 'Dubna', ('Tver', 'Dubna')),           
]

for src, dst, right_ans in tests:
    ans = find_routes(adj_dct, src, dst)
    print(ans[0])
    assert ans[0] == right_ans, f"{ans[0]} != {right_ans}"

БЛОГ НА HUSL

Как реализовать функцию, которая выстраивает маршрут между городами

Ответы (1 шт):