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
from uuid import uuid4, UUID
from datetime import datetime
from collections import defaultdict
from math import inf
from queue import PriorityQueue


class UserDoesNotExistError(Exception):
    def __init__(self, user_uuid):
        self.user_uuid = user_uuid


class UserAlreadyExistsError(Exception):
    def __init__(self, user_uuid):
        self.user_uuid = user_uuid


class UsersNotConnectedError(Exception):
    def __init__(self, first_uuid, second_uuid):
        self.first_uuid = first_uuid
        self.second_uuid = second_uuid


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

    def add_post(self, post_content):
        if len(self._posts) == 50:
            del self._posts[0]

        self._posts.append(Post(self.uuid, post_content))

    def get_post(self, oldest_first=True):
        posts = self._posts if oldest_first else reversed(self._posts)

        for post in posts:
            yield post


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


def validate_uuid(method):
    def inner(self, *args, **kwargs):
        for arg in args:
            if isinstance(arg, UUID) and arg not in self._users:
                raise UserDoesNotExistError(arg)

        for arg in kwargs.values():
            if isinstance(arg, UUID) and arg not in self._users:
                raise UserDoesNotExistError(arg)

        return method(self, *args, **kwargs)

    return inner


class SocialGraph:
    def __init__(self):
        self._users = {}
        self._connections = defaultdict(set)

    def add_user(self, user):
        if user.uuid in self._users:
            raise UserAlreadyExistsError(user.uuid)

        self._users[user.uuid] = user

    @validate_uuid
    def get_user(self, user_uuid):
        return self._users[user_uuid]

    @validate_uuid
    def delete_user(self, user_uuid):
        del self._users[user_uuid]

    @validate_uuid
    def follow(self, follower, followee):
        if follower == followee:
            raise ValueError('Same uuid given')

        self._connections[follower].add(followee)

    @validate_uuid
    def unfollow(self, follower, followee):
        if not self.is_following(follower, followee):
            raise UsersNotConnectedError(follower, followee)

        self._connections[follower].remove(followee)

    @validate_uuid
    def is_following(self, follower, followee):
        return followee in self._connections[follower]

    @validate_uuid
    def followers(self, user_uuid):
        return {
            user for user in self._users.keys()
            if self.is_following(user, user_uuid)
        }

    @validate_uuid
    def following(self, user_uuid):
        return set(self._connections[user_uuid])

    @validate_uuid
    def friends(self, user_uuid):
        return {
            user for user in self._connections[user_uuid]
            if self.is_following(user, user_uuid)
        }

    @validate_uuid
    def max_distance(self, user_uuid):
        fringe = [(user_uuid, 0)]
        visited = set()
        max_dist = 0

        while len(fringe) != 0:
            uuid, depth = fringe.pop()
            visited.add(uuid)
            max_dist = depth

            next_layer = {
                user for user in self.following(uuid) if user not in visited
            }

            for user in next_layer:
                fringe.insert(0, (user, depth+1))

        return max_dist if max_dist > 0 else inf

    @validate_uuid
    def min_distance(self, from_user_uuid, to_user_uuid):
        fringe = [(from_user_uuid, 0)]
        visited = set()

        while len(fringe) != 0:
            uuid, depth = fringe.pop()
            visited.add(uuid)

            if uuid == to_user_uuid:
                return depth

            next_layer = {
                user for user in self.following(uuid) if user not in visited
            }

            for user in next_layer:
                fringe.insert(0, (user, depth+1))

        raise UsersNotConnectedError(from_user_uuid, to_user_uuid)

    @validate_uuid
    def nth_layer_followings(self, user_uuid, n):
        if n == 0:
            return set()

        fringe = [(user_uuid, 0)]
        visited = set()
        distance = 0
        nth_layer = set()

        while len(fringe) != 0:
            uuid, depth = fringe.pop()
            visited.add(uuid)
            distance = depth

            next_layer = {
                user for user in self.following(uuid) if user not in visited
            }

            if distance == n-1:
                nth_layer |= next_layer
            else:
                for user in next_layer:
                    fringe.insert(0, (user, depth+1))

        return nth_layer

    @validate_uuid
    def generate_feed(self, user_uuid, offset=0, limit=10):
        queue = PriorityQueue()
        # idx is used as second item in the priority queue
        # if two timestamps are equal idx is used for comparing
        idx = 0
        for user in self.following(user_uuid):
            generator = self._users[user].get_post(oldest_first=False)
            post = next(generator)
            queue.put((-post.published_at.timestamp(), idx, generator, post))
            idx += 1

        posts = []
        while len(posts) < (offset + limit) and queue.qsize() > 0:
            _, __, generator, post = queue.get()
            posts.append(post)

            try:
                next_post = next(generator)
                queue.put(
                    (-next_post.published_at.timestamp(),
                        idx, generator, next_post)
                )

                idx += 1
            except StopIteration:
                continue

        return posts[offset:]

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

........
----------------------------------------------------------------------
Ran 8 tests in 0.067s

