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
233
234
235
236
237
238
239
from collections import defaultdict
from datetime import datetime
from uuid import uuid4
from math import inf
from queue import Queue


class UserDoesNotExistError(Exception):
    pass


class UserAlreadyExistsError(Exception):
    pass


class UsersNotConnectedError(Exception):
    pass


class IllegalFollowError(Exception):
    pass


def check_user_exists(method):
    def _check_user_exists(*args):
        if isinstance(args[1], User):
            user_uuid = args[1].uuid
        else:
            user_uuid = args[1]
        if user_uuid in args[0]._user_uuids:
            raise UserAlreadyExistsError("User already part of the graph")
        return method(*args)
    return _check_user_exists


def check_user_is_the_same(method):
    def _check_user_is_the_same(*args):
        if args[1] == args[2]:
            raise IllegalFollowError
        return method(*args)
    return _check_user_is_the_same


def check_user_not_exists(*args):
    def _check_user_not_exists(method):
        def wrapper(*args, **kwargs):
            for user_uuid in args[1:end_index]:
                if user_uuid not in args[0]._user_uuids:
                    raise UserDoesNotExistError("User is not part of the graph")
            return method(*args)
        return wrapper

    if len(args) == 1 and callable(args[0]):
        end_index = 2
        return _check_user_not_exists(args[0])
    else:
        end_index = args[0]
        return _check_user_not_exists


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

    def __cmp__(self, other):
        print("SPARTAAA")
        return self.published_at > other.published_at

    def __str__(self):
        return "{0} created at {1}".format(self.content, self.published_at)

    def __repr__(self):
        return "{0} created at {1}".format(self.content, self.published_at)


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

    def add_post(self, post_content):
        self._posts.append(Post(self.uuid, post_content))
        if len(self._posts) == 51:
            self._posts.pop(0)

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


class SocialGraph:
    def __init__(self):
        self._user_uuids = {}
        self._following = defaultdict(set)

    def __check_user_not_exists(self, user_uuid):
        if user_uuid not in self._user_uuids:
            raise UserDoesNotExistError("User is not part of the graph")

    @check_user_exists
    def add_user(self, user):
        self._user_uuids[user.uuid] = user

    @check_user_not_exists
    def get_user(self, user_uuid):
        return self._user_uuids[user_uuid]

    @check_user_not_exists
    def delete_user(self, user_uuid):
        del self._user_uuids[user_uuid]

    @check_user_not_exists(3)
    @check_user_is_the_same
    def follow(self, follower, followee):
        self._following[follower].add(followee)

    @check_user_not_exists(3)
    @check_user_is_the_same
    def unfollow(self, follower, followee):
        self._following[follower].discard(followee)

    @check_user_not_exists(3)
    def is_following(self, follower, followee):
        return followee in self._following[follower]

    @check_user_not_exists
    def followers(self, user_uuid):
        return set(filter(lambda uuid: user_uuid in self.following(uuid),
                          self._user_uuids))

    @check_user_not_exists
    def following(self, user_uuid):
        return self._following[user_uuid]

    @check_user_not_exists
    def friends(self, user_uuid):
        return filter(lambda uuid: user_uuid in self.following(uuid),
                      self.following(user_uuid))

    @check_user_not_exists
    def max_distance(self, user_uuid):
        # Depth-first search in case the longest path is defined
        # as the actual longest path

        # if not bool(self.following(user_uuid)):
        #     return inf
        # visited = set()
        # distance = 0
        # nodes = [(user_uuid, 0)]
        # while bool(nodes):
        #     current_uuid, current_distance = nodes.pop()
        #     # print(current_uuid, current_distance)
        #     # print(current_distance)
        #     if current_uuid in visited:
        #         continue
        #     visited.add(current_uuid)
        #     if distance < current_distance:
        #         distance = current_distance
        #     for followee in self.following(current_uuid):
        #         nodes.append((followee, current_distance + 1))

        # return distance

        if not bool(self.following(user_uuid)):
            return inf
        nodes = Queue()
        visited = set()
        nodes.put((user_uuid, 0))
        distance = 0
        while not nodes.empty():
            current_uuid, current_distance = nodes.get()
            visited.add(current_uuid)
            if current_distance > distance:
                distance = current_distance
            for followee in self.following(current_uuid):
                if followee in visited:
                    continue
                nodes.put((followee, current_distance + 1))

        return distance

    @check_user_not_exists(3)
    def min_distance(self, from_user_uuid, to_user_uuid):
        nodes = Queue()
        visited = set()
        nodes.put((from_user_uuid, 0))
        while not nodes.empty():
            current_uuid, current_distance = nodes.get()
            visited.add(current_uuid)
            if current_uuid == to_user_uuid:
                return current_distance
            for followee in self.following(current_uuid):
                if followee in visited:
                    continue
                nodes.put((followee, current_distance + 1))

        return inf

    @check_user_not_exists
    def nth_layer_followings(self, user_uuid, n):
        if n == 0:
            return set()
        nodes = Queue()
        visited = set()
        nodes.put((user_uuid, 0))
        result = set()
        while not nodes.empty():
            current_uuid, current_distance = nodes.get()
            visited.add(current_uuid)
            if current_distance > n:
                break
            if current_distance == n:
                result.add(current_uuid)
            for followee in self.following(current_uuid):
                if followee in visited:
                    continue
                nodes.put((followee, current_distance + 1))

        return result

    @check_user_not_exists
    def generate_feed(self, user_uuid, offset=0, limit=10):
        skip_index = -1
        yielded_count = 0
        posts = []
        for uuid in self.following(user_uuid):
            posts.extend(self.get_user(uuid).get_post())
        for post in sorted(posts,
                           key=lambda post: post.published_at,
                           reverse=True):
            skip_index += 1
            if skip_index < offset:
                continue
            if yielded_count == limit:
                break
            yield post
            yielded_count += 1

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

