timeit

Програмиране с Python

Курс във Факултета по Математика и Информатика към СУ

Решение на Социална мрежа от Теодор Тошков

Обратно към всички решения

Към профила на Теодор Тошков

Резултати

  • 10 точки от тестове
  • 0 бонус точки
  • 10 точки общо
  • 8 успешни тест(а)
  • 0 неуспешни тест(а)

Код

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
import uuid
import datetime
import math


class UserAlreadyExistsError(Exception):
    pass


class UserDoesNotExistError(Exception):
    pass


class UsersNotConnectedError(Exception):
    pass


class UserCanNotFollowHimself(Exception):
    pass


class User:
    def __init__(self, name):
        self.full_name = name
        self.uuid = uuid.uuid4()
        self.posts = []

    @property
    def number_of_posts(self):
        return len(self.posts)

    def add_post(self, post_content):
        self.posts.append(Post(self.uuid, post_content))
        if self.number_of_posts > 50:
            self.posts.pop(0)

    def get_post(self):
        for post in self.posts:
            yield post


class Post:
    def __init__(self, author, content):
        self.author = author
        self.published_at = datetime.datetime.now()
        self.content = content


class SocialGraph:
    def __init__(self):
        self.graph = {}

    def already_in(self, *args):
        for user in args:
            if user in self.graph:
                raise UserAlreadyExistsError

    def not_in(self, *args):
        for user in args:
            if user not in self.graph:
                raise UserDoesNotExistError

    def add_user(self, user):
        self.already_in(user.uuid)
        self.graph[user.uuid] = (user, set())

    def get_user(self, user_uuid):
        self.not_in(user_uuid)
        return self.graph[user_uuid][0]

    def delete_user(self, user_uuid):
        self.not_in(user_uuid)
        self.graph.pop(user_uuid)
        for followees in self.graph.values():
            if user_uuid in followees[1]:
                followees[1].remove(user_uuid)

    def follow(self, follower, followee):
        self.not_in(follower, followee)
        if follower is followee:
            raise UserCanNotFollowHimself
        self.graph[follower][1].add(followee)

    def unfollow(self, follower, followee):
        self.not_in(follower, followee)
        self.graph[follower][1].remove(followee)

    def is_following(self, follower, followee):
        self.not_in(follower, followee)
        return followee in self.graph[follower][1]

    def followers(self, user_uuid):
        self.not_in(user_uuid)
        result = set()
        for ID, user in self.graph.items():
            if user_uuid in user[1]:
                result.add(ID)
        return result

    def following(self, user_uuid):
        self.not_in(user_uuid)
        return self.graph[user_uuid][1]

    def friends(self, user_uuid):
        self.not_in(user_uuid)
        return {friend for friend in self.graph[user_uuid][1]
                if user_uuid in self.graph[friend][1]}

    def min_distance(self, from_user_uuid, to_user_uuid):
        self.not_in(from_user_uuid, to_user_uuid)
        path = find_shortest_path(self.graph, from_user_uuid, to_user_uuid, [])
        if not path:
            raise UsersNotConnectedError
        else:
            return len(path) - 1

    def generate_feed(self, user_uuid, offset=0, limit=10):
        self.not_in(user_uuid)
        all_posts = []
        for user_id in self.following(user_uuid):
            all_posts.extend(self.graph[user_id][0].posts)
        all_posts.sort(key=lambda x: x.published_at, reverse=True)
        return all_posts[offset:offset+limit]

    def max_distance(self, user_uuid):
        self.not_in(user_uuid)
        maximum = 0
        for node in self.graph.keys():
            path = find_shortest_path(self.graph, user_uuid, node, [])
            if path is not None and len(path) > maximum:
                maximum = len(path) - 1
        return maximum if maximum > 0 else math.inf

    def nth_layer_followings(self, user_uuid, n):
        def nth_friends(graph, user_id, n, friends, visited):
            visited.add(user_id)
            if n == 0:
                if user_id is not user_uuid:
                    friends.add(user_id)
                return friends
            for node in graph[user_id][1]:
                if node not in visited:
                    friends | nth_friends(graph, node, n - 1, friends, visited)
            visited.remove(user_id)
            return friends
        self.not_in(user_uuid)
        return nth_friends(self.graph, user_uuid, n, set(), set())


def find_shortest_path(graph, start, end, path):
        path = path + [start]
        if start == end:
            return path
        if start not in graph:
            return None
        shortest = None
        for node in graph[start][1]:
            if node not in path:
                newpath = find_shortest_path(graph, node, end, path)
                if newpath:
                    if not shortest or len(newpath) < len(shortest):
                        shortest = newpath
        return shortest

Лог от изпълнението

........
----------------------------------------------------------------------
Ran 8 tests in 0.075s

OK

История (9 версии и 2 коментара)

Теодор обнови решението на 09.04.2016 01:48 (преди над 1 година)

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
import uuid
import datetime


class UserAlreadyExistsError(Exception):
    pass


def already_in(graph, *args):
    for user in args:
        if user in graph:
            raise UserAlreadyExistsError


class UserDoesNotExistError(Exception):
    pass


def not_in(graph, *args):
    for user in args:
        if user not in graph:
            raise UserDoesNotExistError


class UsersNotConnectedError(Exception):
    pass