OK

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

Николай обнови решението на 13.04.2016 00:24 (преди над 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
from uuid import uuid4, UUID
from datetime import datetime
from collections import defaultdict
from math import inf
from queue import PriorityQueue


class UserDoesNotExistError(Exception):
    def __init__(self, user_uuid):
        self.user_uuid = user_uuid


class UserAlreadyExistsError(Exception):
    def __init__(self, user_uuid):
        self.user_uuid = user_uuid


class UsersNotConnectedError(Exception):
    def __init__(self, first_uuid, second_uuid):
        self.first_uuid = first_uuid
        self.second_uuid = second_uuid


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

    def add_post(self, post_content):
        if len(self._posts) == 50:
            del self._posts[0]

        self._posts.append(Post(self.uuid, post_content))

    def get_post(self, oldest_first=True):
        posts = self._posts if oldest_first else reversed(self._posts)

        for post in posts:
            yield post


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


def validate_uuid(method):
    def inner(self, *args, **kwargs):
        for arg in args:
            if isinstance(arg, UUID) and arg not in self._users:
                raise UserDoesNotExistError(arg)

        for arg in kwargs.values():
            if isinstance(arg, UUID) and arg not in self._users:
                raise UserDoesNotExistError(arg)

        return method(self, *args, **kwargs)

    return inner


class SocialGraph:
    def __init__(self):
        self._users = {}
        self._connections = defaultdict(set)

    def add_user(self, user):
        if user.uuid in self._users:
            raise UserAlreadyExistsError(user.uuid)

        self._users[user.uuid] = user

    @validate_uuid
    def get_user(self, user_uuid):
        return self._users[user_uuid]

    @validate_uuid
    def delete_user(self, user_uuid):
        del self._users[user_uuid]

    @validate_uuid
    def follow(self, follower, followee):
        if follower == followee:
            raise UsersNotConnectedError(follower, followee)

        self._connections[follower].add(followee)

    @validate_uuid
    def unfollow(self, follower, followee):
        if not self.is_following(follower, followee):
            raise UsersNotConnectedError(follower, followee)

        self._connections[follower].remove(followee)

    @validate_uuid
    def is_following(self, follower, followee):
        return followee in self._connections[follower]

    @validate_uuid
    def followers(self, user_uuid):
        return {
            user for user in self._users.keys()
                    if self.is_following(user, user_uuid)
        }

    @validate_uuid
    def following(self, user_uuid):
        return set(self._connections[user_uuid])

    @validate_uuid
    def friends(self, user_uuid):
        return {
            user for user in self._connections[user_uuid]
                    if self.is_following(user, user_uuid)
        }

    @validate_uuid
    def max_distance(self, user_uuid):
        fringe = [(user_uuid, 0)]
        visited = set()
        max_dist = 0

        while len(fringe) != 0:
            uuid, depth = fringe.pop()
            visited.add(uuid)
            max_dist = depth

            next_layer = {
                user for user in self.following(uuid) if user not in visited
            }

            for user in next_layer:
                fringe.insert(0, (user, depth+1))

        return max_dist if max_dist > 0 else inf

    @validate_uuid
    def min_distance(self, from_user_uuid, to_user_uuid):
        fringe = [(from_user_uuid, 0)]
        visited = set()

        while len(fringe) != 0:
            uuid, depth = fringe.pop()
            visited.add(uuid)

            if uuid == to_user_uuid:
                return depth

            next_layer = {
                user for user in self.following(uuid) if user not in visited
            }

            for user in next_layer:
                fringe.insert(0, (user, depth+1))

        raise UsersNotConnectedError(from_user_uuid, to_user_uuid)

    @validate_uuid
    def nth_layer_followings(self, user_uuid, n):
        if n == 0:
            return set()

        fringe = [(user_uuid, 0)]
        visited = set()
        distance = 0
        nth_layer = set()

        while len(fringe) != 0:
            uuid, depth = fringe.pop()
            visited.add(uuid)
            distance = depth

            next_layer = {
                user for user in self.following(uuid) if user not in visited
            }

            if distance == n-1:
                nth_layer |= next_layer
            else:
                for user in next_layer:
                    fringe.insert(0, (user, depth+1))

        return nth_layer

    @validate_uuid
    def generate_feed(self, user_uuid, offset=0, limit=10):
        queue = PriorityQueue()
        # idx is used as second item in the priority queue
        # if two timestamps are equal idx is used for comparing
        idx = 0
        for user in self.following(user_uuid):
            generator = self._users[user].get_post(oldest_first=False)
            post = next(generator)
            queue.put((-post.published_at.timestamp(), idx, generator, post))
            idx += 1

        posts = []
        while len(posts) < (offset + limit) and queue.qsize() > 0:
            _, __, generator, post = queue.get()
            posts.append(post)

            try:
                next_post = next(generator)
                queue.put(
                    (-next_post.published_at.timestamp(),
                        idx, generator, next_post)
                )

                idx += 1
            except StopIteration:
                continue

        return posts[offset:]

Николай обнови решението на 14.04.2016 19:31 (преди над 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
from uuid import uuid4, UUID
from datetime import datetime
from collections import defaultdict
from math import inf
from queue import PriorityQueue


class UserDoesNotExistError(Exception):
    def __init__(self, user_uuid):
        self.user_uuid = user_uuid


class UserAlreadyExistsError(Exception):
    def __init__(self, user_uuid):
        self.user_uuid = user_uuid


class UsersNotConnectedError(Exception):
    def __init__(self, first_uuid, second_uuid):
        self.first_uuid = first_uuid
        self.second_uuid = second_uuid


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

    def add_post(self, post_content):
        if len(self._posts) == 50:
            del self._posts[0]

        self._posts.append(Post(self.uuid, post_content))

    def get_post(self, oldest_first=True):
        posts = self._posts if oldest_first else reversed(self._posts)

        for post in posts:
            yield post


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


def validate_uuid(method):
    def inner(self, *args, **kwargs):
        for arg in args:
            if isinstance(arg, UUID) and arg not in self._users:
                raise UserDoesNotExistError(arg)

        for arg in kwargs.values():
            if isinstance(arg, UUID) and arg not in self._users:
                raise UserDoesNotExistError(arg)

        return method(self, *args, **kwargs)

    return inner


class SocialGraph:
    def __init__(self):
        self._users = {}
        self._connections = defaultdict(set)

    def add_user(self, user):
        if user.uuid in self._users:
            raise UserAlreadyExistsError(user.uuid)

        self._users[user.uuid] = user

    @validate_uuid
    def get_user(self, user_uuid):
        return self._users[user_uuid]

    @validate_uuid
    def delete_user(self, user_uuid):
        del self._users[user_uuid]

    @validate_uuid
    def follow(self, follower, followee):
        if follower == followee:
            raise ValueError('Same uuid given')

        self._connections[follower].add(followee)

    @validate_uuid
    def unfollow(self, follower, followee):
        if not self.is_following(follower, followee):
            raise UsersNotConnectedError(follower, followee)

        self._connections[follower].remove(followee)

    @validate_uuid
    def is_following(self, follower, followee):
        return followee in self._connections[follower]

    @validate_uuid
    def followers(self, user_uuid):
        return {
            user for user in self._users.keys()
            if self.is_following(user, user_uuid)
        }

    @validate_uuid
    def following(self, user_uuid):
        return set(self._connections[user_uuid])

    @validate_uuid
    def friends(self, user_uuid):
        return {
            user for user in self._connections[user_uuid]
            if self.is_following(user, user_uuid)
        }

    @validate_uuid
    def max_distance(self, user_uuid):
        fringe = [(user_uuid, 0)]
        visited = set()
        max_dist = 0

        while len(fringe) != 0:
            uuid, depth = fringe.pop()
            visited.add(uuid)
            max_dist = depth

            next_layer = {
                user for user in self.following(uuid) if user not in visited
            }

            for user in next_layer:
                fringe.insert(0, (user, depth+1))

        return max_dist if max_dist > 0 else inf

    @validate_uuid
    def min_distance(self, from_user_uuid, to_user_uuid):
        fringe = [(from_user_uuid, 0)]
        visited = set()

        while len(fringe) != 0:
            uuid, depth = fringe.pop()
            visited.add(uuid)

            if uuid == to_user_uuid:
                return depth

            next_layer = {
                user for user in self.following(uuid) if user not in visited
            }

            for user in next_layer:
                fringe.insert(0, (user, depth+1))

        raise UsersNotConnectedError(from_user_uuid, to_user_uuid)

    @validate_uuid
    def nth_layer_followings(self, user_uuid, n):
        if n == 0:
            return set()

        fringe = [(user_uuid, 0)]
        visited = set()
        distance = 0
        nth_layer = set()

        while len(fringe) != 0:
            uuid, depth = fringe.pop()
            visited.add(uuid)
            distance = depth

            next_layer = {
                user for user in self.following(uuid) if user not in visited
            }

            if distance == n-1:
                nth_layer |= next_layer
            else:
                for user in next_layer:
                    fringe.insert(0, (user, depth+1))

        return nth_layer

    @validate_uuid
    def generate_feed(self, user_uuid, offset=0, limit=10):
        queue = PriorityQueue()
        # idx is used as second item in the priority queue
        # if two timestamps are equal idx is used for comparing
        idx = 0
        for user in self.following(user_uuid):
            generator = self._users[user].get_post(oldest_first=False)
            post = next(generator)
            queue.put((-post.published_at.timestamp(), idx, generator, post))
            idx += 1

        posts = []
        while len(posts) < (offset + limit) and queue.qsize() > 0:
            _, __, generator, post = queue.get()
            posts.append(post)

            try:
                next_post = next(generator)
                queue.put(
                    (-next_post.published_at.timestamp(),
                        idx, generator, next_post)
                )

                idx += 1
            except StopIteration:
                continue

        return posts[offset:]