........
----------------------------------------------------------------------
Ran 8 tests in 0.064s

OK

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

Димитър обнови решението на 17.04.2016 03:21 (преди над 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
from collections import defaultdict
from datetime import datetime
from uuid import uuid4
from math import inf
from queue import Queue


class UserDoesNotExistError(Exception):
    pass


class UserAlreadyExistsError(Exception):
    pass


class UsersNotConnectedError(Exception):
    pass


class IllegalFollowError(Exception):
    pass


def check_user_exists(method):
    def _check_user_exists(*args):
        if isinstance(args[1], User):
            user_uuid = args[1].uuid
        else:
            user_uuid = args[1]
        if user_uuid in args[0]._user_uuids:
            raise UserAlreadyExistsError("User already part of the graph")
        return method(*args)
    return _check_user_exists


def check_user_is_the_same(method):
    def _check_user_is_the_same(*args):
        if args[1] == args[2]:
            raise IllegalFollowError
        return method(*args)
    return _check_user_is_the_same


def check_user_not_exists(*args):
    def _check_user_not_exists(method):
        def wrapper(*args, **kwargs):
            for user_uuid in args[1:end_index]:
                if user_uuid not in args[0]._user_uuids:
                    raise UserDoesNotExistError("User is not part of the graph")
            return method(*args)
        return wrapper

    if len(args) == 1 and callable(args[0]):
        end_index = 2
        return _check_user_not_exists(args[0])
    else:
        end_index = args[0]
        return _check_user_not_exists


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

    def __cmp__(self, other):
        print("SPARTAAA")
        return self.published_at > other.published_at

    def __str__(self):
        return "{0} created at {1}".format(self.content, self.published_at)

    def __repr__(self):
        return "{0} created at {1}".format(self.content, self.published_at)


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

    def add_post(self, post_content):
        self._posts.append(Post(self.uuid, post_content))
        if len(self._posts) == 51:
            self._posts.pop(0)

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


class SocialGraph:
    def __init__(self):
        self._user_uuids = {}
        self._following = defaultdict(set)
        self._followers = defaultdict(set)

    def __check_user_not_exists(self, user_uuid):
        if user_uuid not in self._user_uuids:
            raise UserDoesNotExistError("User is not part of the graph")

    @check_user_exists
    def add_user(self, user):
        self._user_uuids[user.uuid] = user

    @check_user_not_exists
    def get_user(self, user_uuid):
        return self._user_uuids[user_uuid]

    @check_user_not_exists
    def delete_user(self, user_uuid):
        del self._user_uuids[user_uuid]

    @check_user_not_exists(3)
    @check_user_is_the_same
    def follow(self, follower, followee):
        self._following[follower].add(followee)
        self._followers[followee].add(follower)

    @check_user_not_exists(3)
    @check_user_is_the_same
    def unfollow(self, follower, followee):
        self._following[follower].discard(followee)
        self._followers[followee].discard(follower)

    @check_user_not_exists(3)
    def is_following(self, follower, followee):
        return followee in self._following[follower]

    @check_user_not_exists
    def followers(self, user_uuid):
        return self._followers[user_uuid]

    @check_user_not_exists
    def following(self, user_uuid):
        return self._following[user_uuid]

    @check_user_not_exists
    def friends(self, user_uuid):
        return {
            followee
            for followee in self.following(user_uuid)
            if user_uuid in self.following(followee)
        }

    @check_user_not_exists
    def max_distance(self, user_uuid):
        # Depth-first search in case the longest path is defined
        # as the actual longest path

        # if not bool(self.following(user_uuid)):
        #     return inf
        # visited = set()
        # distance = 0
        # nodes = [(user_uuid, 0)]
        # while bool(nodes):
        #     current_uuid, current_distance = nodes.pop()
        #     # print(current_uuid, current_distance)
        #     # print(current_distance)
        #     if current_uuid in visited:
        #         continue
        #     visited.add(current_uuid)
        #     if distance < current_distance:
        #         distance = current_distance
        #     for followee in self.following(current_uuid):
        #         nodes.append((followee, current_distance + 1))

        # return distance

        if not bool(self.following(user_uuid)):
            return inf
        nodes = Queue()
        visited = set()
        nodes.put((user_uuid, 0))
        distance = 0
        while not nodes.empty():
            current_uuid, current_distance = nodes.get()
            visited.add(current_uuid)
            if current_distance > distance:
                distance = current_distance
            for followee in self.following(current_uuid):
                if followee in visited:
                    continue
                nodes.put((followee, current_distance + 1))

        return distance

    @check_user_not_exists(3)
    def min_distance(self, from_user_uuid, to_user_uuid):
        nodes = Queue()
        visited = set()
        nodes.put((from_user_uuid, 0))
        while not nodes.empty():
            current_uuid, current_distance = nodes.get()
            visited.add(current_uuid)
            if current_uuid == to_user_uuid:
                return current_distance
            for followee in self.following(current_uuid):
                if followee in visited:
                    continue
                nodes.put((followee, current_distance + 1))

        return inf

    @check_user_not_exists
    def nth_layer_followings(self, user_uuid, n):
        nodes = Queue()
        visited = set()
        nodes.put((user_uuid, 0))
        result = set()
        while not nodes.empty():
            current_uuid, current_distance = nodes.get()
            visited.add(current_uuid)
            if current_distance > n:
                break
            if current_distance == n:
                result.add(current_uuid)
            for followee in self.following(current_uuid):
                if followee in visited:
                    continue
                nodes.put((followee, current_distance + 1))

        return result

    @check_user_not_exists
    def generate_feed(self, user_uuid, offset=0, limit=10):
        skip_index = -1
        yielded_count = 0
        posts = []
        for uuid in self.following(user_uuid):
            posts.extend(self.get_user(uuid).get_post())
        for post in sorted(posts,
                           key=lambda post: post.published_at,
                           reverse=True):
            skip_index += 1
            if skip_index < offset:
                continue
            if yielded_count == limit:
                break
            yield post
            yielded_count += 1

Димитър обнови решението на 17.04.2016 12:22 (преди над 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
from collections import defaultdict
from datetime import datetime
from uuid import uuid4
from math import inf
from queue import Queue


class UserDoesNotExistError(Exception):
    pass


class UserAlreadyExistsError(Exception):
    pass


class UsersNotConnectedError(Exception):
    pass


class IllegalFollowError(Exception):
    pass


def check_user_exists(method):
    def _check_user_exists(*args):
        if isinstance(args[1], User):
            user_uuid = args[1].uuid
        else:
            user_uuid = args[1]
        if user_uuid in args[0]._user_uuids:
            raise UserAlreadyExistsError("User already part of the graph")
        return method(*args)
    return _check_user_exists


def check_user_is_the_same(method):
    def _check_user_is_the_same(*args):
        if args[1] == args[2]:
            raise IllegalFollowError
        return method(*args)
    return _check_user_is_the_same


def check_user_not_exists(*args):
    def _check_user_not_exists(method):
        def wrapper(*args, **kwargs):
            for user_uuid in args[1:end_index]:
                if user_uuid not in args[0]._user_uuids:
                    raise UserDoesNotExistError("User is not part of the graph")
            return method(*args)
        return wrapper

    if len(args) == 1 and callable(args[0]):
        end_index = 2
        return _check_user_not_exists(args[0])
    else:
        end_index = args[0]
        return _check_user_not_exists


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

    def __cmp__(self, other):
        print("SPARTAAA")
        return self.published_at > other.published_at

    def __str__(self):
        return "{0} created at {1}".format(self.content, self.published_at)

    def __repr__(self):
        return "{0} created at {1}".format(self.content, self.published_at)


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

    def add_post(self, post_content):
        self._posts.append(Post(self.uuid, post_content))
        if len(self._posts) == 51:
            self._posts.pop(0)

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


class SocialGraph:
    def __init__(self):
        self._user_uuids = {}
        self._following = defaultdict(set)
        self._followers = defaultdict(set)

    def __check_user_not_exists(self, user_uuid):
        if user_uuid not in self._user_uuids:
            raise UserDoesNotExistError("User is not part of the graph")

    @check_user_exists
    def add_user(self, user):
        self._user_uuids[user.uuid] = user

    @check_user_not_exists
    def get_user(self, user_uuid):
        return self._user_uuids[user_uuid]

    @check_user_not_exists
    def delete_user(self, user_uuid):
        del self._user_uuids[user_uuid]

    @check_user_not_exists(3)
    @check_user_is_the_same
    def follow(self, follower, followee):
        self._following[follower].add(followee)
        self._followers[followee].add(follower)

    @check_user_not_exists(3)
    @check_user_is_the_same
    def unfollow(self, follower, followee):
        self._following[follower].discard(followee)
        self._followers[followee].discard(follower)

    @check_user_not_exists(3)
    def is_following(self, follower, followee):
        return followee in self._following[follower]

    @check_user_not_exists
    def followers(self, user_uuid):
        return self._followers[user_uuid]

    @check_user_not_exists
    def following(self, user_uuid):
        return self._following[user_uuid]

    @check_user_not_exists
    def friends(self, user_uuid):
        return {
            followee
            for followee in self.following(user_uuid)
            if user_uuid in self.following(followee)
        }

    @check_user_not_exists
    def max_distance(self, user_uuid):
        # Depth-first search in case the longest path is defined
        # as the actual longest path

        # if not bool(self.following(user_uuid)):
        #     return inf
        # visited = set()
        # distance = 0
        # nodes = [(user_uuid, 0)]
        # while bool(nodes):
        #     current_uuid, current_distance = nodes.pop()
        #     # print(current_uuid, current_distance)
        #     # print(current_distance)
        #     if current_uuid in visited:
        #         continue
        #     visited.add(current_uuid)
        #     if distance < current_distance:
        #         distance = current_distance
        #     for followee in self.following(current_uuid):
        #         nodes.append((followee, current_distance + 1))

        # return distance

        if not bool(self.following(user_uuid)):
            return inf
        nodes = Queue()
        visited = set()
        nodes.put((user_uuid, 0))
        distance = 0
        while not nodes.empty():
            current_uuid, current_distance = nodes.get()
            visited.add(current_uuid)
            if current_distance > distance:
                distance = current_distance
            for followee in self.following(current_uuid):
                if followee in visited:
                    continue
                nodes.put((followee, current_distance + 1))

        return distance

    @check_user_not_exists(3)
    def min_distance(self, from_user_uuid, to_user_uuid):
        nodes = Queue()
        visited = set()
        nodes.put((from_user_uuid, 0))
        while not nodes.empty():
            current_uuid, current_distance = nodes.get()
            visited.add(current_uuid)
            if current_uuid == to_user_uuid:
                return current_distance
            for followee in self.following(current_uuid):
                if followee in visited:
                    continue
                nodes.put((followee, current_distance + 1))

        return inf

    @check_user_not_exists
    def nth_layer_followings(self, user_uuid, n):
        if n == 0:
            return set()
        nodes = Queue()
        visited = set()
        nodes.put((user_uuid, 0))
        result = set()
        while not nodes.empty():
            current_uuid, current_distance = nodes.get()
            visited.add(current_uuid)
            if current_distance > n:
                break
            if current_distance == n:
                result.add(current_uuid)
            for followee in self.following(current_uuid):
                if followee in visited:
                    continue
                nodes.put((followee, current_distance + 1))

        return result

    @check_user_not_exists
    def generate_feed(self, user_uuid, offset=0, limit=10):
        skip_index = -1
        yielded_count = 0
        posts = []
        for uuid in self.following(user_uuid):
            posts.extend(self.get_user(uuid).get_post())
        for post in sorted(posts,
                           key=lambda post: post.published_at,
                           reverse=True):
            skip_index += 1
            if skip_index < offset:
                continue
            if yielded_count == limit:
                break
            yield post
            yielded_count += 1
  • Декораторите за валидации са много хубава идея. :)
  • Разбирам, че си се опитал да постигнеш накакъв trade-off „памет за удобство/скорост“ с _following и _followers. Предвид факта, че и двете са defaultdict-ове от set-ове обаче, не мисля, че има смисъл. Ако смяташ, че си струва печалбата на удобство и скорост, може би е по-добре да имаш отделен клас, който да се грижи за поддържането на такива двупосочни redundant връзки, така че да не се налага в кода на SocialGraph да внимаваш дали винаги си добавил/махнал и от двата.
  • За friends погледни дали няма хубав метод на set, който да свърши работата вместо тебе.

Евгени Благодаря за забележките - _followers остана, защото имплементирах условието докато го четях и реших, че ще ми трябва за още манипулации - гледайки сега кода наистина няма смисъл от тази "оптимизация". За friends съм направо изумен, че сам съм имплементирал filter, но какво да се прави :D

Димитър обнови решението на 18.04.2016 00:36 (преди над 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
from collections import defaultdict
from datetime import datetime
from uuid import uuid4
from math import inf
from queue import Queue


class UserDoesNotExistError(Exception):
    pass


class UserAlreadyExistsError(Exception):
    pass


class UsersNotConnectedError(Exception):
    pass


class IllegalFollowError(Exception):
    pass


def check_user_exists(method):
    def _check_user_exists(*args):
        if isinstance(args[1], User):
            user_uuid = args[1].uuid
        else:
            user_uuid = args[1]
        if user_uuid in args[0]._user_uuids:
            raise UserAlreadyExistsError("User already part of the graph")
        return method(*args)
    return _check_user_exists


def check_user_is_the_same(method):
    def _check_user_is_the_same(*args):
        if args[1] == args[2]:
            raise IllegalFollowError
        return method(*args)
    return _check_user_is_the_same


def check_user_not_exists(*args):
    def _check_user_not_exists(method):
        def wrapper(*args, **kwargs):
            for user_uuid in args[1:end_index]:
                if user_uuid not in args[0]._user_uuids:
                    raise UserDoesNotExistError("User is not part of the graph")
            return method(*args)
        return wrapper

    if len(args) == 1 and callable(args[0]):
        end_index = 2
        return _check_user_not_exists(args[0])
    else:
        end_index = args[0]
        return _check_user_not_exists


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

    def __cmp__(self, other):
        print("SPARTAAA")
        return self.published_at > other.published_at

    def __str__(self):
        return "{0} created at {1}".format(self.content, self.published_at)

    def __repr__(self):
        return "{0} created at {1}".format(self.content, self.published_at)


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

    def add_post(self, post_content):
        self._posts.append(Post(self.uuid, post_content))
        if len(self._posts) == 51:
            self._posts.pop(0)

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


class SocialGraph:
    def __init__(self):
        self._user_uuids = {}
        self._following = defaultdict(set)

    def __check_user_not_exists(self, user_uuid):
        if user_uuid not in self._user_uuids:
            raise UserDoesNotExistError("User is not part of the graph")

    @check_user_exists
    def add_user(self, user):
        self._user_uuids[user.uuid] = user

    @check_user_not_exists
    def get_user(self, user_uuid):
        return self._user_uuids[user_uuid]

    @check_user_not_exists
    def delete_user(self, user_uuid):
        del self._user_uuids[user_uuid]

    @check_user_not_exists(3)
    @check_user_is_the_same
    def follow(self, follower, followee):
        self._following[follower].add(followee)

    @check_user_not_exists(3)
    @check_user_is_the_same
    def unfollow(self, follower, followee):
        self._following[follower].discard(followee)

    @check_user_not_exists(3)
    def is_following(self, follower, followee):
        return followee in self._following[follower]

    @check_user_not_exists
    def followers(self, user_uuid):
        return set(filter(lambda uuid: user_uuid in self.following(uuid),
                          self._user_uuids))

    @check_user_not_exists
    def following(self, user_uuid):
        return self._following[user_uuid]

    @check_user_not_exists
    def friends(self, user_uuid):
        return filter(lambda uuid: user_uuid in self.following(uuid),
                      self.following(user_uuid))

    @check_user_not_exists
    def max_distance(self, user_uuid):
        # Depth-first search in case the longest path is defined
        # as the actual longest path

        # if not bool(self.following(user_uuid)):
        #     return inf
        # visited = set()
        # distance = 0
        # nodes = [(user_uuid, 0)]
        # while bool(nodes):
        #     current_uuid, current_distance = nodes.pop()
        #     # print(current_uuid, current_distance)
        #     # print(current_distance)
        #     if current_uuid in visited:
        #         continue
        #     visited.add(current_uuid)
        #     if distance < current_distance:
        #         distance = current_distance
        #     for followee in self.following(current_uuid):
        #         nodes.append((followee, current_distance + 1))

        # return distance

        if not bool(self.following(user_uuid)):
            return inf
        nodes = Queue()
        visited = set()
        nodes.put((user_uuid, 0))
        distance = 0
        while not nodes.empty():
            current_uuid, current_distance = nodes.get()
            visited.add(current_uuid)
            if current_distance > distance:
                distance = current_distance
            for followee in self.following(current_uuid):
                if followee in visited:
                    continue
                nodes.put((followee, current_distance + 1))

        return distance

    @check_user_not_exists(3)
    def min_distance(self, from_user_uuid, to_user_uuid):
        nodes = Queue()
        visited = set()
        nodes.put((from_user_uuid, 0))
        while not nodes.empty():
            current_uuid, current_distance = nodes.get()
            visited.add(current_uuid)
            if current_uuid == to_user_uuid:
                return current_distance
            for followee in self.following(current_uuid):
                if followee in visited:
                    continue
                nodes.put((followee, current_distance + 1))

        return inf

    @check_user_not_exists
    def nth_layer_followings(self, user_uuid, n):
        if n == 0:
            return set()
        nodes = Queue()
        visited = set()
        nodes.put((user_uuid, 0))
        result = set()
        while not nodes.empty():
            current_uuid, current_distance = nodes.get()
            visited.add(current_uuid)
            if current_distance > n:
                break
            if current_distance == n:
                result.add(current_uuid)
            for followee in self.following(current_uuid):
                if followee in visited:
                    continue
                nodes.put((followee, current_distance + 1))

        return result

    @check_user_not_exists
    def generate_feed(self, user_uuid, offset=0, limit=10):
        skip_index = -1
        yielded_count = 0
        posts = []
        for uuid in self.following(user_uuid):
            posts.extend(self.get_user(uuid).get_post())
        for post in sorted(posts,
                           key=lambda post: post.published_at,
                           reverse=True):
            skip_index += 1
            if skip_index < offset:
                continue
            if yielded_count == limit:
                break
            yield post
            yielded_count += 1