class User:
    def __init__(self, name):
        self.full_name = name
        self.uuid = uuid.uuid4()
        self.posts = []

    @property
    def number_of_posts(self):
        return len(self.posts)

    def add_post(self, post_content):
        self.posts.append(Post(self.uuid, post_content))
        if self.number_of_posts > 3:
            self.posts.pop(0)

    def get_post(self):
        for post in self.posts:
            yield post


class Post:
    def __init__(self, author, content):
        self.author = author
        self.published_at = datetime.datetime.now()
        self.content = content


class SocialGraph:
    def __init__(self):
        self.graph = {}

    def add_user(self, user):
        already_in(self.graph, user.uuid)
        self.graph[user.uuid] = (user, set())

    def get_user(self, user_uuid):
        not_in(self.graph, user_uuid)
        return self.graph[user_uuid][0]

    def delete_user(self, user_uuid):
        not_in(self.graph, user_uuid)
        self.graph.pop(user_uuid)

    def follow(self, follower, followee):
        not_in(self.graph, follower, followee)
        self.graph[follower][1].add(followee)

    def unfollow(self, follower, followee):
        not_in(self.graph, follower, followee)
        self.graph[follower][1].remove(followee)

    def is_following(self, follower, followee):
        not_in(self.graph, follower, followee)
        return followee in self.graph[follower][1]

    def followers(self, user_uuid):
        not_in(self.graph, user_uuid)
        result = set()
        for ID, user in self.graph.items():
            if user_uuid in user[1]:
                result.add(ID)
        return result

    def following(self, user_uuid):
        not_in(self.graph, user_uuid)
        return self.graph[user_uuid][1]

    def friends(self, user_uuid):
        not_in(self.graph, user_uuid)
        return {friend for friend in self.graph[user_uuid][1]
                if user_uuid in self.graph[friend][1]}

    def min_distance(self, from_user_uuid, to_user_uuid):
        not_in(self.graph, from_user_uuid, to_user_uuid)
        path = find_shortest_path(self.graph, from_user_uuid, to_user_uuid)
        if not path:
            raise UsersNotConnectedError
        else:
            return len(path) - 1

    def generate_feed(self, user_uuid, offset=0, limit=10):
        not_in(self.graph, user_uuid)
        all_posts = []
        for userID in self.following(user_uuid):
            all_posts.extend(self.graph[userID][0].posts)
        all_posts.sort(key=lambda x: x.published_at)
        return all_posts[offset:limit]

    def max_distance(self, user_uuid):
        not_in(self.graph, user_uuid)
        maximum = 0
        for node in self.graph.keys():
            path = find_shortest_path(self.graph, user_uuid, node)
            if path is not None and len(path) > maximum:
                maximum = len(path) - 1
        return maximum

    def nth_layer_friends(self, user_uuid, n):
        pass


def find_shortest_path(graph, start, end, path=[]):
        path = path + [start]
        if start == end:
            return path
        if start not in graph:
            return None
        shortest = None
        for node in graph[start][1]:
            if node not in path:
                newpath = find_shortest_path(graph, node, end, path)
                if newpath:
                    if not shortest or len(newpath) < len(shortest):
                        shortest = newpath
        return shortest

Каква е дефиницията на приятели от ниво n?

Трябва ли да има двоен път в графа от единият до другият? Например А < - > Б < - > В (и няма връзки А < - > В). И А и В да се считат за приятели от 2ро ниво.

Или трябва просто да има път от А до В и от В до А (тогава как се определя нивото ако 2та пътя са с различна дължина?)?

Освен това ако А и В са истински приятели (А < - > В), приятели на кое ниво са (0 или 1)?

Теодор обнови решението на 09.04.2016 12:47 (преди над 1 година)

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
import uuid
import datetime


class UserAlreadyExistsError(Exception):
    pass


def already_in(graph, *args):
    for user in args:
        if user in graph:
            raise UserAlreadyExistsError


class UserDoesNotExistError(Exception):
    pass


def not_in(graph, *args):
    for user in args:
        if user not in graph:
            raise UserDoesNotExistError


class UsersNotConnectedError(Exception):
    pass


class User:
    def __init__(self, name):
        self.full_name = name
        self.uuid = uuid.uuid4()
        self.posts = []

    @property
    def number_of_posts(self):
        return len(self.posts)

    def add_post(self, post_content):
        self.posts.append(Post(self.uuid, post_content))
        if self.number_of_posts > 3:
            self.posts.pop(0)

    def get_post(self):
        for post in self.posts:
            yield post


class Post:
    def __init__(self, author, content):
        self.author = author
        self.published_at = datetime.datetime.now()
        self.content = content


