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
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
import uuid
import datetime
import math
from itertools import islice
from numbers import Number
from collections import deque, defaultdict


class User:
    def __init__(self, full_name):
        self.__full_name = full_name
        self.__uuid = uuid.uuid4()
        self.__posts = deque(maxlen=50)

    @property
    def full_name(self):
        return self.__full_name

    @property
    def uuid(self):
        return self.__uuid

    def add_post(self, post_content):
        self.__posts.append(Post(self.__uuid, post_content))

    def get_post(self):
        return (post for post in self.__posts)

    def __str__(self):
        return "{}, [{}]".format(self.__full_name, self.__uuid)

    def __repr__(self):
        return str(self)


class Post:
    def __init__(self, author, content):
        self.__author = author
        self.__published_at = datetime.datetime.now()
        self.__content = content

    def __str__(self):
        return """Author: {}
                  Published at: {}
                  Content: {}""".format(self.__author,
                                        self.__published_at,
                                        self.__content)

    def __repr__(self):
        return str(self)

    @property
    def author(self):
        return self.__author

    @property
    def published_at(self):
        return self.__published_at

    @property
    def content(self):
        return self.__content


def check_if_users_exist(func):
    def checked_arguments(self, *args):
        for arg in args:
            if not isinstance(arg, Number) and arg not in self.users.keys():
                raise UserDoesNotExistError(arg)
        return func(self, *args)
    return checked_arguments


class SocialGraph:
    def __init__(self):
        self.__users = {}
        self.__graph = defaultdict(set)

    @property
    def users(self):
        return self.__users

    def add_user(self, user):
        if user.uuid in self.__users:
            raise UserAlreadyExistsError(user)
        self.__users[user.uuid] = user
        self.__graph[user.uuid]

    @check_if_users_exist
    def get_user(self, user_uuid):
        return self.__users[user_uuid]

    @check_if_users_exist
    def delete_user(self, user_uuid):
        del self.__users[user_uuid]
        del self.__graph[user_uuid]

    @check_if_users_exist
    def follow(self, follower, followee):
        if follower == followee:
            raise ValueError("User cannot follow himself!")
        self.__graph[follower].add(followee)

    @check_if_users_exist
    def unfollow(self, follower, followee):
        if follower == followee:
            raise ValueError("User cannot unfollow himself!")
        if self.is_following(follower, followee):
            self.__graph[follower].remove(followee)

    @check_if_users_exist
    def is_following(self, follower, followee):
        if follower == followee:
            raise ValueError("User cannot be following himself!")
        return followee in self.__graph[follower]

    @check_if_users_exist
    def followers(self, user_uuid):
        return set(follower for follower in self.__graph.keys()
                   if follower != user_uuid and
                   self.is_following(follower, user_uuid))

    @check_if_users_exist
    def following(self, user_uuid):
        return self.__graph[user_uuid]

    @check_if_users_exist
    def friends(self, user_uuid):
        return set(
            friend for friend in self.__graph[user_uuid]
            if self.is_following(friend, user_uuid))

    @check_if_users_exist
    def max_distance(self, user_uuid):
        max_distance_found = max(self.find_min_distances(user_uuid).values())
        return max_distance_found if max_distance_found != 0 else math.inf

    def find_min_distances(self, user_uuid):
        queue = []
        queue.append(user_uuid)
        # the dictionary maps destinations(other users)
        # with distances from user_uuid
        distances = defaultdict(int)
        visited = set()
        depth_counter = -1
        children_counter = 1

        while queue:
            depth_counter += 1
            new_children_counter = 0

            for _ in range(children_counter):
                current_elem = queue.pop(0)
                for child in self.__graph[current_elem]:
                    if child not in visited:
                        new_children_counter += 1
                        queue.append(child)

                if(distances[current_elem] == 0 or
                        distances[current_elem] > depth_counter):
                    distances[current_elem] = depth_counter
                visited.add(current_elem)
            children_counter = new_children_counter
        return distances

    @check_if_users_exist
    def min_distance(self, from_user_uuid, to_user_uuid):
        if from_user_uuid == to_user_uuid:
            return 0

        distances_found = self.find_min_distances(from_user_uuid)
        if to_user_uuid not in distances_found.keys():
            raise UsersNotConnectedError(from_user_uuid, to_user_uuid)

        return distances_found[to_user_uuid]

    @check_if_users_exist
    def nth_layer_followings(self, user_uuid, n):
        if n == 0:
            return set()
        elif n < 0:
            raise ValueError("Layer number must be at least 0!" +
                             "Yours was {}.".format(n))

        max_distances_found = self.find_min_distances(user_uuid)
        nth_layer = set([destination
                        for destination, distance in
                        max_distances_found.items() if distance == n])
        return nth_layer

    @check_if_users_exist
    def generate_feed(self, user_uuid, offset=0, limit=10):
        if offset < 0:
            raise ValueError("Offset index must be a positive number!" +
                             " Yours was {}".format(offset))
        elif limit < 0:
            raise ValueError("Limit index must be a positive number!" +
                             " Yours was {}".format(limit))

        all_posts = []
        for followee in self.__graph[user_uuid]:
            all_posts.extend(self.__users[followee].get_post())

        sorted_by_date = sorted(all_posts,
                                key=lambda post: post.published_at,
                                reverse=True)
        return islice(sorted_by_date, offset, offset + limit)


