Python-Exercises/mesh_message.py at master · pwgraham91/Python-Exercises · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
# https://www.interviewcake.com/question/python/mesh-message

network = {
    'Min': ['William', 'Jayden', 'Omar'],
    'William': ['Min', 'Noam'],
    'Jayden': ['Min', 'Amelia', 'Ren', 'Noam'],
    'Ren': ['Jayden', 'Omar'],
    'Amelia': ['Jayden', 'Adam', 'Miguel'],
    'Adam': ['Amelia', 'Miguel', 'Sofia', 'Lucas'],
    'Miguel': ['Amelia', 'Adam', 'Liam', 'Nathan'],
    'Noam': ['Nathan', 'Jayden', 'William'],
    'Omar': ['Ren', 'Min', 'Scott'],
    'Nathan': ['Noam', 'Miguel'],
    'Scott': ['Omar'],
    'Sofia': ['Adam'],
    'Lucas': ['Adam'],
    'Liam': ['Miguel'],
}

"""
This works by using a breadth-first search. It iterates through connections creates a queue of routes to check. It
takes the shortest possible path because a breadth first search adds only one edge at a time to the list of possible
paths.
ex: Jayden -> Omar
ex: [['Jayden', 'Ren'], ['Jayden', 'Noam'], ['Jayden', 'Min', 'William'], ['Jayden', 'Min', 'Omar']]
"""
def route_iteratively(originator, receiver):
    if originator == receiver:
        return [originator]

    seen_carriers = {originator}

    check_routes = [[originator]]

    while check_routes:
        current_route = check_routes.pop(0)
        current_phone = current_route[-1]

        for phone in network[current_phone]:
            if receiver == phone:
                current_route.append(receiver)
                return current_route

            if phone not in seen_carriers:
                new_route = current_route[:]
                new_route.append(phone)
                seen_carriers.add(phone)
                check_routes.append(new_route)


assert route_iteratively('Jayden', 'Adam') == ['Jayden', 'Amelia', 'Adam']
assert route_iteratively('Jayden', 'No One') is None
assert route_iteratively('Jayden', 'Jayden') == ['Jayden']
assert route_iteratively('Adam', 'William') == ['Adam', 'Amelia', 'Jayden', 'Min', 'William']
assert route_iteratively('Miguel', 'Jayden') == ['Miguel', 'Amelia', 'Jayden']
assert route_iteratively('Omar', 'Sofia') == ['Omar', 'Ren', 'Jayden', 'Amelia', 'Adam', 'Sofia']