class SocialGraph:
    def __init__(self):
        self.graph = {}

    def add_user(self, user):
        already_in(self.graph, user.uuid)
        self.graph[user.uuid] = (user, set())

    def get_user(self, user_uuid):
        not_in(self.graph, user_uuid)
        return self.graph[user_uuid][0]

    def delete_user(self, user_uuid):
        not_in(self.graph, user_uuid)
        self.graph.pop(user_uuid)

    def follow(self, follower, followee):
        not_in(self.graph, follower, followee)
        self.graph[follower][1].add(followee)

    def unfollow(self, follower, followee):
        not_in(self.graph, follower, followee)
        self.graph[follower][1].remove(followee)

    def is_following(self, follower, followee):
        not_in(self.graph, follower, followee)
        return followee in self.graph[follower][1]

    def followers(self, user_uuid):
        not_in(self.graph, user_uuid)
        result = set()
        for ID, user in self.graph.items():
            if user_uuid in user[1]:
                result.add(ID)
        return result

    def following(self, user_uuid):
        not_in(self.graph, user_uuid)
        return self.graph[user_uuid][1]

    def friends(self, user_uuid):
        not_in(self.graph, user_uuid)
        return {friend for friend in self.graph[user_uuid][1]
                if user_uuid in self.graph[friend][1]}

    def min_distance(self, from_user_uuid, to_user_uuid):
        not_in(self.graph, from_user_uuid, to_user_uuid)
        path = find_shortest_path(self.graph, from_user_uuid, to_user_uuid)
        if not path:
            raise UsersNotConnectedError
        else:
            return len(path) - 1

    def generate_feed(self, user_uuid, offset=0, limit=10):
        not_in(self.graph, user_uuid)
        all_posts = []
        for userID in self.following(user_uuid):
            all_posts.extend(self.graph[userID][0].posts)
        all_posts.sort(key=lambda x: x.published_at)
        return all_posts[offset:limit]

    def max_distance(self, user_uuid):
        not_in(self.graph, user_uuid)
        maximum = 0
        for node in self.graph.keys():
            path = find_shortest_path(self.graph, user_uuid, node)
            if path is not None and len(path) > maximum:
                maximum = len(path) - 1
        return maximum

    def nth_layer_friends(self, user_uuid, n):
        def nth_friends(graph, user_id, n, friends=set()):
            if n == 0:
                if user_id is not user_uuid:
                    friends.add(user_id)
                return friends
            for node in graph[user_id][1]:
                if user_id in graph[node][1]:
                    friends | nth_friends(graph, node, n - 1, friends)
            return friends
        not_in(self.graph, user_uuid)
        return nth_friends(self.graph, user_uuid, n)


def find_shortest_path(graph, start, end, path=[]):
        path = path + [start]
        if start == end:
            return path
        if start not in graph:
            return None
        shortest = None
        for node in graph[start][1]:
            if node not in path:
                newpath = find_shortest_path(graph, node, end, path)
                if newpath:
                    if not shortest or len(newpath) < len(shortest):
                        shortest = newpath
        return shortest

Теодор обнови решението на 09.04.2016 17:40 (преди над 1 година)

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
import uuid
import datetime


class UserAlreadyExistsError(Exception):
    pass


def already_in(graph, *args):
    for user in args:
        if user in graph:
            raise UserAlreadyExistsError


class UserDoesNotExistError(Exception):
    pass


def not_in(graph, *args):
    for user in args:
        if user not in graph:
            raise UserDoesNotExistError


class UsersNotConnectedError(Exception):
    pass


class User:
    def __init__(self, name):
        self.full_name = name
        self.uuid = uuid.uuid4()
        self.posts = []

    @property
    def number_of_posts(self):
        return len(self.posts)

    def add_post(self, post_content):
        self.posts.append(Post(self.uuid, post_content))
        if self.number_of_posts > 3:
            self.posts.pop(0)

    def get_post(self):
        for post in self.posts:
            yield post


class Post:
    def __init__(self, author, content):
        self.author = author
        self.published_at = datetime.datetime.now()
        self.content = content


class SocialGraph:
    def __init__(self):
        self.graph = {}

    def add_user(self, user):
        already_in(self.graph, user.uuid)
        self.graph[user.uuid] = (user, set())

    def get_user(self, user_uuid):
        not_in(self.graph, user_uuid)
        return self.graph[user_uuid][0]

    def delete_user(self, user_uuid):
        not_in(self.graph, user_uuid)
        self.graph.pop(user_uuid)

    def follow(self, follower, followee):
        not_in(self.graph, follower, followee)
        self.graph[follower][1].add(followee)

    def unfollow(self, follower, followee):
        not_in(self.graph, follower, followee)
        self.graph[follower][1].remove(followee)

    def is_following(self, follower, followee):
        not_in(self.graph, follower, followee)
        return followee in self.graph[follower][1]

    def followers(self, user_uuid):
        not_in(self.graph, user_uuid)
        result = set()
        for ID, user in self.graph.items():
            if user_uuid in user[1]:
                result.add(ID)
        return result

    def following(self, user_uuid):
        not_in(self.graph, user_uuid)
        return self.graph[user_uuid][1]

    def friends(self, user_uuid):
        not_in(self.graph, user_uuid)
        return {friend for friend in self.graph[user_uuid][1]
                if user_uuid in self.graph[friend][1]}

    def min_distance(self, from_user_uuid, to_user_uuid):
        not_in(self.graph, from_user_uuid, to_user_uuid)
        path = find_shortest_path(self.graph, from_user_uuid, to_user_uuid)
        if not path:
            raise UsersNotConnectedError
        else:
            return len(path) - 1

    def generate_feed(self, user_uuid, offset=0, limit=10):
        not_in(self.graph, user_uuid)
        all_posts = []
        for userID in self.following(user_uuid):
            all_posts.extend(self.graph[userID][0].posts)
        all_posts.sort(key=lambda x: x.published_at)
        return all_posts[offset:limit]

    def max_distance(self, user_uuid):
        not_in(self.graph, user_uuid)
        maximum = 0
        for node in self.graph.keys():
            path = find_shortest_path(self.graph, user_uuid, node)
            if path is not None and len(path) > maximum:
                maximum = len(path) - 1
        return maximum

    def nth_layer_followings(self, user_uuid, n):
        def nth_friends(graph, user_id, n, friends=set()):
            if n == 0:
                if user_id is not user_uuid:
                    friends.add(user_id)
                return friends
            for node in graph[user_id][1]:
                    friends | nth_friends(graph, node, n - 1, friends)
            return friends
        not_in(self.graph, user_uuid)
        return nth_friends(self.graph, user_uuid, n)