class UserDoesNotExistError(Exception):
    def __init__(self, uuid):
        self.message = "User with uuid [{}] does not exist!".format(uuid)

    def __str__(self):
        return self.message


class UserAlreadyExistsError(Exception):
    def __init__(self, user):
        self.message = "User {} alredy exists!".format(user)

    def __str__(self):
        return self.message


class UsersNotConnectedError(Exception):
    def __init__(self, from_user_uuid, to_user_uuid):
        self.message = """There is no possible path
        between user [{}] and user [{}]""".format(from_user_uuid, to_user_uuid)

    def __str__(self):
        return self.message

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

........
----------------------------------------------------------------------
Ran 8 tests in 0.066s

OK

История (5 версии и 1 коментар)

Георги обнови решението на 11.04.2016 14: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
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
import uuid
import datetime
import math
from itertools import islice
from collections import deque, defaultdict


class User:
    def __init__(self, full_name):
        self.__full_name = full_name
        self.__uuid = uuid.uuid4()
        self.__posts = deque(maxlen=50)

    @property
    def full_name(self):
        return self.__full_name

    @property
    def uuid(self):
        return self.__uuid

    def add_post(self, post_content):
        self.__posts.append(Post(self.__uuid, post_content))

    def get_post(self):
        return (post for post in self.__posts)

    def __hash__(self):
        return hash(self.__uuid)

    def __eq__(self, other):
        return (self.__full_name, self.__uuid) == (other.full_name, other.uuid)

    def __str__(self):
        return "{}, [{}]".format(self.__full_name, self.__uuid)

    def __repr__(self):
        return str(self)


class Post:
    def __init__(self, author, content):
        self.__author = author
        self.__published_at = datetime.datetime.now()
        self.__content = content

    def __str__(self):
        return """Author: {}
                  Published at: {}
                  Content: {}""".format(self.__author,
                                        self.__published_at,
                                        self.__content)

    def __repr__(self):
        return str(self)

    @property
    def author(self):
        return self.__author

    @property
    def published_at(self):
        return self.__published_at

    @property
    def content(self):
        return self.__content