def find_shortest_path(graph, start, end, path=[]):
        path = path + [start]
        if start == end:
            return path
        if start not in graph:
            return None
        shortest = None
        for node in graph[start][1]:
            if node not in path:
                newpath = find_shortest_path(graph, node, end, path)
                if newpath:
                    if not shortest or len(newpath) < len(shortest):
                        shortest = newpath
        return shortest

Теодор обнови решението на 10.04.2016 00:46 (преди над 1 година)

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
import uuid
import datetime


class UserAlreadyExistsError(Exception):
    pass


def already_in(graph, *args):
    for user in args:
        if user in graph:
            raise UserAlreadyExistsError


class UserDoesNotExistError(Exception):
    pass


def not_in(graph, *args):
    for user in args:
        if user not in graph:
            raise UserDoesNotExistError


class UsersNotConnectedError(Exception):
    pass


class User:
    def __init__(self, name):
        self.full_name = name
        self.uuid = uuid.uuid4()
        self.posts = []

    @property
    def number_of_posts(self):
        return len(self.posts)

    def add_post(self, post_content):
        self.posts.append(Post(self.uuid, post_content))
        if self.number_of_posts > 50:
            self.posts.pop(0)

    def get_post(self):
        for post in self.posts:
            yield post


class Post:
    def __init__(self, author, content):
        self.author = author
        self.published_at = datetime.datetime.now()
        self.content = content


class SocialGraph:
    def __init__(self):
        self.graph = {}

    def add_user(self, user):
        already_in(self.graph, user.uuid)
        self.graph[user.uuid] = (user, set())

    def get_user(self, user_uuid):
        not_in(self.graph, user_uuid)
        return self.graph[user_uuid][0]

    def delete_user(self, user_uuid):
        not_in(self.graph, user_uuid)
        self.graph.pop(user_uuid)

    def follow(self, follower, followee):
        not_in(self.graph, follower, followee)
        self.graph[follower][1].add(followee)

    def unfollow(self, follower, followee):
        not_in(self.graph, follower, followee)
        self.graph[follower][1].remove(followee)

    def is_following(self, follower, followee):
        not_in(self.graph, follower, followee)
        return followee in self.graph[follower][1]

    def followers(self, user_uuid):
        not_in(self.graph, user_uuid)
        result = set()
        for ID, user in self.graph.items():
            if user_uuid in user[1]:
                result.add(ID)
        return result

    def following(self, user_uuid):
        not_in(self.graph, user_uuid)
        return self.graph[user_uuid][1]

    def friends(self, user_uuid):
        not_in(self.graph, user_uuid)
        return {friend for friend in self.graph[user_uuid][1]
                if user_uuid in self.graph[friend][1]}

    def min_distance(self, from_user_uuid, to_user_uuid):
        not_in(self.graph, from_user_uuid, to_user_uuid)
        path = find_shortest_path(self.graph, from_user_uuid, to_user_uuid)
        if not path:
            raise UsersNotConnectedError
        else:
            return len(path) - 1

    def generate_feed(self, user_uuid, offset=0, limit=10):
        not_in(self.graph, user_uuid)
        all_posts = []
        for userID in self.following(user_uuid):
            all_posts.extend(self.graph[userID][0].posts)
        all_posts.sort(key=lambda x: x.published_at)
        all_posts.reverse()
        return all_posts[offset:offset+limit]

    def max_distance(self, user_uuid):
        not_in(self.graph, user_uuid)
        maximum = 0
        for node in self.graph.keys():
            path = find_shortest_path(self.graph, user_uuid, node)
            if path is not None and len(path) > maximum:
                maximum = len(path) - 1
        return maximum

    def nth_layer_followings(self, user_uuid, n):
        def nth_friends(graph, user_id, n, friends=set()):
            if n == 0:
                if user_id is not user_uuid:
                    friends.add(user_id)
                return friends
            for node in graph[user_id][1]:
                    friends | nth_friends(graph, node, n - 1, friends)
            return friends
        not_in(self.graph, user_uuid)
        return nth_friends(self.graph, user_uuid, n)


def find_shortest_path(graph, start, end, path=[]):
        path = path + [start]
        if start == end:
            return path
        if start not in graph:
            return None
        shortest = None
        for node in graph[start][1]:
            if node not in path:
                newpath = find_shortest_path(graph, node, end, path)
                if newpath:
                    if not shortest or len(newpath) < len(shortest):
                        shortest = newpath
        return shortest
  • already_in и not_in са функции работещи върху конкретна инстанция на граф. На пръв поглед не би следвало да имаш добра причина те да са функции, а не методи на SocialGraph. От друга страна начинът, по който ги ползваш напомня на декоратор. Избери едно от двете :)
  • userID е лошо име за променлива
  • list.sort метода си има аргумент reverse
  • Не е добра идея да имаш празен списък като аргумент по подразбиране на функция. Това е нещо, което не сме показвали (а трябваше). Пример:
def foo(elements=[]):
    elements.append(1)
    return elements

Изпълни тази функция няколко пъти :)

Теодор обнови решението на 10.04.2016 15:12 (преди над 1 година)

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
import uuid
import datetime
import math


class UserAlreadyExistsError(Exception):
    pass


class UserDoesNotExistError(Exception):
    pass


class UsersNotConnectedError(Exception):
    pass


class User:
    def __init__(self, name):
        self.full_name = name
        self.uuid = uuid.uuid4()
        self.posts = []

    @property
    def number_of_posts(self):
        return len(self.posts)

    def add_post(self, post_content):
        self.posts.append(Post(self.uuid, post_content))
        if self.number_of_posts > 50:
            self.posts.pop(0)

    def get_post(self):
        for post in self.posts:
            yield post


class Post:
    def __init__(self, author, content):
        self.author = author
        self.published_at = datetime.datetime.now()
        self.content = content


class SocialGraph:
    def __init__(self):
        self.graph = {}

    def already_in(self, *args):
        for user in args:
            if user in self.graph:
                raise UserAlreadyExistsError

    def not_in(self, *args):
        for user in args:
            if user not in self.graph:
                raise UserDoesNotExistError

    def add_user(self, user):
        self.already_in(user.uuid)
        self.graph[user.uuid] = (user, set())

    def get_user(self, user_uuid):
        self.not_in(user_uuid)
        return self.graph[user_uuid][0]

    def delete_user(self, user_uuid):
        self.not_in(user_uuid)
        self.graph.pop(user_uuid)

    def follow(self, follower, followee):
        self.not_in(follower, followee)
        self.graph[follower][1].add(followee)

    def unfollow(self, follower, followee):
        self.not_in(follower, followee)
        self.graph[follower][1].remove(followee)

    def is_following(self, follower, followee):
        self.not_in(follower, followee)
        return followee in self.graph[follower][1]

    def followers(self, user_uuid):
        self.not_in(user_uuid)
        result = set()
        for ID, user in self.graph.items():
            if user_uuid in user[1]:
                result.add(ID)
        return result

    def following(self, user_uuid):
        self.not_in(user_uuid)
        return self.graph[user_uuid][1]

    def friends(self, user_uuid):
        self.not_in(user_uuid)
        return {friend for friend in self.graph[user_uuid][1]
                if user_uuid in self.graph[friend][1]}

    def min_distance(self, from_user_uuid, to_user_uuid):
        self.not_in(from_user_uuid, to_user_uuid)
        path = find_shortest_path(self.graph, from_user_uuid, to_user_uuid, [])
        if not path:
            raise UsersNotConnectedError
        else:
            return len(path) - 1

    def generate_feed(self, user_uuid, offset=0, limit=10):
        self.not_in(user_uuid)
        all_posts = []
        for user_id in self.following(user_uuid):
            all_posts.extend(self.graph[user_id][0].posts)
        all_posts.sort(key=lambda x: x.published_at, reverse=True)
        return all_posts[offset:offset+limit]

    def max_distance(self, user_uuid):
        self.not_in(user_uuid)
        maximum = 0
        for node in self.graph.keys():
            path = find_shortest_path(self.graph, user_uuid, node, [])
            if path is not None and len(path) > maximum:
                maximum = len(path) - 1
        return maximum if maximum > 0 else math.inf

    def nth_layer_followings(self, user_uuid, n):
        def nth_friends(graph, user_id, n, friends=set()):
            if n == 0:
                if user_id is not user_uuid:
                    friends.add(user_id)
                return friends
            for node in graph[user_id][1]:
                    friends | nth_friends(graph, node, n - 1, friends)
            return friends
        self.not_in(user_uuid)
        return nth_friends(self.graph, user_uuid, n)


def find_shortest_path(graph, start, end, path):
        path = path + [start]
        if start == end:
            return path
        if start not in graph:
            return None
        shortest = None
        for node in graph[start][1]:
            if node not in path:
                newpath = find_shortest_path(graph, node, end, path)
                if newpath:
                    if not shortest or len(newpath) < len(shortest):
                        shortest = newpath
        return shortest

Теодор обнови решението на 11.04.2016 21:39 (преди над 1 година)

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
import uuid
import datetime
import math


class UserAlreadyExistsError(Exception):
    pass


class UserDoesNotExistError(Exception):
    pass


class UsersNotConnectedError(Exception):
    pass


class User:
    def __init__(self, name):
        self.full_name = name
        self.uuid = uuid.uuid4()
        self.posts = []

    @property
    def number_of_posts(self):
        return len(self.posts)

    def add_post(self, post_content):
        self.posts.append(Post(self.uuid, post_content))
        if self.number_of_posts > 50:
            self.posts.pop(0)

    def get_post(self):
        for post in self.posts:
            yield post


class Post:
    def __init__(self, author, content):
        self.author = author
        self.published_at = datetime.datetime.now()
        self.content = content


class SocialGraph:
    def __init__(self):
        self.graph = {}

    def already_in(self, *args):
        for user in args:
            if user in self.graph:
                raise UserAlreadyExistsError

    def not_in(self, *args):
        for user in args:
            if user not in self.graph:
                raise UserDoesNotExistError

    def add_user(self, user):
        self.already_in(user.uuid)
        self.graph[user.uuid] = (user, set())

    def get_user(self, user_uuid):
        self.not_in(user_uuid)
        return self.graph[user_uuid][0]

    def delete_user(self, user_uuid):
        self.not_in(user_uuid)
        self.graph.pop(user_uuid)

    def follow(self, follower, followee):
        self.not_in(follower, followee)
        self.graph[follower][1].add(followee)

    def unfollow(self, follower, followee):
        self.not_in(follower, followee)
        self.graph[follower][1].remove(followee)

    def is_following(self, follower, followee):
        self.not_in(follower, followee)
        return followee in self.graph[follower][1]

    def followers(self, user_uuid):
        self.not_in(user_uuid)
        result = set()
        for ID, user in self.graph.items():
            if user_uuid in user[1]:
                result.add(ID)
        return result

    def following(self, user_uuid):
        self.not_in(user_uuid)
        return self.graph[user_uuid][1]

    def friends(self, user_uuid):
        self.not_in(user_uuid)
        return {friend for friend in self.graph[user_uuid][1]
                if user_uuid in self.graph[friend][1]}

    def min_distance(self, from_user_uuid, to_user_uuid):
        self.not_in(from_user_uuid, to_user_uuid)
        path = find_shortest_path(self.graph, from_user_uuid, to_user_uuid, [])
        if not path:
            raise UsersNotConnectedError
        else:
            return len(path) - 1

    def generate_feed(self, user_uuid, offset=0, limit=10):
        self.not_in(user_uuid)
        all_posts = []
        for user_id in self.following(user_uuid):
            all_posts.extend(self.graph[user_id][0].posts)
        all_posts.sort(key=lambda x: x.published_at, reverse=True)
        return all_posts[offset:offset+limit]

    def max_distance(self, user_uuid):
        self.not_in(user_uuid)
        maximum = 0
        for node in self.graph.keys():
            path = find_shortest_path(self.graph, user_uuid, node, [])
            if path is not None and len(path) > maximum:
                maximum = len(path) - 1
        return maximum if maximum > 0 else math.inf

    def nth_layer_followings(self, user_uuid, n):
        def nth_friends(graph, user_id, n, friends=set()):
            if n == 0:
                if user_id is not user_uuid:
                    friends.add(user_id)
                return friends
            for node in graph[user_id][1]:
                if node is not user_uuid:
                    friends | nth_friends(graph, node, n - 1, friends)
            return friends
        self.not_in(user_uuid)
        return nth_friends(self.graph, user_uuid, n)


def find_shortest_path(graph, start, end, path):
        path = path + [start]
        if start == end:
            return path
        if start not in graph:
            return None
        shortest = None
        for node in graph[start][1]:
            if node not in path:
                newpath = find_shortest_path(graph, node, end, path)
                if newpath:
                    if not shortest or len(newpath) < len(shortest):
                        shortest = newpath
        return shortest

Теодор обнови решението на 11.04.2016 21:58 (преди над 1 година)

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
import uuid
import datetime
import math


class UserAlreadyExistsError(Exception):
    pass


class UserDoesNotExistError(Exception):
    pass


class UsersNotConnectedError(Exception):
    pass


class UserCanNotFollowHimself(Exception):
    pass


class User:
    def __init__(self, name):
        self.full_name = name
        self.uuid = uuid.uuid4()
        self.posts = []

    @property
    def number_of_posts(self):
        return len(self.posts)

    def add_post(self, post_content):
        self.posts.append(Post(self.uuid, post_content))
        if self.number_of_posts > 50:
            self.posts.pop(0)

    def get_post(self):
        for post in self.posts:
            yield post


class Post:
    def __init__(self, author, content):
        self.author = author
        self.published_at = datetime.datetime.now()
        self.content = content