class SocialGraph:
    def __init__(self):
        self.__users = {}
        self.__users_relations = defaultdict(list)

    def add_user(self, user):
        if user.uuid in self.__users:
            raise UserAlreadyExistsError(user)
        self.__users[user.uuid] = user
        self.__users_relations[user.uuid]

    def get_user(self, user_uuid):
        if user_uuid not in self.__users.keys():
            raise UserDoesNotExistError(user_uuid)
        return self.__users[user_uuid]

    def delete_user(self, user_uuid):
        if user_uuid not in self.__users.keys():
            raise UserDoesNotExistError(user_uuid)
        else:
            del self.__users[user_uuid]
            del self.__users_relations[user_uuid]

    def follow(self, follower, followee):
        if follower not in self.__users.keys():
            raise UserDoesNotExistError(follower)
        elif followee not in self.__users.keys():
            raise UserDoesNotExistError(followee)
        elif not self.is_following(follower, followee):
            self.__users_relations[follower].append(followee)

    def unfollow(self, follower, followee):
        if follower not in self.__users.keys():
            raise UserDoesNotExistError(follower)
        elif followee not in self.__users.keys():
            raise UserDoesNotExistError(followee)
        elif self.is_following(follower, followee):
            self.__users_relations[follower].remove(followee)

    def is_following(self, follower, followee):
        if follower not in self.__users.keys():
            raise UserDoesNotExistError(follower)
        elif followee not in self.__users.keys():
            raise UserDoesNotExistError(followee)

        return followee in self.__users_relations[follower]

    def followers(self, user_uuid):
        if user_uuid not in self.__users.keys():
            raise UserDoesNotExistError(user_uuid)

        return set(follower for follower in self.__users_relations.keys()
                   if self.is_following(follower, user_uuid))

    def following(self, user_uuid):
        if user_uuid not in self.__users.keys():
            raise UserDoesNotExistError(user_uuid)

        return set(self.__users_relations[user_uuid])

    def friends(self, user_uuid):
        if user_uuid not in self.__users.keys():
            raise UserDoesNotExistError(user_uuid)

        return set(
            friend for friend in self.__users_relations[user_uuid]
            if self.is_following(friend, user_uuid))

    def max_distance(self, user_uuid):
        if user_uuid not in self.__users.keys():
            raise UserDoesNotExistError(user_uuid)

        all_paths = self.find_all_paths(user_uuid)
        max_dist = max(map(len, all_paths)) - 1
        return max_dist if max_dist > 0 else math.inf

    def find_all_paths(self, user_uuid, visited=()):
        visited = visited + (user_uuid,)
        followees = self.__users_relations[user_uuid]
        if len(followees) == 0 or all(user in visited for user in followees):
            return [visited]

        find_all_paths = set()
        for followee in self.__users_relations[user_uuid]:
            if followee not in visited:
                followee_paths = self.find_all_paths(followee, visited)
                for path in followee_paths:
                    find_all_paths.add(path)
        return find_all_paths

    def min_distance(self, from_user_uuid, to_user_uuid):
        if from_user_uuid not in self.__users.keys():
            raise UserDoesNotExistError(from_user_uuid)
        elif to_user_uuid not in self.__users.keys():
            raise UserDoesNotExistError(to_user_uuid)

        all_paths = self.find_all_paths(from_user_uuid)
        try:
            min_distance = min(
                [path.index(to_user_uuid) for path in all_paths
                 if to_user_uuid in path])
        except ValueError:
            ''' if the list comprehension returns an empty list there is no connection;
                min([]) throws ValueError'''
            raise UsersNotConnectedError(from_user_uuid, to_user_uuid)

        return min_distance

    def nth_layer_followings(self, user_uuid, n):
        if user_uuid not in self.__users.keys():
            raise UserDoesNotExistError(user_uuid)
        elif n <= 0:
            raise ValueError("""Layer number must be at least 1!
                                Yours was {}.""".format(n))

        all_paths = self.find_all_paths(user_uuid)
        nth_layer = set(
            [path[n] for path in all_paths if len(path) > n])
        return nth_layer

    def generate_feed(self, user_uuid, offset=0, limit=10):
        if user_uuid not in self.__users.keys():
            raise UserDoesNotExistError(user_uuid)
        elif offset < 0:
            raise ValueError("Offset index must be a positive number!" +
                             " Yours was {}".format(offset))
        elif limit < 0:
            raise ValueError("Limit index must be a positive number!" +
                             " Yours was {}".format(limit))

        all_posts = []
        for followee in self.__users_relations[user_uuid]:
            all_posts.extend(self.__users[followee].get_post())

        sorted_by_date = sorted(all_posts,
                                key=lambda post: post.published_at,
                                reverse=True)

        return islice(
            sorted_by_date,
            offset,
            offset + limit
            if offset + limit <= len(all_posts) else len(all_posts))


class UserDoesNotExistError(Exception):
    def __init__(self, uuid):
        self.message = "User with uuid [{}] does not exist!".format(uuid)

    def __str__(self):
        return self.message


class UserAlreadyExistsError(Exception):
    def __init__(self, user):
        self.message = "User {} alredy exists!".format(user)

    def __str__(self):
        return self.message


class UsersNotConnectedError(Exception):
    def __init__(self, from_user_uuid, to_user_uuid):
        self.message = """There is no possible path
        between user [{}] and user [{}]""".format(from_user_uuid, to_user_uuid)

    def __str__(self):
        return self.message