class SocialGraph:
    def __init__(self):
        self.graph = {}

    def already_in(self, *args):
        for user in args:
            if user in self.graph:
                raise UserAlreadyExistsError

    def not_in(self, *args):
        for user in args:
            if user not in self.graph:
                raise UserDoesNotExistError

    def add_user(self, user):
        self.already_in(user.uuid)
        self.graph[user.uuid] = (user, set())

    def get_user(self, user_uuid):
        self.not_in(user_uuid)
        return self.graph[user_uuid][0]

    def delete_user(self, user_uuid):
        self.not_in(user_uuid)
        self.graph.pop(user_uuid)

    def follow(self, follower, followee):
        self.not_in(follower, followee)
        if follower is followee:
            raise UserCanNotFollowHimself
        self.graph[follower][1].add(followee)

    def unfollow(self, follower, followee):
        self.not_in(follower, followee)
        self.graph[follower][1].remove(followee)

    def is_following(self, follower, followee):
        self.not_in(follower, followee)
        return followee in self.graph[follower][1]

    def followers(self, user_uuid):
        self.not_in(user_uuid)
        result = set()
        for ID, user in self.graph.items():
            if user_uuid in user[1]:
                result.add(ID)
        return result

    def following(self, user_uuid):
        self.not_in(user_uuid)
        return self.graph[user_uuid][1]

    def friends(self, user_uuid):
        self.not_in(user_uuid)
        return {friend for friend in self.graph[user_uuid][1]
                if user_uuid in self.graph[friend][1]}

    def min_distance(self, from_user_uuid, to_user_uuid):
        self.not_in(from_user_uuid, to_user_uuid)
        path = find_shortest_path(self.graph, from_user_uuid, to_user_uuid, [])
        if not path:
            raise UsersNotConnectedError
        else:
            return len(path) - 1

    def generate_feed(self, user_uuid, offset=0, limit=10):
        self.not_in(user_uuid)
        all_posts = []
        for user_id in self.following(user_uuid):
            all_posts.extend(self.graph[user_id][0].posts)
        all_posts.sort(key=lambda x: x.published_at, reverse=True)
        return all_posts[offset:offset+limit]

    def max_distance(self, user_uuid):
        self.not_in(user_uuid)
        maximum = 0
        for node in self.graph.keys():
            path = find_shortest_path(self.graph, user_uuid, node, [])
            if path is not None and len(path) > maximum:
                maximum = len(path) - 1
        return maximum if maximum > 0 else math.inf

    def nth_layer_followings(self, user_uuid, n):
        def nth_friends(graph, user_id, n, friends=set()):
            if n == 0:
                if user_id is not user_uuid:
                    friends.add(user_id)
                return friends
            for node in graph[user_id][1]:
                if node is not user_uuid:
                    friends | nth_friends(graph, node, n - 1, friends)
            return friends
        self.not_in(user_uuid)
        return nth_friends(self.graph, user_uuid, n)


def find_shortest_path(graph, start, end, path):
        path = path + [start]
        if start == end:
            return path
        if start not in graph:
            return None
        shortest = None
        for node in graph[start][1]:
            if node not in path:
                newpath = find_shortest_path(graph, node, end, path)
                if newpath:
                    if not shortest or len(newpath) < len(shortest):
                        shortest = newpath
        return shortest

Теодор обнови решението на 12.04.2016 23:55 (преди над 1 година)

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
import uuid
import datetime
import math


class UserAlreadyExistsError(Exception):
    pass


class UserDoesNotExistError(Exception):
    pass


class UsersNotConnectedError(Exception):
    pass


class UserCanNotFollowHimself(Exception):
    pass


class User:
    def __init__(self, name):
        self.full_name = name
        self.uuid = uuid.uuid4()
        self.posts = []

    @property
    def number_of_posts(self):
        return len(self.posts)

    def add_post(self, post_content):
        self.posts.append(Post(self.uuid, post_content))
        if self.number_of_posts > 50:
            self.posts.pop(0)

    def get_post(self):
        for post in self.posts:
            yield post


class Post:
    def __init__(self, author, content):
        self.author = author
        self.published_at = datetime.datetime.now()
        self.content = content


class SocialGraph:
    def __init__(self):
        self.graph = {}

    def already_in(self, *args):
        for user in args:
            if user in self.graph:
                raise UserAlreadyExistsError

    def not_in(self, *args):
        for user in args:
            if user not in self.graph:
                raise UserDoesNotExistError

    def add_user(self, user):
        self.already_in(user.uuid)
        self.graph[user.uuid] = (user, set())

    def get_user(self, user_uuid):
        self.not_in(user_uuid)
        return self.graph[user_uuid][0]

    def delete_user(self, user_uuid):
        self.not_in(user_uuid)
        self.graph.pop(user_uuid)

    def follow(self, follower, followee):
        self.not_in(follower, followee)
        if follower is followee:
            raise UserCanNotFollowHimself
        self.graph[follower][1].add(followee)

    def unfollow(self, follower, followee):
        self.not_in(follower, followee)
        self.graph[follower][1].remove(followee)

    def is_following(self, follower, followee):
        self.not_in(follower, followee)
        return followee in self.graph[follower][1]

    def followers(self, user_uuid):
        self.not_in(user_uuid)
        result = set()
        for ID, user in self.graph.items():
            if user_uuid in user[1]:
                result.add(ID)
        return result

    def following(self, user_uuid):
        self.not_in(user_uuid)
        return self.graph[user_uuid][1]

    def friends(self, user_uuid):
        self.not_in(user_uuid)
        return {friend for friend in self.graph[user_uuid][1]
                if user_uuid in self.graph[friend][1]}

    def min_distance(self, from_user_uuid, to_user_uuid):
        self.not_in(from_user_uuid, to_user_uuid)
        path = find_shortest_path(self.graph, from_user_uuid, to_user_uuid, [])
        if not path:
            raise UsersNotConnectedError
        else:
            return len(path) - 1

    def generate_feed(self, user_uuid, offset=0, limit=10):
        self.not_in(user_uuid)
        all_posts = []
        for user_id in self.following(user_uuid):
            all_posts.extend(self.graph[user_id][0].posts)
        all_posts.sort(key=lambda x: x.published_at, reverse=True)
        return all_posts[offset:offset+limit]

    def max_distance(self, user_uuid):
        self.not_in(user_uuid)
        maximum = 0
        for node in self.graph.keys():
            path = find_shortest_path(self.graph, user_uuid, node, [])
            if path is not None and len(path) > maximum:
                maximum = len(path) - 1
        return maximum if maximum > 0 else math.inf

    def nth_layer_followings(self, user_uuid, n):
        def nth_friends(graph, user_id, n, friends, visited):
            visited.add(user_id)
            if n == 0:
                if user_id is not user_uuid:
                    friends.add(user_id)
                return friends
            for node in graph[user_id][1]:
                if node not in visited:
                    friends | nth_friends(graph, node, n - 1, friends, visited)
            visited.remove(user_id)
            return friends
        self.not_in(user_uuid)
        return nth_friends(self.graph, user_uuid, n, set(), set())


def find_shortest_path(graph, start, end, path):
        path = path + [start]
        if start == end:
            return path
        if start not in graph:
            return None
        shortest = None
        for node in graph[start][1]:
            if node not in path:
                newpath = find_shortest_path(graph, node, end, path)
                if newpath:
                    if not shortest or len(newpath) < len(shortest):
                        shortest = newpath
        return shortest

Теодор обнови решението на 18.04.2016 11:16 (преди над 1 година)

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
import uuid
import datetime
import math


class UserAlreadyExistsError(Exception):
    pass


class UserDoesNotExistError(Exception):
    pass


class UsersNotConnectedError(Exception):
    pass


class UserCanNotFollowHimself(Exception):
    pass


class User:
    def __init__(self, name):
        self.full_name = name
        self.uuid = uuid.uuid4()
        self.posts = []

    @property
    def number_of_posts(self):
        return len(self.posts)

    def add_post(self, post_content):
        self.posts.append(Post(self.uuid, post_content))
        if self.number_of_posts > 50:
            self.posts.pop(0)

    def get_post(self):
        for post in self.posts:
            yield post


class Post:
    def __init__(self, author, content):
        self.author = author
        self.published_at = datetime.datetime.now()
        self.content = content


class SocialGraph:
    def __init__(self):
        self.graph = {}

    def already_in(self, *args):
        for user in args:
            if user in self.graph:
                raise UserAlreadyExistsError

    def not_in(self, *args):
        for user in args:
            if user not in self.graph:
                raise UserDoesNotExistError

    def add_user(self, user):
        self.already_in(user.uuid)
        self.graph[user.uuid] = (user, set())

    def get_user(self, user_uuid):
        self.not_in(user_uuid)
        return self.graph[user_uuid][0]

    def delete_user(self, user_uuid):
        self.not_in(user_uuid)
        self.graph.pop(user_uuid)
        for followees in self.graph.values():
            if user_uuid in followees[1]:
                followees[1].remove(user_uuid)

    def follow(self, follower, followee):
        self.not_in(follower, followee)
        if follower is followee:
            raise UserCanNotFollowHimself
        self.graph[follower][1].add(followee)

    def unfollow(self, follower, followee):
        self.not_in(follower, followee)
        self.graph[follower][1].remove(followee)

    def is_following(self, follower, followee):
        self.not_in(follower, followee)
        return followee in self.graph[follower][1]

    def followers(self, user_uuid):
        self.not_in(user_uuid)
        result = set()
        for ID, user in self.graph.items():
            if user_uuid in user[1]:
                result.add(ID)
        return result

    def following(self, user_uuid):
        self.not_in(user_uuid)
        return self.graph[user_uuid][1]

    def friends(self, user_uuid):
        self.not_in(user_uuid)
        return {friend for friend in self.graph[user_uuid][1]
                if user_uuid in self.graph[friend][1]}

    def min_distance(self, from_user_uuid, to_user_uuid):
        self.not_in(from_user_uuid, to_user_uuid)
        path = find_shortest_path(self.graph, from_user_uuid, to_user_uuid, [])
        if not path:
            raise UsersNotConnectedError
        else:
            return len(path) - 1

    def generate_feed(self, user_uuid, offset=0, limit=10):
        self.not_in(user_uuid)
        all_posts = []
        for user_id in self.following(user_uuid):
            all_posts.extend(self.graph[user_id][0].posts)
        all_posts.sort(key=lambda x: x.published_at, reverse=True)
        return all_posts[offset:offset+limit]

    def max_distance(self, user_uuid):
        self.not_in(user_uuid)
        maximum = 0
        for node in self.graph.keys():
            path = find_shortest_path(self.graph, user_uuid, node, [])
            if path is not None and len(path) > maximum:
                maximum = len(path) - 1
        return maximum if maximum > 0 else math.inf

    def nth_layer_followings(self, user_uuid, n):
        def nth_friends(graph, user_id, n, friends, visited):
            visited.add(user_id)
            if n == 0:
                if user_id is not user_uuid:
                    friends.add(user_id)
                return friends
            for node in graph[user_id][1]:
                if node not in visited:
                    friends | nth_friends(graph, node, n - 1, friends, visited)
            visited.remove(user_id)
            return friends
        self.not_in(user_uuid)
        return nth_friends(self.graph, user_uuid, n, set(), set())


def find_shortest_path(graph, start, end, path):
        path = path + [start]
        if start == end:
            return path
        if start not in graph:
            return None
        shortest = None
        for node in graph[start][1]:
            if node not in path:
                newpath = find_shortest_path(graph, node, end, path)
                if newpath:
                    if not shortest or len(newpath) < len(shortest):
                        shortest = newpath
        return shortest