Георги обнови решението на 16.04.2016 18:49 (преди над 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
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
import uuid
import datetime
import math
from itertools import islice
from collections import deque, defaultdict


class User:
    def __init__(self, full_name):
        self.__full_name = full_name
        self.__uuid = uuid.uuid4()
        self.__posts = deque(maxlen=50)

    @property
    def full_name(self):
        return self.__full_name

    @property
    def uuid(self):
        return self.__uuid

    def add_post(self, post_content):
        self.__posts.append(Post(self.__uuid, post_content))

    def get_post(self):
        return (post for post in self.__posts)

    def __hash__(self):
        return hash(self.__uuid)

    def __eq__(self, other):
        return (self.__full_name, self.__uuid) == (other.full_name, other.uuid)

    def __str__(self):
        return "{}, [{}]".format(self.__full_name, self.__uuid)

    def __repr__(self):
        return str(self)


class Post:
    def __init__(self, author, content):
        self.__author = author
        self.__published_at = datetime.datetime.now()
        self.__content = content

    def __str__(self):
        return """Author: {}
                  Published at: {}
                  Content: {}""".format(self.__author,
                                        self.__published_at,
                                        self.__content)

    def __repr__(self):
        return str(self)

    @property
    def author(self):
        return self.__author

    @property
    def published_at(self):
        return self.__published_at

    @property
    def content(self):
        return self.__content


class SocialGraph:
    def __init__(self):
        self.__users = {}
        self.__graph = defaultdict(list)

    def add_user(self, user):
        if user.uuid in self.__users:
            raise UserAlreadyExistsError(user)
        self.__users[user.uuid] = user
        self.__graph[user.uuid]

    def get_user(self, user_uuid):
        if user_uuid not in self.__users.keys():
            raise UserDoesNotExistError(user_uuid)
        return self.__users[user_uuid]

    def delete_user(self, user_uuid):
        if user_uuid not in self.__users.keys():
            raise UserDoesNotExistError(user_uuid)
        else:
            del self.__users[user_uuid]
            del self.__graph[user_uuid]

    def follow(self, follower, followee):
        if follower not in self.__users.keys():
            raise UserDoesNotExistError(follower)
        elif followee not in self.__users.keys():
            raise UserDoesNotExistError(followee)
        elif follower == followee:
            raise ValueError("User cannot follow himself!")
        elif not self.is_following(follower, followee):
            self.__graph[follower].append(followee)

    def unfollow(self, follower, followee):
        if follower not in self.__users.keys():
            raise UserDoesNotExistError(follower)
        elif followee not in self.__users.keys():
            raise UserDoesNotExistError(followee)
        elif follower == followee:
            raise ValueError("User cannot unfollow himself!")
        elif self.is_following(follower, followee):
            self.__graph[follower].remove(followee)

    def is_following(self, follower, followee):
        if follower not in self.__users.keys():
            raise UserDoesNotExistError(follower)
        elif followee not in self.__users.keys():
            raise UserDoesNotExistError(followee)

        return followee in self.__graph[follower]

    def followers(self, user_uuid):
        if user_uuid not in self.__users.keys():
            raise UserDoesNotExistError(user_uuid)

        return set(follower for follower in self.__graph.keys()
                   if self.is_following(follower, user_uuid))

    def following(self, user_uuid):
        if user_uuid not in self.__users.keys():
            raise UserDoesNotExistError(user_uuid)

        return set(self.__graph[user_uuid])

    def friends(self, user_uuid):
        if user_uuid not in self.__users.keys():
            raise UserDoesNotExistError(user_uuid)

        return set(
            friend for friend in self.__graph[user_uuid]
            if self.is_following(friend, user_uuid))

    def max_distance(self, user_uuid):
        if user_uuid not in self.__users.keys():
            raise UserDoesNotExistError(user_uuid)

        all_paths_by_len = sorted(
            self.find_all_paths(user_uuid), key=len, reverse=True)

        dict_ = {}
        for path in all_paths_by_len:
            dict_[path[-1]] = len(path) - 1
        max_distance = max(dict_.values())
        return max_distance if max_distance != 0 else math.inf

    def find_all_paths(self, user_uuid, visited=()):
        visited = visited + (user_uuid,)
        followees = self.__graph[user_uuid]
        if len(followees) == 0 or all(user in visited for user in followees):
            return [visited]

        find_all_paths = set()
        for followee in self.__graph[user_uuid]:
            if followee not in visited:
                followee_paths = self.find_all_paths(followee, visited)
                for path in followee_paths:
                    find_all_paths.add(path)
        return find_all_paths

    def min_distance(self, from_user_uuid, to_user_uuid):
        if from_user_uuid not in self.__users.keys():
            raise UserDoesNotExistError(from_user_uuid)
        elif to_user_uuid not in self.__users.keys():
            raise UserDoesNotExistError(to_user_uuid)
        elif from_user_uuid == to_user_uuid:
            return 0

        all_paths = self.find_all_paths(from_user_uuid)
        to_user_positions = [path.index(to_user_uuid) for path in all_paths
                             if to_user_uuid in path]
        if to_user_positions == []:
            raise UsersNotConnectedError(from_user_uuid, to_user_uuid)

        return min(to_user_positions)

    def nth_layer_followings(self, user_uuid, n):
        if user_uuid not in self.__users.keys():
            raise UserDoesNotExistError(user_uuid)
        elif n == 0:
            return set()
        elif n < 0:
            raise ValueError("Layer number must be at least 0!" +
                             "Yours was {}.".format(n))

        all_paths = self.find_all_paths(user_uuid)
        nth_layer = set(
            [path[n] for path in all_paths if len(path) > n])
        return nth_layer

    def generate_feed(self, user_uuid, offset=0, limit=10):
        if user_uuid not in self.__users.keys():
            raise UserDoesNotExistError(user_uuid)
        elif offset < 0:
            raise ValueError("Offset index must be a positive number!" +
                             " Yours was {}".format(offset))
        elif limit < 0:
            raise ValueError("Limit index must be a positive number!" +
                             " Yours was {}".format(limit))

        all_posts = []
        for followee in self.__graph[user_uuid]:
            all_posts.extend(self.__users[followee].get_post())

        sorted_by_date = sorted(all_posts,
                                key=lambda post: post.published_at,
                                reverse=True)
        return islice(
            sorted_by_date,
            offset,
            offset + limit
            if offset + limit <= len(all_posts) else len(all_posts))


class UserDoesNotExistError(Exception):
    def __init__(self, uuid):
        self.message = "User with uuid [{}] does not exist!".format(uuid)

    def __str__(self):
        return self.message


class UserAlreadyExistsError(Exception):
    def __init__(self, user):
        self.message = "User {} alredy exists!".format(user)

    def __str__(self):
        return self.message


class UsersNotConnectedError(Exception):
    def __init__(self, from_user_uuid, to_user_uuid):
        self.message = """There is no possible path
        between user [{}] and user [{}]""".format(from_user_uuid, to_user_uuid)

    def __str__(self):
        return self.message

Георги обнови решението на 18.04.2016 16:03 (преди над 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
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
import uuid
import datetime
import math
from itertools import islice
from numbers import Number
from collections import deque, defaultdict


class User:
    def __init__(self, full_name):
        self.__full_name = full_name
        self.__uuid = uuid.uuid4()
        self.__posts = deque(maxlen=50)

    @property
    def full_name(self):
        return self.__full_name

    @property
    def uuid(self):
        return self.__uuid

    def add_post(self, post_content):
        self.__posts.append(Post(self.__uuid, post_content))

    def get_post(self):
        return (post for post in self.__posts)

    def __hash__(self):
        return hash(self.__uuid)

    def __eq__(self, other):
        return (self.__full_name, self.__uuid) == (other.full_name, other.uuid)

    def __str__(self):
        return "{}, [{}]".format(self.__full_name, self.__uuid)

    def __repr__(self):
        return str(self)


class Post:
    def __init__(self, author, content):
        self.__author = author
        self.__published_at = datetime.datetime.now()
        self.__content = content

    def __str__(self):
        return """Author: {}
                  Published at: {}
                  Content: {}""".format(self.__author,
                                        self.__published_at,
                                        self.__content)

    def __repr__(self):
        return str(self)

    @property
    def author(self):
        return self.__author

    @property
    def published_at(self):
        return self.__published_at

    @property
    def content(self):
        return self.__content


def check_if_users_exist(func):
    def checked_arguments(self, *args):
        for arg in args:
            if not isinstance(arg, Number) and arg not in self.users.keys():
                raise UserDoesNotExistError(arg)
        return func(self, *args)
    return checked_arguments


class SocialGraph:
    def __init__(self):
        self.__users = {}
        self.__graph = defaultdict(set)

    @property
    def users(self):
        return self.__users

    def add_user(self, user):
        if user.uuid in self.__users:
            raise UserAlreadyExistsError(user)
        self.__users[user.uuid] = user
        self.__graph[user.uuid]

    @check_if_users_exist
    def get_user(self, user_uuid):
        return self.__users[user_uuid]

    @check_if_users_exist
    def delete_user(self, user_uuid):
        del self.__users[user_uuid]
        del self.__graph[user_uuid]

    @check_if_users_exist
    def follow(self, follower, followee):
        if follower == followee:
            raise ValueError("User cannot follow himself!")
        self.__graph[follower].add(followee)

    @check_if_users_exist
    def unfollow(self, follower, followee):
        if follower == followee:
            raise ValueError("User cannot unfollow himself!")
        self.__graph[follower].remove(followee)

    @check_if_users_exist
    def is_following(self, follower, followee):
        return followee in self.__graph[follower]

    @check_if_users_exist
    def followers(self, user_uuid):
        return set(follower for follower in self.__graph.keys()
                   if self.is_following(follower, user_uuid))

    @check_if_users_exist
    def following(self, user_uuid):
        return self.__graph[user_uuid]

    @check_if_users_exist
    def friends(self, user_uuid):
        return set(
            friend for friend in self.__graph[user_uuid]
            if self.is_following(friend, user_uuid))

    @check_if_users_exist
    def max_distance(self, user_uuid):
        max_distance_found = max(self.bfs(user_uuid).values())
        return max_distance_found if max_distance_found != 0 else math.inf

    def bfs(self, user_uuid):
        queue = []
        queue.append(user_uuid)
        # the dictionary maps destinations(other users)
        # with distances from user_uuid
        distances = defaultdict(int)
        visited = set()
        depth_counter = -1
        children_counter = 1

        while queue:
            depth_counter += 1
            new_children_counter = 0

            for _ in range(children_counter):
                current_elem = queue.pop(0)
                for child in self.__graph[current_elem]:
                    if child not in visited:
                        new_children_counter += 1
                        queue.append(child)

                if(distances[current_elem] == 0 or
                        distances[current_elem] > depth_counter):
                    distances[current_elem] = depth_counter
                visited.add(current_elem)
            children_counter = new_children_counter
        return distances

    @check_if_users_exist
    def min_distance(self, from_user_uuid, to_user_uuid):
        if from_user_uuid == to_user_uuid:
            return 0
        distances_found = self.bfs(from_user_uuid)
        if to_user_uuid not in distances_found.keys():
            raise UsersNotConnectedError(from_user_uuid, to_user_uuid)

        return distances_found[to_user_uuid]

    @check_if_users_exist
    def nth_layer_followings(self, user_uuid, n):
        if n == 0:
            return set()
        elif n < 0:
            raise ValueError("Layer number must be at least 0!" +
                             "Yours was {}.".format(n))

        max_distances_found = self.bfs(user_uuid)
        nth_layer = set([destination
                        for destination, distance in
                        max_distances_found.items() if distance == n])
        return nth_layer

    @check_if_users_exist
    def generate_feed(self, user_uuid, offset=0, limit=10):
        if offset < 0:
            raise ValueError("Offset index must be a positive number!" +
                             " Yours was {}".format(offset))
        elif limit < 0:
            raise ValueError("Limit index must be a positive number!" +
                             " Yours was {}".format(limit))

        all_posts = []
        for followee in self.__graph[user_uuid]:
            all_posts.extend(self.__users[followee].get_post())

        sorted_by_date = sorted(all_posts,
                                key=lambda post: post.published_at,
                                reverse=True)
        return islice(
            sorted_by_date,
            offset,
            offset + limit
            if offset + limit <= len(all_posts) else len(all_posts))


class UserDoesNotExistError(Exception):
    def __init__(self, uuid):
        self.message = "User with uuid [{}] does not exist!".format(uuid)

    def __str__(self):
        return self.message


class UserAlreadyExistsError(Exception):
    def __init__(self, user):
        self.message = "User {} alredy exists!".format(user)

    def __str__(self):
        return self.message


class UsersNotConnectedError(Exception):
    def __init__(self, from_user_uuid, to_user_uuid):
        self.message = """There is no possible path
        between user [{}] and user [{}]""".format(from_user_uuid, to_user_uuid)

    def __str__(self):
        return self.message

Георги обнови решението на 18.04.2016 16:08 (преди над 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
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
import uuid
import datetime
import math
from itertools import islice
from numbers import Number
from collections import deque, defaultdict


class User:
    def __init__(self, full_name):
        self.__full_name = full_name
        self.__uuid = uuid.uuid4()
        self.__posts = deque(maxlen=50)

    @property
    def full_name(self):
        return self.__full_name

    @property
    def uuid(self):
        return self.__uuid

    def add_post(self, post_content):
        self.__posts.append(Post(self.__uuid, post_content))

    def get_post(self):
        return (post for post in self.__posts)

    def __hash__(self):
        return hash(self.__uuid)

    def __eq__(self, other):
        return (self.__full_name, self.__uuid) == (other.full_name, other.uuid)

    def __str__(self):
        return "{}, [{}]".format(self.__full_name, self.__uuid)

    def __repr__(self):
        return str(self)


class Post:
    def __init__(self, author, content):
        self.__author = author
        self.__published_at = datetime.datetime.now()
        self.__content = content

    def __str__(self):
        return """Author: {}
                  Published at: {}
                  Content: {}""".format(self.__author,
                                        self.__published_at,
                                        self.__content)

    def __repr__(self):
        return str(self)

    @property
    def author(self):
        return self.__author

    @property
    def published_at(self):
        return self.__published_at

    @property
    def content(self):
        return self.__content


def check_if_users_exist(func):
    def checked_arguments(self, *args):
        for arg in args:
            if not isinstance(arg, Number) and arg not in self.users.keys():
                raise UserDoesNotExistError(arg)
        return func(self, *args)
    return checked_arguments


class SocialGraph:
    def __init__(self):
        self.__users = {}
        self.__graph = defaultdict(set)

    @property
    def users(self):
        return self.__users

    def add_user(self, user):
        if user.uuid in self.__users:
            raise UserAlreadyExistsError(user)
        self.__users[user.uuid] = user
        self.__graph[user.uuid]

    @check_if_users_exist
    def get_user(self, user_uuid):
        return self.__users[user_uuid]

    @check_if_users_exist
    def delete_user(self, user_uuid):
        del self.__users[user_uuid]
        del self.__graph[user_uuid]

    @check_if_users_exist
    def follow(self, follower, followee):
        if follower == followee:
            raise ValueError("User cannot follow himself!")
        self.__graph[follower].add(followee)

    @check_if_users_exist
    def unfollow(self, follower, followee):
        if follower == followee:
            raise ValueError("User cannot unfollow himself!")
        self.__graph[follower].remove(followee)

    @check_if_users_exist
    def is_following(self, follower, followee):
        return followee in self.__graph[follower]

    @check_if_users_exist
    def followers(self, user_uuid):
        return set(follower for follower in self.__graph.keys()
                   if self.is_following(follower, user_uuid))

    @check_if_users_exist
    def following(self, user_uuid):
        return self.__graph[user_uuid]

    @check_if_users_exist
    def friends(self, user_uuid):
        return set(
            friend for friend in self.__graph[user_uuid]
            if self.is_following(friend, user_uuid))

    @check_if_users_exist
    def max_distance(self, user_uuid):
        max_distance_found = max(self.find_min_distances(user_uuid).values())
        return max_distance_found if max_distance_found != 0 else math.inf

    def find_min_distances(self, user_uuid):
        queue = []
        queue.append(user_uuid)
        # the dictionary maps destinations(other users)
        # with distances from user_uuid
        distances = defaultdict(int)
        visited = set()
        depth_counter = -1
        children_counter = 1

        while queue:
            depth_counter += 1
            new_children_counter = 0

            for _ in range(children_counter):
                current_elem = queue.pop(0)
                for child in self.__graph[current_elem]:
                    if child not in visited:
                        new_children_counter += 1
                        queue.append(child)

                if(distances[current_elem] == 0 or
                        distances[current_elem] > depth_counter):
                    distances[current_elem] = depth_counter
                visited.add(current_elem)
            children_counter = new_children_counter
        return distances

    @check_if_users_exist
    def min_distance(self, from_user_uuid, to_user_uuid):
        if from_user_uuid == to_user_uuid:
            return 0
        distances_found = self.find_min_distances(from_user_uuid)
        if to_user_uuid not in distances_found.keys():
            raise UsersNotConnectedError(from_user_uuid, to_user_uuid)

        return distances_found[to_user_uuid]

    @check_if_users_exist
    def nth_layer_followings(self, user_uuid, n):
        if n == 0:
            return set()
        elif n < 0:
            raise ValueError("Layer number must be at least 0!" +
                             "Yours was {}.".format(n))

        max_distances_found = self.find_min_distances(user_uuid)
        nth_layer = set([destination
                        for destination, distance in
                        max_distances_found.items() if distance == n])
        return nth_layer

    @check_if_users_exist
    def generate_feed(self, user_uuid, offset=0, limit=10):
        if offset < 0:
            raise ValueError("Offset index must be a positive number!" +
                             " Yours was {}".format(offset))
        elif limit < 0:
            raise ValueError("Limit index must be a positive number!" +
                             " Yours was {}".format(limit))

        all_posts = []
        for followee in self.__graph[user_uuid]:
            all_posts.extend(self.__users[followee].get_post())

        sorted_by_date = sorted(all_posts,
                                key=lambda post: post.published_at,
                                reverse=True)
        return islice(
            sorted_by_date,
            offset,
            offset + limit
            if offset + limit <= len(all_posts) else len(all_posts))


class UserDoesNotExistError(Exception):
    def __init__(self, uuid):
        self.message = "User with uuid [{}] does not exist!".format(uuid)

    def __str__(self):
        return self.message


class UserAlreadyExistsError(Exception):
    def __init__(self, user):
        self.message = "User {} alredy exists!".format(user)

    def __str__(self):
        return self.message


class UsersNotConnectedError(Exception):
    def __init__(self, from_user_uuid, to_user_uuid):
        self.message = """There is no possible path
        between user [{}] and user [{}]""".format(from_user_uuid, to_user_uuid)

    def __str__(self):
        return self.message

Георги обнови решението на 18.04.2016 16:54 (преди над 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
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
import uuid
import datetime
import math
from itertools import islice
from numbers import Number
from collections import deque, defaultdict


class User:
    def __init__(self, full_name):
        self.__full_name = full_name
        self.__uuid = uuid.uuid4()
        self.__posts = deque(maxlen=50)

    @property
    def full_name(self):
        return self.__full_name

    @property
    def uuid(self):
        return self.__uuid

    def add_post(self, post_content):
        self.__posts.append(Post(self.__uuid, post_content))

    def get_post(self):
        return (post for post in self.__posts)

    def __str__(self):
        return "{}, [{}]".format(self.__full_name, self.__uuid)

    def __repr__(self):
        return str(self)


class Post:
    def __init__(self, author, content):
        self.__author = author
        self.__published_at = datetime.datetime.now()
        self.__content = content

    def __str__(self):
        return """Author: {}
                  Published at: {}
                  Content: {}""".format(self.__author,
                                        self.__published_at,
                                        self.__content)

    def __repr__(self):
        return str(self)

    @property
    def author(self):
        return self.__author

    @property
    def published_at(self):
        return self.__published_at

    @property
    def content(self):
        return self.__content


def check_if_users_exist(func):
    def checked_arguments(self, *args):
        for arg in args:
            if not isinstance(arg, Number) and arg not in self.users.keys():
                raise UserDoesNotExistError(arg)
        return func(self, *args)
    return checked_arguments


class SocialGraph:
    def __init__(self):
        self.__users = {}
        self.__graph = defaultdict(set)

    @property
    def users(self):
        return self.__users

    def add_user(self, user):
        if user.uuid in self.__users:
            raise UserAlreadyExistsError(user)
        self.__users[user.uuid] = user
        self.__graph[user.uuid]

    @check_if_users_exist
    def get_user(self, user_uuid):
        return self.__users[user_uuid]

    @check_if_users_exist
    def delete_user(self, user_uuid):
        del self.__users[user_uuid]
        del self.__graph[user_uuid]

    @check_if_users_exist
    def follow(self, follower, followee):
        if follower == followee:
            raise ValueError("User cannot follow himself!")
        self.__graph[follower].add(followee)

    @check_if_users_exist
    def unfollow(self, follower, followee):
        if follower == followee:
            raise ValueError("User cannot unfollow himself!")
        if self.is_following(follower, followee):
            self.__graph[follower].remove(followee)

    @check_if_users_exist
    def is_following(self, follower, followee):
        if follower == followee:
            raise ValueError("User cannot be following himself!")
        return followee in self.__graph[follower]

    @check_if_users_exist
    def followers(self, user_uuid):
        return set(follower for follower in self.__graph.keys()
                   if follower != user_uuid and
                   self.is_following(follower, user_uuid))

    @check_if_users_exist
    def following(self, user_uuid):
        return self.__graph[user_uuid]

    @check_if_users_exist
    def friends(self, user_uuid):
        return set(
            friend for friend in self.__graph[user_uuid]
            if self.is_following(friend, user_uuid))

    @check_if_users_exist
    def max_distance(self, user_uuid):
        max_distance_found = max(self.find_min_distances(user_uuid).values())
        return max_distance_found if max_distance_found != 0 else math.inf

    def find_min_distances(self, user_uuid):
        queue = []
        queue.append(user_uuid)
        # the dictionary maps destinations(other users)
        # with distances from user_uuid
        distances = defaultdict(int)
        visited = set()
        depth_counter = -1
        children_counter = 1

        while queue:
            depth_counter += 1
            new_children_counter = 0

            for _ in range(children_counter):
                current_elem = queue.pop(0)
                for child in self.__graph[current_elem]:
                    if child not in visited:
                        new_children_counter += 1
                        queue.append(child)

                if(distances[current_elem] == 0 or
                        distances[current_elem] > depth_counter):
                    distances[current_elem] = depth_counter
                visited.add(current_elem)
            children_counter = new_children_counter
        return distances

    @check_if_users_exist
    def min_distance(self, from_user_uuid, to_user_uuid):
        if from_user_uuid == to_user_uuid:
            return 0

        distances_found = self.find_min_distances(from_user_uuid)
        if to_user_uuid not in distances_found.keys():
            raise UsersNotConnectedError(from_user_uuid, to_user_uuid)

        return distances_found[to_user_uuid]

    @check_if_users_exist
    def nth_layer_followings(self, user_uuid, n):
        if n == 0:
            return set()
        elif n < 0:
            raise ValueError("Layer number must be at least 0!" +
                             "Yours was {}.".format(n))

        max_distances_found = self.find_min_distances(user_uuid)
        nth_layer = set([destination
                        for destination, distance in
                        max_distances_found.items() if distance == n])
        return nth_layer

    @check_if_users_exist
    def generate_feed(self, user_uuid, offset=0, limit=10):
        if offset < 0:
            raise ValueError("Offset index must be a positive number!" +
                             " Yours was {}".format(offset))
        elif limit < 0:
            raise ValueError("Limit index must be a positive number!" +
                             " Yours was {}".format(limit))

        all_posts = []
        for followee in self.__graph[user_uuid]:
            all_posts.extend(self.__users[followee].get_post())

        sorted_by_date = sorted(all_posts,
                                key=lambda post: post.published_at,
                                reverse=True)
        return islice(sorted_by_date, offset, offset + limit)


class UserDoesNotExistError(Exception):
    def __init__(self, uuid):
        self.message = "User with uuid [{}] does not exist!".format(uuid)

    def __str__(self):
        return self.message


class UserAlreadyExistsError(Exception):
    def __init__(self, user):
        self.message = "User {} alredy exists!".format(user)

    def __str__(self):
        return self.message


class UsersNotConnectedError(Exception):
    def __init__(self, from_user_uuid, to_user_uuid):
        self.message = """There is no possible path
        between user [{}] and user [{}]""".format(from_user_uuid, to_user_uuid)

    def __str__(self):
        return self.message